## [CF2108D](https://codeforces.com/contest/2108/problem/D) 交互题 思路很简单 就是细节好多错了好多次 还有输出忘记换行 ILE 了好多次 [CODE](https://codeforces.com/contest/2108/submission/339902894) ## [CF2108E](https://codeforces.com/contest/2108/problem/E) 没有想到这种最大是可以取满的！！！，即每条边对答案贡献可以取到可能的最大 构造的话就**找到重心为新的根，每两个相同颜色的在不同的子树内**（这个用优先队列每次取两个最大的匹配，或者直接重心开始染（需要保证开始染的这个子树大小不为n/2，因为加上重心会使颜色不够） 删边要失去的贡献最小，选最浅的叶子节点（这个比较好想） [CODE](https://codeforces.com/contest/2108/submission/340112826) ## [CF2104D](https://codeforces.com/contest/2104/problem/D) 懒得写 [CODE](https://codeforces.com/contest/2104/submission/340114601) ## [CF2104E](https://codeforces.com/contest/2104/problem/E) 题目不难 就是第一发假了 需要加入最少的字符，应该正着找而不能倒着找 [CODE](https://codeforces.com/contest/2104/submission/340130487) ## [CF2098D](https://codeforces.com/contest/2098/problem/D) 题目不难，但刚开始把题目想复杂了 首先需要把题目转换成图，每次两个点二选一或者一选一 转化成图就连一条边表示边上两点要选出一点 对每个连通块分别计算就好了 对于有环的情况很好考虑，只能是 $0$ 或 $1$ 或 $2$ 我开始准备用树形DP计算方案数，发现整棵树上恰好一个点不取剩下的情况有且仅有 $1$ 种 方案数就为树的大小，根本不用DP [CODE](https://codeforces.com/contest/2098/submission/340688067) ## [CF2098E](https://codeforces.com/contest/2098/problem/E) $$ x+tv_x=p_xn $$ $$ y+tv_y=p_yn $$ $$ t=\frac{p_xn-x}{v_x}=\frac{p_yn-y}{v_y} $$ $$ v_y(p_xn-x)=v_x(p_yn-y) $$ $$ v_ynp_x-v_xnp_y=v_yx-v_xy $$ 算是比较好想的 E 题 把反射换成往外扩展就好做了 直接推式子用 exgcd 求解 但第一发 WA 了，发现对称出去后不是这样： ![]() 而是这样： ![]() 这会导致有可能少碰到一条边，发现此时当且仅当最后到达的终点 $(p_x,p_y)$ 位于交点上 [CODE](https://codeforces.com/contest/2098/submission/340715417) ## [CF2098F](https://codeforces.com/contest/2098/problem/F) 想了半天都没什么想法，看了题解才知道要用到线性代数的思维 但我还没学过线代/kk 题解讲的很详细，看着题解再查询一些定义就可以差不多理解，但是我花了好多时间 这里再整理一下我的理解（下面的矩阵都是 $\mathbb Z_2$，好像就是所有的数对 $2$ 取模，加法相当于亦或） 首先可以把字符串转化成 $n$ 行 $m$ 列的矩阵（一次放入），保证 $n$ 是奇数，$m$ 是 $2$ 的整次幂 考虑对于 $M(s)$ 的变化 当 $n=2$ 时可实现把一行加到另一行，通过若干次操作可实现交换两行（相当于xor实现的swap） 归纳 $n>2$，前/后 $\frac{n}{2}$ 行内可实现任意交换或把一行加到另一行上 下面（来自题解，不过也好归纳）是实现前和后 $\frac{n}{2}$ 间实现把一行加到另一行（需要当成**亦或**理解） $$ \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_t \\ y_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 + x_1 + x_2 \\ y_2 + x_1 \\ \vdots \\ y_t + x_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 + y_2 + x_2 \\ y_2 + x_1 \\ \vdots \\ y_t + x_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 + y_2 + x_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} \to \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_t \\ y_1 + x_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} $$ 因为两部分间可以任意交换，所以实现了把任意一行加到另一行上，即可实现交换任意两行 所以可以实现所有初等行变换 还因为**任何可逆矩阵都能分解成初等变换** 所以只需要判断 $M(S)$ 到 $M(T)$ 是否可以左乘一个可逆矩阵得到 只需要判断他们的**最简行阶梯形**是否相等 ~~我第一次听说这个名词，直接写的高斯消元发现一直过不了，最后是 Gemini 告诉我必须要维护一个秩：~~ ```cpp for (int j=1; j<=m && rank<n; j++) { int pos=-1; for (int i=rank+1; i<=n; i++) if (a[i][j]==1) {pos=i; break;} if (pos==-1) continue; rank++; swap(a[rank], a[pos]); for (int i=1; i<=n; i++) { if (i==rank || a[i][j]==0) continue; for (int k=1; k<=m; k++) a[i][k]^=a[rank][k]; } } ``` 还有这个求最简行阶梯形可以用 bitset 优化 [CODE](https://codeforces.com/contest/2098/submission/340860646) ## [CF2103F](https://codeforces.com/contest/2103/problem/F) 思路想偏了 这种题目刚开始就直接想着从高位最优开始找，发现高位为 $1$ 的并不是一段连续的区间 对于每一位容易发现对于一个区间，从左往右每次碰到 $1$ 值都会变成 $0$，接下来交错，直到碰到下一个 $1$ 剩下的我就没有想到，题解的想法非常妙： 只考虑一位，当右端点固定时，每个区间计算后的值只与最后一次出现 $1$ 的位置有关 这之前的点为左端点时值都相等，之后的点为左端点则01交替，也就是说把编号为奇偶的左端点分开考虑，左端点移动时值只会改变有限次 也就是说当右端点固定时，此时区间的值有 $O(k)$ 种 然后就怎么做都行了 刚开始是准备直接模拟，超级复杂讨论很多 **取值数很少，发现可以用 map 来维护 DP** $f_{i,j}$ 表示以 $i$ 为右端点，取值为 $j$ 时的左端点最小是多少 我们最后会得到 $O(nk)$ 个不同的区间和可能的答案，这时候用 set 来存区间也很妙 [CODE](https://codeforces.com/contest/2103/submission/340919276) Loading... ## [CF2108D](https://codeforces.com/contest/2108/problem/D) 交互题 思路很简单 就是细节好多错了好多次 还有输出忘记换行 ILE 了好多次 [CODE](https://codeforces.com/contest/2108/submission/339902894) ## [CF2108E](https://codeforces.com/contest/2108/problem/E) 没有想到这种最大是可以取满的！！！，即每条边对答案贡献可以取到可能的最大 构造的话就**找到重心为新的根，每两个相同颜色的在不同的子树内**（这个用优先队列每次取两个最大的匹配，或者直接重心开始染（需要保证开始染的这个子树大小不为n/2，因为加上重心会使颜色不够） 删边要失去的贡献最小，选最浅的叶子节点（这个比较好想） [CODE](https://codeforces.com/contest/2108/submission/340112826) ## [CF2104D](https://codeforces.com/contest/2104/problem/D) 懒得写 [CODE](https://codeforces.com/contest/2104/submission/340114601) ## [CF2104E](https://codeforces.com/contest/2104/problem/E) 题目不难 就是第一发假了 需要加入最少的字符，应该正着找而不能倒着找 [CODE](https://codeforces.com/contest/2104/submission/340130487) ## [CF2098D](https://codeforces.com/contest/2098/problem/D) 题目不难，但刚开始把题目想复杂了 首先需要把题目转换成图，每次两个点二选一或者一选一 转化成图就连一条边表示边上两点要选出一点 对每个连通块分别计算就好了 对于有环的情况很好考虑，只能是 $0$ 或 $1$ 或 $2$ 我开始准备用树形DP计算方案数，发现整棵树上恰好一个点不取剩下的情况有且仅有 $1$ 种 方案数就为树的大小，根本不用DP [CODE](https://codeforces.com/contest/2098/submission/340688067) ## [CF2098E](https://codeforces.com/contest/2098/problem/E) $$ x+tv_x=p_xn $$ $$ y+tv_y=p_yn $$ $$ t=\frac{p_xn-x}{v_x}=\frac{p_yn-y}{v_y} $$ $$ v_y(p_xn-x)=v_x(p_yn-y) $$ $$ v_ynp_x-v_xnp_y=v_yx-v_xy $$ 算是比较好想的 E 题 把反射换成往外扩展就好做了 直接推式子用 exgcd 求解 但第一发 WA 了，发现对称出去后不是这样： ![]() 而是这样： ![]() 这会导致有可能少碰到一条边，发现此时当且仅当最后到达的终点 $(p_x,p_y)$ 位于交点上 [CODE](https://codeforces.com/contest/2098/submission/340715417) ## [CF2098F](https://codeforces.com/contest/2098/problem/F) 想了半天都没什么想法，看了题解才知道要用到线性代数的思维 但我还没学过线代/kk 题解讲的很详细，看着题解再查询一些定义就可以差不多理解，但是我花了好多时间 这里再整理一下我的理解（下面的矩阵都是 $\mathbb Z_2$，好像就是所有的数对 $2$ 取模，加法相当于亦或） 首先可以把字符串转化成 $n$ 行 $m$ 列的矩阵（一次放入），保证 $n$ 是奇数，$m$ 是 $2$ 的整次幂 考虑对于 $M(s)$ 的变化 当 $n=2$ 时可实现把一行加到另一行，通过若干次操作可实现交换两行（相当于xor实现的swap） 归纳 $n>2$，前/后 $\frac{n}{2}$ 行内可实现任意交换或把一行加到另一行上 下面（来自题解，不过也好归纳）是实现前和后 $\frac{n}{2}$ 间实现把一行加到另一行（需要当成**亦或**理解） $$ \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_t \\ y_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 + x_1 + x_2 \\ y_2 + x_1 \\ \vdots \\ y_t + x_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 + y_2 + x_2 \\ y_2 + x_1 \\ \vdots \\ y_t + x_t \end{pmatrix} \to \begin{pmatrix} x_1 + x_2 \\ x_1 \\ \vdots \\ x_t \\ y_1 + y_2 + x_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} \to \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_t \\ y_1 + x_1 \\ y_2 \\ \vdots \\ y_t \end{pmatrix} $$ 因为两部分间可以任意交换，所以实现了把任意一行加到另一行上，即可实现交换任意两行 所以可以实现所有初等行变换 还因为**任何可逆矩阵都能分解成初等变换** 所以只需要判断 $M(S)$ 到 $M(T)$ 是否可以左乘一个可逆矩阵得到 只需要判断他们的**最简行阶梯形**是否相等 ~~我第一次听说这个名词，直接写的高斯消元发现一直过不了，最后是 Gemini 告诉我必须要维护一个秩：~~ ```cpp for (int j=1; j<=m && rank<n; j++) { int pos=-1; for (int i=rank+1; i<=n; i++) if (a[i][j]==1) {pos=i; break;} if (pos==-1) continue; rank++; swap(a[rank], a[pos]); for (int i=1; i<=n; i++) { if (i==rank || a[i][j]==0) continue; for (int k=1; k<=m; k++) a[i][k]^=a[rank][k]; } } ``` 还有这个求最简行阶梯形可以用 bitset 优化 [CODE](https://codeforces.com/contest/2098/submission/340860646) ## [CF2103F](https://codeforces.com/contest/2103/problem/F) 思路想偏了 这种题目刚开始就直接想着从高位最优开始找，发现高位为 $1$ 的并不是一段连续的区间 对于每一位容易发现对于一个区间，从左往右每次碰到 $1$ 值都会变成 $0$，接下来交错，直到碰到下一个 $1$ 剩下的我就没有想到，题解的想法非常妙： 只考虑一位，当右端点固定时，每个区间计算后的值只与最后一次出现 $1$ 的位置有关 这之前的点为左端点时值都相等，之后的点为左端点则01交替，也就是说把编号为奇偶的左端点分开考虑，左端点移动时值只会改变有限次 也就是说当右端点固定时，此时区间的值有 $O(k)$ 种 然后就怎么做都行了 刚开始是准备直接模拟，超级复杂讨论很多 **取值数很少，发现可以用 map 来维护 DP** $f_{i,j}$ 表示以 $i$ 为右端点，取值为 $j$ 时的左端点最小是多少 我们最后会得到 $O(nk)$ 个不同的区间和可能的答案，这时候用 set 来存区间也很妙 [CODE](https://codeforces.com/contest/2103/submission/340919276) 最后修改：2025 年 10 月 19 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏