目录
- [x] A
- [x] B
- [x] C
- [x] D
- [x] E
- [x] F
- [x] G
- [x] H
- [x] I
- [ ] J
- [ ] K
A ^&^
给定 (A,B) ，要你找到最小的 (C)，使得 ((A oplus B)&(B|C)) 最小。特别地，如果 (C=0)，那么输出 (1) 。
(1leq B,C < 2^{32})
每一位都是独立的，可以把这个式子看成一个新的位运算，直接算出它每一位的真值表，那么直接按位贪心即可。
时间复杂度 (O(log max(B,C)))
B array
给你一个长度为 (n) 的排列，(m) 个操作。操作有两种，把里面的某个数增加 (10^7)，或者询问不等于 (a_1,a_2,cdots,a_r)，且不小于 (k) 的最小的数是多少。
(n,mleq 10^5,kleq n)
(k) 不超过 (n) ，所以答案必定不超过 (n+1)，如果答案不是 (1 sim n) ，那么必定是 (n+1) 。我们可以考虑权值线段树，维护权值为 (1sim n) 的数在序列中的出现位置。修改可以直接删去这个数，这样我们只需要查询权值 ([k,n]) 的数出现的最小且大于 (r) 的位置。
时间复杂度 (O(mlog n))
C K-th occurrence
给定一个长为 (n) 的字符串 (S)，(q) 次询问，每次询问其子串 (S(l,r)) 在字符串中的从左到右第 (k) 次出现的开始位置。
(n,qleq 10^5)
建SAM，用倍增 (O(log n)) 找出子串的对应节点，并把询问挂在上面，再用线段树合并维护出每个节点的 right 集合，询问即可。离线可以避免对线段树持久化。
(O((n+q)log n))
D path
给一张有向带权图，点数为 (n)，边数为 (m)，多次询问求图中第 (k) 短的路径，允许多次经过同一条边，其边权也要计算多次。
(n,m,kleq 5 imes 10^4,1 leq w_i leq 10^9)
考虑一条路径怎么生成，就是从一个点不断扩展。我们直接用类似BFS的思路搜出最短的 (max k) 条路径即可，按询问的 (k) 大小顺序解决。但由于有可能会有菊花图，即导致中心点不断被访问，加入非常多的无效路径，我们可以考虑把出边按边权排序，然后在遍历到肯定超过 (max k) 的路径时直接 break。注意只维护最小的 (k) 种方案，多余的直接弹出。
考虑怎么分析时间复杂度。我们其实只需要分析我们会搜出多少条不是最小 (k) 条的路径，因为这些方案我们都需要弹出。首先只有前 (k) 小的方案才会被用来更新，在这些方案的基础上，我们由它扩展出的新方案肯定不会再经过某一条边一次以上，因为如果经过两次，那么经过一次的方案肯定会在前 (k) 种方案中，被用来扩展出经过两次的方案，矛盾。因此时间复杂度为 (O((k+m)log k)) 。
E huntian
给定 (n,a,b)，求
(1 leq n,a,b leq 10^9,gcd(a,b)=1)
(i^a-j^a) 可以因式分解出一个 (i-j) 的因子，又保证 (a,b) 互质，(i,j) 互质，那么盲猜后面的式子就是 ((i-j))，打个表发现是对的。
就是要求
考虑后半部分，对于特定的 (i(i>2)) ，由更相减损法的原理我们知道 (gcd(i,j)=gcd(i,i-j)) ，因此互质的数成对出现，且和为 (i) ，那么后半部分其实就是 (frac {iphi(i)} 2) 。当然，特殊处理 (i=1) 时的贡献即可。
这样答案其实就是 (frac 1 2sum_{i=1}^n iphi(i)-frac 1 2)
前面的式子是一个积性函数求和。可以杜教筛，构造 (g=id)，那么 ((f*g)(n)=n^2) 。
F Shuffle Card
有 (n) 张卡牌排成一排，做 (m) 次操作，每次将编号为 (i) 的卡牌拿出来放到最左边，问操作完后整个卡牌的顺序。
(n,mleq 10^5)
用链表模拟即可。
G Windows of CCPC
第 (k) 个矩阵是将 (4) 个 (k-1) 矩阵拼接，但左下角的子矩阵将 (C) 和 (P) 取反后得到。
(kleq 10)
递归模拟。
H Fishing Master
有 (n) 条鱼，抓一条鱼需要花费 (k) 的时间，烤编号为 (i) 的鱼至少需要 (t_i) 的时间，将鱼拿去烤和拿回来都不花费时间。抓鱼时不能做其他事情，但烤鱼时可以同时抓鱼，且同一时间只能烤一条鱼。
(nleq 10^5,1leq k,t_ileq 10^9)
除了第一条鱼一定要单独耗时，显然如果烤鱼 (t_i geq k) ，我们在此过程中至少可以抓 (lfloor frac {t_i} k floor) 条鱼。我们希望尽量少的耽误烤鱼时间，因为我们最后的时间肯定是以烤鱼结束，而不是抓鱼结束。
如果 (sum lfloor frac {t_i} k floorgeq n-1) ，那么我们不需要耽误烤鱼时间。否则，我们就会需要让某次烤鱼多烤一会等待我们再抓一次鱼，这样多耗费的时间是 (t_i-t_i mod k) ，且我们肯定只会在一次烤鱼时耽误一次，因为一次只能烤一条鱼，没必要让第二次耽误时烤炉空着。
贪心即可，时间复杂度 (O(nlog n))，瓶颈在于排序。
I Kaguya
给一个二分图并黑白染色，已知黑点有 (n) 个，白点有 (m) 个，一对黑白点之间有 (frac 1 2) 的概率存在一条双向边，问一对黑白点之间的期望最短距离。
(1leq n,mleq 30)
假设选取一个白点为源点，那么我们就是要求它到所有黑点的距离和。考虑BFS的过程，设 (f[n][a][b][l]) 表示BFS到第 (n) 层时，一共已经遍历过了 (a) 个白点，(b) 个黑点，且当前层的点数为 (l) 的概率。
那么只需要计算一个局面出现的概率，即可进行转移，不妨假设第 (n) 层是白点：
意思就是局面的概率就是下一层的 (t) 个点必须和当前层 (l) 个点至少有一条边，且其他不在下一层的点与他们都没有边。
这样的复杂度是 (O(n^5)) ，但其实有很多冗余操作，优化一下DP的上下界并注意常数和预处理即可。