2019 ICPC Asia-East Continent Final¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 24/? | 6 | 8 | 13 |
A¶
solved by YZW
题意¶
暴力的签到。
题解¶
略。
B¶
upsolved by YZW
题意¶
题解¶
C¶
solved by YZW
题意¶
定义 \(f^2 = f * f, f^n = f * f^{n-1}\)，给出 \(g\) 的前 \(n\) 项与正整数 \(k\)，在模 \(998244353\) 意义下求 \(f\) 满足 \(f^k=g\)。
保证 \(g(1)=1\)，\(n\leq 10^5\)。
题解¶
实际上只需要维护 \(f,f^2,\dots,f^{\log n}\)，组合数搞搞，\(g(n)\) 减去 \(<n\) 项对应 \(f^k(n)\) 的贡献再除以 \(k\) 就是 \(f(n)\) 了。
注意转移顺序，不然会变成傻逼。
\(O(n\log^2 n)\)
D¶
**upsolved by **
题意¶
题解¶
E¶
solved by JLK
题意¶
\(n\)个点\(m\)条边的有向图，边有流量，这个图由\(k\)条从\(1\)到\(n\)的相同长度的路径组成。做若干次操作，每次可以把一条正数流量的边的一个流量转移到另一条边。求达到最大的最大流的情况下，最少的操作次数。
\(2 \le n \le 10^5,1 \le m \le 10^5\)
题解¶
首先把这些路径找出来。
最大流肯定是把每条路径上的边的流量尽可能变成一样的。最大的最大流数值实际上可以除一下算出来。
一次操作就是把大的转移到小的，不妨只计算把小的增加的次数。假设把一条路径上的流量都变成\(a\)，那么代价就是\(\sum\max\{0,a-c_i\}\)。随着\(a\)增加，每次的操作增量也不断增加，是一个分段函数。
把每条路径一起考虑，每次取操作增量最小的路径增加操作，直到满足最大流即可。
由于流量可能很大，实际上一次调整可以直接批量处理到分段函数的下一个转折点。这段区间内都是最优的。
\(O(m\log m)\)
F¶
**upsolved by **
题意¶
题解¶
G¶
solved by JLK
题意¶
模拟题，略
题解¶
H¶
solved by TYB
题意¶
给出长度为\(n\)的序列\(a\)和一个质数\(p\)，找一个\(a\)的最长的子序列\(b\)，使得存在一个整数\(q\in[1,p)\)，满足\(b\)为模\(p\)意义下公比为\(q\)的等比数列。若\(b\)的长度\(<\frac{n}{2}\)，输出\(-1\)，否则输出其长度。
\(n\le2\times10^5,2\le p\le 10^9+7\)
题解¶
如果\(b\)的长度\(\ge\frac{n}{2}\)，由鸽巢原理，\(q\)一定为某个\(\frac{a_{i+1}}{a_i}\)或者\(\frac{a_{i+2}}{a_i}\)，这样的\(q\)有\(2n\)个。考虑一个长度\(len\ge\frac{n}{2}\)的\(b\)，设其为\(a_{p_1},a_{p_2},\dots,a_{p_{len}}\)，显然\(p_i-p_{i-1}\le2\)的\(i\)占了至少一半，也就是在所有可能的\(2n\)个数中，\(q\)的出现次数下界为\(\frac{n}{4}\)左右。这样满足条件的数不会太多，直接check即可。
I¶
**upsolved by **
题意¶
题解¶
J¶
upsolved by TYB
题意¶
给出长度为\(n\)的排列\(p\)和\(c\)，可以任意次进行两种操作：
1、选择一个\(l\le n-c\)，若\(p_l\)为区间\([l,l+c]\)的最小值，任意排列区间\([l+1,l+c]\)的数。
2、选择一个\(l\ge c+1\)，若\(p_l\)为区间\([l-c,l]\)的最小值，任意排列区间\([l-c,l-1]\)的数。
求能够得到多少种可能的排列。
\(n\le5\times10^5\)
题解¶
一个很显然的想法，找到最小值的位置，两边独立，分治下去处理。但这个最小值对两边是有影响的，即其左右的\(c\)个数都可以随意排列。所以不妨将分治的状态设为：\(solve(l,r,x,y)\)表示\([l,r]\)这个区间，左边\(x\)个和右边\(y\)个可以自由排列的方案数。
依然找到最小值的位置，分情况讨论。
若最小值不在可以自由排列的区间内，那么其位置依然固定，直接分治即可；
否则，不妨假设最小值的位置\(p\)在左边\(x\)个的区间中。那么我们可以把这个最小值移到\(l+x-1\)这个位置，然后再任意排列其右边的\(c\)个数。感受一下可以发现，这等价于：\([l,l+x+c-1]\)区间内除最小值的数以外，可以自由移动，而最小值只能在\([l,l+x-1]\)这个区间内自由移动。这就相当于，删掉这个最小值，\(x+=c\)后，再处理这个区间。
那么我们需要：删除一个数，查询区间最小值，单点加，区间求和（后两个用于查询区间没被删掉的数的个数）。线段树即可（注意常数）。
K¶
**upsolved by **
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
solved by YZW
题意¶
略微没那么暴力但是还是比较暴力的签到。
题解¶
略。
记录¶
YZW过A(0:04)，M(0:28)。JLK过E(0:55)。
TYB写H，WA一次后AC(1:20)。
YZW写C，WA一次RE一次后AC(1:50)。
JLK开始写大模拟题G，YZW和TYB看BJ。
G WA两次后AC(3:04)。
一起看B，没什么思路。后来YZW对B打表，JLK和TYB讨论J。
J找到了个看起来可行的写法，TYB开始写。
写到一半YZW感觉找到规律了，然后WA了一次B。
J本地测过交上去直接TLE，卡常失败。B又喂了两发WA。
赛后两题马上都过了。。
总结¶
JLK：确实最后不应该双开
TYB：改线段树写法，准备个zkw线段树的板子
YZW：打表不要写错暴力！！！
Dirt¶
C(-2)
G(-2)
H(-1)