2023.03.23
倒数第五场模拟赛。
读题之后感觉第一题最好入手，第二题和第三题均是我不擅长的计数题。
算法讨论
gift
T1 简单构造，不难发现你可以拿可以拿来拼凑的二进制数形如:
- 100...001 (中间夹着偶数个0)
- 10...010...01 (中间夹着奇数个0)
最基本的形式就是 11 和 10101
那么对于无解条件的判断很显然。
如果只有一个 \(1\)，那没救。
如果只有两个 \(1\)，并且这两个 \(1\) 之间的距离还是奇数，没救。
无解条件仅有上面两条。
然后对于输出 \(1\) 的情况，就是原数是 \(3\) 的倍数
否则输出 \(2\)，乱构造一波，这题就过了。
mahjong
不会打正解，只讨论了没有顺子，即 \(m = 2\) 的情况。
bridge
关键在于同样的速度。这个东西意味着，一个人有可能在走下桥之前，跟若干个人撞一波。
不过可以有一点启发。但是我显然是不会做的。
时间分配
T1
预计时间：\(25min\)
预计得分：\(100pts\)
实际时间：\(2h\)
备注：原来那个变态代码太繁琐了，bug还一大堆没法调，换了个思路后代码清新简洁还容易码。
简而言之，我是nc。
T2
预计时间：\(5min\)
预计得分：\(2pts\)
如果没有顺子这种牌就能做了，太恶心了。
T3
预计时间：\(0min\)
预计得分：\(0pts\)
预计总得分：\(102pts\)
实际总得分：\(100pts\)
T2 挂了，不过名次还可以。
2023.03.24
倒数第四场模拟赛。
吉他 \((guitar)\)
算法讨论
直观感觉应该先突破第三个条件。
由于已经给出了整张图，因此我认为，直接暴力bfs，找到一条到点 \(T\) 长度最短的路径。
把这条路径上的所有边的编号排序，对于编号不是最大值的边，设其编号为 \(i\)，就将其边权也赋成 \(i\)，如果前面的总和加起来都大于 \(D\)，说明无解，否则赋一下边权。
但是这个做法是假的。
不过可以稍给我们一点启发。
首先由题可得，第 \(p_i\) 条边的边权至少为 \(i\)，先这样赋权值跑一遍最短路就可以判断是否有解。
考虑最短路接下来该怎么做。二分一个权值 \(w\)，给每条边都加上这个 \(w\)，使得 \(S\) 到 \(T\) 的最短路是小于等于 \(D\) 的最大值。
如果等于，皆大欢喜。
否则，我们就可以得到，如果在给所有边加 \(1\)， \(S\) 到 \(T\) 的最短路就会超过 \(D\),那么我们只能给一部分边加上 \(1\)，不然最短路无法恰好等于 \(D\)，有由于边的权值必须有单调性，再在 \(p\) 上二分一个位置，判断给这个位置及以后的每个点加上 \(1\) 以后，最短路是否等于 \(D\)。
正确性不保证，但反正有30了，这东西又不会T，不如写了说不定就A了。
其实是给部分边+1的操作让我们的正确性无法保证。设一个 \(pos\)，钦定只能在前 \(pos\) 条边上跑最短路，如果跑出来跟原图最短路相等，就说明我们把编号大于 \(pos\) 的边删掉也没有问题。放在本题中，就是赋个很大的权值。
二分 \(pos\) 即可。前面的二分也能够删去。至于二分的判断条件应当是大于 \(D\) 时扩大 \(pos\),而不是大于当前最短路时,因为这样可能会导致这样一个问题:\(pos\)过大,而次短路的权值也小于 \(D\),你更改 \(pos\) 时就会寄.
至于二分出 \(pos\) 我们应该怎么做?显然,把第 \(pos\) 边重新赋个权值,使得最短路刚好等于 \(D\).然后比 \(pos\) 编号小的边权值不变,大于的按照上面重新赋就是了.
预计时间：\(40min\)
预计得分：\(100pts\)
实际时间：\(2.5h\)
细节太多了。纯粹是因为我没有代码能力！太菜了！
孤独 \((bocchi)\)
不会，一个点可以由左右两边转移而来，太复杂了。
\(10\) 分走人。
蓝色星球 \((planet)\)
考虑 \(n = 1\)，\(5\) 分走人。
预计总得分：\(115pts\)
实际得分：\(105pts\)