奇偶+逆序对构造法：arc102d
奇偶+逆序对构造法：arc102d
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133825414
<https://atcoder.jp/contests/arc102/tasks/arc102_d<>
类似构造题，但不完全是，先从交换类构造题几个常见方面考虑一下：
-
差分：没关系
-
奇偶：发现奇数位一直在奇数位，偶数同理（我们得到判定1了）
-
逆序对
-
交换会使逆序对个数-3，所以总逆序对个数必然是3的倍数（判定2）
-
只在奇数位的逆序对和只在偶数位的逆序对之和必然-1，所以其必须使总逆序对的
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2024-01-02
二分图+生成树构造：留下一条边：AT_arc119_d
二分图+生成树构造：留下一条边：AT_arc119_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135341327 https://www.luogu.com.cn/problem/AT_arc119_d 首先，我们可以发现，同行和同列的红色格子会相互影响。因此我们可以考虑连边。这里我们容易想到两种连边方式： 红色格子之间连边。 位于 (i,j)(i,j)(i,j) 的红色格子，把第 iii 行和第 jjj 列连边。 考虑第一种连边方式。一...
2023-10-25
排列置换环上构造：1025T3
排列置换环上构造：1025T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134035399 http://cplusoj.com/d/senior/p/SS231025C 排列构造的新知识：上置换环！ 我们发现朴素做法是 n2n^2n2 级别的，但数据范围希望我们是 n22\frac {n^2}2 2n2 级别的。我们发现我们暴力复制序列显得非常蠢，因为很多序列前后我们其实可以考虑合并。 至于怎么合并？我们直接维护指针。然后我们现在要“运”东西到相应...
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...
2024-08-29
8.29T2 国际象棋（构造：棋盘拆分成小方阵）
8.29T2 国际象棋（构造：棋盘拆分成小方阵） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141686046 http://cplusoj.com/d/senior/p/NODSX2303B 暴力显然，因为肯定是从奇点到偶点，所以二分图匹配一下就好 首先我们手模一下，比如（11,11），我们可以手模出一个情况，也就是DInic跑出来的情况： 看起来很有规律，但却很难分析，那让我们看另一种方法： 是不是看起来没有什么规律？其实不然： 是了！这种拆分...
2023-10-15
限制条件加入构造范围：Gym - 102832L
限制条件加入构造范围：Gym - 102832L 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840957 https://vjudge.net/contest/587311#problem/D 场上列方程求首项，假设是全部加1，然后一部分（后缀）减去 k+1k+1k+1 ，就用到了以下两个条件： 但在这两种情况符合情况下， 这个条件不一定满足 然后就不会了 我们为什么不能把第三个条件也加入到方程里呢？ 我们发现用减的方法很容易弄成负数，我们就...
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 值...