Day1

A. [NOI2024 模拟赛 Day 1] 加一2.5

对偶问题,则转化为每个位置有一个变量$x_i\ge 0$,要求$\sum_{j\ge i} x_j \le suf_i,\sum_{j\le i} x_j \le pre_j$,最大化$\sum_i b_ix_i$.

容易想到考虑前缀和,则限制变成$s_i\le s_{i+1},s_i\le pre_i,s_n-s_i\le suf_{i+1}$,注意到答案关于$s_n=\sum_i x_i$是凸的,所以直接三分它,后面是Slope Trick.

B. [NOI2024 模拟赛 Day 1] 快速排序

C. [NOI2024 模拟赛 Day 1] 可达点对

课

loj4138. 「PA 2024」Dzielniki

考虑若已经知道了$x+c$是$2^t$的倍数,尝试知道它是不是$2^{t+1}$的倍数,如果不是再加上$2^t$显然就是,于是可以令$t\gets t+1$递归上去.要判断是不是$2^{t+1}$,在$t$较大的时候问因数个数然后分解质因数下有大概率正确,不行就多问两项.而较小的情况下不对,比如$t=0\to t=1$,于是先一直随直到有一个稍微大一点的比如$t=3+$的去判.

感觉就是没有顺着$d$的性质走,而是用一些大概率对,小概率不对的东西,然后多跑几项判?

loj4134. 「PA 2024」Desant 3

考虑如果某一条指令对应的是一个$1$一个$0$,都会统一成$10$,此时把这两个取反是没有区别的.

于是直接搜,有些位确定,有些位没确定,然后当前拿到一条指令,如果只有一位确定,那另一位只有一种情况有必要搜,否则没有区别会消掉,只有两个都不确定的时候你会搜$00$或$11$的情况,于是每次确定两位,复杂度$m2^{n/2}$,然后就做完了.

loj4133. 「PA 2024」Kolorowy las

首先如果没有link-cut,我们直接点分树,复杂度俩log.如果先染色后查询是1log.

哦然后你可以倒着做,碰到染色就把周围的点拿出来回答查询,这样只要支持每次找一个点周围最近的询问,然后上一个lct,找最近点的话就直接把当前点变成根,然后要能维护子树深度最浅点,所以需要套set.这实际上是个AAAtree.复杂度俩log.

toptree!1log了.

树分块!容易发现一个大于$2B$的块可以被分成两个块且保证大小限制(关于边分块,关于点可能不能分成符合要求的两部分),可以$q\sqrt n$.

P10353 [PA2024] Grupa permutacji

[conclusion] 对于置换生成的对称群,任取若干个位置,它们的取值对$(p_{i_1}\ldots p_{i_k})$是均匀的,即每种的方案数相等.

于是拿出$(i,j)$,则经过一次置换后会变成$(p_i,p_j)$,然后连边(由于把一个置换重复若干次就是逆,所以双向边),然后若一个连通块里有$a$个$p_i<p_j$的和$b$个$p_i>p_j$的显然贡献期望$\dfrac{ab}{a+b}$.

这样做复杂度$n^3$,然后第二个结论是只保留$\log n$个就可以得到这个图,需要像loj177 一样进行一些随机复合破坏性质.

Day2

模拟赛

A

发现进行若干次变换后,$a’=-pqa+p(p+q)b+q(p+q)c$,每次操作是$(p,q)\to (p+q,q),(p,p+q)$.

确定$p,q$后辗转相除.

可以同除$pq$使得变成关于$\dfrac{p}{q}$的方程组.

B

容易想到burnside,问题变成对于一个排列算答案,就是边$(i,j)$连边$(p_i,p_j)$然后算连通块数,这个显然是环,其实就是两个环合起来,那么设环长是$a_1\ldots a_k$,则环数就是$\sum_{i\lt j} \gcd(a_i,a_j) + \sum_i \lfloor \dfrac{a_i}{2}\rfloor$.而这组环长对应的排列数是显然组合数.这个直接搜划分数然后卡常可以过$n=96$,好像每次搜一个值的比每次搜一个快.

考虑meet in the middle,划分数拆成$P_{\ge B}$和$P_{<B}$这样的,只有$\sum_{i\lt t} \gcd(a_i,a_j)$是跟两边都有关的,算这个我们只要知道$f_i=\sum_{j} \gcd(i,a_j)$,所以把$f$作为状态发现不多就行了.

C

课

Day3

模拟赛

C. [NOI2024 模拟赛 Day 3] 优先队列

容易发现到是$A$按弹出顺序的后缀最大值限制了填法,设后缀max的值为$a_1\ldots a_k$,位置为$p_1\ldots p_k$.对于一个后缀max $a_i$,有$<a_i$的非$A$集合的数不能在它前面,然后大于$a_i$的$A$集合的数不能在$p_{i-1}$后面.

一维是限制往前一维限制往后是不能简单处理的(赛时考虑容斥可以得到$n^{6,7,8}$做法).考虑把非$A$集合的数限制变成,在$p_i$前面的数值必须大于$a_i$.

于是可以dp,$f_{i,j,k,0/1}$表示考虑前$i$次操作,当前堆中有$j$个$A$集合的数,当前位置往后碰到的第一个后缀max为$k$,$k$是否在堆中,然后在+处计算非$A$集合数的贡献,在-处,若$j=1$且$k$在堆中时说明弹出了一个后缀max,枚举下一个后缀max$l$并计算值在$[l,k]$中的数的贡献,转移是$O(1)$的.复杂度$n^3$

课

CF1989F Simultaneous Coloring

显然每行/列最多被染一次.考虑一个点为红表示染行在染列之后,那么列向行连边,为蓝相反,于是形成一张二分图.此时如果是DAG显然可以一个一个染,否则发现一个SCC必须同时染,所以答案就是每个大小大于$1$的SCC大小平方和.

但是不能暴力跑,考虑只有加边的话可以维护SCC合并的过程,那我们要知道加入哪条边后导致SCC合并了,这个可以考虑整体二分,考虑现在要求图$G$的答案,图$G$中每条边的出现时间在$[l,r]$中,那么加入$[l,mid]$的边跑tarjan,然后把SCC作为新的点,得到一张图递归到$[mid+1,r]$,把每个SCC内的边拿出来递归到左边即可.

复杂度$(n+m)\log q+q\alpha(n)$

Gym105112B

要求构造方案.

考虑假设已经填出第一行$w=\sum_{i=1}^k a_i$,尝试得到第二行,一个朴素想法是把第一个和最后一个换一下,不妨设$a_1<a_k$,但这个方案可能仍然不合法:若仍然存在两前缀相等,容易发现一定有$a_k=a_1+\sum_{i\in S} a_i$,那么在第一行中就把这些元素都替换成$a_k$,重复下去,必然有合法了或者全都变成了$a_k$.

如果全都变成了$a_k$,那么考虑撤销最后一次变换,那么撤销最后一次一定有一个集合$\sum_{i\in S} a_i=a_k$,此时把集合中一个元素放到最前面作为第一行,第二行全都填$a_k$,就是合法的.

但暴力替换是$n^2$的,考虑直接找到一组使用最大块最多的方案即可.这个用bitset做就好了.

Gym105139C

考虑把划分成若干矩形变成切若干刀,那么有$\text{Cut Times}=\text{Rect Count}+\text{Circle Count}$,因为对于一个环需要一刀断开.

考虑找到所有$270°$的外角,容易发现每刀会消掉一个或两个,消掉两个当且仅当同行同列,就是找一个不交的匹配.那么把每种可能的匹配边拿出来,不能同时选的之间连边,就是最大独立集.同时只有横的匹配和竖的匹配之间有边所以二分图转匹配即可.

Day4

模拟赛

C

JSC2023 Final G Fusion

$xy+1$是有意义的,考虑组合意义,发现如果我们让每个合并后的点代表一个连通块,建树,那么算的实际上是这棵树的连通块数(包含空),且每个叶子节点有$a_i$种方案.于是考虑枚举一个连通块,发现他的权值就是它包含的叶子(即原树上点的乘积).那你其实可以把包含相同叶子集合的一起做,于是问题就变成了每个原树上点染色黑/白(即是否选入连通块),然后每次合并两个颜色相同(因为方案包含空点,所以白点成对出现)的点,选择他们的颜色(黑点合并为黑色,白点合并颜色任意).

然后就是这个怎么数,此时我们不关心点权只关心颜色,想到Shrinking Tree那个题

Day5

模拟赛

课

P10441 [JOISC 2024 Day4] 乒乓球

P10433 [JOISC 2024 Day2] 棋盘游戏

首先注意到第一个人是关键的,设它经过$a$轮共走$b$步到达$T$,则其他每个人的贡献可以写作仅有$b$确定的函数$f(b)$,其他人都只是要尽量快的结束自己的回合,只会有两种行为:第一轮走到一个终止位置,然后每次离开一步再回来,此时$f(b)=2x+d_i$,先用$s$轮,$t$步走到一个相邻两个终止位置,以后每次走一步,有$f(b)=(x-s)+t,x>s$,注意到$(x-s)+t\ge 2x+d_i$得到$x\le t-s-d_i\ge s$,因为必然有$t\ge 2s+d_i$.于是每个人的贡献$f(b)$是分$2$段一次函数,且只要计算$t-s$,这个直接给终止点赋值$-1$,边赋值为$1$跑bfs即可.

然后求出所有点的贡献之后要考虑$1$,$1$一个走法是走$a=a_0,b=b_0$,$a_0$是最小合法解,这个是容易求的,因为$b_0-b\le n$,$a$的答案比$a_0$至少大$(k-1)(a-a_0)$,于是$a\le a_0+\dfrac{n}{k-1}$.

于是若$k>B$,只要把走了几个终止点也放到状态里去最短路复杂度即是$\dfrac{n^2}{B}$.

对于$k<B$,注意到段数不多,此时对每一段直接让终止点权值为斜率,边权值为$1$去跑,取最小值既是答案,因为容易发现算错的一定不优.

Qoj7514. Clique Challenge

容易发现最大团大小$k<\sqrt{2m}$.先考虑给定$n\le \sqrt{2m}\le 44$的时候怎么做.

这个数据范围显然meet in the middle,考虑已经处理了两边各自的最大团,那么枚举左边的一个最大团,算出他们点连到右边的集合的交集,则这个交集内的可能是最大团,跑高维子集和即可.

那么现在$n$大了,考虑分成若干个小部分,一个很神秘的做法是我们拓展三元环计数的做法:按照度数把边定向,度数小指向度数大,容易分析出一个点的出度最大为$\sqrt 2m$,于是枚举一个点,对他的出边集合数团数,相当于每个团在拓扑序最小的位置数了.

Qoj6308. Magic

又是必要猜充要题.

考虑若存在区间$[l_1,r_1],[l_2,r_2],l_1<l_2<r_1<r_2$,那么若$(r_1,r_1+1)$贡献就要求$2$比$1$先操作,若$(l_2-1,l_2)$贡献要求$1$比$2$先操作,于是给这两个点连边,则最后选的显然要是图的一个独立集,这是必要条件.

考虑如果选择了一个独立集,那么如果有环,比如选了$[l,r]$的$r,r+1$贡献,那么一定是要求$[l’,r’]$使得这个区间要先执行,而若$l<l’<r<r’$,因为独立集不会选$l’$,所以一定是又钦定了$r’,r’+1$贡献,则这个共线点一定是单调右移的,不会成环.

显然是二分图,bitset优化匈牙利/线段树优化建图后dinic 即可.

CF1844G Tree Weights

考虑从低到高逐位确定,先确定模$2$的情况,那么此时$dis(u,v)=dis(1,u)+dis(1,v)-2dis(1,lca(u,v))\equiv dis(1,u)+dis(1,v)$,于是相当于让若干个$d_u=dis(1,u)$相同/不同,可以直接确定.

然后若确定了模$2^k$的情况,发现容易用相同的方法确定模$2^{k+1}$的情况,就做完了.

[AGC057C] Increment or Xor

建出01trie,我们都知道实际上相当于选择某些层交换子树或者对这个树的右链交换左右儿子.

那么异或一个数,$+1$,再异或一个数,就可以交换任意一条链的左右儿子.

考虑我们始终是要交换左右儿子,所以若当前的树和目标不同构一定无解,否则可以得到每个点是否需要交换,设为$c_u=0/1$.每次可以链翻转$c$和层翻转$c$,要求最后全都变成$0$.

那么枚举是否翻转最后一层,然后就知道了链每个最后一层点是否要翻转,转掉之后check是否每层$c$相同即可.

Qoj8552. Sticks

画一下图,发现可以找到一条左上到右下的线把图分成上下两部分,上面部分只通过列覆盖,下面这部分只通过行覆盖.考虑对这条线dp.为了不数重显然钦定这条线是所有线中最靠上的一条.

需要明确我们的限制,若钦定这条线在第$i$列高度为$h_i$,则要么$h_i$这个格子被从上到下的格子覆盖,要么$h_{i-1}=h_i$,于是可以设$f_{i,j}$表示上半部分最后一个位置是$(i,j)$的情况下,前$i$行和前$j$列的方案数.(其实就是dp这条线吧!)

[AGC057E] RowCol/ColRow Sort

todo

Day6

模拟赛

B

考虑怎么判定一个能不能到另一个,我们试图贪心构造,考虑最大值如何移动,它可以移动到后面的任意位置,如果目标位置在前面肯定寄了,否则考虑它要走一个什么路径移动过去(显然,他的移动过程中会选择若干个元素,把它们往前循环移位).我们肯定希望尽可能多的保留逆序对,于是选择所有位置$i$满足$p_i$比后面的元素都大,移动这些位置.可以$n^2$的判断了.

考虑扩展这个判定,把所有排列放到一个自动机上使得自动机上$a\to b$当且仅当$a$可以转变成$b$,且若$a,b$路径唯一.对于路径唯一的问题是容易dp的.

考虑一个排列操作的第一步会是什么,它应该由当前排列,已经操作了$>x$的值现在要操作$x$,$x$的目标位置$y$ 确定而如果$x=y$它应该连到

Day8

模拟赛

A

注意到对一个$[1,i]$前缀操作完后,最后$k-1$个数(即$[i-k+2,i]$)一定是最大的$k-1$个数.

考虑一轮操作,先把$[1,k]$排序,然后每次加入一个元素,则如果它不是前缀max我们要操作一次把它向前移动到$[i-k,i]$中第一个比它小的数的后面,于是一轮的贡献是$[[1,k] is ordered]+\sum_i [p_i>\max_{j<i} p_j]$.

发现一个位置成为前缀max之后,不会再变成非前缀max.一个前缀$p$经过$1$轮操作后,数集是前$p+k-2$减去前$k-1$大,经过$c$轮后是$p+c(k-1)-1$减去前$c(k-1)$大($c(k-1)$如果超过$n-p$就用$n-p$).前缀$p-1$和前缀$p$的数集的差显然就是$p$处的值.于是一个朴素想法是枚举每一个前缀$p$二分$c$,然后看$[1,p-1]$经过$c$轮后的最大值和$[1,p]$经过$c$轮后的最大值,而这也就是求前缀$kth$,容易主席树树上二分做到整体1log.

B

考虑拆贡献,那么即求$\max \sum_{v=1^n} (\sum_i [A_i\ge v])(\sum_i [B_i\ge v])$.由于$\sum_i [A_i\ge v]+\sum_i [B_i\ge v]$确定,问题即$\min \sum_{v=1^n} (\sum_i [A_i\ge v]-\sum_i [B_i\ge v])^2$,

看起来仍然很不可做,考虑它的下界,当然是所有偶数处是$0$,所有奇数处是$1$.尝试达到这个下界,即数轴上有$n$对点,要给每个点赋值$-1,1$,每对点值不能相同,而要达到下界就是rank为$2i-1$和$2i$两个点值不相同.用边$(u,v)$表示$u,v$不同,那么发现图是二分图(每个点度数都是$2$,且恰好有一个$A_i\ne B_i$的边和一个rank产生的边),于是一定可以染色达到下界,就做完了.

C

考虑最简单的暴力是$f_{i,A,B,C}$表示我们让$i$个点变成$1$,其余点是$0$的部分方案数(部分方案数就是某些系数乘起来,单看他们可能找不到简单的组合意义),且这$i$个点内已经使用过的边集是$A$,$1$的点和$0$的点之间已经使用过的边集是$B$,仍然是$0$的点之间的已经使用的边集是$C$.

容易注意到我们不关心$A$的具体内容而只关心它的大小.

而$C$也只记录大小就能转移,要记录$C$时因为当我们把一个新的点变成$1$的时候,我们需要知道它有多少条边没被选要加入$B$中,而这点可以这时再枚举用了几条边计算贡献.

对于$B$,发现只要记录每个点的度数,且不关心具体的点所以是度数集合.

这样状态做到$2^nn^4$,然后转移的时候要另一个dp,分配新变成$1$的这个点的边要如何加入$B$中并计算贡献.复杂度$2^nn^5$.