January Challenge 2021 Division 1 题解

一直在摸最后一天下午才开始写代码，结果有个题没调出来。。。

Chef and Ants

一个经典问题的加强版，将碰撞分成在原点处的碰撞和不在原点处的碰撞。
当蚂蚁在原点碰撞会回头，不在原点碰撞可以视为两只蚂蚁互相穿过对方。
原点碰撞次数就是那些绝对值出现次数超过一次的绝对值的数量，并且可以根据这个判断每只蚂蚁是否到原点后回头。
不在原点碰撞的次数可以每条线单独考虑，对每只蚂蚁只考虑绝对值比它小的蚂蚁是否与它碰撞，那么只有同半轴且回头或者不同半轴且不回头的蚂蚁会与它碰撞。
如果使用hash表统计每个绝对值出现次数，复杂度\(O(\sum M)\)；也可以使用堆来完成多个数组归并排序，得到稳定的复杂度\((\sum M\log N)\).

Expected Number of SCCs

A能到B当且仅当A的值不比B小，反之亦然。因此同一个强连通分量实际上就是值相等的连通分量。
如果记前\(i\)列的答案为\(f(i)\),那么只需要求\(Ef(1)\)和\(E(f(i)-f(i-1))\)。当\(M\le2\)时,\(f(i)-f(i-1)\)只和第\(i\)列以及第\(i-1\)列相关。
考虑相邻两列所有可能的情况：

分别计算每种情况出现的概率即可，复杂度\(O(1)\).

Guess the Tiling

分为三步：
1.考虑左上角\(2\times2\)的，\(16=4\times2^2\)次可以枚举所有情况，如果存在只改变左上角并且使得\(K\)的值\(+1\)的情况,那么就是11/10变成01/10。
2.考虑前\(2\)列，考虑到第\(i\)行先将第\(i-1\)行变成01，然后修改第\(i\)行第\(1\)列：
a.如果不改变答案，说明第\(i\)行第\(2\)列是1，把它改成\(0\)再次修改第\(i\)行第\(1\)列
b.如果改变答案，如果答案变小，先把第\(i\)行第\(1\)列变回去，这个时候第\(i\)行前两列可能是01和下一行形成正方形或者10和上一行形成正方形，这个时候再修改上一行即可判断。
最多只需要\(5=2.5\times2\)步，同理可确定前\(2\)行。
3.剩下的格子从左到右从上到下，可以修改它左上，上，左的位置为01/1?,然后只需要修改一次它即可判断它的方向。
每个格子平均不超过\(4\)步。

Blackjack

只需要求出前\(i\)个数和为\(j\)至少需要删去几个数，后\(i\)个数和为\(j\)至少需要几个数，每次取一个前缀的dp值和后缀的dp值用单调栈来求出答案。复杂度\(O(NY)\).

Cool Subsets

有原根的数只有\(1,2,4,p^k,2p^k\),其中\(p\)是奇素数。用线性筛计算函数\(f(x)=r_3+r_5+\cdots+\cdots,x=2^{r_2}3^{r_3}5^{r_5}\cdots\)。
那么集合的coolness为\(\sum f(x)(1+[\)存在偶数\(])+\)积存在因子\(4\)，用简单的容斥就可以计算大小为\(A\)到\(B\)的所有集合coolness之和，但是需要计算组合数的前缀和，即
\(SC(N,M)=\displaystyle\sum_{i=0}^M\binom{N}{i}\).由于已知\(SC(N,M)\)可以\(O(1)\)计算\(SC(N\pm1,M\pm1)\)，那么可以用类似莫队的方法计算所有要用到的组合数前缀和。
复杂度\(O(R_\max\sqrt T+T)\).

And-Or Game

记值域为\([0,2^M)\)。考虑从\(0\)出发到所有点的距离，如果暴力建边，就是\(4^M\)；但实际上有些边是重复的，比如每个点在与作用下只会连向其子集，因此边数只有\(3^M\).
可以发现，从起点到任何一个可以到达的点距离不超过\(M\)步，因为从后往前看，每一步至少都会改变一位，并且这位与结果相同，否则这步就没意义。
那么用FWT可以\(O(M2^M)\)求一步后可以到达的所有结果，复杂度为\(O(M^22^M)\)。

Curious Matrix

数学部分很简单：原限制等价于对所有\(2\times2\)的格子行列式为\(0\)，因为如果对所有\(n\)阶成立，那么\(n+1\)阶可以对每一行展开仍然是\(p\)的倍数。
进一步的，这等价于给每一行每一列分配一个非零数，那么每个格子的值是对应行和对应列的积。需要注意\(p-1\)中分配方式对应\(1\)种格子的填写方式。
那么，每个\(x,y\)的值赋为\(v\)其实就是添加了某些等价关系，由于这个等价关系的运算是可逆的，可以用并查集处理，每个结点记它与并查集的根的关系，就能推出同一并查集中两个结点的关系。
由于还有删除操作，那么需要使用线段树采用类似对时间分治的方法，只保留添加操作到每个线段树的结点中，那么前序遍历线段树时同时维护并查集，离开结点时撤销操作，就可以在叶子结点求出答案。
由于需要撤销并查集操作，并查集不能支持路径压缩，复杂度为\(O(Q\log Q\log N)\).
ps：写了但过不了，可能漏了什么细节。

Sequence Creation

大概就是对每个\(i\),\(A_i\)和\(B_i\)连边，考虑每个连通块给边定向，使得每个点入度不超过\(1\)。
首先连通块边数肯定大于点数\(-1\)，如果边数等于点数，那么就是棵基环树，环上可定两个向。如果边数等于点数\(-1\)，那么就是棵树，选一个根就可定向。如果边数大于点数，那么不够选，答案为\(0\).
由于需要在线加边删边，需要动态树来维护连通性。
ps：根本不会LCT维护连通性。

Greedy Students

没看

January Challenge 2021 Division 1 题解

原文：https://www.cnblogs.com/Heltion/p/14263765.html