2023.8 做题笔记

kawaii-lkx / 2023-08-13 / 原文

不愿忘却。

早知如此绊人心，当初何必相识。

记录了好玩的题目，代码都很好写（

[ARC092F] Two Faced Edges tag：tarjan，dfs

che 的题解。

tarjan 之后按在不在 scc 上面分讨边，发现要求不含 \((u,v)\) 的路径是否存在。想办法算路径长度 \(>1\)，裸 dfs 算路径是搜索树一条边。正反 dfs 一定有一个可以算出如果存在的合法路径。

[CF348C] Subset Sums tag：根号分治

根号分治。将集合按照跟 \(t=\sqrt n\) 的大小关系分为轻|重集合，因为 \(\sum n_i\) 范围确立，这么干有两个好处，重集合最多有根号个，轻集合长度不超过根号。对于轻集合，直接暴力处理，对于重集合，我们打上标记。然后会发现诶这个重集合贡献需要加到别的里面，那我们预处理每个集合跟每个重集合的公共部分大小就可以了喵。

具体而言，预处理重集合和每个集合的交集大小。

重集合修改：打上修改标记。
轻集合修改：在原序列暴力修改。
重集合查询：提前算好的 sum 加上跟重集合的贡献。
轻集合查询：暴力算 sum 然后加上跟重集合的贡献。

[AGC011C] Squared Graph tag：二分图

原图乘出来非常非常非常非常抽象，考虑 \((a,b)\to (c,d)\) 联通的情况，那是一个在原图上同时游走的游戏 /se。对于原本的一个联通块，有奇环显然随便玩，不然就得二分图裂开，特殊的孤立点也是一种情况。这样计算各种东西的数量就能算出贡献了。

[CF741C] Arpa’s overnight party and Mehrdad’s silent entering tag：二分图，构造

考虑配对显得非常难做，构造题做起来要猛一点，就像原神玩家一样！直接间歇性强制配对，然后发现肯定是有解。二分图染色？启动！

P3573 [POI2014] RAJ-Rally tag：拓扑排序，堆

DAG 图很好，先预处理 \(f[i]\) 和 \(g[i]\) 表示从 \(s,t\) 在正|反图上面的最短路。按照拓扑序考虑，对于一个点 \(x\)，\(p\) 在 \(x\) 前面，\(q\) 在 \(x\) 后面，删掉祂之后的最长路有三种情况，\(f[p],g[q],f[p]+g[q]+1\)，最后一种要求 \((p,q)\) 存在捏。因为 DAG 性质很好直接按 DAG 动态维护就好了，使用优先队列 /kel/kel

[CF442C] Artem and Array tag：贪心，构造

如果一个数比两边小，随便删，然后最后就是一个数组的峰的单。考虑怎么构造，比如说最大值和次大值分别在 \(x,y\)，祂们谁旁边的大删谁。最终的贡献就是前 \(n-2\) 小的 \(a_x\) 啦 qwq

[ARC072F] Dam tag：建模，凸包

设 \(f[i]=j\) 表示 \(i\) 的容量最多能拿到 \(j\) 的热量（温度乘体积），这是一个上突壳子的函数。明确一点我们加水是强制的捏，所以每一轮先把原本的加上一个向量，去掉多的地方，然后我们发现后面的放水可能会让前面的答案更好，所以每个点忘原点连一条线之后新的上突壳子即为新的 \(f\) 函数！

玩一个单调队列维护就可以啦，每次删掉斜率比后面小的点。有一种 ~~跟我的可爱的 teriri 一样~~ 可爱的做法，直接把每次加水的向量加到队列里面，不维护那种丑陋的东西也可以啦，每次就，如果斜率比不上就两个向量加起来！

[ABC191F] GCD or MIN tag：数论，枚举

che 的题解。

考虑各种弱化拼在一起就行了。这篇题解因为 latex 被打回多次，不开心捏。任意 gcd 可以枚举约数搞 gcd 判断合不合法，然后发现 \(\min\{a_i\}\) 是 gcd 合法的界限。

[ABC243G] Sqrt tag：dp，整除分块

\[f_n=\sum_{i=1}^{\sqrt n}f_i=\sum_{i=1}^{\sqrt{\sqrt n}}(\lfloor \sqrt n\rfloor-i^2+1)f_i \]

事实上一直类似搞进去可以拥有很离谱的复杂度，但感觉没太大必要。

[ABC308G] Minimum Xor Pair Query tag：xor

把序列排序，xor 最小值肯定在 a[x]^a[x+1] 中出现过，感性理解就是 xor 是类似减法所以要求的是尽量接近，证明可以搞点交换。开俩 multiset 动态维护就可以了。

P9378 [THUPC 2023 决赛] 物理实验 tag：贪心

注意到权值有绝对的领先，我们考虑贪心的取，维护选的数的集合 \(in[]\)，如果能加入那就加入。再考虑怎么判断，维护 \(vis[i]\) 表示每个点有没有被做掉或者炸掉，碰到不要的直接就炸了，不然就一直用做掉这个实验的方式保护祂，如果保护不来就是不可以。

[AGC016D] XOR Replace tag：xor，贪心，基环树

a[1]^...^a[n-1]^a[n]=M,a[1]^...^a[n-1]^M=a[n] 所以可以当成在末尾多放一个 M 然后每次可以 swap(a[x],a[n+1])。对于一组 \((a_i,b_i)\) 可以看做一个「放入 \(b_i\) 得到 \(a_i\)」的游戏，自然而言想到建图于是得到变成了走到。

每个点出入度均为 1 的情况：如果没有重复值（指 \(a_i=a_j\) 且 \(i\neq j\)）那这是一堆环，有重复值就是环打结，也不影响答案。每个环需要额外走一次，答案就是「边数+联通块个数」。如果 M 可以混入其中那就 -1。存在点出|入度不为 1 的情况：其实就是上面的情况一个环变成了一条链，我们会发现链跟点没啥区别，如果 M 出现在链上一定是底，不会有额外贡献。

[AGC004C] AND Grid tag：构造

前缀唯一绿题（划掉。

两个答案图与起来等于原图，并且分别四（上下左右的）联通。首先原图的部分肯定要 1 进去！剩下的一个位置要不然 A 有要不然 B 有要不然 AB 都没有。考虑到这是一个构造题，AB 都没有什么的肯定是人家不喜欢的啦。

所以我们想一种办法，恰好能把 A 联通，剩下的部分全部给 B 然后 B 也可以联通。这个就有很多办法啦，第一列给左，最后一列给右，其它奇数行给左偶数行给右，或者直接构造两个蛇型玩意儿也可以。大概思路就是，拿宽度为 2，两种颜色的笔刷从边上出发用合法的颜色覆盖整个图即可。

[ARC107D] Number of Multisets tag：dp

\(f[i][j]\) 表示 \(i\) 个数凑成 \(j\) 的方案数，\(j\) 也是整数谢谢喵。对于整数贡献显然是 \(f[i-1][j]\)，但是分数怎么办呢，分母都是 2 的倍数那转化成整数问题就能做了，贡献是 \(f[i][2j]\)。

[CF1270G] Subset with Zero Sum tag：基环树

化丑陋的 \(i-n\leq a_i\leq i-1\) 为可爱的 \(1\leq i-a_i\leq n\)，然后我们连边 \((i,i-a_i)\)，每个点一个出边这是一个内向基环树森林，一条边可以看成一个变化，若干次变化之后变成自己意思就是被 -0 了，上面的一个环就是一组解了。

[CF1364E] X-OR tag：交互，or，and

我们想着，先找到 0 的位置，然后可以用 1 次询问到任意 \(a_x\) 的值，合计 \(n-1\) 次。极限情况 \(q=2n+173\)，所以我们要在 \(n+174\) 次里面找出来 0。先考虑对于位置 \(p\) 怎么求 \(a_p\)，随便随几个 and 起来基本上就对了捏。然后我们不断的维护数 \(p\) 和祂的 \(a[p]\)，新加的数如果是 \(p\) 的子集就替换，不然就跳过，这样最后就可以得到 0 了。询问次数 \(O(n+t\log n)\)，\(t\) 是求一个数的随机次数，log 是因为每次至少去掉一个 1，随机次数我取了 15 过了题，询问上可以搞点去重小优化之类的，这个复杂度稍微有点危险的（？