【题解】Solution Set - NOIP2024集训Day44-45 图论
【题解】Solution Set - NOIP2024集训Day44-45 图论
https://www.becoder.com.cn/contest/5579
「BZOJ3706」反色刷
倒过来想，因为你不管怎么反色，形成的一定是若干个黑圈，所以答案就是黑圈个数（？
8min
我靠，不会求这个东西。😥
哦！看是不是一个环，重要的不是判边数=点数，而是每个点度数为 \(2\)。
https://www.becoder.com.cn/submission/2621783
答案大了？
哦！不是黑圈个数，其实就是连通块个数，因为在同一个联通快里面的黑圈是可以一次性走完的。
判无解的话，可以直接维护度数是奇数的个数。
有解的话，就是包含黑边的连通块个数。
同样维护每个连通块内黑边的个数，就行了。
「联合省选 2020 B」丁香之路
一股贪心的味道。
根据 \(s,t\) 把所有的边分成 \(6\) 部分：
- \(s\) 左边的；
- \(s,t\) 中间的；
- \(t\) 右边的；
- 跨过 \(s\) 的；
- 跨过 \(t\) 的；
- 同时跨过 \(s,t\) 的。
https://www.luogu.com.cn/article/wbf3o0j9（下面按自己理解重新把题解梳理了一下
直接做还是不太好像的，还是得建图。
我们先把这 \(m\) 条边放在图上，然后加入尽量少的边使从 \(s\to i\) 变成欧拉路。
连边 \((i,s)\)，就是要变成欧拉回路，也即让每个点的度数都为偶数。
（注意：因为我们的加边是可以加重边的，所有这里的欧拉回路并不是严格意义上的。
下面会分成两步：
-
保证度数均为偶数
我们先把所有的度数为奇数的点拿出来，设为 \(a_1,a_2,\dots,a_n\)，可以证明的是 \(n\) 是偶数，因为我们的奇数点一定是成对出现的。
然后我们贪心地将 \((a_1,a_2)\dots(a_{n-1},a_n)\) 连边，这样就保证了是一个不连通的但是度数是偶数的图。
这个贪心是对的，是因为变为为 \(|i-j|\)。
-
保证图联通
介于边权为 \(|i-j|\)。
我们把先排除无用的点，然后相邻两个点两两连边，这样一定不劣。
然后对使图联通的代价就是 mst 的两倍（因为一个连通块内的点的个数一定大于 \(1\)，我们又需要保证度数仍都是偶数，就必须每条树边都加两条进去。
（题解感觉都没把实现过程写清楚，纠结了半天还是决定看一下代码，才理解。😥
「AHOI2014/JSOI2014」骑士游戏
做过。
显然 dp，所有的转移都是取 \(\min\)，直接用最短路来转移，避免环就行了。
3min
「APIO2015」雅加达的摩天楼
做过。
先建图。其实就是求一个边权为 \(1\) 的最短路。
感觉像根号分治。
- \(p>\sqrt n\)，直接暴力连边，至多 \(n\sqrt n\) 条。
- \(p<\sqrt n\)，可以先对 \(b\) 取模 \(p\)。然后这样的 \((b,p)\) 对之多有 \(n\) 个，暴力连边也才 \(O(n^2)\)，调调参说不定就过了（（