0%

ARC107F

题意

给出一张$n$个点,$m$条边的无向图,每个点有点权$A_i,B_i$。你可以选择若干个点删掉,代价为它们的$A_i$之和,然后对于剩下的每个连通块,获得的分数为其$B_i$之和的绝对值。

最大化收益减去代价。

题解

对于保留下来的每一条边,这条边连接的两个端点的$B_i$符号必然相同。注意到最后要最大化收益,因此可以去掉$B_i$的绝对值,相当于我们要给每个点分配$-1,0,1$,同时保证删去$0$点之和的每个连通块内所有点的标号相同。

对于原图中的每个点$i$,拆成两个点$i,i’$,连边$s\rightarrow i\rightarrow i’\rightarrow t$。割去这三条边分别表示$1,0,-1$。即一开始我们默认所有点的权值都是$B_i$,然后根据最小割的定义给这三条边分配容量。答案就是$\sum B_i$减去最小割。

考虑如何连边。由于每个点的状态只有三种,而当一个点被删去时,与它相连的所有边产生的限制都将消失。因此,我们只需要满足,一旦某个连通块内存在一个$-1$,就意味着这个连通块内必须全部是$-1$。不需要考虑$1$的限制。

因此,对于一条边$(u,v)$,连边$u’\rightarrow v,v’\rightarrow u$,边权$\infty$。即如果$u$或者$v$为$-1$,要么另一个点被删去,要么另一个点也必须为$-1$。

Gym101471J

题意

给出一张$n$个点$m$条边的有向图,其中有两个源点$S_1,S_2$和汇点$T$。有两种液体,分别从$S_1,S_2$流入。第一种液体每单位会占用$1$的容量,第二种液体每单位会占用$v$的流量(单位可以是小数)。设这两种液体到达汇点的流量分别为$W,F$,那么最后的收益为$W^aF^{1-a}$。输出最大值。

题解

观察一下可以发现$v$是没用的,我们可以将这两种液体都当成每单位只会占用$1$的流量,最后再将收益除以$v^{1-a}$。

分别从$S_1,S_2$开始跑一遍普通的网络流,记最大流量分别为$W_{max}$和$F_{max}$。接着建一个超级源点,向$S_1,S_2$连边,可以跑出$W+F$的上界$S$。

接下来我们证明,如果记$(W,F)$为最终一组可行的流量,那么它合法当且仅当:

  • $W\leq W_{max}$
  • $F\leq F_{max}$
  • $W+F\leq S$

这三个条件显然是必要的。接下来我们证明充分性。

考虑两种可行的流量:$(S-F_{max},F_{max})$以及$(W_{max},S-W_{max})$。我们可以给这两种方案分配$\alpha,\beta$的系数,只需要满足$\alpha+\beta\leq 1$。此时每条边最终的流量必然没有超过容量上界。运用向量的知识即可发现可以得到所有满足上述条件的$(F,W)$。

问题转化为了一个简单的不等式问题:如何分配$\alpha,\beta$使得$W^aF^{1-a}$最大。

运用简单的求导知识可得$[\alpha^a(1-\alpha)^{1-a}]’=0$时$\alpha$最优,化简得$\alpha=a$。即$\frac WF=\frac{a}{1-a}$时答案最优。

CF1307G

题意

一张有向图,$q$次询问,每次给出$x_i$,可以给每条边的边权加上一个数,使得加的数之和不超过$x_i$,最大化$1$到$n$的最短路。

题解

先考虑一次询问怎么做。

它看起来就非常的线性规划,首先将原问题转化为线性规划问题。

设原来的边权为$w_{u,v}$,加的数为$a_{u,v}$,我们想要判断答案能否超过$D$,那么有

最小化

满足约束

将第一个限制移项变为$d_u-d_v+a_{u,v}\geq -w_{u,v}$。于是我们得到了一个需要初始化的线性规划。

显然我们不可能每次都重新跑一遍这个线性规划,考虑将它转成对偶。

此时我们给原来每个方程分配一个新的变量$b_{u,v}$,给$d_n-d_1$这个方程分配变量$f$,可以得到对偶线性规划:

最大化

满足约束

可以发现,它长得非常像费用流。

直接在原图上跑单路增广费用流,容易发现最终的最小费用是一个关于流量的分段一次函数,断点是每次增广之后的当前流量。

$D$与边权是无关的,于是我们可以在所有询问之前先求出流量为$i$时的最小费用,然后大概是一个斜率优化。

CF1383F

题意

给出一张$n$个点$m$条边的有向图,其中有$k$条边是特殊边。$q$次询问,每次会给这$k$条边重新分配容量,问$1$到$n$的最大流。

题解

最大流等于最小割,因此我们可以暴力枚举这$k$条边割的情况,因此一共只有$2^k$种本质不同的最大流。

复杂度为$O(flow\times 2^k+2^k\times q)$。

需要预处理保留这$k$条边的每个子集时的最大流,直接跑很难过,考虑优化

第一种优化是先将这$k$条边全部去掉,跑一遍最大流,然后仅保留残量网络。接下来每次在残量网络上增广。

第二种优化是采用优秀的转移方式,可以使用类似格雷码的方式,每次在原来网络的基础上加入一条边。

A

题意

有一个$n\times m$的表格,第$i$行$j$列的值为$\gcd(i, j)$。给出一个数列$a$,判断它是否在表格的某一行出现过。

题解

求出$a_i$的$\text{lcm}$。显然行必须是这个$\text{lcm}$的倍数。同时行取这个$\text{lcm}$的时候最优,因为如果取$\text{lcm}$的倍数的话会产生额外的质因子干扰$\gcd$,同时我们也应满足行的编号尽量小。

接下来考虑列。假设这个数列$a$对应第$i$行的第$j+1,j+2,\cdots, j+|a|$列,那么对于每个$k$我们有$a_k|j+k$,即$j\equiv a_k-k\bmod a_k$。用中国剩余定理合并之后可以得到$j\equiv x\bmod \text{lcm}(\{a\})$。求出最小的非负整数解$x$,由于$a_k|\text{lcm}(\{a\})$,根据$\gcd$的性质我们可以发现当$j$取这个$x$的时候最优。接下来扫一遍$a$,根据定义判断$a$是否在第$i$行$j$列合法即可。

B

题意

$T\leq 5000$组数据,$a,b\leq 10^9$。

题解

假设我们找到了一组系数$f(n)$使得$\sum_{d|n}f(d)=\frac{1}{n}$。那么

第二个$\sum$里面的东西相当于求出一段区间内有多少个数是$d$的倍数,这非常好求。如果我们能算出$f$,那么只需要枚举$b$的所有因数就可以计算答案。

考虑如何算$f$。首先,由于$\frac{1}{x}$是个积性函数,因此$f$也必然是积性函数。

因此,我们可以得到$f(n)=\frac{1}{n}\prod (1-p_i)$。这里$p_i$是$n$的所有质因子。

C

题意

题解

此时最后一个$\sum$相当于$1\sim i$中与$i$互质的数之和,它等于$\frac{i\varphi(i)}{2}$。注意当$i=1$时要特判。

D

题意

题解

注意到$j$只用枚举到$\sqrt n$,最终复杂度为

E

题意

定义$d(x)$是满足$y|x$且$y>1$的最小正整数$y$。

定义

求$\sum_{i=1}^nf(i)$

题解

有两种做法。

$d(x)$实际上就是$x$的最小质因子,观察$f$的式子可以发现,

它等价于

如果$u$满足$u\mid x$,那么$u$以及它的所有因数也满足这个条件,并且只有这些数满足条件

因此我们可以将这个东西变换一下

因此我们实际上要求的就是

第二种做法是直接考虑powerful number筛。

定义powerful number为所有质因数的质数均$\geq 2$的数,可以证明$\leq n$的powerful number只有$O(\sqrt n)$个。

回到这道题,不难看出$f(x)$是积性函数。

考虑求出$h(x)$满足$f(n)=\sum_{d|n}h(d)$。我们有

同时,$h(p^k)$是很好算的东西,这里就不推了。

注意到当$p$是质数时,$h(p)=0$,也就是说,$h$在所有非powerful number处取值都为$0$。

暴力搜出$n$以内的所有powerful number,然后用这个$h(n)$求值即可。

F

题意

记$\text{sgcd}(i,j)$为$i,j$的公约数中第二大的,特别地若$\gcd(i,j)=1$,定义$\text{sgcd}(i,j)=0$。

题解

记$\text{minp}(x)$为$x$的最小质因子,特别地若$x=1$则$\text{minp}(x)=\infty$。

那么问题等价于

第二个$\sum$可以使用一次杜教筛解决,问题转化为求$\left(\frac d{\text{minp}(d)}\right)^k$的前缀和。这个可以用类似min25筛的方式解决。

记$F(i,j)$表示考虑$[1,j]$中的数,最小质因子大于第$j$个质数的所有数的$k$次方之和。

记$G(i,j)$表示考虑$[1,j]$中的数,最小质因子大于第$j$个质数的数的个数。

记$H(i,j)$表示考虑$[1,j]$中的数,最小质因子不超过第$j$个质数的所有数的答案之和。

那么有

当$p_j>\sqrt n$时,最小质因子为$p_j$的数只有$p_j$,且它的答案为$1$。

用类似min25筛的方式$dp$一下即可。

G

题意

给定$x,a,b$,求有多少对$(i,j)$满足$i\in[1,a],j\in[1,b]$且$\lfloor\frac xi\rfloor j=\lfloor\frac {xj}i\rfloor$。

题解

问题等价于求出有多少对$i,j$满足$(x\bmod i)\times j<i$。

将这个式子改写一下

枚举$\lfloor\frac xi\rfloor$,可行的$i$是一段区间。

将这个值相等的$i$划分为一段,由于这个东西随着$i$增加而递增,所以每次可以二分找出这一段的结尾。

然后打一下表会发现总段数不会很多。(我也不知道为什么)

H

题意

求$(Fib_n\bmod Fib_k)\bmod 10^9+7$,$50000$组数据

题解

我们知道

同时

观察左上角的元素,我们可以得到

另外,根据行列式的运算法则$\det(AB)=\det(A)\det(B)$,将第一个等式两边同时取行列式,可以得到

接下来,我们将数列的下标拓展到负数,有$F_{-n}=(-1)^{n-1}F_n$。

将$(1)$式两边同时对$F_k$取模,可以得到

固定$k$,不断地用这个等式替换$F_{n-k}$,那么每次我们能将下标减去$k$,直到$n<k$。即

记$i=\lfloor\frac nk\rfloor,j=n\bmod k$,分类讨论:

  • $i=2t$

    此时$F_n\equiv(F_{k-1}^2)^tF_j$,将$(2)$代入得到

  • $i=2t+1$

    此时用$(1)$式再次替换$F_j$后就变成了$i$是偶数的情况

注意到$j=n\bmod k<k$,因此问题转化为求斐波那契数列某一项的值$\bmod 10^9+7$。

I

image.png

8会

棋盘

题意

image.png

题解

如果$n$是偶数,那么我们可以直接对棋盘进行黑白染色,每一列都可以取到$\frac n2$的上界。

否则,将$a_i=\lfloor\frac{n}{2}\rfloor$的那些列拿出来,这些列的放法是唯一的,并且它们将整张棋盘分为若干段,每一段互不影响。

考虑这样一种情况:

1
2
3
4
5
6
7
32222223

10101011
01010100
10101011
01010100
10000001

直接按照黑白染色的方式放的话会放出上面的这种情况,注意到倒数第二列无论是奇数行还是偶数行都已经1被占用了。原因是第一列和最后一列中间夹了偶数列。

我们将正常放会放到的格子称为“白格”,将不会放到的格子称为“黑格”。

解决方法是:对于每一列,从下往上优先放所有能放的黑格,如果还有剩余的棋子,从上往下放白格。

对于这个样例,放出来大概长这样:

1
2
3
4
5
10101001
01010010
10100101
01001010
10010101

Flip and Reverse

题意

给出一个01串,每次你可以选择一个01个数相等的区间,将这个区间翻转并且01互换。你可以进行任意多次操作,问最终能得到的字典序最小的串。

题解

0看作$-1$,1看作$+1$,然后求出这个序列的前缀和,看作是一条每次往右上或者右下的折线。由于01个数相等,每次选择的区间在折线上的两个端点高度必然相等。同时区间翻转可以看作将这一段折线中心对称,01互换可以看作上下翻转,因此这个操作对折线的影响本质是直接水平翻转这一段区间,也就是翻转一段前缀和。

最小化原序列的字典序等价于最小化前缀和的字典序,问题转化为给出一个序列,每次可以选择两个位置,满足这两个位置上的数相同,然后翻转它们构成的区间。

注意这个前缀和有一个性质:相邻两个数之差的绝对值必然为$1$。

记这个前缀和为$s_i$,对于两个相邻的位置$s_i,s_{i+1}$,我们让$s_i$这个数向$s_{i+1}$这个数连一条双向边。注意翻转操作并不会导致边的连接方式改变,因为翻转区间的首尾相同。

考虑直接确定最终的序列。假设当前已经确定的最后一个数是$x$(一开始为$0$),统计$x\rightarrow x+1$和$x\rightarrow x-1$有多少条边。如果存在到$x+1$的连边,并且到$x-1$的连边只有一条,那么此时只能走$x+1$。因为$x+1$必然只能由$x$或者$x+2$走一步得到,如果这次走了$x-1$,那么接下来想要得到$x+1$就必然需要回到$x$,而$x$到$x-1$的连边只有一条,显然不行。

因此,我们断言:如果$x$向$x-1$的连边至少有两条,或者不存在$x$向$x+1$的连边,那么当前位置可以放$0$,否则必须放$1$,同时删去这条经过的边。

这显然是必要条件,接下来我们证明一定存在一种操作的方案。

如果不存在向$x+1$的连边,只有向$x-1$的连边,那么前缀和必然为$x,x-1,x,x-1,\cdots$,此时直接将其还原回序列即可,即不需要进行任何操作。

否则,如果操作到这个位置时,$x$的下一个数恰好为$x-1$,那么我们可以不进行操作,直接跳到下一个数。

否则,$x$的下一个数为$x+1$,由于前缀和序列的性质,此时的序列必然为$x,x+1,\cdots, x+1,x,x-1,\cdots, x-1,x$。选择首尾的两个$x$翻转一次,就能把$x-1$翻转到下一个位置。

因此一定存在一种合法的操作方案。

Latin Square

题意

给出一个$n\times n$的矩阵,矩阵的每行每列都是一个排列,定义如下操作:

  • $D$:将矩阵向下循环移动一次
  • $U$:将矩阵向上循环移动一次
  • $L$:将矩阵向左循环移动一次
  • $R$:将矩阵向右循环移动一次
  • $I$:将每行的排列变成其逆排列
  • $C$:将每列的排列变成其逆排列

给出一个操作序列,问最终得到的矩阵。

题解

将矩阵的每个数看作一个三元组$(i,j,a_{i,j})$,表示矩阵的第$i$行$j$列为$a_{i,j}$。

可以发现所有操作要么相当于给这个三元组的某一维$+1,-1$,要么相当于交换某两维。

Nim Shortcuts

题意

有两堆石子,两个人玩nim游戏,但是规定必败局面不止有$(0,0)$,还有给定的$m$个局面。多组询问,每次给出一个初始局面,问先手必胜还是必败。

题解

如果$m=0$,那么当$x=y$时先手必败,可以看作是二维平面上一条$y=x$的射线。

否则,对于规定的这些必败点,这个点正上方和正右方的所有点都是必胜点。

考虑如何确定所有的必败点:$x$从小到大枚举,找到当前未确定状态的$y$最小的点,然后将这个点标为必败,将这个点正上方和正右方的所有点标为必胜。

Longest Loose Segment

题意

定义一个区间合法当且仅当$\max+\min>len$。

给出一个序列,$m$次询问,每次会给出$k$个修改,每次修改交换某两个数,输出修改后的数组的最长合法区间。

题解

修改是交换这个性质似乎是没用的,我们直接考虑如何$O(n)$地求出一个序列的答案。

考虑枚举这个序列的$\min$。单调栈求出每个数在哪个极长的区间里是最小值。假设当前枚举的最小值下标为$i$,对应的区间为$[l,r]$,问题转化为在$[l,r]$这个区间内找到一个数作为区间的$\max$,同时在满足$a_j+a_i>j-i+1$的条件下最大化$a_j$。

观察发现这个限制其实是没用的。如果$a_j+a_i\leq j-i+1$,则意味着这个区间的长度最长只能取到$a_j+a_i$,无法同时包含$i$与$j$。注意到$i$是整个区间的最小值,我们可以直接令这个区间的右端点为$j$,此时这个区间的$\min$一定不小于$a_i$,同时这个区间必然合法。

问题转化为求一段区间的最大值。

Assignment Problem

题意

给出一张完全二分图,左侧有$n$个点,右侧有$m$个点。

你不知道每条边的边权,但是对于右侧的每个点,你知道左侧的点与它连边的边权的大小关系。

对于左侧的每个点,判断是否存在一种合法的分配边权的方式,使得它存在于唯一的最大匹配中。

题解

结论:对于任意一个最大匹配,一定存在右侧的一个点,这个点匹配了与它相连的边权最大的点。

因此我们可以枚举是右侧的哪个点匹配了边权最大的点,同时在左侧将这个点删去,删去之后的二分图仍然满足这个结论。

因此最大匹配只有$O(m!)$种,爆搜。

Lockout vs tourist

题意

你和tourist要进行一场1v1的比赛,一共有$n$道题,由于只有两个人,因此每道题只会给最先通过这道题的人$a_i$分。

每次你和tourist会各自选择一道题开始写,你们不知道对方选的是哪道题。tourist非常强,如果你和他选了同一道题,那么他会比你先写完,并且得到这$a_i$分。接下来你们再重新各自选题。

如果你和tourist选的不是同一道题,那么你的机会就来了。你可以获得这道题的分数,但是看到你过了这道题之后tourist会进入疯狂模式,瞬间过掉所有剩下的题。

你想要最大化自己的得分,tourist想要最小化你的得分,双方都采取最优策略并且知道对方采取的是最优策略。问最终你的得分的期望。

题解

标准的双人零和博弈:我们可以认为如果你过了某道题,那么tourist的得分是$-a_i$,那么此时无论最终局面如何,两人获得的分数之和都将是$0$。

对于这种双人零和博弈,如果两人都采取最优策略,那么有一个结论是:问题等价于其中一个人先选择策略,然后另一个人看到这个人选择的策略之后再选。

于是我们可以当作tourist先选,然后你可以看到tourist的策略,再决定自己的策略。

tourist的策略一定是给每道题分配一个$p_i$,表示选择这道题的概率。假设你最终选了第$i$道题,且$f_S$表示仅考虑$S$集合中的题目,你能获得的得分的期望。那么你此时得分的期望为

这里$b_i$是一个与$p_i$无关的确定常数。

你肯定会选择$a_i-p_i\times b_i$的最大值,那么tourist的目标就是合理地分配$p_i$,最小化这个最大值。

将所有题目按照$a_i$排序,可以求出将最大的$a_i$减到第二大的$a_i$所需要的$p_i$之和、将前两大的$a_i$减到第三大的$a_i$所需的$p_i$之和……,我们可以$O(n)$确定最优的$p_i$。

因此总时间复杂度$O(2^n\times n)$

由于难度差异较大,这篇题解里面只会写部分比较有意思的题。

Nullify The Matrix

题意

给出一个$n\times m$的棋盘,第$i$行第$j$列的格子的权值为$a_{i,j}$,有两个人要玩游戏。每次当前玩家可以选择一个非零的格子,让这个格子减去一个正整数,但不能减到负数,同时选择一条从这个点到$(n,m)$的最短路径,将路径上的其它位置随意赋值。不能操作的那一方输。你需要判断先手必胜还是后手必胜。

题解

注意到最短路径上每走一步都会从一条副对角线跨到与其相邻的另一条副对角线,这启发我们按照对角线来考虑。

依次考虑这张棋盘的每条副对角线。

如果我们仅考虑某条副对角线,将矩阵的其余部分完全忽略,那么它就变成了一个nim游戏,即每次当前玩家可以任选一堆棋子拿走至少一个,不能操作的玩家输。

加强一下这个游戏,考虑最靠左上的那条非全$0$的对角线,我们不妨假设它的编号为$i$,显然前$i-1$条对角线对游戏不会产生任何影响,接下来我们加入一条限制:每次当前玩家只能在第一条非全$0$的对角线上操作。

当一名玩家拿走第$i$条对角线的所有棋子,他一定可以决定$i+1$到$\min(n,m)$这些对角线的异或,即可以保证单独在这些对角线上进行nim游戏时先手必胜。这名玩家操作完毕之后,两个玩家开始轮流操作第$i+1$条对角线,由于之前这名玩家已经保证了先手必胜,因此这一条对角线最后操作的玩家仍然是他,他可以继续保持最后操作的优势。

因此,我们可以得出一个结论:对于这个简化版的游戏,先手获胜的条件是第一条非$0$的对角线异或和不为$0$

接下来进一步加强这个游戏,考虑原问题。仍然假设第一条非$0$的对角线为$i$。

如果$i$满足异或和不为$0$,也就是在这条对角线上先手必胜,那么先手一开始可以选择这条对角线,接下来我们讨论后手的决策。

  • 如果后手操作第$i$条对角线,那么先手也操作这条对角线,最后必然可以使得这条对角线最后是由先手操作的。
  • 如果后手操作其它的对角线,由于先手已经操作了一次第$i$条对角线,因此先手可以使得所有对角线上都是先手必胜。此时先手与后手在同一条对角线上继续操作,由于先手后操作,因此可以保证所有对角线仍然是先手必胜。

因此,如果第$i$条对角线先手胜,则先手必胜。

如果第$i$条对角线后手必胜,那么先手一定不会操作它,我们不妨假设存在一条对角线$j$使得一开始这条对角线上先手必胜,我们讨论先后手的策略。

  • 先手一开始操作第$j$条对角线,使得$j+1$到$\min(n,m)$这些对角线都是先手必胜。
  • 根据之前的讨论,后手一定不会选择$j$到$\min(n,m)$这些对角线操作,否则后手必败。
  • 而$(i,j-1)$这些对角线上先手必败,而此时后手由于只能选择这些对角线,因此此时先后手翻转,先手采用之前的策略即可,因此先手必胜。

如果所有对角线都是先手必败,那么只要先手操作一条对角线后手就跟着操作,可以使得最终先手必败。

因此这题的结论是:若存在一条对角线先手胜,则先手必胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int G[N][N], s[2 * N];

int main() {
int T; scanf("%d", &T);
while (T--) {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &G[i][j]), s[i + j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) s[i + j] ^= G[i][j];
bool flag = false;
for (int i = 2; i <= n + m; i++) if (s[i]) flag = true;
if (flag) puts("Ashish");
else puts("Jeel");
}
}

小Y的序列

题意

来源:auoj1622

有一个序列$a$,定义一个位置$i$是好的当且仅当$i$前面有至少$k$个位置小于$a_i$。给定$n,m$,对于每个$k$求出所有每个数不超过$m$的序列中好的位置的个数之和。

题解

考虑二项式反演。定义$g_i$表示所有数列中满足前面有恰好$i$个数小于它的位置的个数之和,那么答案就是$g_i$的后缀和。

$g_i$不是很好求,我们定义$f_i$表示在每个数前面钦定$i$个位置,这些位置都小于这个数的个数之和。

那么我们很容易写出$f_k$的表达式。

前两项容易求出,而后面的东西是一个自然数幂和,这个东西比较麻烦。

回顾我们熟悉的自然数幂和求法,主要有以下几种(假设求$\sum_{i=1}^n i^k$)

  • 插值:这种做法适用于$k$不变的情况,但这道题中$k$是变化的。
  • 斯特林数转下降幂:可以很方便地$O(k^2)$求出一个,但是很难优化。
  • 伯努利数:适用于底数固定,指数变化的情况。

因此我们选择伯努利数,它的式子是这样的:

记伯努利数的$EGF$为$B(x)$,则有$B(x)=\frac{x}{e^x-1}$。这个可以通过求逆快速求出。

求出$f$之后我们有

再跑一遍差卷积即可。

T1 Replicate Replicate Rfplicbte

题意

有一个细胞自动机,对于每个格子,如果它周围(包含它)$9$个格子中$1$的个数为奇数,那么它就会变成$1$,否则变成$0$。

但是在变换的过程中这个自动机有一定几率会出错,每一轮变换之后可能有至多一个格子翻转,你并不知道是哪个格子。现在给出一个状态,你需要求出最小的初始状态使得它有可能达到这个终止状态。

容易发现最小化初始状态的行数时列数也会达到最小值。

题解

先考虑忽略变异的情况该怎么做。

容易发现每一回合这个自动机都会向外扩展一圈,那么我们可以知道这些格子在第$k-1$回合的时候必然全是$0$。那么我们可以从左上到右下通过第$k$回合每个位置的值倒推回第$k-1$回合。

具体来说,设$f_{i,j}$为第$k$回合的格子,$g_{i,j}$为第$k-1$回合的格子,当我们尝试计算$g_{i,j}$时,对于$i’\leq i,j’\leq j$的$g_{i’,j’}$,它已经计算完毕,因此我们可以通过$f_{i-1,j-1}$以及它周围除$i,j$以外的$8$个格子计算出$g_{i,j}$。

这时我们发现一件事情,由于第一行、最后一行、第一列、最后一列必然是$0$,我们没有用到这些地方的$f$。另外,这些位置的$g$也不需要计算,因此最后两行、两列的$f$是没有用到的。

考虑翻转一个$f$会对算出的$g$产生什么影响,我们可以画出这样一张图:

image-20210419201109553

左上角的$f$被翻转了,可以发现此时所有橙色格子计算出的$g$与实际上的$g$恰好相反。

image-20210419204925997

假设最后一行与最后一列为已经确定的$0$,那么可以发现黄色格子的$f$与当前计算出的$g$无法匹配,若最后一行或者最后一列恰好没有被翻转,那么倒数第二行或倒数第二列的黄色格子会无法匹配。

因此,只要我们找出所有失配的位置,对它们的$x$和$y$坐标分别取最小值,我们就能够得到变异的点的坐标。

将这个坐标的$f$翻转,重新计算$g$后再尝试找到变异点,如果仍然能找到变异点,说明变异的点不止一个,当前状态即为初始状态。

否则我们不断重复这个过程,直到行之差或者列之差小于等于$2$。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

int G[310][310], g[310][310];

typedef pair<int, int> P;

P get(int lx, int rx, int ly, int ry) {
memset(g, 0, sizeof(g));
for (int i = lx + 1; i < rx; i++)
for (int j = ly + 1; j < ry; j++) {
for (int t = 0; t <= 2; t++)
for (int p = 0; p <= 2; p++) if (t | p) g[i][j] ^= g[i - t][j - p];
g[i][j] ^= G[i - 1][j - 1];
}
P pos(rx + 1, ry + 1);
auto val = [&](int i, int j) {
int res = G[i][j];
for (int t = -1; t <= 1; t++)
for (int p = -1; p <= 1; p++) res ^= g[i - t][j - p];
return res;
};
for (int i = lx; i <= rx; i++)
for (int j = ly; j <= ry; j++)
if (val(i, j)) pos.first = min(pos.first, i), pos.second = min(pos.second, j);
return pos;
}

char s[310];

int main() {
int n, m; scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j++) G[i][j] = s[j] == '#';
}
int lx = 1, rx = n, ly = 1, ry = m;
auto fuck = [&]() {
int a = 1e9, b = -1e9, c = 1e9, d = -1e9;
for (int i = lx; i <= rx; i++)
for (int j = ly; j <= ry; j++)
if (G[i][j]) a = min(a, i), b = max(b, i), c = min(c, j), d = max(d, j);
lx = a, rx = b, ly = c, ry = d;
};
for (; rx - lx > 1 && ry - ly > 1; memcpy(G, g, sizeof(g)), fuck()) {
auto res = get(lx, rx, ly, ry);
if (res.first == rx + 1) continue;
G[res.first][res.second] ^= 1;
auto tmp = get(lx, rx, ly, ry);
if (tmp.first == rx + 1) continue;
G[res.first][res.second] ^= 1; break;
}
for (int i = lx; i <= rx; i++, puts(""))
for (int j = ly; j <= ry; j++) putchar(G[i][j] ? '#' : '.');
}

T2 Winding polygonal line

题意

平面上有$n$个点,给定一个长度为$n-2$的字符串$s$,$s$由LR构成,你需要找到一种遍历所有点的方案,使得每次拐弯的方式与$s$相同。

题解

找到$y$坐标最小的点,这个点一定在凸包上,我们从这个点开始出发。

每次拿出一段极长的L或者R。假设现在有$k$个L连在一起,那么对于前$k-1$步,我们找到偏离当前方向最小的点,对于第$k$步,找到偏离当前方向最大的点,这样看起来就非常优秀。R的构造与L类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;

typedef long long LL;

int x[N], y[N], vis[N], n;

LL cross(int x1, int y1, int x2, int y2) {
return (LL)x1 * y2 - (LL)y1 * x2;
}

int least1(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) > 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) > 0) pos = i;
}
}
return pos;
}

int least2(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) < 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) < 0) pos = i;
}
}
return pos;
}

int most1(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) > 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) < 0) pos = i;
}
}
return pos;
}

int most2(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) < 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) > 0) pos = i;
}
}
return pos;
}

char s[N];

void solve() {
memset(vis, 0, sizeof(vis));
vector<int> res;
int lst = 1, st = 0;
for (int i = 2; i <= n; i++)
if (y[i] < y[lst]) lst = i;
vis[lst] = 1, res.push_back(lst);
double mn = 1e9, mx = -1e9;
for (int i = 1; i <= n; i++) if (i != lst) {
double ang = atan2(y[i] - y[lst], x[i] - x[lst]);
if (s[1] == 'L') {
if (ang < mn) mn = ang, st = i;
} else {
if (ang > mx) mx = ang, st = i;
}
}
vis[st] = 1, res.push_back(st);
for (int t = 2; t < n; t++) {
int tmp = st;
if (s[t - 1] == s[t]) {
if (s[t - 1] == 'L') st = least1(lst, st);
else st = least2(lst, st);
} else {
if (s[t - 1] == 'L') st = most1(lst, st);
else st = most2(lst, st);
}
lst = tmp, vis[st] = 1, res.push_back(st);
}
for (auto t : res) if (!t) return;
for (auto t : res) printf("%d ", t);
exit(0);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
scanf("%s", s + 1), solve();
// puts("-1");
}

T3 Distinctification

题意

有$n$个数对$(a_i,b_i)$,每次你可以选择一个数对,让它的$a_i$加一或者减一,但是需要满足如下条件:

  • 如果存在$j\neq i,a_i=a_j$,那么可以将$a_i$加一,花费$b_i$的代价。
  • 如果存在$j\neq i, a_j=a_i-1$,那么可以将$a_i$减一,花费$-b_i$的代价。

你希望使得最终所有$a_i$互不相同,且最小化花费的代价,容易发现这个代价可以是负的。你需要对于每个前缀求出这个最小的代价。

保证$b_i$互不相同。

题解

设$c_i$表示满足$a_j=i$的$j$的个数。

我们将极长的$[i,j]$使得$a\in [i,j]$均出现过成为一个连续段,容易发现最终每个连续段的左端点必然不变,右端点可以往外拓展。

具体来说,对于一段连续段$[i,j]$,它最终能够拓展到的区间为$[i,i+\sum_{k\in[i, j]} c_k]$。

如果某两端连续段拓展到的区间有交,那么最终这两个连续段必然会合并为一段。

对于一段连续段来说,最终它的最优状态必然是段内的所有数对按照$b_i$从大到小排序,这样花费的代价必然最小。

因此我们可以给每段开一棵线段树,以$b_i$为下标维护这个最小代价,合并两个连续段的时候就是线段树合并。

另外,我们需要开一个并查集维护连续段,每次在并查集上暴力向后跳,判断下一个连通块是否可以合并到当前连通块,容易发现这样的复杂度是$O(n\log n)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

const int N = 400010;

typedef long long LL;

struct node {
int ls, rs, sz; LL res, sum;
} T[N * 32];

int ncnt;

void pushup(int rt) {
int ls = T[rt].ls, rs = T[rt].rs;
T[rt].sum = T[ls].sum + T[rs].sum, T[rt].sz = T[ls].sz + T[rs].sz;
T[rt].res = T[ls].res + T[rs].res + (LL)T[rs].sz * T[ls].sum;
}

void update(int &rt, int l, int r, int x) {
if (!rt) rt = ++ncnt;
if (l == r) return T[rt].sum = T[rt].res = x, T[rt].sz = 1, void();
int mid = (l + r) >> 1;
if (x <= mid) update(T[rt].ls, l, mid, x);
else update(T[rt].rs, mid + 1, r, x);
pushup(rt);
}

void merge(int &x, int y, int l, int r) {
if (!x || !y) return x |= y, void();
assert(l != r);
int mid = (l + r) >> 1;
merge(T[x].ls, T[y].ls, l, mid), merge(T[x].rs, T[y].rs, mid + 1, r), pushup(x);
}

int rt[N], fa[N], sz[N]; LL res[N], sum[N];

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

set<int> s;

int main() {
int n; scanf("%d", &n);
LL ans = 0;
for (int i = 1; i <= n; i++) {
int a, b, f; scanf("%d%d", &a, &b);
auto pos = s.upper_bound(a);
if (pos == s.begin()) f = fa[a] = a, s.insert(a);
else {
pos--;
if (*pos + sz[*pos] >= a) f = *pos;
else f = fa[a] = a, s.insert(a);
}
ans -= T[rt[f]].res, update(rt[f], 1, n, b), ans += T[rt[f]].res;
LL tmp = (LL)(a - f + 1) * b; ans -= tmp, res[f] += tmp, sz[f]++, sum[f] += b;
while (233) {
int nxt = f + sz[f];
if (fa[nxt]) {
int t = find(nxt);
ans -= T[rt[f]].res + T[rt[t]].res, merge(rt[f], rt[t], 1, n), ans += T[rt[f]].res;
ans += res[f] + res[t], sz[f] += sz[t], fa[t] = f, s.erase(t);
res[f] += res[t] + (LL)(t - f) * sum[t], sum[f] += sum[t], ans -= res[f];
} else break;
}
printf("%lld\n", ans);
}
}

T4 博弈

题意

image-20210419213031935

题解

这道题正着做非常困难,考虑倒着递推。

我们称一个“终止状态”为一种分配方案,满足所有人都会同意这种方案。

显然,$n$个$0$是一个终止状态。考虑从这个状态往前推。

记录下当前提议的玩家编号,以及距离上一个终止状态剩余了多少金币可以分配(即每往前倒推一个玩家,金币数量$+k$)

如果当前剩余的金币数量$<n$,那么无论如何分配,必然有一个人分配到的金币数量与下一个终止状态相同,那么根据题意这个人会否决提议。

如果当前剩余的金币数量$\geq n$,那么最优的策略必然是这个人给所有人分配一枚金币,然后将剩下的所有金币全部留给自己。

因此我们得到了一个$80$分暴力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef long long LL;

int num[N];

int main() {
int n, m, k; cin >> n >> m >> k;
int turn = (m + k - 1) / k, pos = turn % n + 1, all = 0, tmp = m % k;
for (int i = turn + 1, nw = 0; i >= 1; i--) {
if (nw >= n) num[pos] += nw - n, all++, nw = 0;
if (pos == 1) pos = n; else pos--;
if (nw < tmp) nw = tmp, tmp = 0;
else nw += k;
}
for (int i = 1; i <= n; i++) printf("%d ", num[i] + all);
}

考虑优化这个暴力,可以发现两个终止状态中间相隔的轮数是一个定值(最后一次除外),而终止状态中分配的玩家是循环的,且由于只有$n$个人,因此循环节大小至多为$n$。

我们可以快速算出最终一共循环了多少次,对于边角则暴力处理,代码细节比较多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef long long LL;

LL num[N];

int main() {
int n; LL m, k; cin >> n >> m >> k;
auto get = [&](int a, int t) {
int res = ((a - t) % n + n) % n;
return res ? res : n;
};
LL turn = m / k + 1, pos = (turn - 1) % n + 1, tmp = m % k, step = (n + k - 1) / k;
LL first = (n - tmp + k - 1) / k;
int t = get(pos, first);
if (first * k + tmp <= m) for (int i = 1; i <= n; i++) num[i]++;
num[t] += tmp + first * k - n, pos = get(t, step);
if ((first + step) * k + tmp > m) {
for (int i = 1; i <= n; i++) printf("%d ", num[i]);
return 0;
}
LL delta = step * k - n, all = ((m - tmp) / k - first) / step;
vector<LL> fuck = {pos}; LL nw = pos;
while (233) {
nw = get(nw, step);
if (nw == pos) break;
fuck.push_back(nw);
}
LL hh = all / fuck.size();
for (auto t : fuck) num[t] += delta * hh;
for (LL nw = pos, t = hh * fuck.size() + 1; t <= all; t++) {
num[nw] += delta;
nw = ((nw - step) % n + n) % n;
if (nw == 0) nw = n;
}
for (int i = 1; i <= n; i++) printf("%lld ", num[i] + all);
}

T1 CNF2

题意

有$n$个bool变量$b$和$m$条限制,第$i$条限制为$a_{i,1}|a_{i,2}|\cdots|a_{i, k}$,这里$a_{i,x}$可能为$b_t$或$\neg b_t$。记第$i$条限制得到的值为$v_i$,你需要求出一组解满足$v_1\and v_2\and\cdots\and v_k=1$或判断无解。

保证每个变量和其相反变量出现次数的和不超过$2$,在一条限制中至多出现一次。

题解

做法一:用类似Dijkstra的方法,将所有限制按照剩余的未确定的变量个数从小到大排序,优先取较小的,然后将其涉及的第一个未确定的变量确定下来,同时更新包含这个变量的相反变量的限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef pair<int, int> P;

int fa[N], ans[N], ct[N], vis[N], bl[2][N];

vector<int> p[N];

int main() {
int n, m; scanf("%d%d", &n, &m), memset(ans, -1, sizeof(ans));
for (int i = 1; i <= n; i++) {
int k; scanf("%d", &k), ct[i] = k;
for (int j = 1, a; j <= k; j++)
scanf("%d", &a), p[i].push_back(a), bl[a < 0][abs(a)] = i;
}
priority_queue<P> q;
for (int i = 1; i <= n; i++) q.push(P(-ct[i], i));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue; vis[u] = 1;
if (!ct[u]) return puts("NO"), 0;
for (auto t : p[u]) if (ans[abs(t)] == -1) {
int cur = t < 0; t = abs(t);
ans[t] = cur; int nxt = bl[cur ^ 1][t];
if (nxt && !vis[nxt]) ct[nxt]--, q.push(P(-ct[nxt], nxt));
break;
}
}
puts("YES");
for (int i = 1; i <= m; i++) if (ans[i] == 1) putchar('0');
else putchar('1');
}

做法二:对于每个变量,我们将其看作一条边,将所有限制看作点。如果这个变量及其相反变量都在限制中出现过,那么将这两个限制连接起来,否则连一个自环。问题转化为每次可以选择一条边的一个端点标记,需要使得最终所有点都被标记。

对于一个连通块来讲,如果它是树那么肯定不合法,因为边数小于点数。

否则一定存在一种方案。具体来说,我们随便找出一条非树边,选择它的其中一个端点作为根,从根出发找到一棵不经过这条边的生成树。对于生成树上的每条边,选择它的儿子标记,对于选中的这条边,选择根标记。这样可以使得每个点都被标记过。

T3 Son of Pipe Stream

题意

给出一张无向图,每条边有其流量限制$w_i$。$1$号点流入一种叫做Flubber的液体,$2$号点流入水,它们的共同汇点是$3$。给定$v$,对于每条边Flubber的流量$\times v$加上水的流量不能超过$w_i$。记最终Flubber的总流量为$F$,水的流量为$W$,给定$a$,你需要最大化$F^aW^{1-a}$。

如果一条边同时有Flubber与水的流量,那么它们流的方向不能相同。输出方案。

题解

首先从$1$号点和$2$号点开始分别跑一遍最大流,记它们的流量分别为$F’,W’$。接着建一个超级源点,同时向这两个点连边,记此时的最大流为$S$。

有一个定理是对于$a,b$,如果满足$a\leq 1, b\leq 1$且$F’a+W’b\leq S$,那么一定存在一个最大流满足其流量恰好为$F’a+W’b$,且它由$F’a$的Flubber与$W’b$的水组成。

不妨令$F’a+W’b=S$,根据简单的求导可以求出,当$F^aW^{1-a}$取得最大值时有$\frac FW=\frac{a}{1-a}$。

考虑怎么构造方案。

将超级源点连向$1$的边的容量改为$F’a$,将连向$2$的边容量改为$W’b$,跑一遍最大流。然后仅保留最大流上的那些边,并且将它们改为单向边,容量为最大流中的流量。

接着从$1$出发,在新图上跑一个大小为$F’a$的流,可以发现此时最大流扣去这个$F’a$的流就得到了一个从$2$开始,流量为$W’b$的流。且这样构造可以使得每条边中两种液体的流向是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

const int N = 210;
const int M = N * N * 2;
const double eps = 1e-10;

struct edge {
int to, next; double w;
} e[M], e2[M];

int head[N], cur[N], ecnt;

void adde(int from, int to, double w) {
e[++ecnt] = { to, head[from], w }, head[from] = ecnt;
e[++ecnt] = { from, head[to], w }, head[to] = ecnt;
}

void adde1(int from, int to, double w) {
e[++ecnt] = { to, head[from], w }, head[from] = ecnt;
e[++ecnt] = { from, head[to], 0 }, head[to] = ecnt;
}

int dep[N];

bool BFS(int s, int t) {
memset(dep, -1, sizeof(dep)), dep[s] = 0; queue<int> q; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next)
if (e[i].w > eps && dep[e[i].to] == -1) {
dep[e[i].to] = dep[u] + 1, q.push(e[i].to);
if (e[i].to == t) return true;
}
}
return false;
}

double DFS(int u, double f, int t) {
if (u == t || f < eps) return f;
double res = 0, tmp;
for (int &i = cur[u]; i; i = e[i].next)
if (e[i].w && dep[e[i].to] == dep[u] + 1 && (tmp = DFS(e[i].to, min(f, e[i].w), t)) > eps) {
res += tmp, e[i].w -= tmp, e[i ^ 1].w += tmp, f -= tmp;
if (f < eps) break;
}
return res;
}

double dinic(int s, int t) {
double res = 0;
while (BFS(s, t)) memcpy(cur, head, sizeof(head)), res += DFS(s, 1e9, t);
return res;
}

int from[M], to[M], w[M], rev[M];

int main() {
int n, m; double v, a; scanf("%d%d%lf%lf", &n, &m, &v, &a);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &from[i], &to[i], &w[i]);
auto reset = [&]() {
ecnt = 1, memset(head, 0, sizeof(head));
for (int i = 1; i <= m; i++) adde(from[i], to[i], w[i]);
};
reset(); double F = dinic(1, 3);
reset(); double W = dinic(2, 3);
reset(), adde1(n + 1, 1, 1e9), adde1(n + 1, 2, 1e9); double A = dinic(n + 1, 3);
double F1 = A * a; F1 = min(F1, F), F1 = max(F1, A - W);
reset(), adde1(n + 1, 1, F1), adde1(n + 1, 2, A - F1), dinic(n + 1, 3);
memcpy(e2, e, sizeof(e)), ecnt = 1, memset(head, 0, sizeof(head));
for (int i = 1; i <= m; i++) {
if (e2[i * 2].w > w[i]) adde1(to[i], from[i], e[i * 2].w - w[i]), rev[i] = 1;
else adde1(from[i], to[i], w[i] - e2[i * 2].w);
}
adde1(n + 1, 1, F1), dinic(n + 1, 3);
for (int i = 1; i <= m; i++) {
double t1 = e[i * 2 + 1].w / v, t2 = e[i * 2].w;
if (rev[i]) t1 = -t1, t2 = -t2;
printf("%.10lf %.10lf\n", t1 + eps, t2 + eps);
}
printf("%.10lf\n", pow(F1, a) * pow(A - F1, 1 - a) / pow(v, a));
}

T1 Inverter SwapSort

题意

给定一个排列,求出所有逆序对的一个排列,使得依次交换每一对数最终能使得整个数组有序。

题解

考虑每次找到关于一个位置的所有逆序对。

将最后一个位置拿出来,观察前面的所有数与它形成的逆序对。假设最后一个数为$x$,那么可以发现依次交换$x+1,x+2,\cdots$不会对前面的数的相对顺序造成影响,且可以将最大的数挪到结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int A[N], pos[N], buk[N];

int main() {
int n; scanf("%d", &n); vector<int> v;
for (int i = 1; i <= n; i++) scanf("%d", &A[i]), v.push_back(A[i]);
sort(v.begin(), v.end()), v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 1; i <= n; i++) {
A[i] = lower_bound(v.begin(), v.end(), A[i]) - v.begin() + 1;
buk[A[i]]++;
}
for (int i = 1; i <= n; i++) buk[i] += buk[i - 1];
for (int i = n; i >= 1; i--) A[i] = buk[A[i]]--;
vector<pair<int, int>> res;
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= n; j++) pos[j] = 0;
for (int j = 1; j < i; j++) if (A[j] > A[i])
pos[A[j]] = j;
int lst = A[i];
for (int j = lst + 1; j <= n; j++) if (pos[j])
swap(A[pos[j]], A[i]), res.push_back(make_pair(pos[j], i));
}
printf("%d\n", res.size());
for (auto t : res) printf("%d %d\n", t.first, t.second);
}

T2 Blog Post Rating

题意

有一个一开始为空的序列,每次你会给序列插入一个元素,然后将整个序列从小到大排序。

现在你手里有一个值$x$,它一开始为$0$,你从小到大查看序列中的每个元素,如果当前元素比$x$大,那么让$x+1$,如果比$x$小,那么让$x-1$,否则保持不变。你需要回答每次插入之后这个值最终会变成多少。

题解

考虑给定一个序列,如何计算$x$最终的值。

假设现在这个序列已经排好序了,且第$i$个位置的数是$a_i$。

如果$x$在第$i$个位置恰好等于$a_i$,那么显然最终的$x$不能超过$a_i+n-i$。并且容易发现最终的$x$就是$a_i+n-i$的最小值。

加入了修改操作之后,考虑建一棵值域线段树,那么每次修改相当于给一段后缀的排名加上$1$,同时我们需要维护$a_i+n-i$的最小值。

$x$从$0$开始比较恶心,观察到$x$的变化必然是一开始一直减,直到小于或等于当前的数,然后再要么不变,要么$+1$。

二分这个拐点,那么这个拐点必须满足$-i\leq a_i$,即查询$a_i+i\geq 0$的第一个位置,并且可以得出,$x$在这个位置的值为$\max(-i,a_i)$。

假设拐点的位置为$j$,那么我们只需查询$j$之后的数的$a_i+n-i$的最小值,并对此时的$x+n-j$取$\min$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

struct node {
int l, r, tag, x, y;
} T[N << 2];

void pushup(int rt) {
T[rt].x = min(T[rt << 1].x, T[rt << 1 | 1].x);
T[rt].y = max(T[rt << 1].y, T[rt << 1 | 1].y);
}

void pushdown(int rt) {
if (!T[rt].tag) return;
T[rt << 1].x -= T[rt].tag, T[rt << 1 | 1].x -= T[rt].tag;
T[rt << 1].y += T[rt].tag, T[rt << 1 | 1].y += T[rt].tag;
T[rt << 1].tag += T[rt].tag, T[rt << 1 | 1].tag += T[rt].tag;
T[rt].tag = 0;
}

void build(int rt, int l, int r) {
T[rt].l = l, T[rt].r = r;
if (l == r) return T[rt].x = T[rt].y = l, void();
int mid = (l + r) >> 1;
build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r), pushup(rt);
}

void update(int rt, int start, int end) {
int l = T[rt].l, r = T[rt].r, mid = (l + r) >> 1;
if (start <= l && r <= end) return T[rt].tag++, T[rt].x--, T[rt].y++, void();
pushdown(rt);
if (start <= mid) update(rt << 1, start, end);
if (end > mid) update(rt << 1 | 1, start, end);
pushup(rt);
}

int find(int rt) {
int l = T[rt].l, r = T[rt].r, mid = (l + r) >> 1;
if (T[rt].y < 0) return -1e9;
if (l == r) return l;
pushdown(rt);
if (T[rt << 1].y >= 0) return find(rt << 1);
return find(rt << 1 | 1);
}

int query(int rt, int start) {
int l = T[rt].l, r = T[rt].r, mid = (l + r) >> 1;
if (start <= l) return T[rt].x;
pushdown(rt);
if (start > mid) return query(rt << 1 | 1, start);
return min(T[rt << 1 | 1].x, query(rt << 1, start));
}

int tree[N], mn, mx;

void upd(int x) {
for (x -= mn - 1; x <= mx - mn + 1; x += x & -x) tree[x]++;
}

int que(int x) {
int res = 0;
for (x -= mn - 1; x; x -= x & -x) res += tree[x];
return res;
}

int main() {
int n; scanf("%d", &n), mn = 0, mx = 0;
vector<int> v;
for (int i = 1, a; i <= n; i++)
scanf("%d", &a), v.push_back(a), mn = min(mn, a), mx = max(mx, a);
build(1, mn, mx);
for (int i = 1; i <= n; i++) {
int a = v[i - 1]; update(1, a, 1e9), upd(a);
int pos = find(1);
if (pos == -1e9) printf("%d\n", -i);
else {
int t = que(pos), tmp = max(pos, -t) + i - t, res = query(1, pos) + i;
printf("%d\n", min(tmp, res));
}
}
}

T3 咕

题意

来源:auoj471

一个随机排列,你从第一个位置走到第$n$个位置,每走一步你可以得知当前数是否是前缀最小值,你可以选择是否拿走这个数,问在最优策略下你拿走$1$的概率。多组数据。

题解

最优策略必然是:你选择一个位置$x$,然后扔掉$x$及之前的所有数,在$x$之后取走第一个为前缀最小值的位置。

写成$dp$的形式就是,记$f_i$表示已经扔掉了前$i-1$个数,此时在第$i$个数时开始决策,最后拿走$1$的概率。

第$i$个位置为前缀最小值的概率为$\frac 1i$,在是前缀最小值的条件下为$1$的概率为$\frac in$。

因此我们可以得出转移:

转移里的$\max$非常讨厌,尝试去掉这个东西。

如果$f_{i+1}>\frac in$,那么有$f_i=\frac 1i f_{i+1}+\frac{i-1}if_{i+1}=f_{i+1}$。因此我们只需找到第一个$\frac in>f_{i+1}$的位置,容易发现满足这个条件的必然是一段后缀。

当$\frac in$取到最大值时,有

记$g_i=nf_i$,那么$g_i=1+\frac {i-1}ig_{i+1}$,显然有$g_{n+1}=0$,那么有

后面是一个调和级数,可以预处理调和级数的后缀和,每次二分出第一个$\frac in>f_{i+1}$的位置即可。

另外,这个位置约等于$\frac ne$,也可以用一些奇妙的方法求出这个断点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int N = 1000010;

typedef long long LL;

int frac[N], inv[N];

const double e = exp(1);

double wkr[N];

int main() {
int T; scanf("%d", &T), inv[1] = frac[1] = 1;
for (int i = 2; i <= N - 10; i++) inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
for (int i = 1; i <= N - 10; i++) wkr[i] = wkr[i - 1] + 1. / i;
for (int i = 2; i <= N - 10; i++) inv[i] = (inv[i - 1] + inv[i]) % mod, frac[i] = (LL)frac[i - 1] * i % mod;
while (T--) {
int n; scanf("%d", &n);
if (n == 1) { puts("1"); continue; }
int pos = round(n / e + 1 - 0.5 / e), res;
if (wkr[n - 1] - wkr[pos - 2] < 1) pos--;
res = (LL)(pos - 1) * (inv[n - 1] - inv[pos - 2] + mod) % mod;
printf("%d\n", (LL)res * (inv[n] - inv[n - 1] + mod) % mod);
}
}

T4 function

题意

定义$P(x)$表示满足$1<y<x,y^3\equiv 1\pmod x$的$y$的数量,求在$n$以内有多少正整数满足$P(x)=m$。

题解

把条件放宽为$1\leq y<x$,先考虑给定一个$x$,如何快速地求出$P(x)$。

显然$x$的每个质因子都可以分开考虑,最后用中国剩余定理合并就可以还原,因此条件等价于:将$x$分解为$\prod p_i^{c_i}$,只需对每个$p_i$都满足$y^3\equiv 1\pmod {p^{c_i}}$。

如果条件满足,那么显然$y$与$p$互质,因此有

容易得出当$3\nmid \varphi(p^c)$时满足条件的$y$只有$1$。

我们有$\varphi(p^c)=(p-1)p^{c-1}$,只需考虑$p=3$或者$3\mid p-1$,且当$p=3,c=1$时是不行的。

设原根为$g$,则阶为$\varphi(p^c)$。不妨设$y=g^k$,由于$y\bot p$,因此这样的$k$一定存在。

故条件转化为

即$3k\equiv 0\pmod {\varphi(p^c)}$。

同时除以$3$,有$k\equiv 0\pmod{\frac {\varphi(p^c)}3}$

因此满足条件的$k$只有$3$个,即$y^3\equiv 1\pmod {p^c}$的解只有$3$个。

因此有

注意到需要求出$\bmod 3=1$的质数的个数,定义$f(x)=\begin{cases}0&3|x\\1&3|x-1\-1&3|x-2\end{cases}$,筛出$f$以及$n$以内的质数个数就可以解出$\bmod 3=1$的质数个数,而这两个东西都是完全积性的。

使用min25筛的变种即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 200010;

int flag[N], prime[N], tot, sum[N], wkr[N];

void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
prime[++tot] = i, sum[tot] = sum[tot - 1], wkr[tot] = wkr[tot - 1];
if (i % 3 == 1) sum[tot]++, wkr[tot]++;
else if (i % 3 == 2) sum[tot]--;
}
for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}

LL val[2 * N], g[2 * N], p[2 * N], n; // g[i][j]: 1 ~ i, s(n) > p_j
int id1[N], id2[N], lim;

int get(LL x) {
return x <= lim ? id1[x] : id2[n / x];
}

array<LL, 10> S(LL n, int m) {
// cout << n << ' ' << m << endl;
array<LL, 10> nw; nw.fill(0);
if (n < prime[m]) return nw;
// if (((g[get(n)] + p[get(n)]) % 2 + 2) % 2 != 1) cout << "FUCK: " << n << endl;
LL A = (g[get(n)] + p[get(n)] - 1) / 2 - wkr[m - 1];
nw[1] = A, nw[0] = p[get(n)] - (m - 1) - A;
for (int i = m; i <= tot && (LL)prime[i] * prime[i] <= n; i++) {
for (LL j = prime[i], c = 1; j * prime[i] <= n; j *= prime[i], c++) {
int t = (prime[i] == 3 && c > 1) || prime[i] % 3 == 1;
nw[prime[i] % 3 != 2]++; auto tmp = S(n / j, i + 1);
if (t) rotate(tmp.begin(), tmp.end() - 1, tmp.end());
for (int k = 0; k < 10; k++) nw[k] += tmp[k];
}
}
return nw;
}

int main() {
LL m; scanf("%lld%lld", &n, &m), m++;
int ct = 0;
while (m != 1) {
if (m % 3) return puts("0"), 0;
m /= 3, ct++;
}
lim = ceil(sqrt(n)), sieve(lim); int blk = 0;
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
LL t = n / l;
blk++, val[blk] = t;
if (t <= lim) id1[t] = blk; else id2[n / t] = blk;
g[blk] = (t % 3 == 1) - 1, p[blk] = t - 1;
}
for (int i = 1; i <= tot; i++)
for (int j = 1; j <= blk && (LL)prime[i] * prime[i] <= val[j]; j++) {
int pos = get(val[j] / prime[i]);
if (prime[i] % 3) {
int t = prime[i] % 3 == 1 ? 1 : -1;
g[j] -= t * (g[pos] - sum[i - 1]);
}
p[j] -= p[pos] - (i - 1);
}
auto res = S(n, 1); res[0]++;
printf("%lld\n", res[ct]);
}

T1 Escape Route

题意

来源:JOI2021 Day2T1

有一张无向图,每条边有边权$L_i,C_i$。一天共有$S$个时刻,这些时刻被编号为$0\sim S-1$。每天开始时所有道路都会打开,但是第$i$条道路从时刻$C_i$开始会关闭,然后第二天会重新开放。你需要花费$L_i$的时间通过第$i$条道路,并且通过的过程中道路不能关闭,也就是说你必须在$0\sim C_i-L_i$这些时刻才能走第$i$条边。多组询问,每次给定$U,V,T$,表示从$U$在第一天的第$T$个时刻出发,询问到达$V$的最小时刻。第二天的第$0$时刻等于总的第$S$时刻,以此类推。

阅读全文 »

A DiagonalColumn

题意

一个$n\times m$的网格,一开始所有格子都是白色的,你可以进行若干次操作。每次操作你选择一列或者一条从左上到右下的对角线,然后将这条线上的所有格子都染黑。(对角线一共有$n+m-1$条)。问最后有多少种可能的染色方案。

题解

想了一早上。

我们先考虑右上角的这个格子。

image-20210129201150129

如果这个格子所在的对角线选了,那么这一列选不选对这个格子最终的颜色并没有影响。此时我们可以直接将这个格子删去,对网格剩下的部分求出方案数。

否则,这个格子一定是白色(否则我们可以当作选了对角线处理),此时这个格子所在的列一定没有被选,考虑这些对角线

image-20210129201721340

由于最后一列没有选,因此这些对角线是否选择会在最后一列的格子中反应出来,即如果这些对角线选择的方案不同,最后的染色方案也一定不同。

考虑更一般的问题:对于下面这个多边形:

image-20210129202306251

考虑最靠右上的这条对角线:如果这条对角线选,那么线上的格子可以删去,接下来是子问题。

否则,第$i$列及之后的列是否选择都会在这条对角线上反应出来,并且这些列不能全部选。此时一定存在最靠前的一列没有被选,我们记这一列为$j$。

注意,此时$[i,j)$这些列全部被选,$(j,m]$这些列可选可不选。

考虑在$j$之后的那些对角线,这些对角线是否选择也能在第$j$列反应出来。如果这些对角线全部选,那么矩形将只留下由第$j-1$条对角线以及第$i-1$列包围的部分,这是子问题。

否则,又有一些列的状态会在某条对角线上反应出来,继续考虑会导致这种“反应”一直嵌套下去,这启发我们重新设计状态。

考虑这样一个状态:记$dp[i][j][k]$表示考虑由第$k$条对角线与第$i$列围成的多边形,其中第$j$列到第$i$列选择方案不同则视为最终方案不同的染色方案数。

此时$dp[m][m+1][n+m-1]$就是答案。

接下来考虑如何转移。

image-20210129203826809

当$j=i+1$时:

如果$k$这条对角线选,转移到$dp[i][j][k-1]$。

否则,$k$对下来的列到第$i$列不能同时选,容斥掉这种情况,接着第$k-n+1$列到第$i$列是否选都会在这条对角线上反应出来,转移到$dp[i][k-n+1][k-1]$。

当$j\leq i$时:

先判掉第$j$列到第$i$列全选的情况,此时这些列可以全部删掉。

否则,一定存在某一列没有被选,枚举这一列,不妨设为$l$。

$l$以上的对角线是否选择都会在第$l$列反应出来,判掉这些对角线全选的情况,此时这些对角线和$j$列之后都可以删掉。

接着枚举最靠下的没有被选的这条对角线,假设为$t$,此时第$t-n+1$列到第$j-1$列是否被选会在这条对角线上反应出来,这恰好可以用我们的$dp$状态表示,转移到$dp[j-1][t-n+1][l-1]$。

代码