CSP模拟赛

【2022 正睿 CSP 七连测 Day1】A - 上海

质数与 $1$ 无解，剩下的考虑指数奇偶讨论。

【2022 正睿 CSP 七连测 Day1】B - 华二

观察到 $a \in [1,10]$，找关系。

既然是互质可以交换。

那么不互质我们可以划分为，$n_i$ 表示元素 $i$ 的出现次数，$S_1$ 是可以任意交换的集合，$S_2~S_3$ 是集合内任意两个元素都不可以交换的集合。

$$\begin{cases} S_1={n_1·1,n_5·5,n_7·7}\\ S_2={n_2·2,n_4·4,n_8·8,n_6·6}\\ S_3={n_3·3,n_9·9,n_6·6} \end{cases}$$

考虑 $6$，$6$ 是分界线，$1 ~5~ 7$ 随便换，那么也就是说。

对于集合 $S_1$ 它可出现再在序列的任意位置，物品们考虑最后去排列他们，先单独放出来不管。

我们发现 $6$ 很特殊，不如考虑把它变成集合的分隔点，分隔点包含的元素是可以任意交换的，那我们就可以求一下多重集排列数，此时先不考虑 $S_1$。

那么每次我们把集合内部的考虑完了，运用乘法原理就好了。

现在考虑对于放在一边的 $S_1$ 集合，他们是可以任意交换的。

那其实就相当于 $n$ 个元素随便排列，但是对于 $6$ 分隔开的集合，他们相当于是等价的，是不能多算的，因此我们得出去这个相对关系，但是我们可以破环他们的绝对关系，而相对关系是无影响的。

我的疑惑点在于这个，现在我要把我自己解释清楚。

如果对于 $S_1$ 集合的元素我们换到了不能交换的几个数之间，我们其实可以发现，他们的相对关系还是不变，动的仅仅只是这个可以任意交换的元素。

因此这绝对是等价多重集合排列数。

此题绝对是考察对多重及集排列数的好题。

再多说一句，就是不同的元素可以插到连续的相同元素中，这个相同元素又是可以扩展到等价类的。

【2022 正睿 CSP 七连测 Day1】C - 高爸

考虑操作的实际影响对象。

转化完之后发现他是一个带有限制的一个东西，不能直接取中位数，但是考虑到他的单调性很简单，是单谷函数，考虑三分。

对于三分求值的优化，可以使用线段树去维护，线段树下标代表这离散化后的实际位置，统计也是简单的。

我用的双 $log$ 做法，是不优秀的，这是因为没有考虑到一个性质，决策是在原基础上偏移一位的。

【2022 正睿 CSP 七连测 Day1】D - 金牌

这题是最简单的组合计数题了。

考虑新加入一条边对原贡献的影响。

优化考虑使用 $tarjan$ 算法 $O(n)$ 求 $LCA$，离线处理询问，保存 $k$ 级别祖先是可以做到 $O(n)$ 的。

总结

• 部分分还是没有拿全，明明是可以的。

• 还是抓紧考场上的每一分每一秒，去思考。

• 对算法的模板的掌握程度，将决定你的分数上线。

• 论思考的重要性，从一点突破，缺什么就去找什么，一定要深入思考，不能畏缩，畏缩就会失败。

• 取模得问题还是得记得负数，以后写成这样标准的形式 $(x \% p +p)\%p$。

• 关于对拍切记把 $define ~int ~long~ long$ 给我挂上。

• 优化不要慌先写出暴力，再优化。

• 论 $Linux$ 得重要性。

• 造数据一定得要有梯度，就是某些感觉比较的特殊得就写上。

这不知道谁写的，感觉还是可以的。

1
2
3
4
5
6
7
8
9
10

数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。

__END__