题解1359a cf
AT_abc020_c 题解
链接(atcoder) 链接(luogu) 简单算法组合(? 算法一 爆搜,时间复杂度 \(O(2^{n \times m} \times t)\),不能通过此题。 算法二 考虑二分 \(t\),然后暴搜,时间复杂度 \(O(2^{n \times m} \times log2(t))\),不能通过 ......
CF1234F 题解
blog。小清新题,下文 \(V=20\) 即值域。 反转操作,本质就是选两个不相交连续段拼起来。 显然合法的最终串长度一定 \(\le V\)。将这些合法串预处理出来,那么每个串都对应一个「字母集合」。 随便 DP 一下,求出所有集合中,的最大的合法「字母集合」大小。\(dp_{\small U} ......
CF1917F Construct Tree 题解
题目链接:https://codeforces.com/contest/1917/problem/F 题意 有 \(n\) 条长度 \(l_i\) 的边,问它们是否能组成一棵 \(n + 1\) 个节点的树,使得树的直径长度为 \(d\)。\(n, d \le 2000\)。 题解 首先当然要存在一 ......
AT_joisc2015_h 题解
传送门 题意:给定长为 \(n\) 的字符串 \(s\),你可以选择一个区间,将区间内的字符从小到大排序,求可以得到的最长回文子串长度,字符集大小为 \(n\)。 很有意思的题目。 首先容易做到 \(O(n^3)\)。考虑怎么优化。 我们先考察排序的区间和回文区间的关系。 如果两个区间无交,那么显然 ......
在不使用内置函数和中间变量的情况交换数字LeetCode力扣题解面试题16.01
#异或法#Kotlin ```Kotlinclass Solution { fun swapNumbers(numbers: IntArray): IntArray { numbers[0] = numbers[0] xor numbers[1] numbers[1] = numbers[1] xo ......
CF1835C Twin Clusters 题解
题目链接 点击打开链接 题目解法 很牛逼的构造题 好像随也可以过 长度为 \(2^{k+1}\) 的序列的不同区间有 \(2^{2k+1}\) 个,值域是 \(4^k\),所以一定有解 将 \(a\) 做一遍前缀和,那么问题转化成了找 \(s_{r1}\oplus s_{l1-1}=s_{r2}\o ......
[P4240] 毒瘤之神的考验 题解
[P4240] 毒瘤之神的考验 题解 知道: \[\varphi(ij)\varphi(\gcd(i, j)) = \varphi (i)\varphi(j)\gcd(i, j) \]可以进行转化,之后可以化简出形如: \[\sum_{i = 1}^n g(i)f(i, n/i)f(i, m / i ......
ICPC2021Kunming G Glass Bead Game 题解
Question ICPC2021Kunming G Glass Bead Game 有 \(n\) 个玻璃珠, \(B_1,B_2,\cdots, B_n\) 每一步你可以选择一个 \(B_i\) 移道第一个位置上,花费的代价为操作前 \(B_i\) 前面的玻璃珠的个数。已知每一步选择玻璃珠 \( ......
ICPC2021Kunming G Find the Maximum 题解
Question Find the Maximum 给出一个树,每个点有一个权值 \(b_n\),求一条树上路径 \(V\),要求 \(\frac{\sum_{u\in V (-x^2+b_u x)}}{|V|}\) 最大,其中 \(x\) 是自己选择的一个树 Solution 先转化一下 \(\f ......
CF1884C Medium Design
CF1884C Medium Design 翻译 首先可以想到一个性质:覆盖 \(\min\) 的区间加上一定不优。因此考虑以每个点为 \(\max\),判断包含这个位置的所有线段中和的最小值 然后就不会了 \(QwQ\) 原来这里还有一个性质:最小值一定是 \(\min(a_1,a_m)\),因为 ......
[Codeforces] CF1536C Diluc and Kaeya
CF1536C Diluc and Kaeya 题意 题目传送门 给你一个字符串 \(S\),其中只包含 'K' 或 'D' 两种字符,要求划分这个字符串使得各部分的 \(n(D):n(K)\) 相同,其中 \(n(D)\) 表示 \(S\) 中字符 'D' 出现的个数,最大化划分后形成的组数。 求 ......
AT_joisc2015_e 题解
AT_joisc2015_e 传送门 更好的阅读体验 题意 给定长为 \(n-1\) 的数组 \(b_i\),要求有多少长为 \(n\) 的数组 \(a_i\) 满足: \(b\) 数组可以由 \(a\) 数组删掉一个数得到。 存在一个排列 \(p\) 满足 \(a_i\) 是以 \(p_i\) 结 ......
CF342E Xenia and Tree
题意 给定一棵 \(n\) 个节点的一棵树,初始时 \(1\) 号点为红色,其余为蓝色。 要求支持以下操作: 将一个节点变为红色。 询问节点 \(u\) 到最近红色节点的距离 共 \(q\) 次操作。 Sol 喵喵题。 不难想到点分树做法,不再阐述。 考虑简单的操作分块。 对于块外,可以考虑每做完一 ......
P8868 [NOIP2022] 比赛 题解
Description 小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP!小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 \(n\) 个人的队伍,选手在每支队伍内都是从 \(1\) 到 \(n\) 编号。每一个选手都有相应的程序设计水平。具体的,小 N ......
【CF1917F】Construct Tree
题目 题目链接:https://codeforces.com/contest/1917/problem/F 给出 \(n\) 条边的边权,询问是否可以构造出一棵树,使得所有边都被用上恰好一次且直径为 \(d\)。 \(n,d\leq 2000\)。 思路 首先肯定是找出一条长度为 \(d\) 的链, ......
「题解」P9747 「KDOI-06-S」签到题
一个区间合法的充要条件是存在 \(x\) 满足其为区间按位或,并且《\(x\) 左侧所有数或起来》《\(x\) 右侧所有数或起来》二者有其一为 \(x\)。 扫描线扫右端点,不同的按位或将左端点分为 \(\log A\) 个区间,对于每个区间 \([l,r]\) 先在区间按位或 \(v\) 在序列中 ......
「题解」Codeforces 1427G One Billion Shades of Grey
感谢 127 的指导/ll \(|h_u-h_v|=\max(0,h_u-h_v)+\max(0,h_v-h_u)\),那么可以把它看成这样的问题: \[\min \{\sum_{(u,v)}\max(0,h_u-h_v+w_{u,v})c_{u,v}\} \]对偶一下,问题就变为:如果两个格子相邻 ......
CF1874E Jellyfish and Hack
题目链接 点击打开链接 题目解法 一个朴素的结论是:\(fun(p)\le \frac{n\times (n+1)}{2}\) 所以可以把 \(lim\) 的范围缩小到 \(\frac{n\times (n+1)}{2}\) 首先可以得到一个简单的 \(O(n^6)\) 做法: 令 \(f_{i,j ......
CF1109
CF1109 Codeforces Round 539 (Div. 1) CF1109A link CF1109A题意 给定一个含 \(n\) 个整数的序列 \(a\),定义 \((l,r)\) 是一个funny pair当且仅当 \(r>l,r-l+1\) 为偶数,且 \(a\) 中下标自 \(l ......
CF1910G Pool Records记录
题目链接:https://codeforces.com/contest/1910/problem/G 题意简述 有两个运动员以未知的固定速度 \(v_1 \ne v_2\) 在一个长为 \(50\) 米的游泳池中游泳,一旦到边缘就立即掉头。现在有他们前 \(n\) 次相遇时间 \(t_i\)(递增, ......
CF396C On Changing Tree 题解
CF396C 考虑将贡献表示出来:\(\forall v\in \text{subtree}_u\),\(v\) 会加上 \(x - (dep_v - dep_u)k\),然后发现这个东西可以维护整棵子树,即把 \(x,dep_u\times k\) 和 \(dep_v\times k\) 分开计算 ......
CF1408I
Hyperlink 题意很明白,不复述了吧 qwq solution 一个数 \(a_i\) 减去 \(\Delta\) 之后对整个数组的异或和会造成 \(a_i~\text{xor}~(a_i-\Delta)\) 的影响。所有数的影响 \(\text{xor}\) 起来就是对整个数组的影响总和。 ......
CF1523F
Portal description 0 时刻你可以选择二维平面上任意一个整点作为起始点。每个单位时间你可以上下左右走或原地不动。平面上有 \(n\) 个处在整点的传送门,你可以走到一个传送门所在的位置并激活它。一旦传送门被激活,你可以在任意时刻立即传送到这个传送门的位置。 现在有 \(m\) 个任 ......
CF 数位DP两题sol
# CF855E Salazar Slytherin's Locket ## 题面翻译 求$l...r$之间转成$b$进制后,$0,1,2...,b-2,b-1$都出现偶数次的数的个数。 第一行一个数$q$,为数据组数。 下面$q$行,每行$3$个整数,表示$b,l,r$。 $1\le q \le ......
题解 P9993【[Ynoi Easy Round 2024] TEST_133】
就硬把 线段树 3 和 数列分块入门 2 揉到一起出。 维护原数组 \(a\) 及其历史最大值 \(hist\),对每个块,维护块内 \(a\) 升序排序后结果 \(p\)、块内 \(a\) 升序排序后历史最大值前缀和 \(prehist\)、块加标记 \(add\)、块历史和加标记 \(hista ......
[WC2018] 通道题解
先考虑只有两颗树要咋做,柿子先变成 \(dep_x+dep_y-2\times dep_{lca}+dist_2(x,y)\) 我们可以新建节点 \(x'\rightarrow x\),边权为 \(dep_x\),这样上面的式子可以看作枚举 \(lca\) 后,选出一个端点在不同子树中的直径,可以直 ......
ARC167D Good Permutation 题解
ARC167D 看到排列并且有 \(i\gets a_i\),就可以直接建出图来,显然是若干个不相干的环。 如果不求字典序最小,就可以直接不在同一个环中的 \(i,j\) 直接交换就可以了,因为它要求了最小化操作数。如果求字典序最小,直接从前往后扫一遍,可以用 set 维护不在这个环中且 \(j>i ......
P5513 [CEOI2013] Board 题解
P5513 容易发现,每次等价于对一个二进制数进行操作。但是这个二进制数长为 \(n\),即需要高精。但是这样支持加一和减一是复杂度会退化为 \(\mathcal{O}(n^2)\),有一个很正常的做法就压位,仿照 bitset 的做法进行操作,复杂度 \(\mathcal{O}(\frac{n ^ ......
ARC105E Keep Graph Disconnected 题解
ARC105E 正向考虑是很难的,从结果入手,发现最后一定是分别包含 \(1\),\(n\) 的两个完全图。 考虑表示出这两个人一共加了多少边:\(\frac{n(n-1)}{2}-m-x(n-x)\),\(x\) 表示点 \(1\) 所在集合的大小。 由于是判断先手还是后手必胜,所以只需看结果对 ......