2022-2023 BUAA XCPC Team Supplementary Training 02¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 4/17 | 9 | 12 | 12 |
A¶
solved by YZW
题意¶
题解¶
B¶
solved by TYB
题意¶
给出一个由空格和字母组成的句子，对于\(\forall i\in[l,r]\)，求若排版时每行长度为\(i\)，每行第一个单词长度之和。排版就是单词间有一个空格间隔，当前这行长度不够就开下一行。
所有都\(\le5\times10^5\)
题解¶
暴力，每次跳一行，因为总行数是\(n\ln(n)\)级别的。
C¶
upsolved by YZW
题意¶
题解¶
D¶
solved by JLK
题意¶
给一个长度为\(n\)的数字串，问多少种划分使得每一连续段都是\(m\)的倍数。
\(1 \le n \le 3\times 10^5,1 \le m \le 10^6\)
题解¶
从前往后考虑，每个点可以作为分界点的充要条件是，它前缀的数是\(m\)的倍数。
假设有两个点\(i,j\)都能作为分界点，满足\(m \mid sum_i,m\mid sum_j,i \lt j\)。
那么如果两个点都切开， 后面一段的值为\(sum_j-sum_i\times 10^{j-i}\)。仍然是\(m\)的倍数。所以找到这些分界点之后任意划分就行，也就是\(2^s\)种方案。
而最后一个点是必须要划分的，不满足则无解。同时最后一个点也不是任意选，不算在\(s\)里。
\(O(n)\)
E¶
solved by JLK
题意¶
\(n\)个点\(m\)条边的无向图，边有权值。\(q\)次询问，每次询问一个\(t\)，删去小于\(t\)的边，然后把图中孤立点删掉，有恰好两条边而且不是自环的点删掉而把两条边对面的点连起来。不断进行这个操作，问最后有多少个点，多少条边。
每次询问独立。
\(1 \le n,m,q \le 3\times 10^5\)
题解¶
考虑这个删点是怎么操作的。度数为\(2\)的点会被删掉，而度数为\(1\)或者大于\(2\)的都会保留。单独的一个环除外，它会产生一个有自环的点。
去掉所有环之后，答案的点数就是度数不为\(0\)和\(2\)的点，边数就是这些点数加起来除\(2\)。每个环又会同时贡献\(1\)的点数和边数，两者相加即可。
可以离线从大到小加边然后回答询问，用并查集维护，需要维护每个连通块的siz和度数为\(2\)的点，还要实时维护答案。
\(O((m+q)\log (m+q))\)（需要排序）
F¶
solved by JLK
题意¶
\(n\times n\)的数组\(F\)。给定\(l,t,a,b,c\)，\(F\)按下列方式构造。
-
\(F_{k,1}=l_k\)
-
\(F_{1,k}=t_k\)
-
\(F_{i,j}=a\times F_{i,j-1}+b\times F_{i-1,j}+c\)
求\(F_{n,n}\)。
\(2 \le n \le 2\times 10^5\)。
题解¶
先不管\(c\)，考虑\(l\)和\(t\)的贡献。
本质上就是往右和往下走，往右则乘\(a\)，往下则乘\(b\)。
以\(l\)为例，\(F_{1,1}=l_1\)是没有贡献，然后对于每个\(F_{k,1}=l_k\)，第一步必须往右，而第二步之后是任意的。总贡献是\(l_k\times b\times C_{R+D}^D a^R b^D\)。其中\(R=n-2,D=n-k\)。
然后考虑\(c\)。总贡献是\(\sum\limits_{i=2}^n \sum\limits_{j=2}^n c\times C_{n-i+n-j}^{n-i} a^{n-j} b^{n-i}\)。
令\(i=n-i,j=n-j\)。有\(\sum\limits_{i=0}^{n-2} \sum\limits_{j=0}^{n-2} c\times C_{i+j}^{i} a^{j} b^{i}\)。
这个实际上可以考虑一行一行或者一列一列转移。
令\(S_i=\sum\limits_{j=0}^{n-2} C_{i+j}^{j} a^{j}\)
\(S_{i+1}=\sum\limits_{j=0}^{n-2} \times C_{i+j+1}^{j} a^{j}=\sum\limits_{j=0}^{n-2} (C_{i+j}^{j}+C_{i+j+1}^{j-1}) a^{j}=S_{i}+aS_{i+1}-a^{n-1}C_{i+1+n-2}^{n-2}\)。
求出\(S_0\)之后递推即可。
\(O(n)\)
G¶
upsolved by TYB
题意¶
\(n\)朵花，第\(i\)朵高度\(h_i\)，有\(m\)天，每天太阳在左边或者右边，如果在左边，从左到右依次看每朵花，若其左边的花比它高，那么其高度\(+1\)，在右边也类似，求最后每朵花的高度。
\(n,m\le3\times10^5,0\le h_i\le10^9\)
题解¶
可以发现，当相邻的两朵花高度变成一样后，之后他们的高度也会一样，所以可以把连续一段相同高度的花合并成一段。若一段时间内没有花发生合并，那么时间段内每段花如何生长是固定的。可以用链表维护，每天只处理那些会合并的段，合并后再重新计算下次发生合并的时间即可。
复杂度线性。
H¶
solved by YZW
题意¶
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
solved by TYB
题意¶
\(n\)个点\(m\)条边的无向图，每个点度数至多为\(3\)，每条边流量为\(1\)，求\(\sum_{i<j}\rm{maxflow}(i,j)\)。
\(n\le3000,m\le4500\)
题解¶
只有\(0、1、2、3\)四种情况。
\(0\)就是不连通，\(1\)就是连通但不在一个边双，\(\ge2\)就是在同一个边双，考虑怎么区分\(2、3\)。
结论：尝试删掉每条边，若删掉每条边后都在同一个边双就是\(3\)。必要性显然，充分性的话可以从最小割的角度考虑，这种情况说明最小割是\(3\)，所以最大流就是\(3\)。
K¶
solved by YZW
题意¶
题解¶
L¶
upsolved by JLK
题意¶
给一个\(n\times m\)的迷宫，上下左右无限复制，成为一个无穷的迷宫。\(q\)次询问，每次询问从\((0,0)\)出发是否能到达某个点。
\(1 \le n,m \le 100,1 \le q \le 2\times 10^5\)
题解¶
其实本质上只有三种情况。
- 只能到达一个封闭的连通块
- 可以沿一个方向一直走
- 所有点都可以到达（除了被封闭住的点）
题解的做法是bfs \(10^6\)次，如果停止了就是情况1，如果没停止就要讨论一下。
如果可以到达\((n,0)\)和\((m,0)\)，就是情况3，否则是情况2。
感觉有点玄学，找了另一个做法。
首先把每个坐标可以分成块坐标和块内坐标\((x,y)=(a\times n+c,b\times m+d)\)。记为\((a,b,c,d)\)。
有这几个性质：
- 若\((a,b,0,0)\leftrightarrow (0,0,0,0)\)，则\(\forall \lambda,(a,b,0,0)\leftrightarrow (\lambda a,\lambda b,0,0)\)
- 若\((a_1,b_1,0,0)\leftrightarrow (0,0,0,0) \leftrightarrow (a_2,b_2,0,0)\)，则\(\forall \lambda,\mu,(\lambda a_1+\mu a_2,\lambda b_1+\mu b_2,0,0)\leftrightarrow (0,0,0,0)\)
- 若\((a,b,0,0)\leftrightarrow (\lambda a,\lambda b,0,0)\)，则\((a,b,0,0) \leftrightarrow (0,0,0,0)\)
稍微证明一下最后一个，先把路径扩展到无穷长，然后可以把路径从\((\lambda a,\lambda b,0,0)\)平移到\((a,b,0,0)\)。此时如果相交，那么显然可以从\((0,0,0,0)\)到达\((a,b,0,0)\)。
如果不相交，不妨设\((a,b,0,0)\)的路径完全在\((0,0,0,0)\)的路径的上方。同样地，考虑\((a,b,0,0)\leftrightarrow (a+\lambda a,b+\lambda b,0,0)\)的同样的路径，可以得到\((2a,2b,0,0)\)的路径在\((a,b,0,0)\)的路径上方。最后可以得到\((\lambda a,\lambda b,0,0)\)的路径在\((0,0,0,0)\)的路径上方。但是这两个路径是完全一样的，所以假设寄了。
因此一定相交。也就是一定能从\((0,0,0,0)\)到\((a,b,0,0)\)。
得到了这些性质之后，发现实际上最后的可达情况可以用方向向量来表示。
- 没有方向向量 也就是只有一个封闭图形。直接bfs就可以搜出来。
- 有一个方向向量\((u,v),\gcd(u,v)=1\) 那么从原点bfs，只要能到\((a,b,c,d)\)，就能到\((a+\lambda u,b+\lambda v,c,d)\)。而在这种情况下对于某个\((a,b,c,d)\)，\(a,b\)肯定都在这条直线上。也就是只有这一条直线，可以直接判断。
- 有两个及以上不同的方向向量 那么任何一个\((a,b,0,0)\)都可以到达。只要一开始bfs能到达某个\((*,*,c,d)\)即可。
问题是如何求解这个方向向量。从原点开始bfs，限制每个\((*,*,c,d)\)只能被加入队列一次。如果在不同块里访问了多次，就和上一次访问的块坐标作差，找到了方向向量。这样复杂度是\(O(nm)\)。
但是只找\(nm\)个点能把所有可能的方向向量都找出来吗？感性理解一下就是，bfs会往可能的方向都进行扩展，所以能找到所有可能的方向向量。
记录¶
YZW过A(0:14)。
JLK写D，发现想错了，卡了一会。最后三个人一起讨论才写出来(0:42)。
YZW写K，WA了两次，没找到错先扔了。
TYB猜了个J的结论，WA了。
YZW找到K的bug，改对了(2:10)。
JLK写F，写完发现式子有点问题，TYB先写B。
F推出了正确的式子，然后过了(2:53)。
TYB过B(2:56)。
YZW过H(3:17)。
JLK写E，WA一次后AC(3:43)。
TYB又猜了一发结论，WA一次后AC(3:55)。
YZW写I，WA一次后AC(4:30)。
然后就没啥想法了。
总结¶
JLK：简单题卡住的时候直接一起看比较好。
Dirt¶
E(-1)
I(-1)：整除！！！
J(-2)：清空！！！
K(-2)