当前位置：首页 > news >正文

杂题记录2

news 2025/10/16 10:51:23

一些 AT *2000 上下的小清新题

[ARC186B] Typical Permutation Descriptor

题目保证有解，我们建出笛卡尔树过后是经典问题，可以组合数求解。

注意到大小关系给出的是一段区间比一个数大的形式，我们考虑开 vector 把 \(i\) 挂在 \(a_i\) 上，然后区间最大值其实就是查 \(vec_l\) 中 \(r\) 的前驱，然后就能 \(n\log n\) 建树了。

[ARC149D] Simultaneous Sugoroku

假如做过 Ynoi 某个题应该可以知道这东西可以用并查集做。

具体的，我们考虑维护整体的值域为 \([l,r]\)，以及一个并查集，并查集中的祖先就是这个数当前的值，对于一次修改，我们整体打个偏移的 \(tag\)，然后考虑跨过 \(0\) 的部分，中间的一大段是对称的，打个取反，然后考虑不对称的部分，在并查集上把小的一边往大的一边连，打上取反的 \(tag\) ，这是势能的。

实现细节很多。

[ARC146C] Even XOR

考虑从已有集合构造新集合，然后递推。

记选 \(i\) 个数的时候答案为 \(f_i\)，然后 \(f_0=1,f_1=2^n\)

对于一个大小为 \(i\) 的集合添加数转到 \(i+1\)，方案是 \(2^n - 2^{i-1}\) 的，但要注意对于每个大小为 \(i+1\) 的集合会被算 \(i+1\) 次，于是要除以个 \(i+1\)

[ARC138D] Differ by K bits

我怎么不会格雷码/yun

\(k=1\) 时是格雷码，不会格雷码结论也可以分治构造。

考虑把这个扩展到其它 \(k\)，考虑无解的情况，因为相邻两个数的异或值 popcount 为 \(k\)，所以我们把所有 popcount 为 \(k\) 的数全部插入线性基，然后假如基不是满的就说明无解。

那我们现在相当于要让相邻两个数所选基底的方案只差一个数，于是我们再套用一遍格雷码代表选哪几维就行了。

[ARC173D] Bracket Walk

考察注意力的题目。

因为是强联通所以我们可以一直走，我们记左括号权值为 \(1\)，右括号是 \(-1\)。

考虑一种构造的通解，假如有一个大小为 \(A\) 的正环，权值为 \(-B\) 的负环，那我们假如想走一个权为 \(C\) 的环上的边，那我们只需要把权值为 \(C\) 的环转 \(A,B\) 次，然后跑正负环即可。

假如只有正环或只有负环我们就无法消去正负环。

假如都不存在那么所有环权值都是 \(0\)，随便走都行。

[ARC175D] LIS on Tree 2

难点在第一步。我们记 \(sz_i\) 为 \(i\) 子树的大小。

假如 \(k<n\) 或 \(k>\sum sz_i\) 则肯定无解。

我们尝试对所有合法的 \(k\) 构造通解，注意到对一个节点 \(u\)，\(sz_u=\sum_{v\in son_u}sz_v+1\)，假如一个点 \(u\) 能对答案贡献 \(sz_u\)，也可以贡献为 \(0\)，要凑出来 \(k\)，那这个背包是一定有解的。

接着我们考虑对于一个选点的方案构造排列，这是简单的，我们只需要先 dfs 一边将有贡献的点依次从小到大赋值，然后再 dfs 一遍将不贡献的点依次从大到小赋值即可。

[ARC171D] Rolling Hash

简单题。

考虑记一个前缀的 hash 值为 \(h_i\)，因为 \(P\) 是质数，\(B<P\)，所以 \(B^i\) 非 \(0\) 且有逆元，我们记 \(\frac {h_i}{B^i}\) 的值为 \(f_i\)，那么给出一个区间 \([l,r]\) hash 不为 \(0\) 等价于 \(f_{l-1}\neq f_r\)，于是问题变成用 \(P\) 种颜色给 \(n+1\) 个点染色，有 \(m\) 条边，要求有边相连的点颜色不同。