CF 稍微难点的题

不是多难的题，不要不敢做。只是比 2200-2400 难 暂定目标 11 月底完成率 70% 年底做完（看完题解写掉能写的，太麻烦的不写） 10.20 在想一下 CF1646F，再不会直接看题解 我贺了，这题还行 CF1628E 想了很长时间，刚开始觉得完全不可做，可能是什么巨大麻烦的维护题，然后突然想到做法后发现是若志题目。 CF1630E Burnside 引理练习题难度。不算很难，也没那么傻逼。需要对它有一定理解。 CF1641E bui，打算晚上贺 贺了，这题没想到我 remosk 我觉得核心问题是没想到把 p 看作单点加一然后前缀和，以及没把式子列出来（拆每个距离的贡献我想到了，但没列示，佛了） CF1630F 贺了，还是做题做太少，遇到的模型少导致的 先复习一下 DAG 最小链覆盖，分为两种 1. 点可复用 2. 点不可复用 考虑第二种。先每个点自己成一条路径，答案为 $n$，将点拆为 $v_{x_1},v_{x_2}$，对于所有有向边 $(a,b)$，连边 $(v_{a_2},v_{b_1})$。跑最大匹配为 $m$，答案为 $n-m$。一个匹配边相当于合并了两条路径。拆点是为了让一个点两边都可以连出路径。 第一种只需要在建图时对于所有 $u$ 能到达 $v$，补充连边 $(u,v)$ 即可（在 DAG 上）。原因留作思考。 这个题对所有 $a_v\mid a_u$ 的连有向边 $(u,v)$。bipartite 的充要条件是每个保留点仅有入度或仅有出度。 将每个点拆为 $x,x'$ 分别表示只有入度，只有出度。在新图上，希望在所有矛盾的点对间连边。$(x,x')$ 显然要连。若 $a_v\mid a_u$，则连边 $(u,v),(u',v'),(u,v')$。这是 DAG。并且，如果 $s$ 可以走若干步到达 $t$，则必存在边 $(s,t)$。 求出 DAG 上最大点集，使得任意两点间没有边，**在这里就等价于任意两点间不单向连通**。这一点并不难证明（写出具体标号后非常明显）但对建模的正确性至关重要！我觉得现有题解都糊弄过去了！！！！如果没有这一性质的话，最长反链的“反”就不是“不单向连通”的意思了。 求最长反链，根据 dilworth 定理想到最小正链覆盖。也就是 DAG 的点可重复路径覆盖问题。二分图匹配即可。 CF1615G 这题先想了 trivial 的部分。 先把已经成功的 $k$ 拎出来，考虑每个 $0$ 连续段长度为 $len$。 若 $2\mid len$，考虑其两边 $a,b(a\neq b)$，若不管两边，则答案加上 $len/2$。若两边不等，且同时满足两边的都相邻相等，答案额外 $+1$。 若 $2\nmid len$，考虑其两边 $a,b$，若不管两边，则答案加上 $\lfloor len/2\rfloor$。若两边不等，且两边相邻相等满足恰好一个，则答案额外 $+1$。 也就是说，我们得到了两种类型的数对 $(a_i,b_i)$。 令 $S:= \{x\mid \text{x doesn't success preliminarily}\}$。 对于 $type=1$，可选择同时消除 $a_i,b_i$（$S$ 中目前还有），收益 $+1$。 对于 $type=2$，可选择消除 $a_i,b_i$ 其中一个，收益 $+1$。 只有类型二的话是简单的二分图匹配问题。但有类型一。 考虑网络流。这种题有两种处理思路：1. 最小割 2.费用流。但是两种似乎都难以处理类型一。卡住了。 这个思路确实是完全没救的。考虑对 $type=2$ 每个建一个虚电 $S_i$，在 $S_i$ 与 $x,y$ 之间连一条边，在 $type=1$ 的每个 $x,y$ 间连一条边，则问题转化为求出该无向图的最大匹配，复杂度爆炸了。 我们肯定想尽量匹配 $type=1$ 的东西。如果对 $1$ 建边 $(x,y)$，一个连通块内非树的话，一定全可以用 $type=1$ 匹配掉，不用管 $type=2$ 了，如果是树的话，一定可以匹配到只剩下任意一个点 $v$。因此 $type=2$ 就是在两棵树间连边匹配，而树的个数只有 $600$，可以跑带花树了。 先学带花树。 CF1695E 又贺 在所有骨牌对应的 $(x,y)$ 间连无向边，对每个连通块跑欧拉环游。具体来说，跑遍所有边，第一次进入某个点时，依次访问其所有出边；否则直接回溯。直接记录路径上依次访问的点，搞成一个环即可。 CF1810G Bui 先转化为求所有方案的价值总和。 感觉还是得考虑对每个长度 $k$ 求出 $f(x)$ 表示最大前缀和大于等于 $x$ 的方案数，之后就好做了。 单钦定某个前缀之和为 $x$ 是不够的。因为最大前缀和可能出现多次。如果钦定 $s_{i_1}=s_{i_2}=s_{i_3}=\cdots =s_{i_t}=x$，则对答案贡献为 $(-1)^{t-1}\times \displaystyle \sum_{[1,i_1]=x,[i_1+1,i_2]=0,\cdots [i_{t-1}+1,i_t]=0} 1$。$[]$ 表示区间之和。对于不同的 $k,x$，这些方括号是可以共用的。第一段可以直接暴力背包求出。这很好。但问题是，无法快速求出 $[]=0$ 的方案数。 当然对于区间和为 $0$ 这个可合并的东西，容易想到区间 dp。但好像并没有 $O(1)$ 转移的方法。这东西不能用两个前缀的答案来合并，因为不独立。 思路完全错误。 考虑求出最大前缀和的另一种方法。 设 $f_i$ 为长度为 $n$ 的序列的 $i+1\sim n$ 这个后缀的最大前缀和。则 $f_i=\max(0,f_{i+1}+a_i)$。 一种方法是，考虑在序列的出发点就钦定好它到底需要到多少的前缀和，计算其贡献。则 $dp_{0,i}=h_i$。已经到达目标，即后一维为 $0$ 时，不再向后转移。并且，$(j>0)p_{i+1}dp_{i,j}\rightarrow dp_{i+1,j-1},(1-p_{i+1})dp_{i,j}\rightarrow dp_{i+1,j+1}$。 长度为 $k$ 时的答案，即为 $ans=\displaystyle \sum_{i=0}^{k}dp_{i,0}$。 另一种方法是，假设 $[i+1,n]$ 的最大前缀和为 $j$ 时，整个长度为 $n$ 的序列对答案的贡献的期望值为 $dp_{i,j}$。 则长度为 $k$ 的答案是 $dp_{k,0}$。 考虑到 $dp_{i+1,j}=p_{i+1}dp_{i-1,j+1}+(1-p_{i+1})dp_{i-1,\max(j-1,0)}$。 我觉得还是第一个思路比较好一点。 10/27 CF1610G 飒切 3300 这个题感觉不是太难想。根据括号包含关系直接 dp 即可。 题解区主要做法是设 $f_i$ 表示 $i$ 开头的答案。可以倍增维护哈希值，求出 lcp 后比较从哪里转移比较好一点。 10/31 这个 CF1687D 我贺了。思路确实不是很难，写起来也还行，这个不会是我的问题。一开始就想着乱搞，其实这个思路并不一定就对，应该冷静下来分析一下性质。 过几天有时间了补一下。 CF1672G 这个题通过接近 1h 的打表观察发现了以下事实： 若 $n,m$ 均为偶数则 $?$ 处随便填； 若 $n,m$ 一奇一偶，不妨设 $n$ 行数为奇数，则所有列的 $1$ 的个数的奇偶性必须相同，这个也很简单，枚举所有都是奇数或者所有都是偶数，随便怎么算下就行。 若 $n,m$ 都是奇数，则所有行列的 $1$ 的个数的奇偶性必须相同。这个还没想好怎么算，但可以确定的是，总方案数（假设全是问号）一定是 $2^{(n-1)(m-1)+1}$。 这种情况下，左行右列建出二分图，在 $(x,y)$ 的一个 $?$ 对应一条边 $(L(x),R(y))$；考虑一个连通块，如果它需要的异或次数为奇数，则不合法；否则任意选取一颗生成树，非树边随意填 $0/1$，生成树上的边和剩下的需求对应的系数矩阵必满秩，剥叶子可证。因此方案数为 $2^{M-(N-1)}$，$M$ 为边数，$N$ 为点数。 11.30 CF1844G Tree Weights 猜想 I. 将所有 $dis(i,i+1)=L_i$ 的条件转化为 $n-1$ 个若干边权相加得到 $L_i$ 的方程，发现未知数和方程个数都为 $n-1$，猜测系数矩阵满秩。 思路 I. 若原图为链，以链的某一端为开头，设一个边权的前缀和 $S_i(1\leq i \leq n),S_1=0$，每个方程均表示 $S_r-S_l=L$，可以从 $S_1=0$ 开始 dfs，求出所有 $S_i$，再推出边权。 注意到对于 $i\in[2,n-1]$ 的度数均为 $2$，而 $i=1,n$ 度数为 $1$，所以是很容易能搜出来的。 这个东西可以扩展上树。以某个点 $r$ 为根，令 $S_i$ 表示 $r$ 到 $i$ 的边权和，则 $d_i+d_{i+1}-2d_{lca(i,i+1)}=L_i$。但是好像就解不了了。 如果能使得 $lca(i,i+1)\leq i$ 或 $=r$，那么问题就完美解决了（逐个递推出 $d_i$）。这个真的可以做到吗？ 不能。 你的数学水平还是太低了。 ——姬野永远 $d_i+d_{i+1}-2d_{lca(i,i+1)}=L_i$ 这个方程两边模 $P=2$。 立得 $d_i+d_{i+1}\equiv L_i\pmod 2 $，又 $d_1\equiv 0$ 所以可以解出所有 $d_i\pmod 2$。 然后得到所有边权 $\pmod 2$，在所有 $d_i$ 上消去这些影响。继续往下考虑 $\bmod 2^k$ 即可。 一旦出现 $d_i<0$ 或最终某条边 $e=0$，则无符合要求的解；否则一定有解。 这个角度也可以说明系数矩阵确实一定是满秩的。即使数域不再是 $\mathbb{Z}$，无法如此递推，但并不影响矩阵的秩。 1/6 CF1610F 这个题目有两个做法。 第一种好想一点：合并同类边，最后对于只有链和环的图暴力定向就可以了。这个比较难写，而且复杂度是线性对数的，不够优秀，无法通过洛谷上的加强版题目。 第二种很难想。我们考虑对于度数为奇数的点，都连一条边权为 $1$ 的边到虚点 $S$。然后跑欧拉回路。跑回路的时候，优先走与入边边权相同的出边，若是没有才走不同的边。我们知道答案的上界就是原图上连有奇数条 $1$ 边的点的个数，那么考虑以下两种原图上的关键点的情形： 1. 奇数个 $1$，奇数个 $2$。 2. 奇数个 $1$，偶数个 $2$，又补上了一个虚拟的 $1$。 注意按照既定的策略来走，最后消掉虚拟边，正好可以使得所有关键点相关的边定向正确。 CF1610H 小贪心题，其实很简单。 主要思路是发现选 $1$ 次根可以消掉所有两端不等于 LCA 的要求，而只考虑竖直的链的情况，显然贪心地选较浅的点是最优的。不仅如此，对于所有两端不等于 LCA 的要求，若 $x$ 合法，则 $fa[x]$ 同样合法。所以我们只要先贪心，最后再 check 是否所有所有两端不等于 LCA 的要求都被处理掉了就可以了。 或者也可以从子树内选点个数 $c_x$ 构造不等式的角度来考虑，不论怎么做，都是好想好写的题目，放在 H 属实过分了。 CF1592F 核心思路是操作 $2,3$ 没有用。 我们容易求出只用操作 $1$ 需要的次数 $c$ 和每个位置是否需要操作 $b[i][j]$，因为显然这个系数矩阵是满秩的下三角矩阵。 对于 F1，若要用代价为 $3$ 的操作 $4$ 代替，那么必须满足 $b[i][j]=b[i][m]=b[n][j]=b[n][m]=1$，并且显然不会用多次，判一下就好了。 对于 F2，操作 $4$ 可能会用多次，但不可能在同一行或同一列用多次。用到的格子 $(i,j)$ 必须满足 $b[i][j]=b[i][m]=b[n][j]=1$，二分图匹配一下就行。根据匹配数量的奇偶性和 $b[n][m]$ 的值再来判断对于 $b[n][m]$ 是额外省下 $1$ 的代价，额外付出 $1$ 的代价还是代价没有变化就可以了。