竞赛图缩点后成链状（拓扑序唯一）
竞赛图缩点后成链状（拓扑序唯一）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132993089
一个常见结论
竞赛图缩点后必然成链状。
不是真正的链，只是类似链的偏序关系。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-18
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...
2021-12-10
【牛客IOI周赛26-普及组 D-最短路 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15673449.html 题目链接 题目 给定长度为 n 的数列 a，如果 （按位与），则在 i,j 之间存在一条长度为 的边，求 1 至所有点的最短路。 思路 暴力连边，边太多，最多 n2n^2n2 条，MLE+TLE。 于是考虑减少边的数量。 首先建32个虚点。 然后加入 aia_iai 在第 kkk 位上为1，就在 iii 和第 kkk 个虚点当中连边，边权为 aia_iai。 这样最多有 n×32n\times 32n×32 条边。...
2022-06-07
欧拉图和欧拉回路判定小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16352894.html 注意：下面讨论中的连通是不考虑孤立点的 无向图判欧拉图 连通 所有点度数为偶数 无向图判欧拉路径 连通 可以有两个点度数，其它点度数为偶数 有向图判欧拉图 基图连通（有向边不考虑方向连通） 所有点入度等于出度 有向图判欧拉路径 基图连通 允许有一个点入度比出度大于且同时有个点出度比入度大1，其他点度数为偶数
2021-11-16
【P1772 [ZJOI2006]物流运输】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15562734.html 题目链接 一道很好的最短路+dp。 先考虑最后结果，设 dpidp_idpi 表示前 iii 天的最小费用。设 f(i,j)f(i, j)f(i,j) 为从第 iii 天到第 jjj 天都走同一条道路的最小费用。 f(i,j)f(i, j)f(i,j) 很好求，提前预处理这段时间内哪些点不能走然后再可以走的点内跑一遍最短路即可。 转移： dpi=minj=1i(dpj+f(j+1,i)×(i−(j+1)+1)+k)d...
2023-09-16
可能的模拟网络流部分思路整理（CF1408H）
可能的模拟网络流部分思路整理（CF1408H） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093428 https://www.luogu.com.cn/problem/CF1408H 先转换 模拟网络流，所以要么割最上面一层，要么割最下面一层。 对于最上一层，肯定是左边连续+右边连续。 考虑枚举左边连续，对应到某些颜色节点，又对应到某些右边节点。 对右边节点建棵线段树，由于左边的点已经确定，先假设下面的和右边的点全部割掉。 右边的点全部割掉，所以...
2022-01-24
【AT3621 [ARC084B] Small Multiple】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15839565.html 题目链接 题目 Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K. 给定一个整数K.求一个K的整数倍SUM,使得SUM的数位累加和最小 思路 考虑翻倍。 如果一个数翻10倍，那么这个数位之和不变。 如果它翻 (10+k)(10+k)(10+k) 倍 (k⩽9)(k\leqslan...