ACM刷题日记
想起来去年还在打acm的时候写了一段时间的做题日记，索性放到博客上好了
CF1898D Milena and Admirer
贪心 绝对值图像化思想
把$ a_i $，$b_i$抽象成线段的端点，|$a_i-b_i$|表示线段长，操作等同于交换两个线段的端点，通过分类讨论求每种情况下产生的贡献
CF1901B Chip and Ribbon
思维
还算有趣的题，推一下发现每次操作的贡献是当前段数 * 当前剩下的最小的数，如果是第一次操作则后者减一，对于维护段数，考虑对于每个数存它出现的位置，如果删除时左右都有数则标记段数++，如果左右都空则标记段数–
CF1901C Add， Divide and Floor
推式子找规律
让整个序列都相同等价于把最大的和最小的变成相同的
假设每次选一个满足$minn \leq x \leq maxn$的x
$\Delta maxn=\lvert \frac{maxn-x}{2}\rvert= \frac{maxn-x}{2}$
$\Delta minn=\lvert \frac{minn-x}{2}\rvert= \frac{x-minn}{2}$
发现如果不考虑精度误差则x可以任意选，考虑精度误差，发现当maxn为奇数，minn为偶数时，选x为偶数可以使maxn下降更快，minn上升更快，反之同理
CF1901D Yet Another Monster Fight
思维
意外的简单，不知道为啥场切人数那么少
显然对于每一个$a_j$，答案最差的情况是在到达$a_j$左侧或右侧某个很大的点$a_i$之前多走弯路(浪费威力最多)，可以对这个大点$a_i$按在$a_j$的左侧或是右侧分类讨论，通过手模发现，结果为$ans_{a_j}=max\begin{cases} n-i+a_i ，\quad i < j \ i+a_i，\quad i >j \ a_j\end{cases}$
直接开两个multiset L，R，j从左向右扫，每次删掉一个右边的，增加一个左边的，对于每个j统计答案取min即可
数论涉及多个gcd求和 CF1900D
有可能是欧拉反演，但是不想学数论
CF1900E Transitive Graph
图论tarjan
对于随便一个环(强连通分量)，按题意会连成一个完全图，也就是说在这个块里可以任意走
要走长度最长且点权和最小的路，因为上面的条件所以随便一个强连通分量我们都可以一笔画走完，显然能走就走是最优的，tarjan跑完写个拓扑跑类似最长路的dp即可
####CF1896A Jagged Swaps
结论
$a_1=1$就是合法的，手模得出
CF1896B AB Flipping
结论
同样有趣的题，手模发现原序列去掉前导B和后导A后每个点都可以操作(后面的B可以被一路换到前面去)，固答案为$max \lbrace 0，len-1 \rbrace$
CF1896D Ones and Twos
结论+DS
题目里给了$a_i \in \lbrace 1，2\rbrace$是有道理的
对于一个左右端点都是1的子串，任意删掉一个端点的1可以改变子串和的奇偶性，连续删去两个1等价于删去一个2(无论两个1是否相连，由分类讨论得)，那么显然对于每个询问，先取出左右端点为1的最长的串L，如果$sum_L\geq v$那就合法，否则考虑$sum_L$和$v$的奇偶性，奇偶性相同就向两边凑2，不同则删去一侧的1然后取剩下侧的2，左右端点重合的情况也适用
用set存每个1的位置，查询时直接取set的头尾，区间和用树状数组维护
CF1896C Matching Arrays
贪心
似乎这种题都是大的对大的小的对小的？
constexpr预处理
这个关键字放在定义前可以让后面的东西在编译的时候跑，可能初始化素数表之类的挺有用的？
####重载运算符
对于二元运算符重载的时候成员函数作为左边的参数，显式操作数作为右边的参数
move()
a=move(b) 把b的资源转移给a，比复制快很多，大概在滚动数组里有用
CF1902C Insert and Equalize
贪心
还算巧的贪心，选择一个数$x$使得可以通过不断加$x$让$a_{1…n+1}$相等，首先考虑$a_{1…n}$，先从小到大排序然后考虑相邻项的差值，因为只能不断加一个数这个数只能是这些差值的大公因数，不然凑不齐。然后考虑$a_{n+1}$，记之前得出的最大公因数为$g$，则$a_{n+1}$可以由$a_n$加上或减去g得到，我们优先考虑减，如果减了n次都不行就直接令$a_{n+1}=a_n+g$，同时把{a_{1…n}}抬高g
CF1902D Robot Queries
DS+前缀和
询问执行给定操作后是否经过指定点，先不考虑翻转，可以把经过的点做成一个前缀和，对于每个询问查询前缀和数组里是否有这个点
考虑翻转的情况，对于一个原本能到达的点$pre_i=(x，y)$，我们先把它还原到翻转区间的起点，即$pre_i-(pre_i-pre_{l-1})$，然后看他翻转后是什么样，即$pre_i-(pre_i-pre_{l-1})+(pre_r-pre_{i-1})$
如果这个反转后到达的点就是所求的$P=(x，y)$，那么整理下得出$pre_{i-1}=pre_{l-1}+pre_r-P$，所以对于翻转过的区间，我们只要在$[l-1，r-1]$里找是否有符合条件的$pre_{i-1}$即可，对于正常的区间就在$[0，l-1]，[r+1，n]$里找是否有询问的点$P$即可，显然翻转后对于翻转区间外的点是没影响的。
找点的具体实现用线段树套set，线段树的每个节点上开一个set，添加点就一路insert到叶子，查的时候合并各区间答案即可
CF1907B YetnotherrokenKeoard
栈
签到题，分大小写开两个栈即可
CF1907C Removal of Unattractive Pairs
贪心
发现最后肯定只剩一个字母了，而且那个字母肯定是数量最多的，根据出现次数最多的字母的数量和n的大小分类讨论即可
CF1907D Jumping Through Segments
二分
二分答案，在check的过程中维护每次能到达的点的区间$[a，b]_n$，显然这个$[a，b]n$的更新可以通过分类讨论$[a，b]{n-1}$与$[l_n，r_n]$的相交情况实现，如果不相交就说明k非法
CF1907F Shift and Reverse
哈希+结论
首先这道题要知道只有以下几种情况可能是最优的：
1.一直往前翻
2.翻转然后一直往前翻
3.翻转一直往前翻然后翻回来
4.一直往前翻最后翻转
这四种情况1，4等价于把后面的搬到前面去，2，3等价于把前面的搬到后面，然后最后的结果是使序列变成递增或递减的
然后我们把原序列复制一遍放在后面，这样扫过去就可以直接得到所有我们可能通过操作产生的序列，然后操作数可以直接算出来，具体通过手模找规律，然后只要扫到某个数$a_i$是最大或是最小的（可以作为单调序列的起点），我们就用哈希判断$a_{i…i+n-1}$是否和排序好的序列一样，如果一样就计算把原序列变成这样需要的最小操作数并更新答案
set使用自定义类型
对于自定义类型，劣质的重载<会影响set的行为(大概率导致set出问题)
CF1904B Collecting Game
双指针
双指针板子题，排序后跑双指针即可
CF1904D1 Set To Max (Easy Version)
贪心
easy version的数据较小，直接跑$n^2$的贪心即可，hard version可能要在原做法上加一个线段树维护区间最大值
从小到大依次取$a_i$，然后分别向左右拓展，只要是扫到的数比$a_i$小并且比$b_i$小就可以把他设为$a_i$，最后扫一遍a看和b是否相同即可
CF1904D2 Set To Max (Hard Version)
贪心+RMQ
还真是原做法随便加一个单次logn或者更优的rmq，对于一个需要set to max的$a_i$显然我们需要找到它左边或右边最近的和$b_i$相等的$a_j$，选最近可以让一次操作对其他数字的影响最小，然后用rmq查$a_{i…j}$里面是否有比$b_i$大的，$b_{i…j}$里面是否有比$b_i$小的，如果都没有显然这次操作是合法的，然后优化下easy version取数的方式，改成从小到大取$b_i$（从结果入手），总的复杂度限制在rmq初始化$nlogn$
CF1904C Array Game
分类讨论
发现对于k>=3，可以直接先选两次一样的$a_i，a_j$，然后第三次让两次的差互相减，答案肯定为0
对于k=1，直接在所有的差和本来就有的数中间选一个最小的即可
对于k=2，先$n^2$搞出来所有的差，然后每次在原数组中lower_bound一下去找和这个差最近的数再做差，也是把搞出来的所有数取min求答案，复杂度$n^2logn$
后缀BIT
把前缀树状数组的所有循环顺序倒过来就能实现后缀bit
费马小定理
一个数在 mod b下关于a的逆元为 $a^{b-2}$
CF1917B Erase First or Second Letter
计数
对于一个字符串，如果确定第一个和第二个字符，那就不能继续操作了，可以将最终的字符串拆分成一个后缀和一个字母组合的形式，我们可以不断进行操作2来使一个字母匹配每一个后缀，同时因为我们只能删前两个字母，所以实际上我们最多有n个不同的后缀，且长度分别为1~n，所以我们要统计对于每一个后缀，前面有多少个不同的字母可以与其组合，开一个桶计数即可，把每个后缀的答案求和就是总的答案。
CF1917C Watering an Array
贪心
一个重要的性质，假设a=[0，0，…，0]，不管b的组成是什么样的，且执行几次添加操作，始终最多有1个$a_i=i$，因为假设$a_x=x$，那么对于$a_x$前面的所有$a_i$肯定有$a_i \geq a_x$（因为每次是对一个前缀+1），对于后面的同理，所以如果我们进行过一次reset操作，之后最优的做法一定是add一次就reset一次，总贡献为d/2，所以问题转化成确定第一次reset的时间，注意到第一次reset最多也就产生n的贡献，所以如果我们第一次reset的时间晚于2*n+1，则一定不是最优的，即一开始最多add 2n次，直接暴力add 并统计答案取max即可，注意判断操作是否合法
CF1917E Construct Matrix
构造
非常神秘的构造，答案一半很显然，一半很不显然
要求构造一个n*n的矩阵m，n为偶数，要求每行的1的数量同奇或同偶，每列同奇或同偶，且总数等于k
首先特判，如果$k = n^2-2 || k=2 $，此时如果k!=2，则无解
然后是对于k%4=0的部分，显然我们可以尝试把1组合成2x2的块放进去，一个2x2的块对横纵的奇偶性都是没影响的
对于k%4=2的部分(不知道怎么想到的)如果k<6肯定是第一种无解的情况，当$k \geq 6$，我们先把$m_{1，1}，m_{1，2}，m_{2，1}，m_{3，3}，m_{3，2}，m_{2，3}$这六块变成1，然后剩下k-6的部分在除左上角4x4的范围继续组成2x2的块填进去，然后$k=n^2-6$则正好会有4个1多出来，则在$m_{1，3}，m_{1，4}，m_{4，4}，m_{4，3}$四个位置填上1，对于其他的所有情况，均无解
CF1913B Swap and Delete
思维，字符串
定义两种操作，从s中删去任意一个字符，代价为1，任意交换一对字符，代价为0
记操作任意次后得到的字符串为t，问使t与s对应位置的字符均不相同的最小代价
因为交换是无代价的，所以只要让t的1数量和s长度为|t|的前缀的0数量相同，反之亦然即可
考虑直接枚举答案，显然答案最大为|s|，删完了肯定都一样了，对于每个答案n，实际上我们可以在合法的前提下任意删除总数为n的0和1，如果s里的0比t里的1多肯定这个答案是不行的，因为我们只能从t里删东西，对于每个可能成为答案的t，一定有$cnt1_t=cnt1_{preS_|t|}$，所以我们只要对于每个可能成为答案的t，统计s的0与t的1的数量差值和s的1与t的0的数量差值，如果两个差值和与我们枚举到的答案相等，则这个答案就是合法的，从小到大枚举找的合法的就退出即可
CF1913C Game with Multiset
贪心，二进制
很套路的题
往一个集合里多次插入$2^x$，多次询问集合里的数是否可以凑出w
显然先把w拆成二进制的形式，然后每次询问从低位向高位枚举，如果集合里这位有多的就除二借给下一位，一路枚举到头即可
CF1913E Matrix Problem
最小费用最大流
板子题，出在div2E估计是科技太高了
发现n很小，且是约束问题，考虑网络流
要求$i$行要有$a_i$个1，$j$列要有$b_j$个1，可以建超级源超级汇，合法的情况就是每个$a$点有$a_i$的流量，每个$b$点有$b_j$的流量，直接从源点向每个$a$拉流量为$a_i$的边，从每个$b$向汇点拉流量为$b_i$的边，费用均为0
然后中间$a，b$直接拉完全图，边代表矩阵里的点，流量都是1，如果这个点本来是0，就拉费用为1的边，如果已经是1了，就拉费用为-1的边，同时先在答案里+1，表示如果这个点最终就是1，则不需要付出代价，所以费用和先加的1抵消，如果这个点最终应该是0，那这个点的流量就不会算进总流量里，也不会计算这个点的费用，按题意需要付出一点代价，而这个代价在拉边时已经加好了
建完图跑dinic板子即可，最后如果a，b流量都跑满且相同就是合法答案
CF1914C Quests
贪心
显然最优答案是前i个先各做一次，然后剩下k-i次全部做b最大的那一个
CF1914D Three Activities
贪心
假设每次我们都只选a，b，c里前三大的i，最差的情况是这三个都相同，如果随意拿掉一个a，b，c也总还有两个可以选，而且这些选的都是前三大的，答案一定是在这里面产生的，所以直接找三元组里a，b，c分别是前三大的，从这几个(3~9个)里暴力枚举答案
CF1914E Game with Marbles
贪心
easy version直接爆搜
hard version这么考虑，对alice，一次操作产生的贡献是$a_i+b_i$（A取了$a_i-1$，同时B的$b_i-1$不能取了，等价于对总答案的贡献是$(a_i-1)-(b_i-1)$），发现对bob来说也是同理，所以直接按照$a_i+b_i$排序，依次取大的即可
CF1914G1 Light Bulbs (Easy Version)
tarjan
这题有2100？ 不是很认可
mod 998244353不开long long 是存在溢出并且输出不是负数的可能性的(能开long long 尽量开)
发现对于一个颜色，显然如果我们先把一个灯点亮，那另一个灯也亮了，然后这两个灯之间的通过操作2也全亮了
把灯抽象成线段的两端，如果一条线段被另一条完全覆盖，那只要长的那条点亮就行，如果交叉覆盖，则任意点亮一条即可，考虑对于每条线段u，向他所覆盖到的所有线段v拉单向边，表示点亮u就能点亮v，这样对于完全覆盖就是只能点亮u，对于交叉覆盖就是u，v任意点亮一个，注意到这里产生了强连通的问题，把图建好后跑缩点，缩完点的图中入度为0的点的数量就是S的大小，然后显然这些入度为零的点里被压缩了颜色数*2个灯泡，用乘法原理全乘在一起就是方案数
CF1918A Brick Wall
贪心
一个砖的大小是$1k$，墙的稳定性是横着的砖的数量减去竖着的砖的数量
显然偶数长度就直接全部$12$的砖，奇数长度就一排$13$的砖，其他的就全部继续用$12$的
CF1918B Minimize Inversions
思维
给定两个序列A，B，可以同时交换$a_i，a_j和b_i，b_j$，要求输出排序后的A，B，使得其中逆序对的数量和最少
考虑单独的一对$a_i，a_j，b_i，b_j$可能会有0，1，2对逆序对的情况，对于0的情况，交换产生2组逆序对，对于1的情况，交换消除一组逆序对，并产生一组逆序对，对于2的情况，交换消除两组逆序对
发现如果对A排序，那么A中的逆序对数为0，那么对于所有的$a_i，a_j，b_i，b_j$，只会出现1和0的情况，而这两种情况无论怎么交换都无法减少逆序对的总量，所以此时总的逆序对数达到最小
CF1918C XOR-distance
思维
异或问题拆位考虑
假设$a>b$，发现如果我们搞a，b的最高位（对齐情况下），就会搞完后$a < b$，那后面就没法确定怎么搞了，所以考虑不动最高位，从次高位开始搞，这样不管怎么弄都能满足$a>b$，只要尽可能缩小a并增大b就行了
对于a，b该位都是0或1的情况显然对答案没影响
1：对于a是1，b是0的情况，x这位是1对答案有贡献
2：对于a是0，b是1的情况，x这位是0对答案有贡献
所以对于每一个情况1，在$x \leq r$的前提下不断将x这位置1就可得到最终的x
CF1918D Blocking Elements
二分 单调队列 dp
给定一个序列，要求通过删去元素把序列分为的几段，同时删去的元素一起作为一段，要求使所有段中和最大的最小
最大值最小考虑二分答案，在序列头和尾分别设两个值为0的虚点，$dp_i$表示目前到第i个元素，并删除这个元素，此时被删除元素的总和的最小值，我们每次更新$dp_i$最好是选择某一块合法区间内最小的dp值，考虑单调队列维护这个值，当队头不合法时（队头和i之间的元素和超过二分的答案），不断弹出队头，每次使用队头的值更新此时的$dp_i$，并不断弹出比$dp_i$大的队尾元素，并把i插入单调队列，只要$dp_{n+1}$比此时的答案小，就继续更新答案
CF1921D Very Different Array
贪心
从B里选n个作为数组A，使$A_{1…n}和C_{1…n}$对应位元素差的绝对值之和最大
考虑先让B里最大的对应C里最小的数，这样B里会剩下一些最小的数，同时发现这样每次产生的贡献使递减的，同时最后可能会有B中的数比C中的数小的情况，所以我们再倒着用B里最小的数去对应C里最大的数，这样每次更新答案只用变换一个位置的值，不断更新答案的最大值即可
CF1921E Eat the Chip
贪心 结论
Alice可以往下，左下，右下走，Bob可以往上，左上，右上走，Alice先手，问谁赢或者平局
贪心地想，两边同时向左，同时向右，一左一右都不影响横向距离的奇偶性，即不影响最后谁赢，只有纵向距离的奇偶性影响结果，所以纵向距离为奇数时，bob必定会考虑保平，反之同理
考虑保平的情况，显然游戏结束的时间时确定的，即双方纵向位置相同的时候，此时不能吃掉对方就一定平局，所以直接考虑不可能赢的那方在结束前最远能到达左边或右边的哪个位置，再看另一方能否也到达那个位置，能到达就赢，否则平局
CF1922A Tricky Template
贪心
给定一个字符串s，称满足以下条件的小写字符串t是符合题意的
1.如果s第i位是小写，t这一位必须和s一样
2.如何s第i位是大写，t这一位必须和s不一样
给定符合题意的字符串a，b ，和不符合题意得字符串c，问这样的t是否存在
如果a，b，c这一位不一样，只要让t这一位和c一样并大写即可
如果a，b这一位一样，和c不一样，只要让t这一位和ab一样并小写即可
CF1922B Forming Triangles
组合数
给定n个木棍，第i根木棍的长度是$2^{a_i}$，问选三根木棍组成三角形有多少种方案
首先发现木棍的长度都是2的幂，显然想组成三角形就只能组成等边三角形，找到每种长度的棍的数量求组合数就行了
CF1922C Closest Cities
贪心
n个城市在数轴上，有两种移动方式
1.移动到任意城市，代价为两城市间的距离
2.移动到最近的城市，代价为1
q次询问，问从a到b的最小代价
发现对于每个城市，发现在只考虑往一个方向走的情况下他和离他最近的那个城市的距离可以压成1，然后显然我们每次询问肯定都是往一个方向走的
考虑向左和向右走两种情况分开做，预处理出新的位置，然后询问时直接位置相减算答案
CF1922D Berserk Monsters
贪心 set 链表
每个怪物每轮会被他的邻居攻击，每轮结束时，受到的伤害大于防御的怪物会死亡，问每轮死亡的怪物数
每一轮结束后，如果一个怪物这一轮没有死，且他的邻居也没有死，那他下一轮也不会死（受到和这一轮一样的伤害）
所以我们考虑每轮结束时，把死亡的怪物加入set，显然下一轮我们只要更新这些怪物的邻居的答案就行了，更新答案的总复杂度最差为O(3n)，找邻居和删除的过程用链表实现
CF1923A Moving Chips
贪心
一个1可以被移到最左边最近的空格，问把所有1连起来的最小移动次数
显然删除前导0，后导0，剩下的0的数量就是我们要移动的次数
CF1923B Monsters Attack!
贪心
每秒发射k个子弹，任意分配，每发子弹造成1点伤害，数轴上n个怪物，每秒向原点移动一格，如果任意一秒结束时原点上有存活的怪物则失败，问能否杀死全部怪物
先把所有怪物按离原点的距离排序，考虑按秒模拟，每秒射出的总子弹数增加k，并减去这一秒到达原点的所有怪物的血量值，如果出现子弹数不够则失败
CF1923C Find B
贪心 构造
一个长度为m的序列a是好的当且仅当存在一个长度为m的序列b满足
1.a的和等于b的和
2.a和b每一位均不相等
3.b每一位都大于0
给定一个序列c，q次询问，每次问c的一个子段是否是好的
显然有一种贪心的构造法，我们考虑c的这个子段里有多少个1，对于这些1，我们构造2，对于剩下不是1的，我们全部构造1，然后如过此时总和还不够，就把少的全部任找一个2加进去，如果不能这么做则这个子段就是不是好的
CF1923D Slimes
贪心 二分 前缀和
n个史莱姆，每秒有且只有一只史莱姆吃掉一个大小严格小于他的邻居，且大小变为两者之和，n次独立询问，问每只史莱姆最早第几秒被吃掉
一个重要的性质，假设一个史莱姆i最终被j吃掉，而j在吃i之前一定吃了包含j的一个子段里的所有史莱姆，然后我们发现，找到j等价于找到这个子段，而这个子段一定是在i的左边或右边且与i相邻，且和正好大于i，即不用去考虑j吃掉i的具体过程，$ans_i$就是这个子段的长度，所以问题转化为对于每个i，找到他左边或右边最短的总和大于他的子段，前缀和+二分即可，总复杂度O(nlogn)
CF1945B Fireworks
结论
观察样例发现答案就是$m/a+m/b+2$
CF1945C Left and Right Houses
前缀和
前缀和统计1的数量，枚举断点即可
CF1945D Seraphim the Owl
贪心
假设从i交换至j，发现有两种交换途径，一种是每次只前进一格，这样每次代价为$a_{i+1}$，或者前进x格，那么代价为$\sum_{p=i+1}^{i+x-1}b_p+a_x$，发现这两种前进方式是灵活的，如果这一步不是终点的话，我们的代价是$\min(a_i，b_i)$，因此从i交换到j的最优解是$\sum_{p=i+1}^{j-1}\min(a_p，b_p)+a_j$，倒着累加即可
CF1945E Binary Search
结论
考察了二分的性质，对于我们瞎跑出来的l，可以发现有$p_l \leq x$，这是给出的描述决定的，然后发现如果我们把此时的$p_l$换成一个不大于$x$的数，显然对l的位置也没有影响
所以我们直接在原序列上跑题目给出的二分，然后把$x$的位置和跑出来的$l$交换即可
CF1945F Kirill and Mushrooms
贪心 set
首先为了方便处理不能选的情况，把原序列按$i_{s_j}$从小到大排序
依次考虑选$k$的个情况
假设我们要选$k$个，那么最优的做法肯定是从可以选的$n-(k-1)$个里选$k$个最大的，可以考虑从选$k-1$个的情况转移来，我们考虑开两个set，把没选的扔进unselect里，选了的扔进select个里，当我们准备选第$k$个的时候，根据题意此时排序后的第$k-1$个就不能选了，如果他在unselect里，就把他删了，然后再选unslect里最大的移到select里，如果他在select里，也把他删了，再从unselect里选最大和次大的移到select里，可以发现这样单次更新答案是logn的，unselect空了就结束，每次更新答案时统计最大值即可
gym104090M ICPCHZ2022 M. Please Save Pigeland
换根 线段树
缝合怪题，给定点集$S$，要求在树上找到一个点$u$，使得$\frac{\sum dist(u，S_i)}{gcd(dist(u，S_i))}最小$
考虑换根，我们先求出$u$为1的情况，然后以1为根开始换根，发现我们每向经过一条边$E(u，v)$，对答案产生的影响是$v$子树内的所有特殊点的$dist$全部减去$dis_{E(u，v)}$，其余的特殊点全部加上$dis_{E(u，v)}$，考虑记录以1为根的每个点的dfs序，可以发现一个点子树内的点满足$dfn[u]\leq dfn[v] \leq dfn[u]+siz[u]-1$，可以把特殊点按dfs序排序并每次通过两次二分求左右端点的方法得到哪段是要被减去距离的，我们需要一个可以维护区间加减和区间gcd的数据结构，考虑线段树，由gcd的性质得知一个序列的gcd等同于这个序列的差分的gcd，问题转化成单点修和区间gcd，所以每次换根的时候，用线段树维护差分数组，并统计整个特殊点序列的gcd计算答案即可，总复杂度$O(nlog(n)log(V))$
CF1956F Nene and the Passing Game
set 思维
因为能否传接球的关系是双向的，不妨设$i>j$，把给定的式子化简一下，可以得到
- $i-l_i \geq j+l_j$
- $i-r_i \leq j+r_j$
可以在保证1式成立的前提下考虑2式，我们可以把n个人拆成权值分别为$i-l_i$和$i+l_i$的2n个点，再把这些点按权值从小到大排序，这样我们就能保证每个点对前面的所有点都满足1式，同时我们可以把权值为$i+l_i$的点视作修改，把权值为$i-l_i$的点视作询问，每当扫到前者时，我们往一个递减的set中插入该点，权值为$i+r_i$，这样当我们扫到代表询问的点x时，只要不断从set头中取出满足$x-r_x \leq i+r_i$的点i与x组成连通块，并从set中删去该点，连完后再把整个连通块的根塞回set里，最后统计连通块的数量就可以得到答案了
同时我们注意到，对于一个连通块，我们只要看他最大的$i+r_i$的值，所以只要把第一个取出的点作为整个连通块的根即可，因为我们保证了set中第一个取出的点一定是全局$i+r_i$值最大的
CF1942A Farmer John’s Challenge
结论
对于$n=k$ 显然全部输出1就行了
对于$k=1$ 显然先输出n，再依次输出1~n-1即可
对于$1<k<n$，发现一个有序序列只要平移一次一定会变成无序的，所以这些都是不可能的情况
CF1942B Bessie and MEX
贪心
由于mex和排列的性质，考虑倒着做
对于$ans_n$，显然此时的mex为n，直接可以算出$ans_n$，当知道了ans_n后，$ans_{n-1}$的mex显然就是目前的mex和$ans_n$的值取小的那个，不倒推即可
CF1942C Bessie’s Birthday Cake
贪心 思维
考虑y=0的情况，把给定的点连成多边形，对于一个多边形，其内部能划分出的三角形个数就是其边数x-2，然后我们发现如果两个给定的点之间夹了一个未给定的点，这种情况也能组成三角形，所以就是统计距离为2的点对的数量ans,最终答案是ans+x-2
当$y \neq 0$时，我们要不断构造上面所说的距离为2的点对的情况，这也能分两类讨论，当两个相邻的给定点距离大于2时，根据画图找规律可以发现，在把间隔按照中间每隔一格赛一个点的规则填满时，当距离（$a_x-a_y$）为偶数，一共可以填$(a_x-a_y)/2$个点，产生$(a_x-a_y)/+1$个三角形，当填不满时则少一个，当距离为奇数时，可以填$(a_x-a_y-1)/2$个点，产生$(a_x-a_y-1)/2$个三角形，所以我们先填距离为偶数的间隔，并先填短的，注意处理未填满的情况即可
CF1957B A BIT of a Construction
贪心
直接从低位到高位枚举$a_i$并将k减去$a_i$即可
CF1957D A BIT of an Inequality
思维 二进制
我们把原式展开，首先可以的到几个结论：
- 当x=y=z时肯定不符合题意
- 原问题等价于，对于一个区间的异或和$pre_{l…r}$，问这个区间内有几个数$a_i$满足$a_i \bigoplus pre_{l..r} >pre $
- 进一步分析2，发现2等价于，要求$a_i$的最高位对于$pre_{l..r}$而言，该位为0
发现如果枚举区间复杂度无法接受，考虑对于y寻找可能的x，y，即区间的左右端点，从左往右枚举y，考虑分别记录y左边至0，y右边至n有多少个$pre_i$第j位为0或者1，假设j为$a_i$的最高位，我们只需简单使用乘法原理（cnt0之间相乘,cnt1之间相乘）就可以得到有多少对$pre_r \bigoplus pre_l$满足题意
实现过程中注意，开始应该把所有点都扔进右边的桶里计数
在计算$a_i$的答案时，考虑到实际的区间左端点是$l+1$，所以我们先算答案，再把$pre_i$从右边的桶移到左边的桶，这点通过画图可以得知
CF1966A Card Exchange
贪心
发现我们只关心一次换了k-1张牌，不关心牌具体的情况，所以最优策略就是每次换当前数量最多的，换过来的k-1张牌存进tot里，遇到不够换的时候拿tot补，最后没法换了把剩下的总牌数加上剩下的tot就是答案（注意最后tot和k-1取min）,开个堆瞎搞即可
CF1966B Rectangle Filling
思维
发现对于一种颜色，我们相当于是选一条对角线代表的矩形涂色，我们考虑看对于每个颜色，显然它在x轴上最多只能涂到x值最大的同色块那么远，然后x轴和y轴的答案显然是不干扰的，所以要全部涂成同一颜色，我们只要看对一个颜色，它最小的x值和y值是否为1，最大的x值和y值是否为n和m即可
CF1966C Everything Nim
博弈论
对于每轮游戏，选择一个最多不超过最小石子堆石子个数的正整数k，并将每个堆都移去k个石子
因为每次移的个数有上限，而且还是对所有的堆都移，考虑每轮最多能移几个，发现问题等价于对原序列排序后的差分数组进行移石子，且遇到0全部跳过（显然），而且只能从左往右移，然后考虑先后手，当目前堆石子数大于1的时候,先手的那个人可以选择全部移走，或者留一个，意味着他可以决定在移下一堆石子是自己是先手还是后手，也就是再之后遇到1时的强制交换先后手对它没有影响（这点手摸可以发现），所以我们只要考虑遇到第一个大于1的数时谁是先手，也就是统计去0后的差分数组里连续的前导1的数量（不包括差分数组最后一位的数），偶数Alice，奇数Bob
CF1966D Missing Subsequence Sum
构造
看到串的长度小于25，考虑二进制分解，我们可以构造一个1,2,4…的串，同时这个串不包含k最高位的1，这样我们就确保了对于这一位是1的所有数都凑不出来
然后考虑如何凑出这一位是1的，且不等于k的其他数，假设这一位为i，串中比它低的位的和加起来是$2^i-1$，那我们如果放一个$k-2^i$，它与前面这些数加起来就是k-1，根据二进制分解的原理我们确保了1…k-1都可以凑出来,然后我们可以暴力添加一个k+1，那么这个k+1与我们前面已经构造出来的1…k-1就可以凑出k+2…2k,
CF1969A Two Friends
贪心
有长度为2的环答案就是2，否则是3
CF1969B Shifts and Sorting
贪心
手玩发现对于1100，我先操作$s_{1…3}$再操作$s_{2…4}$和直接操作$s_{1…4}$结果是一样的
问题就化为从左往右，对于每一个1，把他和他后面遇到的第一个0交换位置（以这两个数为端点执行一次右移）
注意到我们这么做的实质是不断把1后面的0提到最前面，所以我们只要记录第一个1的位置pos，然后每次操作后pos+1就是下一个1的位置，所有的1是很自然被排到一起的
CF1969C Minimizing the Sum
dp
一次操作可以把一个数左边或右边的邻居替换为它，问最多操作$k (k \leq 10)$次后整个序列和的最小值
发现k很小，考虑预处理以i为右端点，i-j为左端点,操作j次产生的贡献$v_{i,j}$,以i为右端点可以方便处理后效性的问题
自然想到dp数组$dp_{i,k}$代表前i个数操作k次产生的最小贡献
考虑如何转移，假设我们在i处操作j次，此时总共操作了k次，$dp_{i,k}$显然就要从$dp_{i-j-1,k-j}$前面的状态转移来，然后我们肯定要从前面里选一个最小的,所以$mindp_{i,j}$表示$dp_{1…i,j}$里最小的值，转移方程就是$dp_{i,k}=min(dp_{i,k},mindp_{i-l-1,k-j}+v_{i,j})$，记得每次转移完后更新$mindp_{i,j}$,并且$mindp_{i,j}$在进入第一次转移前初始化为$mindp_{i-1,j}$，dp入口为$dp_{0,0}$，因为没说一定要选k次，所以dp和mindp初始化全0即可
CF1969D Shop Game
贪心
选任意个物品，alice可以以$a_i$的价格买入,并以$b_i$的价格卖给bob，bob可以选择不超过k个物品免费拿走，bob希望alice的总收入最少，alice希望最多，问alice的最大收益是多少
对bob来说，显然他会拿走alice的物品里$b_i$最大的k个，所以我们按b从大到小排序，可以将原序列分成两部分，对于一个$i(i>k)$，它左边需要选k个a最小的的让bob拿，并且其他的都不拿，右边则是a>b的全拿，然后我们往右枚举这个断点并每次统计答案，左边拿一个优先队列维护前k个最小的a的和即可，右边先对$b_i-a_i$求和，然后不断减掉即可，对于左边为什么不用选超过k个，我们考虑，因为bob的行为其实是固定的，对于alice一个物品都不移除的情况，bob实际上就是选第1…k个免费拿，当断点移动到k+2的时候，如果我们不移除k+1，实际上bob还是拿1…k，而不移除k+1的情况在断点为k+1时已经计算过答案了，所以只需要保证左边留k个，其他全移除即可
CF1972A Contest Proposal
暴力
按题意模拟即可，答案最大不会超过n
CF1972B Coin Games
思维 结论
n个硬币排成环，可以对朝上的硬币进行操作，若硬币数小于2则直接删除这个硬币，否则删除这个硬币的同时翻转相邻的两个硬币，无法操作的人输
发现对于所有的情况，朝上的硬币数要么一次减少3个，要么减少1个，要么增加1个，所以每次操作都会改变朝上硬币数的奇偶性，最后把数量变成0，即偶数的那个人赢，所以开始朝上硬币数为奇数时alice赢，否则bob