0%

2.17杂题

棋盘

题意

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)$