2023-2024 ICPC, NERC, Northern Eurasia Onsite
G
答案为 \(\sum \min\{pre_i,suf_i\}-a_i\) ,其中 \(pre_i,suf_i\) 表示前缀后缀最大值。发现每次区间加1的时候, \(pre_i,suf_i\) 同样最多也有一段区间加1,于是线段树二分找到这个区间,维护一下贡献即可,为便于处理,我实际上求的是 \(\sum suf_i + \sum \min\{pre_i-suf_i,0\}-\sum a_i\) ,线段树上二分 \(0\) 的位置即可求出该式。
H
考虑每个弱连通块,若无环则做法显然。考虑有环的时候,若存在一个方案,则必存在一个包含所有点的环的方案,我们可以枚举环方案中最后到达的点 \(u\) ,将所有目的地为 \(u\) 的移动先忽略,如果忽略后图无环,则显然有解,否则无解。
J
给定 \(a,b,c\) ,求满足 \(ax+by+cz=N\) 的三元组 \((x,y,z)\) 数量, \(N\le 10^9,a,b,c \le 16\) 。
考虑取 \(x^*=x\bmod c,y^*=y\bmod c\) ,则原式为
\[ (x^*+\hat{x}c)a+(y^*+\hat{y}c)b+cz=N \]
则有
\[ z=\frac{N-x^*a-y^*b}{c}-(\hat{x}a+\hat{y}b) \]
令 \(z^*=\frac{N-x^*a-y^*b}{c}\) ,则 \((x,y,z)=(x^*+\hat{x}c,y^*+\hat{y}c,z^*-(\hat{x}a+\hat{y}b))\) ,其中 \(\hat{x},\hat{y} \ge 0\) ,枚举 \(x^*,y^*\) 后,其等价于求满足 \(\hat{x}a+\hat{y}b \le z^*\) 的 \((\hat{x},\hat{y})\) 数量,用类欧求出即可,总复杂度 \(P(c^2\log N)\) 。
或再进行进一步转化,令 \(p^*=\hat{x}\bmod b\) ,有 \((p^*+\hat{p}b)a+\hat{y}b\le z^*\) 等价于 \(\hat{p}a+\hat{y} \le \frac{z^*-p^*a}{b}\) ,该式可直接求出,总复杂度为 \(O(bc^2)\) 。
另解:
本题即求 \([x^N]\frac{1}{(1-x^a)(1-x^b)(1-x^c)}\) ,有结论 \(f_n=\sum_{i>0}-f_{n-i}\cdot [x^i]P(x)\) ,其中 \(P(x)=(1-x^a)(1-x^b)(1-x^c)\) ,做矩乘即可,本题直接矩乘会T,把非0位存下来做也能过,或者手动矩阵乘法展开一下也能过。