2022-2023 BUAA XCPC Team Supplementary Training 03¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 8/14 | 4 | 5 | 10 |
A¶
upsolved by
题意¶
题解¶
B¶
solved by TYB
题意¶
签到。
题解¶
略。
C¶
**upsolved by **
题意¶
题解¶
D¶
**upsolved by **
题意¶
题解¶
E¶
upsolved by TYB
题意¶
对于\(k\in[2,n+1]\)，求\((a_1\mod k)\oplus(a_2\mod k)\oplus\cdots\oplus(a_n\mod k)\)。
\(1\le a_i\le n\le5\times10^5\)
题解¶
奇妙的DP。
预处理\(f_{i,j}\)表示\(x\ge i\)且\(x-i\)的第\(j\)位为\(1\)的\(x\)的个数的奇偶性。
\(f_{i,j}=f_{i+2^{j+1},j}\oplus[i+2^j,i+2^{j+1})区间的奇偶性\)。含义是将区间分成两部分，\([i,i+2^{j+1})\)和\([i+2^{j+1},+\infty)\)，前者只有\([i+2^j,i+2^{j+1})\)内的数合法，后者可以利用\(f_{i+2^{j+1},j}\)的信息，因为它们\(0\)到\(j\)位是一样的。
对于每个\(k\)，枚举其倍数，那么问题转化为求\([l,l+k)\)区间内的数减去\(l\)后的异或和。按位考虑，对于第\(j\)位，同样将贡献分为两部分：令\(t=l+((k>>(j+1))<<(j+1))\)，即将其\(0\)到\(j\)位清零，则\([l,t)\)区间的贡献为\(f_{l,j}\oplus f_{t,j}\)（跟上面一个道理），而\([t,l+k)\)区间的贡献为\([t+2^j,t+2^{j+1})\)内的奇偶性。
F¶
solved by JLK
题意¶
两个人打怪兽，每个怪兽有\(h_i\)血量。A的攻击力是\(a\)，B的攻击力是\(b\)。A每次任意选择一个怪兽打（可以不动），但B每次只会选编号最小的还活着的怪兽打。
问A最多能抢到几个人头。
\(1 \le n \le 3\times 10^5,1 \le a,b,h_i \le 10^9\)
题解¶
可以稍微抽象一下。对于每个怪兽，如果A不想抢人头，就会一直让B打，在自己的回合打后面的或者不动。肯定是尽可能让B操作更多次，这样A才有更多的自由操作的空间。
那么每个怪兽有两种情况，要么A打死，要么B打死，每种情况对应的A和B分别的攻击次数是确定的（A让自己的攻击次数尽量少，也就是B的攻击次数尽量多）。如果选择A打死，那么分数+1，否则不变。
现在要选定一些怪兽让A打死，其余的B打死，并且要满足每个怪兽打完之后A的攻击次数不超过B的次数+1。在这样的情况下使得A打死尽量多。
可以使用回撤贪心。A能打死就打死，操作次数不够的情况下考虑回撤。既然次数不够，那么这次分数肯定不能增加，但是可以通过调整让后面的可操作次数更多。
可以把前面某个怪兽让B打死，当前怪兽让A打死。如果这样会让A的操作次数更多，就把前面的撤回，改完之后再把新的加进去。用一个set维护差值，反正就是回撤贪心的模板。
\(O(n\log n)\)。
G¶
**upsolved by **
题意¶
题解¶
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
solved by JLK
题意¶
给一个无向简单图，要把每条边赋值为\([0,4]\)中的整数，使得每个点周围的边权之和为5的倍数。
\(1 \le n\le 2\times 10^5,0 \le m \le 3\times 10^5\)。
题解¶
如果只有一棵树，显然只有一种（全0）。
只有环才有可能有多种方法。对于偶环，可以交错赋值，使得每个点的边权和都是0，有5种方法。对于奇环，只考虑自己的情况下是只有全0的情况，但是两个奇环连在一起的时候也是可以有5种方法。
不同环之间实际上是没有影响的，每个环相当于是自己对每个边有一个赋值。而对于环的交里的边，可以看做是若干个环在上面的赋值之和，所有点的边权和仍然是0。
那么可以找到本质不同（线性无关？）的环组，答案就是5的若干次方。
对每个连通块考虑，先建一个dfs树，偶环肯定有一个5的贡献。对于奇环，实际上可以两两组合成树形结构，使得相邻两个奇环可以看做是一个偶环。即贡献为奇环个数-1。
每个连通块数一下非树边构成的环的个数即可。
\(O(n+m)\)
记录¶
YZW过I(0:16)。TYB过B(0:33)。
TYB推出了E的式子，但是不会算。
一起看J，JLK分析了一波开始写，然后WA了。改了几次之后过了(2:20)。
然后坐牢，CEH都不太会。TYB一开始觉得C可写，写一半被JLK叉掉了。
JLK看F，分析了一波开始写，然后又寄了，改了几次之后过了(4:08)。
最后一起看H，没有想法。JLK想到C一个改进的写法，但是比较麻烦，不写。
总结¶
Dirt¶
J(-3)
F(-4)