暂无评定

CF2225D Exceptional Segments 题解 思路 定义 $f(i)=1\oplus 2\oplus\dots\oplus i$，有经典结论： $$ f(i)= \begin{cases} i &\text{if } i\bmod 4=0\ 1 &\text{if } i\bmod 4=1\ i+1 &\text{if } i\bmod 4=2\ 0 &\text{if } i\bmod 4=3 \end{cases} $$ 证明可以通过数学归纳或观察二进制规律得到。 那么区间 $[l,r]$ 的异或和可以写成： $$ l\oplus (l+1)\oplus\dots\oplus r=f®\oplus f(l-1) $$ 因为 $f®=f(l-1)\oplus (l\oplus\dots\oplus r)$。 所以区间异或为 $0$ 等价于： $$ f®=f(l-1) $$ 令 $L=l-1$，$R=r$，则条件变为： $0\le L\le x-1$ $x\le R\le n$ $f(L)=f®$ 我们需要统计满足上述条件的 ...

CF2225B Alternating String 简化题意 给定一段 01 数组 $a$。 选择一段区间 $[l,r]$，将其翻转，可以将其取反，问能否实现一次操作后数组中每个 $a_i\ne a_{i-1}$。 思路 最后若能得到合法数组，有两种情况： $a_i=i \bmod 2$； $a_i=1-i\bmod 2$。 那么我们只需要将初始值全部取反，就可以使第二种与第一种处理方法相同。 而要翻转的区间端点一定是在原数组中不合法的点。 考虑若翻转多奇数个合法点，则可以通过取反操作使其与翻转不合法点等价。 而多翻转偶数个合法点本身就与翻转不合法点等价。 所以遍历一遍整个数组，记录最左和最右的不合法点 $l,r$。 然后若 $[l,r]$ 内存在两个相邻点相等，那我也没招了，不管对整个区间取几次反都不能成功，这种情况直接不成立，排除掉。 其他情况一定可以通过取反成立，不再赘述。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...

CF2225C Red-Black Pairs 思路 只有两行，所以是简单 DP。 考虑只能通过竖着的一对或横着且左右端点相同的两对矩形组成最后的大矩形，否则会产生一个一格的缺口，一定填不满。 那么设 $f_i$ 表示要填第 $i$ 列时的最小代价，算出本次转移代价再向 $f_{i+1}$ 和 $f_{i+2}$ 转移即可。 最后取 $f_{n+1}$ 为答案（要填 $n+1$，已经填完 $n$）。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i&g...

CF2220B OIE Excursion 思路 首先每个时间点都可以在原地停留，向左或向右。 先考虑 $m=2$ 的情况。 对于 $i$ 号位置，若可以到达，则可能可以通过一些调整使其在除 $a_i$ 之外的其他时间到达。 考虑什么时候做不到调整，即 $a_i=a_{i+1}$ 时，不论怎样通过这一段都需要至少 $3$ 秒的空档期，无法通过。 那么对这个东西进行推广，若有 $i\in[l,r]$，所有 $a_i$ 相等，则至少要 $(r-l+1)+1$ 的时间才可以通过，而我们拥有 $m$ 秒的时间，进行比大小即可。 所以线性地扫描一遍，判断每段连续的区间长度加一与 $m$ 的大小关系即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<bits/stdc++.h>#define fir first#define sec second #define int long ...

CF2203B Beautiful Numbers 思路 首先满足 $F(x)=F(F(x))$ 的数所有数位之和一定 $<10$。 我们设 $dp_{i,j}$ 表示处理完前 $i$ 位数字，各位和为 $j$ 时的最少修改次数。 初始设为一个极大值表示不可达。 枚举最后的总数位和 $1$ 到 $9$。 遍历每一位数字 $i$。 遍历总数位和 $j$。 枚举当前位要修改成什么数 $k$。 如果当前要修改成的数字 $k$ 不等于原数字，则修改次数增加。 核心转移方程为 $dp_{i+1,j+k}=\min(dp_{i+1,j+k},dp_{i,j}+(k\neq d));$ 最后再看是否存在可达的状态即可，更新答案为这些最终数位和对应的最小值。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc++.h>#define fir...