分治构造：P9384
分治构造：P9384
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134366235
https://www.luogu.com.cn/problem/P9384
分治构造是很常见的一种构造
不能有三元环和五元环，考虑推广出去，也就是不能有奇环
那如果我们让每种颜色都为二分图，那么必然满足
考虑 0-9 总共10个数字，数据范围1000，考虑 ，考虑 级复杂度的做法
假如我们采用分治构造，左区间所有点向右区间所有点连边，边为分治层数。显然对于每种颜色都是个二分图，满足题意
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-11-06
前缀LCM构造——从后往前进行：ARC122E
前缀LCM构造——从后往前进行：ARC122E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134238967 https://vjudge.net/contest/591700#problem/J 发现题目是一个类似前缀LCM的问题： 我们可以考虑从后往前构造，枚举最后一个数放什么 然后递归下去 1234567891011121314151617181920212223242526272829303132333435363738394041424344...
2023-11-06
偏序关系用分治优化建图：ARC165F
偏序关系用分治优化建图：ARC165F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134253598 https://atcoder.jp/contests/arc165/tasks/arc165_f 首先可以建图，然后变成求字典序最小的的拓扑排序 然后发现这样复杂度会炸，观察连边的条件是什么： li<ljl_i<l_jli<lj ri<rjr_i<r_jri<rj 这是个二维偏序问题，我们考虑用分...
2022-04-15
关于多人中3人相认识或4人相不认识研究报告
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/articles/16151398.html 关于多人中3人相认识或4人相不认识研究报告 作者：张霆希 时间：2022.4.15 题目 求至少任意多少个人，必有3个人全都互相认识或者4个人全都互相不认识，不存在A认识B但B不认识A的情况 条件1 3个人全都互相认识 条件2 4个人全都互相不认识 解析 连通块：假如A认识B，B认识C，则A，B，C在一个连通块里，A和C的关系不确定. 连通块的大小：连通块里的人数成为连通块的大小. 连通块的 kkk 值...
2023-09-26
中间相遇法（分治类问题非等大分治的平衡做法）
中间相遇法（分治类问题非等大分治的平衡做法） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321701 分治，如果分成两半大小不一样，很容易被卡到 O(n2)O(n^2)O(n2) 在某些题目中，利用中间相遇法，我们可以优化这个过程 其优化的前提是分治的大头在找分界点 复杂度不用证，很好理解吧 这层找地越久，下一层就越均匀
2023-11-07
不完全考虑构造+DP与构造：1107T2
不完全考虑构造+dp与构造：1107T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134274865 http://cplusoj.com/d/senior/p/SS231107B 发现reverse操作会对一堆数进行修改，但如果我们只关注其中一些数呢？ 假设我们已经构造好 [1,i−1][1,i-1][1,i−1] ，我们现在尝试构造 [i,n][i,n][i,n] ，我们可操作的范围是在 [i−1,n][i-1,n][i−1,n] 假设 iii 在...
2023-09-27
线性代数+分治：446E
线性代数+分治：446E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133336367 https://codeforces.com/problemset/problem/446/E 把官方题解翻译了一遍 考虑暴力，肯定想到dp，然后变成矩阵。设 用 代替 （这样子数之间的差值不会变化，但对于问题的处理能方便很多） 我们先令（也就是初始时的方案数） ，然后尝试构造转移矩阵 BBB BBB 的大小应该为 n×nn\times nn×n ，每个格子对...