21 2024.7.14
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(100\) | \(10\) | \(100\) | \(0\) | \(210\) |
排名：rank \(2\)。
2 题解
T1
考虑到原先距离 \(2\) 的现在变为距离 \(1\)，那么记原先两点间距离为 \(D(i,j)\)，那么答案其实就是：
\[\sum_{i=1}^n\sum_{j=i+1}^n \lceil\dfrac{D(i,j)}{2}\rceil \]那么这其实就牵扯到距离之间奇偶性的问题，考虑到还要计算距离和，采用树形 dp 的方式。考虑到还需要计算任意两点间距离，考虑以每个点为根计算一边答案，于是想到 up and down。
那么记录下四个信息：到自己距离为偶数的距离之和、到自己距离为奇数的距离之和，到自己距离为偶数的点的个数、到自己距离为奇数的点的个数。暴力树形 dp 即可。
转移方程并不难想，这里就不给了。
T2
看到异或值最大，不难想到利用 01-Trie 求解。现在问题在于前两个性质。首先简单的是第一个性质，其实质就是 \(v\le s-x\)，我们在 01-Trie 上贪心求解异或最大值的时候判断一下当前数字的值是否在范围内即可。
现在考虑第二个性质，不难发现其实质就是 \(k\mid v\) 且 \(k\mid x\)。后一个条件我们特判即可，至于前一个条件，考虑对于所有的 \(k\) 建立一颗 01-Trie，上面存储 \(k\) 的所有倍数，这样我们在对应的 01-Trie 上求解即可。
如果担心爆空间还可以使用根号分治，对于 \(k\ge 300\) 的部分暴力求 \(k\) 的倍数，剩下的建 01-Trie 求解。
T3
看到要求最小油箱容量满足所有要求，想到二分答案。我们对于每一次行程都二分一次，然后取最大值即可。check 函数直接贪心即可，可以利用二分查找优化一些。
现在的复杂度是 \(O(nm\log V)\) 的，其实比较危险，我们考虑如何优化复杂度。首先，如果当前求出的最大值已经可以满足当前的行程需求就不必再二分了。也就是说，我们二分的次数其实就是前缀最大值的个数。
考虑一个结论：对于一个随机序列，前缀最大值的个数是 \(O(\log n)\) 级别的。因此我们可以使用一种骚操作：对于原先的序列进行 random_shuffle，这样前缀最大值的个数就是 \(O(\log m)\) 级别的，复杂度就降至 \(O(n\log m\log V)\)，可以通过。
T4
炒鸡大码力题。
首先我们必须要知道，如果存在方案，一定是每个人按照一定的顺序从起点不停的走向终点。我们要考虑的其实就是走的顺序。
考虑两个囚犯路径会直接产生冲突的情况，发现不好直接进行判断。我们考虑反向判断必须要满足的条件，看条件之间两两是否互不冲突即可。
容易观察到如下性质：
- 如果 \(A\) 的终点在 \(B\) 的路径上，则 \(B\) 一定要先于 \(A\) 走。
- 如果 \(A\) 的起点在 \(B\) 的路径上，则 \(A\) 一定要先于 \(B\) 走。
现在如果 \(A\) 要先于 \(B\) 走，我们就连边 \(A\to B\)；如果出现环，则一定不存在合法方案，否则一定存在。这个可以用拓扑排序简单求解。
现在的新问题是，如果暴力连边，那么复杂度是 \(O(n^2)\) 的，显然无法通过。我们考虑连边的实质，对于一个囚犯 \(i\)，其路径为 \((s_i,t_i)\)，则所有起点在该路径上的囚犯都要向 \(i\) 连边；同理，该囚犯 \(i\) 应该向所有终点在该路径上的囚犯连边。
容易发现条件中起点和终点的条件是分开的，我们建两棵树 \(S,T\)，分别存储每个囚犯路径的起点和终点。根据上面的分析，在 \(S\) 树上路径 \((s_i,t_i)\) 的所有点要向 \(i\) 连边，\(i\) 要向 \(T\) 树上路径 \((s_i,t_i)\) 的所有点连边。为了能够转移限制条件，还需要从囚犯 \(i\) 的终点向 \(i\) 连边，\(i\) 向囚犯 \(i\) 的起点连边。
此时我们发现，连出的边在树上都是连续的一段，想到通过线段树优化建图的方式进行区间和单点之间的连边。而此时的区间是在树上的，不难想到利用树链剖分进行连边。
连完边之后就可以跑拓扑排序找环了，复杂度为 \(O(n\log^2 n)\)。剩下的就全是细节了。
3 挂分
- T2 01-Trie 写假，\(100\to 10\)。
22 2024.7.15
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(100\) | \(62\) | \(60\) | \(20\) | \(242\) |
排名：rank \(4\)。
2 题解
T1
我们以 < 开头举例，不难发现其行走的路径是一段左右横跳的路径，即走到左侧第一个 >，掉头走到右侧第一个 <，接着再掉头走到左侧第二个 >……。我们设右边的 < 的位置分别是 \(r_1,r_2,\cdots\)，左侧 > 的位置分别是 \(l_1,l_2\cdots\)。那么行走的总距离就是：
利用前缀和求解即可。注意左右端点处理时的细节即可。
T2
通过扩欧我们知道，对于方程 \(\sum\limits_{i=1}^n a_ib_i=z\)，当且仅当 \(\gcd\limits_{i=1}^n(a_i)\mid z\) 的时候有解。但是此时我们发现这个方程解出的 \(b_i\) 可能有负数，我们考虑给式子再加上一项 \(kb_{n+1}\)，代表取模 \(k\) 之后的结果，那么有解的情况实际上是 \(\gcd(a_1,a_2,\cdots,a_n,d)\mid z\)，而所有能生成的 \(z\) 就是前面一坨的倍数，枚举即可。
标签：连边,路径,21,30,距离,囚犯,log,01,比赛 From： https://www.cnblogs.com/dzbblog/p/18304046