2022ByteCamp网络预选赛¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 32/289 | 9 | 9 | 13 |
A¶
solved by JLK
题意¶
签到题，略
题解¶
B¶
solved by JLK
题意¶
签到题，略
题解¶
C¶
solved by JLK
题意¶
\(n\)个人打比赛，每个人有两个属性\(a_i,b_i\)，每次选择两个人，然后指定他们比较一个属性，属性高的人获胜。问对于每个人，是否存在一种比赛的方案，使得他能够赢下最终胜利。
\(1 \le n \le 10^5,1 \le a_i,b_i \le 10^9\)（\(a_i,b_i\)互不相同）
题解¶
由于存在间接赢下的情况，不能直接做判断。
但是只要A能赢B，B能赢C，那么存在一种方案让A赢过B和C。这本质上可以转化成：每个人向能够打败的人连边，最后形成一个有向图，强连通分量缩点之后必须是一条链，在链最上方的SCC里的人才能赢，其他人都不能赢。
优化连边，可以对每个\(a_i\)和\(b_i\)建点，然后向同一个属性的最大的小于它的点连边。这样总点数和边数是\(O(n)\)的。
需要排序，之后就是线性的做法。
\(O(n\log n)\)
D¶
solved by TYB
题意¶
有\(n\)个多米诺骨牌，两个面可以为黑色或白色。某些骨牌的一个或两个面已被涂色。求涂色的方案数，使得可以将\(n\)个骨牌排成一个环（顺序自定），相邻两个骨牌相对的两面颜色不同。
\(n\le10^5\)
题解¶
一种染色方案合法的充要条件为：1、WW和BB个数相等。2、若WB和BW的个数都不为\(0\)，则WW和BB的个数也不为\(0\)。考虑第一个条件，其实等价于W和B的个数都为\(n\)，这个方案数可以用组合数简单计算。再减去WW和BB的个数都为\(0\)的方案数即可。
E¶
solved by YZW
题意¶
题解¶
F¶
solved/upsolved by
题意¶
题解¶
G¶
solved by TYB & YZW
题意¶
交互题，你需要询问\(\le2\)次猜出\(n(1\le n\le10^5)\)，每次问一个\(k(1\le k\le4\times10^4)\)，得到\(n^n\%k\)的值。
多组数据，\(T\le5000\)。
题解¶
第一次可以用一个大质数（如\(39989\)）询问，然后可以根据得到的余数将\([1,10^5]\)的数分成若干类，显然每类不会有太多数，那么再用另外一个质数将这些数区分开即可。
H¶
solved/upsolved by
题意¶
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
solved by YZW
题意¶
题解¶
K¶
solved by TYB
题意¶
给一个\(n\)的排列\(p\)，定义\(F(p)\)为通过交换两数将\(p\)从小到大排序，所需的最小次数。再给出操作数\(k\)，你需要恰好\(k\)次交换两个不同的数，求操作完后\(F(p)\)的最小值和最大值。
\(2\le n\le10^5,0\le k\le10^9\)
题解¶
设开始时\(F(p)=x\)，若\(x-k\ge0\)，则\(F(p)\)的最小值为\(x-k\)，否则最小值和多余操作次数的奇偶性有关，若多余操作为奇数，最小值为\(1\)，否则为\(0\)。最大值同理。
L¶
solved/upsolved by
题意¶
题解¶
M¶
solved/upsolved by
题意¶
题解¶
记录¶
开局平稳签到ABCGIK，此时过去1h20min。
YZW说会F并给出D的一个重要结论，但TYB和JLK都没听懂F做法，YZW开始写F，TYB和JLK讨论D。
JLK说D可以卷积，TYB也觉得好像可以，没有仔细确认。
YZW写完过不了样例，发现理解错了题意，JLK写D，TYB和YZW讨论E。
YZW会了E。
JLK发现式子推错了，尝试修没修出来，YZW开始写E，TYB和JLK继续讨论D。
讨论发现原思路不好搞，尝试换了个思路后会了D，先换下YZW，AC(3:10)。
YZW写完E后WA了两次，肉眼查错后AC(3:40)。
然后看FHJ。
YZW说会了J，开始写，TYB和JLK看H。
发现H是个动态最小生成树，并找到了模板。
J一发AC(4:22)，JLK开始抄模板，但是TYB和JLK都搞错了复杂度，抄完后TLE，没时间优化，比赛结束。
总结¶
TYB：应该至少两人确认做法，这次中期两次假了，差点血崩。
Dirt¶
E(-2)