0%

2023-2024 ICPC, NERC, Northern Eurasia tutorial

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位存下来做也能过,或者手动矩阵乘法展开一下也能过。