夏晓光(loveJY)的博客

T1

0~n-1的三个排列,问是否能找到一种排列方式满足$a_i+b_i=c_i(mod n)$

偶数无解,左右和不相等

因为左边是0,右边是一个不是n的倍数的数

奇数直接0,1,2,3,4....排着加就好了,得到每个位置是2i

2 mod n不同余

所以每个数乘上一个不同余的数还是不同余

T2

2^n-1的完全图,你要找出尽量多没公共边三元环,$2^n<1000$

这个答案等价于 两个三元环中 任意两个元素 不相同的构造

然后我们考虑这个构造是能卡到上界的,就是能构造到边数/3个三元环

就是$\frac{(2^n-1)(2^n-2)}{6}$

具体方法就是对于x^yz=0的三元组,我们把它加入答案

因为一条边确定了,在这个构造中其余两条边也就唯一确定了,而且不会确定到其他case

所以可以证明这些两两不交

又因为固定了x,y后z唯一,所以我们仅枚举x,y能有$(2^n-1)*(2^n-2)$种方案

另外不难发现这样每个三元组被统计了6次,所以实际上我们是算了$(2^n-1)*(2^n-2)/6$,卡到了上界

T3

一个 2𝑛 个点的完全图，你需要把这些边分成 2𝑛−1 组，每组 𝑛 条边，且每组都是一个匹配（即任噫两条边没有公共点）

$𝑛≤1000$

假设两个点编号为x,y,钦定$0<=x,y<2n-1$

$x+y(mod 2n-1)=i$的x,y扔进组i中,考虑为啥不重复啊

首先显然一个边只能分入一组中,同时因为是$mod 2^n-1$剩余系,所以这个点显然也只能分入一次(匹配)

2n-1的连边怎么办啊

因为2n-1是奇数,那么对于每一个i,存在唯一的k使得$2k=i (mod 2n-1)$

所以k和2n-1的连边分入i组就是一组合法的解,这样2n-1就好啦

T4

n点完全图,从中选出尽量多不相交生成树,$n<=1000$

上界显然是$\lfloor n/2 \rfloor$

偶数怎么构造?

考虑归纳,已经构造好了n=2k case

n=2k+1是显然可以构造的

因为此时每个点都在每棵树中,所以我们只需要随便选择k个不同的点,然后连接上新点(2k+1)即可

注意这个是构造到最后的时候才能用,要不然下一步就没有2k的case了....

n=2k+2

先选1_{k这些点连上2k+1,k+1}2k连上2k+2,这样我们就把之前k棵树都加上了新的点2k+2,2k+1

然后我们还要多出一棵树,此时我们直接把k+1_{2k和2k+1连边,然后1}k和2k+2连边,然后2k+1和2k+2连边就好啦

时间复杂度就是快的

T5

答案是2n-2-凸包上的点数

证明是下界?

考虑用三角剖分,就是相邻层凸包之间的多边形三角剖分,这些是至少要满足哒

观察可知点数为$l_i,l_{i+1}$的相邻两层多边形三角剖分可以贡献$l_i+l_{i+1}$个

故这样是$l_1+l_2+l_2+l_3.....+l_k-2=2n-2-l_1$(最内层直接三角剖分即可)

构造方案?

随机一个方向p向量

然后在每个点附近+p方向-p方向无穷小距离放置一个点

这样所有三角形都能被覆盖啦?

你会发现三角形内角和180度,也就是完全覆盖了一个半平面

那么三个顶点中放置的点至少有一个是满足落在内部...或边上的!

不过发现落在边上的可以随机一个方向打败他!(如果真非就......)

然后我们可以把在最外面的凸包上的点外面防止的点删掉,所以用的一定可以减去外层凸包的

然后凸包最左边和最右边的点(严格来说是和p相切的两个位置)可以多删掉一个点,因为两个点都在凸包外面qwq

T6

考虑增量构造就是我们先构造好前i列都是key第i+1列怎么构造

移动方法很简单,我们可以把右边任意一个字符放到左边,加入我们现在要把这一列都变为k

i       j
k        
*      k
*
k
*

就是*右移到k这个位置,然后再上移j直到一个k在那个位置,然后再把这一行左移回去

不难发现这一行左边都没变

而后面所有列的k都不够了,此时我们有一些abc垃圾优先塞入这些不是k的空位上,然后ey尽量留着

除非e,y也够了,够了他们就是垃圾了,丢进去就好了

如果列数不是3的倍数,此时直接操作到最后一次能凑齐key的就停就好了,右边的不用瞎踢蹬

除非是3的倍数,最后一个可能凑不齐y了....

i j
e?
e(?)
e?
e[y]
?y
?y
??

只需要考虑两边都是小于n的,因为都等于n或者一个等于n我们不用动

转一下,一定可以找到一行满足最后两个位置都是垃圾,挪到最下面一行

使用这两个垃圾位置可以交换最后两列任意其他位置!!(),[]

第一次 把要交换的位置()下去,然后第二次最后一行右移一位,然后再把最后一列[y]移动过来,再左移一位

i j
ey
ey
ey
e?
??
??
[y](?)

然后我们再把最后一列移动到原来()的位置,然后再把y右移一位,然后最后一列还原原位置,然后最后一行左移一位,这样最后一行不会变化!

T6

*李队切了

我们会发现可以把序列分成n段,每一段n+1个数字,然后每次我们找到第二小的数字最小的段

把这一段最小的和次小的数字选入子序列中,然后删除这一段,同时把所有其他段里面小于这段第二小的数字全部删掉

那么你会发现,第一次操作最多删除n+1,删除n+1的结果其他的都就是删掉$1~n$,而且每个均摊删掉至多一个

同样的我们递归进行下去,所有其他段数字个数至多减少1,所以每一段不可能减少到0个!

所以必然有解

T7

有个 2𝑛×𝑚 的棋盘，有 𝑛×𝑚 个红格子和 𝑛×𝑚 个蓝格子。保证棋盘的左上角是红色，右下角是蓝色。你需要把蓝色格点中心两两连出一个向量，红色格子中心两两连出一个向量，你需要让这些向量之和为 0.

*李队切了

nm为奇数跑欧拉回路内部向量和为0

如果左上角时红色,右下角是蓝色,我们会发现可以直接去掉,剩下的跑奇数的情况,然后左上角连到所有
红右下角连到所有蓝的怎么搞成0

整张图中心对称一下,如果颜色不一样可以直接抵连边抵消

如果都是一样颜色的呢?同时向这个点连边,会发现这个向量的和是对角线,因为中心对称所以是整个斜对角线

然后会发现这样的点对数量是一样的,因为点数是一样的,所以相反的对角线数量相同,所以直接向两个点方向连就好了.....

这样做下去一定对角线也都消掉了,所以做完了qaq

这个有点过分巧妙

T8

给定一个环，环上每个点是三种颜色（RGB）之一，若一个点左右两边点的颜色不一样，你就可以任意改变这个点的颜色。
问能否在 10𝑛 次操作内，把一个环变成另一个。如果能，给出构造。
$ 5≤𝑛≤10^5$

关键在于你要发现这个操作是可逆的......所以我们只需要把两个环变成同一个中间状态

首先我们定义一个东西是破拆就是把一个有限制的变成任意位置都没有限制的

RBGRBG就是一个合法状态

首先暴力把两个都破拆后

我们考虑从1_{n扫,把他们都变成RBQRBQ}~

每次操作保证i-1和i+1颜色绝对不同,然后改变i即可,如果改变了i使得相同了,就先变一下i+2

这样可以保证任意时刻所有点都能够操作,直到合环的时候

你发现其实合环的时候也是可以的,因为我们这个目标状态是完全破拆态,所以不会导致夹死了n位置(n-1和1一定不同)

仔细数一下这个操作次数从一个环变到另一个环

就是4n的

T9

*李队切了

我们四方格考虑4次操作保证右下角格子是最大的,而且上面两个格子是无效的

无用行 :12

pos : 34

操作就是如果3位置大于4转一次,这样我们一行的较大值就移到右边去了

如果从下向上工作的话,你会发现我们可以把每一行的最大值集中到最右端,除去第一行和第二行我们无法操作!

然后我们想,把这些最大值集中起来,所以在最右列集中到顶部即可

然后再从右向左转第一行,就能保证最大值一直在最左边

然后再从第一行向下转一次,就能转到最后第一列最后一行

然后再把这个最大值从最后一行翻到最后一列就能确定好第一个位置了

但是第一列是不能放进2*2的矩阵的,就是你把第二列到第n列都放好后出问题了,没空位了

* ab
x cd

我们要把cd转到bd腾出一个位置

我们转c>b?abcd即可

但是你会发现我们可能相等,就是$c==b$

然鹅此时你会发现转不转都一样,等价的

怎么转回来,此时我们要把

bd
ac

转回去

12
34

编号不随着转动变

2>3?转一次

1>4?转一次

3>2?转一次

当2>3的时候转3次,否则会一次也没转,所以是等价的

注意我们没法维护最小值,但是可以按顺序排好最大值,n<=9

所以$n^6$是可以的

T10

2-sat

每个元素要么取上界要么取下界,这样显然合法

一般的元素上下界就是$[0,n]$这样

那么我们强行建出图,0/1表示取到这个点上下界,对于max,表示如果我取下界你取上界,我取上界你随便这样子,这个2-sat边是或边

min也是一样的,是或边,那么跑一个2-sat,可以知道一个连通块里面是一样的

所以直接弄2-sat然后跑个缩点拓扑图

你会发现跑tarjan进行的标号,其中最深的强联通分量显然就是拓扑序头头,然后一个个回溯就好啦

上下界找的方法很简单,就是所有max取min,所有min取max,显然是可以的

然后如果已经矛盾直接连我有了就好了

T11

非叶节点即出度为2的点啊,一开始是树的,结果直接树形DP就好了

这个有点玄妙

就是你考虑如果全是0/1值相等的时候我们可以直接判断出来:全部钦定1

然后如果0/1值不同,我们会发现(x,y是这个叶节点局面下根的取值)

0000000 x
1000000 x
1100000 x
1110000 x
1111000 y
1111100 y
1111110 y
1111111 y

这样的一个取值序列,中间一定会有一个时刻发生了变化

所以我们把那个位置外其他位置都钦定了,然后那个位置是0的时候和前一个一样是x,然后那个是1后面是y

所以我们直接二分这个位置检验即可....

答案就是n-1 qwq

这个正确性好像是微积分的区间套,连续变化

T12

如果没有一颗树的限制,我们可以考虑分治,log的时间确定一个边

具体的,这个点和前1_{n/2的问一次,和后n/2+1}n的问一次,这样子

一条边只会被问log次确定

但现在是一颗树,不妨把一些已知信息拿出来,然后用做差值呢

所以我们考虑能不能先确定1->2,2->3,3->4.....这些边是否存在

可以用点1,先问一遍1->2,2->3.....的边数

然后断开1和2的边,每次问一下1和别的点共n次,会发现要么是(第一次的值-1,第一次值)要么是(第一次+1第一次),前者是1->2一定存在,后者是1->2一定不存在

如果都相同,我们再问一下1所在的菊花图即可

从而确定1号点出边是否存在,然后根据点1来得到其他所有点的连边情况

就是每次断掉1->x,然后加入x-1->x来看这个答案对不对

再对于每个点来一个可爱的二分就做完了

T13

前两行前两列只要能削成0就完了,如果此时不能变为0就无解啦

证明:

123
456
789

然后我们会发现无论怎么操作,1+6+8位置的值和2+4+9位置的值和都是不变的(自己玩以下)

那怎么解决这两行这两列呢

就是两行上面的用对角线消,下面的用列消

T14

考虑值域分块,我们有一个很优秀的性质:整个序列的值域分块得到的每一段的子序列也是区间值域分块的每一段

就是说
1,2,4,5,6 9,10,11是整个的值域分块

那么区间的只能是1,2,4 9,10这样他的子序列

而又发现我们处理出每一块的值域分块的所有子序列对应集合然后一个询问直接合并根号次就好了

那么每次询问相当于下标在每个块中的提取出来合并,这个方法很简单,可以把开头找到然后查出前驱后继

就是下标在这块中的前驱后继

比如$1,8,9,7,2$在$5,3,1,2,4$和$8,9,7,6$

就是$1,2$,$8,9,7$

会发现我们就有$O(n/B*Q)$

怎么处理一个块内连续段??

按值域剖开预处理左右两端连续小段

按照归并排序似的方法

找到每个元素在原序列中下标,此时下标已经排好序了

然后从按照下标来归并,如果左边放进去了就和右边的都合并一次

$O((n+q)\sqrt n)$

T14

CF1364E

考虑我们随机一个数,然后把或出来的最小值都拿出来再随机一个数,操作一下,直到最小值是1

这样我们是期望减半的qwq,二进制位1的个数

这样我们期望是:n + \sqrt n +4^\sqrt n.....

但是我们还有n次询问,所以不卡常就完蛋了

这样的做法可以达到2n卡不满,因为只有第三种要额外花费,所以我们randomshuffle一下

虽然我们看上去这个做法是3n的,但是根据随机的理论,是可以随便过的

T15

CF1365G

有一个数组 A，你可以每次询问一些位置，会告诉你这些位置上数字的或。
你需要在 13 次操作内得到所有的 𝑃_𝑖 表示除了 𝐴_𝑖 以外其它所有数字的按位或。
$𝑛≤1000$

映 射

首先二进制分组很简单吧,就是拿下标二进制分组做

这样要20次操作,命没了

把所有13位的恰好有6个1的二进制数拿过来,显然可以做到满射

然后把每个二进制位为1的拿出来求一次或

那你会发现对于一个数x,他的表示有一些位置是0,那么把这些位置是1的数拿出来,然后他们或起来

你想,这样可能会有10110没有算入10010的case

然鹅,我们每个数的二进制下1的个数是相同的,所以不可能少算,那一位不同之后一定会有一位相同!

T16

CF1290D

卡 常 数

相当于找一个数字之前是否出现过

$\frac{k}{2}$一个块

每次考虑把前面的块放入队列,然后后面的块放进去查

这样复杂度是O(2n^2\k)

我们可以卡 常

枚举$i=1~\frac{2n}{k}$

然后每次把间隔为i的块加入队列

这样差不多我们有一个1/2常数

因为你会发现我们不需要把前面的块推出来再加入啦!

常数之和3/2

T17

CF1292E

询问CC,CH,CO,HO,OO

我们就知道所有C后面的和O前面的,这些把序列分成若干段,中间的都是相同字符,根据开头结尾判断即可

这样只有最后一个和前面一个没有确定,再花三次问出来就好了

但是4不对的!

T18

CF1288F

上下界费用流(?)

$S-[1,\infty]>R-r>T$

对于red,源点向其连下界为1

右边也一样,连接

中间的我们连接$(u,v,1,r)$和$(v,u,1,b)$

T19

CF1097E

g(P)表示把P划分为最少的上升子序列和下降子序列的个数

eg:123456 = 1

145236=1456+23=2

132456=1456+32=2

$f_n=max g_p$

上界是$1+2+3+....+x>n$的x

即$x*(x+1)/2>n$最小的x

根据dirworth定理,这个东西张这个样子

1 3,2 6,5,4 10,9,8,7

那么怎么构造一个小于这个的方案呢?

如果一个排列$LIS>f_n=x$

$n-=l$,那你会发现$<x*(x-1)/2$

所以这样n必然可以x-1次操作完成

如果$l<=f_n$

l就是最长反链

直接用LDSdp划分,就只用l次了!

复杂度就是$O(nlogn)$

T20

CF1227G||CF1261E

做过啊

显然可以变成矩阵,问题是每一行都要不相同

先排序保证数字不降

然后我们考虑有一个合法的方案是从i,i开始填,向下放a_i个1

怎么证明任意两行不同呢

首先你会发现对于$i->j$都会有1

那么对于i+1列,他一定是第i+1行开始填的,如果i和i+1行要相同,a_i+1就不能跨过第j列,那继续向下推

你会发现推到第j行我们能推出那个数是0,就没了

T21

模型转换换

黑色的是有球的,白色的无球,是坑

那么我们要把一个球放入另一个坑中

你会发现我们一个球会一路爬过去要先清空路中的球

考虑算贡献,对于一个点代表的子树向他父亲的边算贡献

那么对于这条边相当于我们要花费路径长度的代价才能实现一次操作

环套树,我们要讨论环的奇偶性

环是奇数,你会发现我们断开一条边后u,v深度奇偶性相同,等价于操作后我们会+2个球

那么也就是说我们可以对于这两个点同时+1/-1,多放入或者少放入球

有解当且仅当坑和球奇偶性相同,那么我们就可以

偶环,操作一次相当于把球扔进动或者抠出来

有解当且仅当坑和球数量相同

解法:

T22

矩阵中的数互不同

找等价操作

先分析一下这个操作下的不变量是什么。

首先一列里面三个数字要么是顺着的要么是反着的，它们不可能被分开。并且一次交换只能交换奇数位/偶数位中的相邻两个。

按奇偶位置分开，设 𝑓(1/0) 表示奇数位/偶数位上反转列数量的奇偶性，𝑔(1/0) 表示奇数位/偶数位的逆序对数量的奇偶性。

首先一次奇数位为中心的操作会让 𝑔(0)^=1,𝑓(1)=1，偶数位的操作相反。因此总有 𝑓(0)=𝑔(1),𝑓(1)=𝑔(0)。

接下来我们证明这是充分条件。

我们先把所有列不管正反先交换到对应位置上。然后设小写字母表示原来的列，大写字母表示反转之后的列：

就是说我们先把两列变成间隔为1的,然后交换回去就好了

上述构造证明了任意距离为 2 的两列都可以直接被反转。

由于奇偶性的保证，刚交换完时的 𝑓 必然和最终的 𝑓 相等，因此直接反转必然可以成为答案。

也就是说,我们奇数列/欧数列单独一定满足不符合的/翻转的位置写出来是

0111000111,其中有偶数个1

那么我们从左向右扫一遍,遇到一个1就翻转i和i+1即可

事实上如果 𝑛≤1000，可以输出方案，步数级别 𝑂(𝑛^2)。

不要求输出方案只需要球逆序对数量，直接 bit 即可（或者由于只需要球奇偶性可以做到线性）。

但是这题是判yes/no qwq