https://atcoder.jp/contests/abc306/tasks
n点,m有向边
从1开始，每次 从当前点选一条边移动，问$10^{10^{100}}$次时能否回到1
n,m 2e5
2s
1024mb
次数巨大，如果走k1次回到1，k2次回到1
那么可以 gcd(k1,k2)次的足够大的倍数回到1， 因为 问题中的次数巨大，所以 ak1+bk2=c gcd(k1,k2) = 10^{10^{100}}能找到正解
所以 问题是能否找到 两个不同的次数的 gcd 只有2和5的因子
一个不会证明的想法是，计算从1出发到达每个点的不超过2种 距离，和逆向从1倒退不超过2种距离
这样每个点 可以得到2x2种从1到1的距离
对所有距离做gcd看看是否只有 2和5的因子
但是这个做法，正确性 感觉不会证明
https://atcoder.jp/contests/abc305/tasks
N个问题, 难度(Ai,Bi)
选择$D \in [1,N]$天 完成所有N个问题，即把N个问题分成D个连续非空子区间
疲劳x 每天初始 = 0，每天完成当前的区间中的问题
区间内问题顺序可以任意调整，每次完成一个问题后 x_new = A x_old+B
给定X, 问 min D, 使得 sum x_每天结束<= X
输出 (min D, 对于 min D时最小的sum x_每天结束)
n 2e5
X 1e8
ai [1,1e5]
1<= bi
sum bi <= X
3s
1024mb
先说一天内，如果指定了区间
先i后j: $a_j(a_i x + b_i) + b_j$
先j后i: $a_i(a_j x + b_j) + b_i$
如果要 $a_j(a_i x + b_i) + b_j < a_i(a_j x + b_j) + b_i$
即 $a_j b_i + b_j < a_i b_j + b_i$
即 $(a_j-1) b_i < (a_i-1) b_j$
即 $\frac {a_j-1}{b_j} < \frac{a_i-1}{b_i}$
即每个元素 可以按照key = $-\frac{a-1}{b}$ 排序
反过来排序则是最大
问题其实变成对于给定D, 求min
对于min显然 随着D增加，min 单调递减，因为至少有一天两个问题，而后一个问题的额外代价 是 (Ax+B)-x = (A-1)x+B, 而单独放一天则是B, 而A>=1
有一个巨大的dp
dp[i][d] 以i结束，i前面划分了d天的 最小消耗
就是求 dp[n][min d] <= x
dp[i][d] = min(dp[j][d-1] + cost[j+1..i]), j<i
首先 状态就n^2,空间就n^2 ,转移看上去要n^2,时间就是n^4
先说能否降低到n^3, 也就是cost[i...j] 有没有什么快速的计算方法或者预处理
显然x=Ax+B可以用矩阵乘法表示
那么就可以用线段树按 上面 -(a-1)/b 的顺序 维护
一个区间就是区间内的变成 对应的矩阵，而区间外的 变成 单位矩阵
那么计算一个区间cost[i...j] 无非就是cost[i...j-1] 基础上让 j在线段树中对应的 变为对应矩阵再计算完整线段树的 矩阵乘法结果，
这样显然 循环 遍历i,j 能 n^2 log n 算出所有cost[i..j]
至少时间复杂度变成 n^3 + n^2 log n
感觉 还缺了什么数学性质
但对于相邻的两个区间，并不知道 相邻位置放在哪个区间好
因为并不知道 它 排序后的位置，
虽然可以 预估它放最前 和 最后的贡献变化，一个是预估，另一个是需要他前后的区间的信息
https://atcoder.jp/contests/abc304/tasks
给长2n的数组A,让元素配成n对，每对做xor得到长n的序列B
求 max(sorted(B)[n/2+1])
n 1e5
ai [0,2^30]
5s
1024mb
xor + max 常见思路从高位向低位贪心,
对于第b位
min(count 0, count 1) 就是能构成1 的方案数
如果 min >= n/2 +1, 那么 就是 从 b位是0和是1的分成两组，其中各选出一个，还需要对低位进行处理啊
如果 min < n/2+1, 那么就是b位无法成为1,那么0和1分成两组，这两组内部选两个排序
这两个都并不好处理，因为第n/2+1大在这过程中不光没有消掉，而且还会增加维度
https://atcoder.jp/contests/abc303/tasks
n包, i个x[i]钱
每次3选1
两人交替, 分别是X,Y, 求X-Y 的双方最优操作后的值，一个要最大，一个要最小
n 3000
xi,a,b,c,d, 1e9
2.5s
1024mb
如果没有后两种
那就是经典的dp[l][r] = 从当前开始最优差值
dp[l][r] = max(x[l] - dp[l+1][r], x[r] - dp[l][r-1])
现在多了两种批量的情况
例如其中第二个方案就是 x[l...i] + x[j...r] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B
但是注意到可以变换一下
x[l...r] - x[i+1..j-1] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B
令 ndp[i..j] = x[i..j] + dp[i..j]
dp[l..r] = max(x[l] - dp[l+1][r],x[r]-dp[l][r-1],x[l..r] - A/C - ndp[i+1..j-1])
不妨设 第一种是 支付E=0元，取得F=1个
dp[l..r] = x[l..r] - min(A/C/E + ndp[i+1..j-1,A/C/E])
因此 需要一个 能够快速查询
[l...r]区间内 A/C/E + min(ndp[len(l..r)-B/D/F]) 即可
minndp[l..r] 可以通过minndp[l-1..r-1] 维护小根堆转移得到
https://atcoder.jp/contests/abc302/tasks
n点树,无向边,点上 有 写有数字Ai的球 和写有数字Bi的球
令 v = 2..n 个独立问题
n 2e5
ai,bi [1,n]
2s
1024mb
考虑把1选做根
那么每次查询的就是 当前点到根的路径上每次 选一个数， 选出数字 max(distinct)
显然 ans[u] - ans[fa[u]] \in [0,1]
如果单次求， 就是做并查集， 对于是树的 贡献 = 边
对于 不是树的（边 >= 点) 贡献是点
听起来 需要一个 可持久化 并查集?
点+点 = 树(+1)
点+树 = 树(+1)
点+图 = 图(+1)
树+树 = 树(+1)
树+图 = 图(+1)
图+图 = 图(+0)
树内部 = 图(+1)
图内部 = 图(+0)