GRYZ20211103模拟赛解题报告
- T1 city
- T2 paint
- T3 vanilla
期望得分：\(100+100+100=300pts\)
实际得分：\(100+100+0=200pts\)
恭喜我自己，没有算空间挂了 100pts。
7:40 发题面
7:48 读完题，发现 T1 和二进制有关
7:56 调完 T1。T2 期望感觉巨难直接开 T3，想了想 T3 的做法稍微算了一下复杂度，感觉正确性没什么问题，复杂度可能有点卡，然后开写。
8:45 调了好久终于过了样例，然后一发过了大样例，只不过跑的有点慢，算了一下发现复杂度果然过不去，对一些地方进行了优化，极限数据本地跑了 7s，应该刚好能卡过去的程度。可能会爆 long long 就把 define int long long 写上了。（埋下伏笔）
9:10 上厕所，回来开始想 T2，推了推感觉 k=1 的情况挺好写，就把这一部分写了，现在对于正解还是没有思路的。
9:35 想起来答应给 @斜揽残箫 写的题解还没写，于是先把他的题解写完了。
10:00 有上了次厕所，回来看了看 T2，转化了一下思路，感觉可以做，手推了式子开始写。
10:35 终于调出来了，有惊无险（一发过大样例还是挺不错的）。检查了一下，把这个题解写了，然后开始摆烂，拿出了 BS 给的小说。
10:55 收卷。果然自己被卡空间了，wsdsb。/hanx
感觉 T2 最后能想出来非常的幸运，不过 T3 没算空间就比较傻逼了。
为什么我老挂分啊/ll，为什么我老挂分啊/ll，为什么我老挂分啊/ll，为什么我老挂分啊/ll，为什么我老挂分啊/ll，为什么我老挂分啊/ll，为什么我老挂分啊/ll，为什么我老挂分啊/ll
T3 最后在评测机和洛谷上测了测，有两个点是踩着 2000ms 的线卡过去的。
| T1 | T2 | T3 |
|---|---|---|
| T208866 city | T208867 paint | T208869 vanilla |
T1 city
如果把数转化成二进制再来看这三个操作就非常简单了。
分别是左移一位+1，左移一位，右移一位。
所以每次操作只能更改两个数的低位，那我们看看这两个数从高位开始匹配能匹配多少位，答案就是两个数剩下的不能匹配的位数和。
int main()
{
// freopen("city.in","r",stdin);
// freopen("city.out","w",stdout);
n = read();
while(n--) {
x = read(), y = read(), sc = 0, top = 0;
while(x) a[++sc] = (x & 1), x >>= 1;
while(y) b[++top] = (y & 1), y >>= 1;
while(sc && top && a[sc] == b[top]) sc--, top--;
printf("%d\n", sc + top);
}
fclose(stdin);
fclose(stdout);
return 0;
}
T2 paint
如果你按照题意去模拟会非常难搞，考虑转化一下思路。
首先，一张画纸期望是什么颜色只与它被修改几次有关。因此我们可以设 \(f_{i,j}\) 表示一张画纸被修改了 \(j\) 次变成了 \(i\) 的期望。
然后我们考虑一下区间覆盖的问题，如果一次作画框住了区间 \([l,r]\)。设这个区间长度为 \(len\)，我们考虑其中的某个位置会被选中多少次，那就是假设它被选中其他的位置随便选的方案数，所以它会被选中 \(2^{len-1}\)，而整个区间的子集有 \(2^{len}\) 种，说的可能麻烦了，但不难发现，一个位置被选中的概率为 \(\frac{1}{2}\)。
所以呢，我们就可以利用差分快速统计出每个位置被区间覆盖了多少次。
然后开始统计答案！
我们枚举每个位置，枚举它可能被覆盖了几次，计算出这个次数，计算它期望的颜色，对所有的期望的颜色求和就是答案。
那写成公式就是：
\[\sum_{i=1}^{n} \sum_{k=0}^{d} \frac{1}{2^d} \binom{d}{k} \sum_{j = 0}^{c - 1} j \times f_{j, k} \]其中 \(i\) 表示第 \(i\) 个位置，\(k\) 表示枚举到被覆盖了 \(k\) 次，\(d\) 表示一共被 \(d\) 个区间覆盖，\(j\) 表示期望为颜色 \(j\) 的概率。
时间复杂度为 \(\mathcal O(Kc^2 + nK(K+c))\)
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
Believe yourself !
OHHHHHHHHHHHHHHHHHHH一发过大样例！
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define LD long double
#define orz cout<<"lkp AK IOI!"< T3 vanilla
你看这个数据范围就知道要状压，你看它要求最短路径就得状压最短路。
我们先跑个 Folyd 求出两两之间的最短距离。
我们在设两个数组 \(f[S][i], g[S][i]\) 分别表示以 \(1\) 作为出发点，已经进行收割/播种的状态为 \(S\)，最后一个点为 \(i\) 的最短距离，\(g\) 数组则表示以 \(n\) 为出发点。
上面这个 \(f,g\) 数组可以预处理出来。时间复杂度为 \(\mathcal O(2^n n^2)\)，这个复杂度有点危，我们发现我们不用枚举全部的，我们只需要枚举 \(S\) 中 \(1\) 的个数 \(\le \frac{n-2}{2}+2\) 的状态即可。复杂度就被我们优化掉一个 \(n\)（我们本质还是枚举所有子集，只不过在某些子集只做了 \(\mathcal O(n)\) Check ）
然后你枚举首先选择哪 \(\frac{n-2}{2}\) 个花田收割，设枚举的收割的花田的状态为 \(S\)。
我们考虑收割的过程，考虑怎么把前一半的最短路和后一半的最短路合并起来，那就是，枚举在集合中的点 \(i\) 和不在集合中的点 \(j\)，设答案为 \(res\)，则：
\[res = \min \{ f[S|1][i] + g[M^(S|(1<其中 \(M\) 表示所有点的全集。
这样就保证了 \(S\) 状态中选中的点一定会在前 \(\frac{n-2}{2}\) 花田里收割，剩余的点在后来收割。
同理，我们考虑播种的过程，其实就是反过来，我们再设一个播种的答案 \(ans\)，则
\[ans = \min \{ g[S|1][i] + f[M^(S|(1<最终答案就是 \(\min \{res + ans\}\)。
这个直接上搜索就行，控制一下搜索上限，可以控制复杂度为 \(\mathcal O(2^{\frac{n-2}{2}} \frac{n-2}{2}^{2})\)。
在本地跑了 7s，但 XP 的拉是众所周知的，所以应该是没问题的。
除非正解有一个更牛逼的做法。
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< N) return ;
if(pos == n) {
if(cnt != N) return ;
int res1 = INF, res2 = INF;
// cout< N + 2) continue;
for(int i = 1; i <= n; ++i) {
if(!(S & (1 << i - 1))) continue;
for(int j = 1; j <= n; ++j) {
if(S & (1 << j - 1)) continue;
f[S | (1 << j - 1)][j] = min(f[S | (1 << j - 1)][j], f[S][i] + dis[i][j]);
}
}
}
memset(g, 0x3f, sizeof g);
g[(1 << n - 1)][n] = 0;
for(int S = 0; S < (1 << n); ++S) {
int cnt = 0;
for(int i = 1; i <= n; ++i) if(S & (1 << i - 1)) cnt++;
if(cnt > N + 2) continue;
for(int i = 1; i <= n; ++i) {
if(!(S & (1 << i - 1))) continue;
for(int j = 1; j <= n; ++j) {
if(S & (1 << j - 1)) continue;
g[S | (1 << j - 1)][j] = min(g[S | (1 << j - 1)][j], g[S][i] + dis[i][j]);
}
// cout<