Day1

A. [21 ZR联赛集训 day1]数字变换

你有一个素数 $p$ 和二元组 $(a, b)$, 它们的和不被 $p$ 整除.

你想对这个二元组进行若干次操作, 让它变成另外一个二元组. 每一步, 你可以二元组做如下操作中的一个:

  • 把 $(a, b)$ 变成 $(2a \mod p, (b+p-a) \mod p)$
  • 把 $(a, b)$ 变成 $((a+p-b) \mod p, 2b \mod p)$

你需要回答 $q$ 次询问, 每次询问, 给你 $a_i, b_i, c_i, d_i$, 问最少需要多少步能将 $(a_i, b_i)$ 变成 $(c_i, d_i)$. 如果不可行, 那么输出 $-1$.

注意, 这里 $(a, b)$ 和 $(b, a)$ 是不同的.

$2 \leq p \leq 10^9, 1 \leq q \leq 10^5, 0 \leq a_i, b_i, c_i, d_i < p$, 保证 $a_i + b_i \not\equiv 0 \pmod p, c_i + d_i \not\equiv 0 \pmod p$.

操作不改变 $(a+b)$, 会判无解了, 此时只要让 $a=c$, 而此时考虑 $b$ 不如考虑 $s=a+b$, 因为不变.

发现每次 $a=2a$ 或 $a=2a-s$, 那么操作 $k$ 次后就成了 $2^a-vs$, 其中 $v\in[0, 2^k]$(用二进制表示 $v$ 照着操作即可). 而如果 $2^k>p$, 因为 $p$ 是素数, 一定有解, 于是枚举 $k$ 判有无解即可.

B. [21 ZR联赛集训 day1]均分财产

有 $n$ 个数 $(2 \leq n \leq 2 \times 10^5)$, 你可以删除其中不超过 $k$ 个数 $(min(25, n-2) \leq k \leq n-2)$, 然后将剩下的数划分成两个子集(可以有重复的数字), 满足这两个子集中的数的和是相等的. 这 $n$ 个数都是在 $1$ 到 $W$ 内随机的, 其中 $W=200000$.

$n$ 小于 $40$, 可以Meetinthemiddle, 很大的时候, 在前面部分先从大到校贪心着随便放, 最后得到一个 $W$ 以内的数 $x$, 然后把它当成一个数添加进去, 和剩下的匹配, 40个数的话, 因为随机, 抽屉原理一下可能性还是非常大的.

至于 $k$, 不需要的(乐)

C. [21 ZR联赛集训 day1]查询工资

重点就是分析一个点什么时候能被知道. 如果有兄弟一定不可知是显然的. 如果这个点子树大于 $k$, 那么直接用父亲子树减自己子树, 否则这个点子树大小不大于 $k$, 此时不能问这个点的子树信息, 那只能把子树删空变成叶子, 而父亲点就只有它一个儿子, 于是要用父亲的父亲点的子树减去所有儿子再减去其他儿子的子树.

分类完全, 考虑dp, $f_u$ 表示 $u$ 子树内的答案, 那么第一种转移显然, 若存在儿子 $v, siz_v>k$, $f_u=f_v+1$. 第二种转移一定是 $f=0$ 的点都弄成叶子(大小一定不大于 $k$, 而大于 $k$ 的一定有dp值), 留下一个子树大小为 $2$ 的点 $v$, 然后 $f_u=\sum f_v+1$.

D. [21 ZR联赛集训 day1]多项式题

听说联赛可以考多项式.

你有一个长度为 $n$ 的数字串, 你想把它划分成若干段(一整段也可以), 一共有 $2^n-1$ 种不同的划分.

你把每个子串看成一个十进制数字, 可以有前导0. 我们令一个划分的权值是所有子串的乘积.

输出所有划分权值的和, 对 $998244353$ 取模.

$n\le 2\times 10^5$

简单题, 直接dp.

Day2

A. [21 ZR联赛集训 day2]幻方

三阶幻方, 每次交换相邻两个数, 求最少次数

简单题, $9!$ 种记忆化去搜即可.

B. [21 ZR联赛集训 day2]数集

有一个集合 $S$, $q$ 次加入 $x$ 或询问 $\max_{y\in S} x \mathrm{op} y, \mathrm{op}\in {\mathrm{and}, \mathrm{or}, \mathrm{xor}}$
$q, x<2^20$

异或是字典树典题, 或操作相当于取反之后与再取反, 和与是一样的.

与的话, 高位到地位贪心, 相当于判定 $v$ 是否是 $S$ 中某一个元素的子集, 可以在插入的时候直接标记子集, 从大到小标记, 注意如果有个子集标记过了就不标记子集的子集, 复杂度是什么?

那就按照子集的枚举方式, 对一个集合, 先枚举删一个元素的, 如果被标记了就直接跳, 否则递归? 递归次数是 $O(V)$, 枚举次数是 $V\log V$, 非常好!

C. [21 ZR联赛集训 day2]染色

⼀棵树上有两个⿊点 , 其余都是⽩点.
接下来, 每过⼀个单位时间, 树上的每个⿊点可以选择⼀个它相邻的点染⿊.
请问, 在最优策略的情况下, ⾄少要经过多少个单位时间, 才能把整棵树染⿊
$n\le 3\times 10^5$

如果两个相邻是直接dp的简单题

现在两个不相邻, 就要考虑中间的链, 要确定链上两边染色的分界点, 这玩意单调的吧! 三分!

D. [21 ZR联赛集训 day2]电路板

一个电路板可以抽象为一个无向图, 图中每个点代表一个元件, 每条边代表一条导线. 每个元件 $a$ 有一个启动电压和一个功能属性 $b_j$. 当 $a_i \leq V$ ($V$ 代表整个电路的电压) 时, 这个元件将被激活. 激活的元件在原图中会形成若干个联通块(这里的联通块可以包含损坏的元件). 对于一个连通块 $A$, 我们说它包含功能属性 $p$, 当且仅当 $A$ 中存在元件满足 $b=p$, 且这样的元件的个数是 $k$ 的整数倍.

在激活的元件中, 有一些联通块包含了损坏的元件, 它们无法正常工作. 现在给出若干个询问, 每个询问包含电路的电压 $V$ 和损坏的元件集合 $S$, 你需要回答在这个条件下, 一个没有损坏元件的联通块, 最多包含了几种功能属性.

离线按 $V$ 排序, 启发式合并维护每个连通块里每个元素出现的次数. 开一个堆维护所有连通块的答案, 询问的时候, 删除包含禁用掉的连通块, 询问结束再插回去.

Day3

A. [zr联赛集训day3]史上最简洁的题面

直接dp, $f_{S}$ 表示点集 $S$ 的导出子图边数, 转移就考虑去掉 $S$ 最低位 $u$, 设 $u$ 的边集是 $e_u$, 那么加上 $\mathrm{popcount}(e_u\mathrm{and} S)$.

B. [zr联赛集训day3]史上第二简洁的题面

给定一个长度为 $n$ 的序列 $a$, 给定 $m$ 个询问 $(l, r, x)$, 求 $a_l, a_{l+1}, . . . , a_r$ 中有多少个数与 $x$ 互质.

$n, m, a_i, x\le 10^5$

容斥, 变成 $qd$ 次求是某个数倍数的个数, 预处理每个值的倍数的下标, 离线, 在这个数组上双指针.

复杂度为什么不是 $nd\ln n$ 呢? 因为容斥的时候只会用到 $\mu^2(x)=0$ 的数, 就能过了.

C. [zr联赛集训day3]史上第三简洁的题面

有 $n$ 个人排成一排, 从左到右编号为 $1. . . n$, 接下来你每次可以指定两个相邻的人战斗, 输的一方将会离开队伍, 直到最后只有一个人留在队伍里, 这个人将会称为最后的赢家. 你知道任意两个人打谁会赢, 求哪些人可能会成为最后的赢家.

$n\le 2000$

区间dp, $f_{l, r, i}$ 表示 $l, r$ 内打完了剩下一个 $i$ 是否可能. 则转移是 $f_{l, r, i}=f_{l, p, i}\mathrm{and} f_{p+1, r, j}\mathrm{and} s_{i, j}$ 以及反过来的. 复杂度是 $n^5$ 的爆炸.

考虑再维护 $g_{l, r, i}$ 表示 $[l, r]$ 内打完了剩下一个打不过 $i$ 的, 转移的时候用 $g$ 转移 $f$ 就只要枚举一个 $p$ 了, 变成了 $n^3$.

于是直接上个bitset就过了

D. [zr联赛集训day3]史上第四简洁的题面

考虑最短路树, 则如果被堵死的路不在最短路树上就没影响, 则是最短路上的一条边. 于是设 $u\to fa_u$ 被堵死后 $u$ 到 $v$ 时间为 $t_u$, 答案为 $f_u$, 则 $f_u=\max t_u, \min f_{a}+w_{u\to a}=\min (\max f_a+w_{u\to a}, t_u)$, 可以跑最短路, 问题就是如何求 $t$.

求 $t_u$ 时, 路径一定是 $u\to a(a\in subtree(u))\to b(b\notin subtree(u))\to v$, 也就是只会走一条非树边, 代价就是 $dep_b-dep_u+dep_a+w$, 要求 $a$ 在 $u$ 子树内, $b$ 在 $u$ 子树外, dfs序转化一下就是两个区间了.

然而直接上线段树会被卡常卡爆, 考虑枚举一条边, 那它能贡献的点是一条链(边里较深的点到lca的一个儿子), 那么按值从小到大枚举, 就成了把链上没被赋值过的赋成当前边的 $dep_a+dep_b+w$, 可以用并查集实现找下一个没被赋值的点的操作.