6.29
CYEZ XXS Round 活动安排
题目大意：给定 \(n\) 个线段，求最少划分为几个集合，使得每个集合内线段不交。\(n\le 100\)
解题思路：可以 \(O(n^2)\) 对于每一个线段，找到距离当前右端点最近的左端点然后跳到那个线段的右端点。
可以 \(O(n\log n)\) 用优先队列维护。
完成度：\(100\%\)。
CYEZ XXS Round 最小步数
题目大意：有 \(n\) 个格子，走到第 \(i\) 个格子获得 \(a_i\) 元。或花费 \(100\) 元跳过第 \(i\) 格，时刻保持身上的钱非负。求最少需要跳过的格子数。
解题思路：dp 即可。\(dp_{i,r}\) 表示到第 \(i\) 格，身上有 \(r\) 元最少需要跳过的格子数。
显然是好转移的。\(dp_{i,r}\to dp_{i+1,r-100}+1,dp_{i,r}\to dp_{i+1,r+a_i}\)。
答案是 \(\min_r dp_{n,r}\)。
完成度：\(100\%\)。
CYEZ XXS Round 烤饼干
题目大意：给定 \(R\times C\) \(01\) 矩阵，每一行每一列可以翻转，求最大 \(1\) 个数。
发现 \(R\) 很小。考虑枚举 \(R\) 的反转情况，共有 \(2^R\) 种可能。
然后通过位运算计算 \(C\) 的反转情况即可。
完成度：\(100\%\)。
CYEZ XXS Round 坐船旅行
题目大意：加边最短路
解题思路：发现数据范围很小，\(n\le 100,k\le 5000\)。
考虑 dijkstra 堆优化的复杂度 \(O(n\log n)\)，每加一次边就重新算一次就可以了。时间复杂度 \(O(kn\log n)\)。
完成度：\(100\%\)。
梦熊周赛 堡垒
题目大意：重拍偶长度数组 \(a\)，设 \(F(S)\) 表示 \(S\) 中不同元素的种类数量。要求对于所有 \(i\bmod 2=0\)，\(F(a_1,a_2,\cdots,a_i)\bmod2=0\)。或报告无解。
解题思路：发现偶长度数组 \(a\) 长度为 \(n\)，则 \(n\bmod 2=0\)，则 \(F(a_1,a_2,\cdots,a_n)\bmod 2=0\)。所以 \(a\) 中的元素数量必须是偶数，不然无解。
然后考虑下标 \(i\) 和 \(F\) 都是偶数这样的对应关系，一个比较简单的解是先将 \(a\) 中的所有不同元素排在前面。这样的话，一定可以满足条件。
备注：题面中的两个偶数的对应关系的提示具有启示性，全场第四个过。爽了哦哦。
完成度：\(100\%\)。
梦熊周赛 催化剂
题目大意：有糖果集合 \(S\)，划分出 \(k\) 个子集 \(S_1,\cdots,S_k\)。定义 \(F(S)\) 为一种划分方案使得 \(\sum^k_{i=1} f(S_i)\) 最小的值。\(f(T)\) 表示 \(T\) 内元素的出现个数 \(-1\) 的和。集合 \(S\) 带修。
解题思路：考虑将 \(S\) 划分成 \(k\) 个子集，如何划分最优。显然对于 \(S\) 内的某一种元素 \(o\) 出现了 \(cnt_o\) 次，如果 \(cnt_o\le k\)，无贡献，反之贡献最小是 \(cnt_o-k\) 。
所以我们只要维护每一种元素的 \(cnt_o\) 即可。\(F(S)=\sum_o \max(0,cnt_o-k)\)。
考虑 \(cnt_o\ge k\) 的情况，\(F(S)=\sum_{cnt_o\ge k} (cnt_o-k)\)。
用树状数组维护出来 \(cnt_o\ge k\) 的个数和 \(cnt_o\) 的和即可。
备注：这种基于元素出现个数的数据结构维护具有启示性。
梦熊周赛 电动力学
题目大意：选出 \(S,T\subseteq\{1,2,\cdots,n\}\)，使得对于 \(S\) 内的元素 \(u\)，一定有 \(u\in T\) 要么存在 \(x\to y\) 经过 \(u\) 且 \(x,y\in T\)。
解题思路：考虑 \(n\le 20\) 的情况，枚举 \(T\)，集合 \(S\) 一定是 \(T\) 里的点所构成的连通块的子集。
枚举 \(T\) 计算 \(T\) 的连通块大小 \(m\)，这个 \(T\) 的贡献是 \(2^m\)。
考虑是链的情况，必须有 \(\min T\le \min S \le \max S\le \max T\)。显然，先选择 \(T\)，\(S\) 的方案数是 \(2^{\max T-\min T+1}\)。
对于 \(\max T-\min T+1=t\)，这样的 \(\max T,\min T\) 的取法共有 \(n-t+1\) 种。其中的 \(t-2\) 个数任取。
所以方案数即为 \(\sum^n_{t=2} 2^t\times 2^{t-2}\times (n-t+1)\)。考虑 \(t=0,1\) 的特殊情况，方案数分别为 \(1,2n\) 加上即可。
至此可以获得 \(30\) 分。
备注：将在后文补题。
完成度：\(30\%\)。
ARC180 A
题目大意：每一次可以挑 \(ABA\) 转为 \(A\) 或 \(BAB\) 转为 \(B\)，求结果字符串个数。
解题思路：
考虑如果存在一坨 \(ABABA\) 或 \(ABABAB\)，则他们的答案都一定是 \(3\)。如果存在 \(AA\) 或 \(BB\) 前后两坨就独立开来。
答案是 \(\prod \lfloor \frac {连续的相邻字符不同子串长度+1}2\rfloor\)。
模拟即可。
ARC180 C
题目大意：挑出一个子序列，做出这个子序列的前缀和，填回原来的位置。求这样操作以后的数组的可能数。
解题思路：考虑改以前是 \(a\)，改完以后是 \(b\)。
考虑 \(dp_{i,j,k}\) 表示考虑前 \(i\) 位，上一个 \(a_j\neq b_j\) 的位置在 \(j\)，值是 \(k\)。
转移有点复杂，但是比较自然。
ARC180BD 梦熊T4
6.30
百度之星 A
题目大意：有 \(n\) 个灯，一个灯在所有 \(b_i+ka_i=t\) 有整数 \(k\) 的解时闪烁，求从 \(l\) 开始所有灯加起来闪烁至少 \(c\) 次的最小时间刻，或判断到 \(r\) 仍不足 \(c\) 次。
做法：二分答案。考虑 \(OK(mid)\) 如何写。
首先计算 \(l\) 以后每一个灯第一次闪烁的时间，然后闪烁次数即为 \(\frac {mid-st}{a_i}+1\)。 \(st\) 有细节。
百度之星 B
题目大意：给定一个数列（长度 \(1e9\)），\(m\) 次区间加。最后询问 \(a_i\bmod 4=1\) 的个数。
做法：发现有用的端点不会超过 \(2m\) 个，对于每两个端点构成的区间的值必然是一样的，可以快速计算。
百度之星 C
题目大意：给定一个字符串，\(q\) 次询问，询问 \([l_1,r_1]\) 和 \([l_2,r_2]\) 的这两个子串中失配的位置中包含哪些字符。
做法：首先这种题目一眼丁真可以 bitset，但是 \(O(10^5\times 10^5\times 26\div w)\) 过不了。
然后考虑 bitset 转化成二进制哈希。对于 \([l_1,r_1]\) 如果某一个字符存在的位置的哈希权 \(\times 2^{l_2-l_1}\) 等于 \([l_2,r_2]\) 的哈希权，则认定这两段对于这个字符而言相等。
百度之星 D
题目大意：给定一个数列，求 原数列最长连续子段长度 与 删去一种数以后的最长连续子段长度 的最大差。
做法：暴力的瓶颈在于数的种类编号上至 \(10^6\)。考虑离散化，发现数的种类不超过 \(n\) 。枚举这个数即可，时间复杂度 \(O(n^2)\)。
百度之星 E
题目大意：给定一棵 01 权树，花费 \(1\) 的代价交换相邻顶点，求使得存在一条边删去后两连通块内颜色单一的代价最小值，或判断无解。
做法：考虑颜色的数量都是不变的，只有交换，所以需要找到一个节点的子树放满 \(0\) 或放满 \(1\)。
然后考虑将外部的 \(0\) 全部塞进子树 \(u\) 的代价是：外部 \(0\) 到 \(u\) 的距离和 \(+\) 子树内 \(1\) 到 \(u\) 的距离和。
维护出来外部 \(0/1\) 到 \(u\) 的距离和，子树内 \(0/1\) 到 \(u\) 的距离和。
前者直接算不好算，它等于全部 \(0/1\) 的距离和 \(-\) 子树内 \(0/1\) 到 \(u\) 的距离和。
前面的可以换根 dp 做，后面的是 dfs 朴素算。
ABC ABC 过于简单，略
ABC D
题目大意：给定初始方向和坐标，求运动 \((T+0.1)\) 秒过后的相遇对数。
做法：考虑到初始坐标不同，方向相同是不会相遇的。
初始方向不同的话，如果 \(\max(X_i,X_j)-\min(X_i,X_j)\le 2T\)，则会相遇。
朴素 \(O(n^2)\) 算爆炸。枚举一个计算另一个即可。
ABC E
题目大意：一开始有一个球在 \(1\)。每一次选择 \((i,j)\) 交换 \((i,j)\) 上的情况。重复 \(k\) 次，求该球最后位置的期望。
考虑 \(2\sim n\) 的情况是相同的，概率也是相同的。
所以我们计算出来 \(1\) 的概率 和 \(2\) 的概率就可以了。
第 \(0\) 次，\(1\) 的概率是 \(1\)，\(2\) 的概率是 \(0\)。
考虑选择 \((i,j)\)，当前在 \(x\) 时。如果选到 \((x,x)\)（概率 \(\frac 2 {n^2}\)）或者 \(i,j\neq x\)，概率 \(\frac{n^2-2n}{n^2}\)，则都停留在 \(x\)。
反之，有 \(\frac 2 n\) 的概率在剩下的每一个点。
第 \(1\) 次，\(1\) 的概率是 \(\frac{n^2-2n+2}{n^2}\)，\(2\) 的概率是 \(\frac 2 n\)。
不断地维护这个就可以了。反正设 \(f_{i,u}\) 表示第 \(i\) 次过后在 \(u\) 的概率，则 \(f_{i,u}=f_{i-1,u}\times \frac{n^2-2n+2}{n^2}+(1-f_{i-1,u})\times \frac 2 n\)。
然后就会得到 \(f_{i,1}\) 和 \(f_{i,2}\)。
\(f_{i,2}=f_{i,3}=\cdots=f_{i,n}\)。
所以期望就是 \(f_{i,1}+(2+\cdots+n)\times f_{i,2}=f_{i,1}+\frac{(2+n)(n-2)}2 f_{i,2}\)。
ABC G
题目大意：任意修改一个数，求 LIS
做法：一个典题是 hdu5489 removed interval。
考虑 \(L=1\) 的情况，就是这道题。
但是修改一个数和删去一个数在如下情况中是不同的。
- 如果 \(a_i-a_{pre}\ge 2\)，则答案增大 \(1\)
- 如果答案从 \(2\) 开始，则答案一定增大 \(1\)
- 如果答案以 \(n-1\) 结束，则答案一定增大 \(1\)。
当然，还有最坑的 \(n=1\)，把我卡死了。
7.1
随机选做题+补题。
AGC 012B
difficulty:2047
下文设 \(E_u\) 为无向图中 \(u\) 的邻域。
如果对于一个染色 \((time,u,d,c)\) 存在另一个染色 \((time',u,d',c')\) 且 \(time<time',d<d'\)，则 \((time,u,d,c)\) 无用。
考虑 \((time,u,d,c)\) 可以转化为 \((time,v,d-1,c),v\in E_u\)。
又，\((time,u,d,c)\) 可以转化为 \((time,u,d',c)\)，\(d'<d\)。
又，发现 \(time\) 与 \(c\) 可以 \(O(1)\) 对应。
所以可以设计 \(dp\) 表示，按照上述转化后，\((u,d)\) 的最晚 \(time\) 即可。
代码非常好写。
ARC 180B
考虑 \(P\) 的逆数组 \(Q\)，然后重新论述这个题面就应该变成
- 选择 \((i,j)\) 使得 \(1\le i<j\le N\)，使得 \(Q_i-Q_j\ge K\)，\((Q_i,Q_j)\) 没被选过，交换 \(Q_i,Q_j\)。
将 \(f(Q)\) 设为 \((i,j)\) 的个数满足 \(i<j\) 且 \(Q_i-Q_j\ge k\)。
显然，每一次操作会使 \(f(Q)\) 减少 \(1\)。考虑如何让 \(f(Q)\) 每次减小且仅减小 \(1\)。
有若干构造方式。
ARC 180D
题目大意：多次询问 \(A\) 的区间，将这个区间分成 \(3\) 段，使得三段分别的最大值之和最小。
考虑将 \([l,r]\) 分成三段：\([l,r_1],[r_1+1,r_2],[r_2+1,r]\)。
如果 \([l,r]\) 的最大值在 \([r_1+1,r_2]\) 范围中，则令 \(r_1=l,r_2=r-1\)。
这时候第一段 第三段的长度都是 \(1\)，可以简单地 RMQ 解决。
如果 \([l,r]\) 的最大值在 \([l,r_1]\) 或 \([r_2+1,r]\) 中，显然后者和前者问题等价。
显然的，我们可以令第二段的长度为 \(1\)。即 \(r_2=r_1+1\)。
然后我们用一个指针维护 \(r\)，开一棵线段树维护 \(l_2\) 的位置即可。
是分类讨论妙用线段树的好题。
ABC F
梦熊 C
首先，我们考虑题目中现有 \(S\) 后有 \(T\) 不好计算。
考虑对于 \(T\) 去算满足条件的 \(S\) 的个数。显然对于一个 \(T\)，所有满足条件的 \(S\) 必然是某一个满足条件的 \(S\) 的子集，也就是 \(2^{|S|}\) 种可能。我们只需要考虑这个 \(S\) 的情况即可。
先看树的情况，不难发现，\(S\) 的点必须在 \(T\) 中的点构成的虚树上。推广到图，这个东西大胆猜测就是 \(T\) 中所有路径经过的点双的并集大小。考虑建出圆方树 dp。
要给圆方树上的每个点赋权，对于圆点，权值为 \(0\)，对于方点，权值为 \(s_x-1\)，\(s_x\) 表示第 \(x\) 个点双的大小。继续算，所有有 \(|T|\) 中路径经过的点双的并集大小即为所有 \(T\) 中的在圆方树上构成的虚树中的点的权值和 \(+1\)。设这个玩意是 \(f(T)\)，则 \(\sum_T2^{f(T)}=2\sum_T2^{f(T)-1}\).
然后问题就真的转化成了 在圆方树上构成的虚树中的点的权值和。
考虑 dp，设 \(f_x\) 表示虚树中以 \(x\) 为根的方案数。考虑子树合并状态，一定为若干个在 \(x\) 的不同子树的点，然后对其求和。设 \(g(y,x)\) 表示 对于 \(x\) 是 \(y\) 的祖先，\(x\) 到 \(y\) 上的路径和。设 \(t(x)=\sum_{y\in S_x} f_y 2^{g(y,x)}\)，设 \(S_x\) 表示 \(x\) 的子树构成的集合。\(T\) 同理。
- \(x\) 是方点，则一定为选择大于等于 \(2\) 个子树中的点合并。则 \(f(x)=2^{s_x-1}((\prod_{y\in T_x}(1+t_y))-1-\sum_{y\in T_x} t_y),t_x=2^{s_x-1}\sum_{y\in T_x}t_y\)
- \(x\) 是原点，则 \(f_x=(2\prod_{y\in T_x}(1+t_y))-1-\sum_{y\in T_x} t_y\)。
梦熊 D
没题解。
标签：题目,sum,练习,7.1,大意,frac,考虑,dp,6.29 From： https://www.cnblogs.com/wtc-qwq/p/18278207