[总结] 2024 CSP-S 模拟赛 Day1

jr_zch · 2024-09-12 15:47:25 · 学习·文化课

2024 CSP-S 模拟赛 Day1

给我一种多学了一年还是做不出来 \text{T2} 的绝望感。

感受到和 \gcd(n,k) 很有关系，然后把每种颜色分开讨论就做完了，耗时 30 \min。

看完题很容易想到按位去贪心，但是我的思考方式似乎和正解不太一样。

我想的是对于每一位去判断是否存在一种方案满足当前位和之前的高位已经确定下来的值，于是便执着于去寻找一种确切的方案，这是非常不可做的。

容易发现我在考虑当前位的时候还要处理很多高位的限制，这显然是不太对的，既然都已经按位处理了，考虑当前位时就不该去处理前面的限制，或者说是前面的限制都已经有了大致的方案可以满足，现在要做的只是根据当前位的限制将这个大致的方案再次进行细分，本质上就是分治。

所以正解就是对于当前位，把数分成 0/1 两类，然后再去向下递归，如果 1 的个数为奇数，做一些正常的字典树查找就好了。

我的思考方式就导致了这道题一直没有什么进展，浪费了很多时间，但是我并没有死磕，这个决定显然是正确的，虽然结果同样很糟糕（

神秘暴搜题，赛时一直觉得是状压 \text{DP}，自己的乱搞没过样例，就交了个 -1。

因为题目对方案的限制太强了，事实上可以很直观地感受到合法方案数是非常少的，而且和状压 \text{DP} 题目的风格也是大相径庭。

所以说像这种“二维网格”、“选格子操作”，然后还有各种限制条件的题，数据范围又很小，还是多往搜索上靠靠，之前也见过不少这类题。

因为每次操作都是对相邻格子做，所以按行搜索后可以确定下一行是哪些格子做操作，仅需要对第一行 O(2^m) 枚举一下即可。这个套路以前也见过：手机游戏。

赛时写了一个 O(n^2 \log_2 n) 的暴力，但是好像有点问题，只拿了 6 \text{pts}。

做法似乎很套路，尤其是拿线段树维护最深的点，每次取出一个贪心做连边操作，真的很像超级钢琴一类题用堆维护前 k 个最值的思想。

时间分配没问题，爆炸的主要因素在于 \text{T2}，感觉自己想这道题的时候好蠢……