2022-2023 BUAA XCPC Team Supplementary Training 01¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 2/16 | 6 | 7 | 10 |
A¶
solved by JLK
题意¶
给定\(A,B\)，可以进行下列四个操作不超过5000次，要求最后\(A=B\)，求一种方案。
- \(A\)+=\(A\)
- \(A\)+=\(B\)
- \(B\)+=\(A\)
- \(B\)+=\(B\)
\(1 \le A,B \le 10^{18}\)
题解¶
首先在任意时刻都可以把\(A,B\)同时除以它们的gcd，这是等价的。因为操作只会有加法，完全可以把gcd这部分拆出来，这部分始终不变，是不影响结果的。
那么只需要考虑两种情况：一个奇数一个偶数，和两个奇数。
前者，直接把奇数乘2之后同除以gcd，相当于让偶数减少一半。
后者，设小的为\(A\)，大的为\(B\)，执行操作\(B\)+=\(A\)和\(A\)+=\(A\)。之后继续同除以2，相当于让它们的差减少一半。
在经过若干次之后，一定会变成\(A=B=1\)，也就是两者相同。操作的次数是\(O(\log A)\)级别的。
B¶
**upsolved by **
题意¶
题解¶
C¶
upsolved by JLK
题意¶
给定一棵仙人掌，求邻接矩阵的行列式。
\(1 \le n \le 5\times 10^4,1 \le m \le 2.5\times 10^5\)
题解¶
考虑行列式的图论意义。
对于某个排列\(p\)，要产生贡献肯定是\(i,p_i\)之间有边。而按排列连边会构成若干个环。相当于是用若干个环来覆盖整个仙人掌（二元环也算）。
考虑一种覆盖的贡献。首先对于每个非二元的环，连边可以全部反向达到一样的效果，也就是说一个非二元环可以对应两个排列，所以总共对应2的（非二元环数量）次方个排列。
然后就是看排列的逆序数奇偶性。环和环之间是没有影响的，因为实际上矩阵可以交换任意两行两列而行列式不变，那么就可以把一个环全放在一起（看成编号连续的一段），交换完再放回去。并且可以把每个环都交换成\(2,3,\cdots,n,1\)的形式，这样看逆序数就很显然了。简单来说就是偶环会改变奇偶性，而奇环不会。贡献是\(-1\)的（偶环数，包括二元环）次方。
现在每个环的贡献清楚了，可以在仙人掌产生的圆方树上dp。\(dp_{i,0/1}\)表示子树内全部覆盖，\(i\)是否已经被覆盖的贡献（也就是有没有被选过）。定义方点被选了代表父亲的圆点被选了。
对于一个环（方点），要么所有点都不选，自己成环，要么所有点都选，或者选一些点，剩下的相邻两两成二元环。要注意父亲的圆点和环上邻接的点也可以成二元环。需要分类讨论一下。
对于一个圆点，它没被选需要它邻接的方点都没被选，而它被选需要恰好有一个方点选了，其他都没选。
\(O(n+m)\)
D¶
**upsolved by **
题意¶
题解¶
E¶
solved by TYB
题意¶
\(2N\)道菜，第\(i\)道菜作为午餐花费\(L_i\)，作为晚餐花费\(D_i\)，假设每天只需要吃午餐和晚餐，每道菜只能作为午餐或晚餐吃一次，求\(\forall i\in[1,N]\)，吃\(i\)天的最小花费。
\(N\le2.5\times10^5\)
题解¶
反悔贪心/模拟费用流。
午餐的决策实际上只有两种：选一道菜作为午餐，或者让之前是晚餐的菜变为午餐，再选一道菜作为晚餐。晚餐同理。堆维护一下即可。
F¶
solved by TYB
题意¶
树上绝对众数。
题解¶
摩尔投票法。
G¶
**upsolved by **
题意¶
题解¶
H¶
solved by JLK
题意¶
给定一棵以\(1\)为根，\(n\)个点的树，每个点有权值\(A_i,B_i,C_i\)。满足\(C_1=10^9,B_{parent(x)}\le B_x\)。
\(q\)次询问，每次询问\(1\)到\(V\)的路径上\(C_i\ge T\)的\(i\)当中，\(A_i+B_i\times T\)的最小值。
\(1 \le n \le 8\times 10^4,1 \le q \le 1.6\times 10^5,1 \le A_i,B_i,C_i \le 10^9,0 \le T \le 10^9\)。
题解¶
一眼可持久化李超树。每个点相当于是\([0,C_i]\)这个区间加入一条\(y=B_i \times x+A_i\)的线段。询问的又是到根的路径上所有点，所以可持久化李超树即可维护。
\(O(n\log ^2n+q\log n)\)
I¶
solved by YZW
题意¶
题解¶
J¶
solved by JLK
题意¶
\(n-1\)个学生，每个人有\(n\)朵花，要送给\(n\)个老师，每个老师要收到\(n-1\)朵花。
给出\(m\)个关系，只有这\(m\)个关系的学生和老师才能送若干朵花。
求合法方案。
\(2 \le n \le 10^5,1 \le m \le 2\times 10^5\)
题解¶
暴力flow肯定寄。
首先可以跑一遍流量为1的最大流，也就是二分图匹配。如果匹配不是\(n-1\)，那么肯定无解。
匹配完之后相当于有\(n-1\)对关系，每个学生给老师\(n-1\)朵花，还剩下一个老师。考虑把这个老师加进去。
如果能够构造出一个树形结构，就是以剩下的老师为根，连边到学生，学生只连已经匹配到的老师，老师再连学生……在这样的树形结构下，是一定有解的，可以把流量从叶子往根逐步推上去，最后能满足根的需求。
现在问题就是，如果不能构造出这样的树形结构，是否一定无解。因为现在是老师选择学生，如果一个学生连不进来这棵树，说明这个学生只有一条连向已经匹配的老师的边，那么必然无法消耗掉这多的一个流量，一定无解。
所以就是跑一遍最大匹配，然后建树，算答案即可。
\(O(m\sqrt n +m)\)
记录¶
TYB写F，JLK和YZW讨论A。
TYB过F(1:04)，JLK过A(1:15)。
TYB发现E和牛客某题有点像，开始写E并AC(1:42)。
JLK写H，RE一次后AC(2:15)。
然后一起看I，感觉也有点像之前做过的题，YZW开始写。
YZW过I(3:02)。
还剩下J比较可做，但是没什么想法。JLK想到先跑一遍流量为1的最大匹配优化暴力，结果TLE。
TYB又想到连成一棵树，结合一下就过了(4:38)。然后下班。
总结¶
Dirt¶
H(-1)：线段树写炸了
J(-1)：试了一发暴力