CF构造口胡笔记
luogu_gza
·
·
个人记录
CF1476A(1000)
n=(n+k-1)/k*k
然后直接平均分配，有余数答案 +1
CF1520C(1000)
一开始以为偶数阶无解，wssb
奇数阶考虑奇数放上三角，偶数放下三角
然后对角线处考虑特殊处理一下就好了
偶数从对角线开始，从 $2$ 开始放
奇数从对角线开始，从 $n-n \mod 2$ 开始放
### CF1326A(1000)
我的做法应该是比较神奇的
$4999 \cdots 99
很简单对吧
首先 4 肯定不可能整除，各个位数之和也不被 9 整除
CF1360C(1100)
考虑二分图最大匹配，然后就没了（doge）
CF1342B(1100)
构造最小循环节为 10 的 s
然后就没了
当然可以优化长度，再判断一遍最小循环节为 01 的 s 就好了
记得特判全 0 和全 1 的情况
CF1370B(1100)
考虑使 b 中的数全部都是偶数
用两个数组记录奇数和偶数
然后考虑种内斗争
如果各个种内有残余势力，全部在删去的时候消除
CF1401B(1100)
0抵1
2抵2
然后剩下乱抵，尽量2抵1
CF1511B(1100)
想象一下 \gcd 干成 10^{c-1}
考虑构造 a,b 令 \gcd(a,b)=1
简单的来说，构造质数就可以了
找oeis查一下 k 位的最小质数就好了。
CF1407A(1100)
明显的，选择相同的数字就好了
因为不限制个数，所以怎么选都可以捏
实现？可以先选光0在选光1
CF300A(1100)
第三个集合把 0 全塞进去
第二个集合考虑塞偶数个负数和所有正数
第一个集合塞剩下的
CF1352B(1200)
塞一堆 $2$ ，然后最后再塞一个满足和
$n$ 是奇数怎么办？
如果是偶数个的话，不可能。
否则塞一堆 $1$ ，然后塞一个满足和。
如果 $n < k$ 则不可能。
### CF1339B(1200)
**错误想法：**
有点hard啊。
考虑一下只有正数。
震荡放。
有了负数怎么办？
在正数震荡的时候，考虑负数顺便震荡掉。
斯。想错了捏。
**正确想法：**
考虑排序前后交替放就好了
### CF1537C(1200)
前后固定后，考虑一次性降到谷底，然后慢慢升上来。
官方做法放一下：
考虑头尾一定相邻（在排序数组中）
所以乱做一下就好了。
### CF1527B1(1200)
这不是把做题人当傻逼吗？
考虑一下 $0$ 的个数，是 $1$ 个或者偶数个 $B$ 胜。
是奇数个 $A$ 胜。
全 $1$ 就 $\texttt{DRAW}$ 了。
### CF1497C1(1200)
$n$ 为奇数：
$k\ k\ 1
$k\ k\ 2
$k\ k\ \frac{k}{2}
结束了。
CF478B(1300)
简单。
平方级别的数的增长速度就算有 \frac{1}{2} 的常数，依然比线性要快。
所以多放人或者平均放人。
CF1335D(1300)
简单。
直接替换任意一个数字。
CF1365B(1300)
考虑冒泡排序。
如果 b_i=b_j 就用跳板交换。
没有跳板了怎么办？
直接 \texttt{NO} 就好啦。
CF1401C(1300)
如果不是最小数的倍数的数连起来未排序的话，输出 \texttt{NO} 。
否则 \texttt{YES}
不是这样的……
正确的是，如果一个数在排序数组中位置与现在不一样并且不是最小数的倍数，输出 \texttt{NO} 。
否则 \texttt{YES}
CF1367C(1300)
恶评啊。
怎么可能1300呢？
明显的每次在“边缘”放 1 ，已经有“续费”的就更新区间。
CF1454D(1300)
考虑分解质因数，最多个数的质因数就是长度。
然后每次铺一个后缀。
铺：把数组中的数乘上一个值
没了。
CF1603A(1300)
发现删后面的对于删前面的毫无关系。
筛出每个数的最小质因子，考虑在不能删去的“边界”上的先删去。
然后考虑一个个慢慢删。
有更加简洁的方法！
考虑每一个数其实可以在比它小的位置“删去”。
所以枚举一遍就好了。
CF570B(1300)
考虑几何意义。
发现贴着 m 会最好。
然后 m-1 和 m+1 尝试一下就好了。
CF1365C(1400)
### CF1375C(1400)
考虑逆序分析，发现只有 $1$ 和 $n$ 是独立于其他的。
$a_1<a_n$ 就是满足条件的。
### CF1506D(1400)
考虑统计每一种出现的次数
摩尔投票法就好了。
发现不能干了，就停止。
### CF401C(1400)
考虑一下各种情况。
有两种方法：
$110
10
使用的时候怎么配套呢？
2x+y=1_{num}
x+y=0_{num}
考虑消元即可。
数据保证一定有解哈。
但是超出能力范围了怎么办？
### CF1463B(1400)
找一下最接近的 $2$ 的幂次就好啦。
### CF1355D(1400)
发现不会做捏。
考虑 $S$ 的范围。
$S\ge 2n$ 的时候，明显的可以平均分，然后令 $k=1
### CF1332B(1400)
可以发现整个数组的质因数小于 $\sqrt {1000}
里面的质数个数 \le 11
触发灵感！
考虑为 p_i 的倍数就分到 i 组中。
CF538B(1400)
每位的独立的嘛。
直接考虑拆位最后加起来就好了呀。
CF1800E1(1400)
发现可以通过中间变量交换实现任意两个的交换捏。
然后，直接考虑计算“不可交换边界”
当且仅当 n-k \le i<k 的时候可以“调整”第 i 位。
代码不是问题捏。
我顺便把E2解决了啊！
CF1790E(1400)
个人认为绝对的Ad-hoc！
考虑分析一下。
a+b=a \oplus b+(a\ \texttt{and}\ b) \times 2
所以需要构造
a \oplus b=x
a\ \texttt{and}\ b=\frac{x}{2}
那么！
这玩意不就可以直接构造了吗？
考虑令 a=\frac{x}{2},b=2x-\frac{x}{2}
手玩发现似乎可行诶！
思路是错位，但是错位怎么错是凑出来的。
CF1753A1&CF1753A2(1300&1500)
A1简单的要死。
设干完以后 -1 的个数为 x ，则 1 有 n-x 个。
总和为 n-2x ，发现奇偶性与 n 相同。
所以，当 n 为奇数的时候，无解。
有解的时候，相邻两个相同，两个一起消掉。
否则，一个一组一个区间，都翻转。
相当于一个一组的不翻转。
其实抽屉原理就可以证了，不过我做的时候是口胡的。
A2更加简单，直接跳过 0 。
但是 0 会影响奇偶性，怎么办？
简单，影响了奇偶性就抽出来嘛。
CF1742F(1500)
只有一种字母的时候明显是 YES 。
### CF1739C(1500)
考虑一下胜利的情况。
平局明显是 $1$ 。
A胜是因为拿到了 $n$ 。
B胜肯定是因为A没有那道 $n$ 。
记得排斥掉平局的情况。
### CF1806C(1600)
考虑构造简单的情况捏。
发现可以分为一下几种。
1. $n=1$ :两个相同的数
2. $n=2$ :全 $2
-
脑子不好使了，n \geq 3 的构造差点想不出来，div2C诶。
定义完"好的"的构造方法后，考虑一下最小距离和。
n=1$ ，$|a_1-a_2|
$n \geq 3$ ，把最大的数配上 $m$ ，其他的都配 $-1$ 。
### CF1801A(1600)
考虑构造。
发现异或具有自反性诶！
考虑构造使得 $i$ 与 $j$ 无关。
错开一定位数就好拉。
$$i \times 2^{10} \oplus j$$
### CF1798D(1600)
震荡放啊。
和为正数就放负的，和为负的就放正的。
### CF1797C(1600)
明显的，当国王在 $(x,y)$ 的时候，如果你询问了 $(a,b)$ ，答案是 $\max(|x-a|,|y-b|)$ 。
考虑可以判定国王在一个正方形上，询问 $2$ 次。
发现这两个正方形要么要么有 $2$ 个重合点 ，要么就是重合一条边。
前者如何解决？询问一次其中任意一个点。
后者如何解决？询问这条线端点上的点。
### CF1781C(1600)
考虑将字符串转化为所有字符出现的次数。
直接考虑枚举 $n$ 的因子，然后就是贪心求答案了。
那么答案如何求得呢？
考虑直接还原，然后尽量“匹配”。
### CF1774D(1600)
水玩意！
考虑平均分配后 $1$ 的个数一定不变。
那么缺啥补啥呗，多的人就往少的人里面补。
### CF1707A(1600)
有一个显然的dp。
$f[i][j]=\min(f[i-1][j],f[i-1][j]+1(j \geq a_i))$ 或者 $f[i][j]=\min(f[i-1][j],f[i-1][j+1]+1(j < a_i))
考虑优化转移，发现可以一次性转移诶！
然后？解决力！
其实大众做法是一个贪心。
考虑先能打就打，后来再疯狂打扣智商。
发现有一个顶峰值，所以可以二分。
CF1698D(1600)
一个很明显的二分
考虑询问 l 到 r 的区间，如果在 l 到 r 的元素个数为奇数的话，说明 x 在 l 到 r 之间。
otherwise？otherwise。
CF1671D(1600)
手玩发现一个单调的区间的分数是首尾的绝对值之差。
随便插，只要满足单调性就好了。
注意到超过原来的值域的数需要特判。
错误的！
题目读错了/kk
但是思路还是正确的，我们只需要考虑 1 与 x 就好了。
CF1660E(1600)
发现需要最多的数在一条斜线上。
既然我们可以循环操作，那么我们假设整个矩阵就是循环的不就好了嘛？
考虑到了这一点，就很好做啦。
发现题解区有妙妙做法。
分享一下这个trick。
既然是循环的，上下左右复制一遍不就好了嘛。
CF1603B(1600)
1600做起来好爽啊。
原来分析了一大坨，屁用没有。
考虑简单的分讨。
x>y$ : $n=x+y
x=y$ : $n=x
继续分讨。
考虑 $n=y-a
做不下去了。
看了题解发现 a=\lfloor \frac{y \operatorname{mod} x}{2} \rfloor 似乎是可行的？
不知道怎么证明。
gza还是太菜了。
CF1582D(1600)
先给负数乘个 -1 ，方便说明。
考虑凑 0 的情况就是找两个数，然后考虑别的东西直接乱选，剩下的交给这两位。
但是考虑到别的东西凑不出来，怎么办？？？
发现有一个更加简单的做法。
考虑两个数相互抵消，但是有时候 n 是奇数，怎么办？
考虑随便挑选一个已经被抵消的再抵消一下就好啦。
CF1555D(1600)
明显的，我们只要保证不存在长度为 2,3 的回文串就好了。
那么也就是保证不存在相邻相同或者是隔位相同。
互斥的条件如何处理？
尽量每一个点的改变要对答案贡献“大”一点。
我震惊了！
题解区的做法太神秘了！
枚举 6 种排列，取其最小值就好了。
CF1530D(1600)
先改，满足第二个条件。
然后考虑第一个条件如何满足。
有人要，有人给，直接换。
有人要，但是没人给？不存在的，最终的不同个数是偶数。
CF1511D(1600)
发现其实是连续两个字符相对应就是一个花费。
考虑连续两个字符不能重复。
如 k=4 可以如此构造。
aabacadbbcbdccdd
循环便是了。
其实还可以跑一遍欧拉路径。
其实还可以跑一遍欧拉路径。
其实还可以跑一遍欧拉路径。
CF1618E(1700)
发现了一个线性方程组！
考虑发现规律……
找不到规律啊，看了题解发现是推式子……
CF1776F(1700)
找个 u ，于其相连？为 1 。
否则为 2 。
我考虑不够全面啊。
只有在原图是完全图的时候才找不到这样的节点 u，此时拿出一个颜色 1 的边，将其改为颜色 3 即可。显然这种构造符合要求。
CF1765D(1700)
诶呀，想了好久好久。
总而言之就是能装就装，下次再看。
不能装了？看掉一个最小的。
考虑简单的双指针。
CF1702F(1700)
发现全部转化为奇数以后就好做了。
考虑简单的排序，能干掉就干掉，不能干掉就更新一下再干掉。
CF1700C(1700)
考虑其差分数组，重新认识各个操作。
-
-
-
### CF1699C(1700)
考虑手玩。
会发现一个有趣的性质：你可以把整个问题看做一个一个放数字。
然后直接考虑定义目前区间 $[l,r]$ ，方案数？每个数字的放置位置种数乘积。
### CF1688C(1700)
每一次都会产生一些字母，消除一些字母。
但是发现，总体的奇偶性是不变的。
考虑记录出现奇数次的字母，即为答案。
### CF1687B(1700)
考虑询问后可以得到每一条边的边权。
我们需要判定两点是否连通，怎么办呢？
考虑通过“边权”的询问来解决问题。
发现kruskal的问题就在于判断这一条边是否需要，那么记录所有比他小的边，看看这一条边是否“需要”就好了。
简单的来说？排序边后询问前缀。
### CF1684D(1700)
考虑贪心。
每一次考虑放置给后续带来的影响。
然后“更改”每一个权值，但实际是在优先队列中的单调性不会改变。
然后？做完了。
### CF1672D(1700)
发现改变的顺序不是问题。
操作相当于把一段相同的数都push到了最后面。
被相同的数夹住的一段数是“不可改变”的。
因此我们考虑一下“不可改变”的一段只可能位置改变，所以看A中“不可改变”的一段如果在B中对应的一段的前面，那么就是“没救了”。
### CF1658C(1700)
简单的看一下，先发现“权值”就是。
$$dif\{ \max_{j=1}^{i}a_j \}$$
考虑每一个元素的贡献。
$$\sum_{i=1}^{n} is\_bigger_{j=1}^{i-1}(a_i)$$
那么可以发现一次性置换后权值增长不超过 $1$ 。
然后就做完了。
### CF1619E(1700)
这个题目我看过！
考虑令 $0\sim i-1$ 的数都出现过。
考虑当前在 $0\sim i-1$ 的数的个数是否大于等于 $i$ 就好了。
次数？考虑先干大的，下次个数不够了再去干小的。
总体复杂度 $O(n)
CF1594D(1700)
- 老实人说老实人是老实人
- 老实人说说谎者是说谎者
- 说谎者说老实人是说谎者
- 说谎者说说谎者是老实人
发现，如果被说是老实人，则与其同类。
如果被说是说谎者，则与其异类。
那么确实可以使用并查集来解决问题了。
两类的size取其大值。
出现矛盾了就输出 -1 。
CF1592C(1700)
考虑删除一条边，然后枚举+换根dp。
以上为错误想法
看了题解才知道是这样的……
若 x 为偶数，则满足 sum=0，因为可以将偶数个 x 两两异或，结果为 0，输出 YES。
若 x 为奇数，可以两两消去直到剩 3 个，dfs check 即可。