Codeforces Round 668 (Div. 1)

题解

A.Balanced Bitstring

题意:安排$?$,使得$01$字符串,的所有$K$长的子串$NUM_0=NUM_1$

暴力安排所有$1+K,2+2K….$,$2+K,2+2K$…最后看一下 $[1,K]$是否可以满足情况即可

B. Tree Tag

题意:在一棵树上,$a,b$两个点,$a$最多可以走$da$步,$b$最多可以走$db$步。$a$先走,然后$b$再走,$b$不想被抓到,找到就输了。

考虑一条链的情况,如果$a$把$b$堵在角落,必须要$db>2da$,反之

  • 如果第一次$a$能走到直径的中点,就可以覆盖所有点
  • $dis(a,b)\leq da$需要判断。

C. Fixed Point Removal

题意:询问区间$[L,R]$内,执行以下操作删除$a_i=i$,然后拼接继续删除$a_i=i$。问最多删除几次。

先让$a_i=i-a_i$

$F(l,r)\Rightarrow F(l,r+1)$ ,这是重点,显然需要判断$F(l,r)\leq a[i]$ 即可,显然我们发现$F[1,R],F[2,R]….F[R,R]$单调递减。就可以二分出需要更新的区间。 用线段树上二分,区间更新即可。

D. Game of Pairs

题意:
先手选择$1.2.3….2n$的分成$n$对。
后手从每对里面挑出$1$个,如果能组成$2n$的倍数就胜利。

给定$n$,询问你选择先手还是后手,并且给出必胜策略。

$n$为偶数的时候先手必胜。

  • 我分成$n$堆偶数,$n$堆奇数,显然怎么挑都是奇数,不可能是$2n$的倍数。

$n$为奇数的时候后手必胜。

  • $\sum = 2n(n+1) \mod 2n=n$,如果存在$\sum =0 \mod 2n$,也一定存在$\sum =n \mod 2n$,那么我只需要找到$n$的倍数即可。$0….n-1$一定可以取到
    我们其实是建了一张无向图。有$n$个节点,标号$0,1,…,n−1$。如果$(x,y)$配对,就在$x\mod n$和$y\mod n$之间连一条边。因为每个点度数都是$2$,所以整张图一定是若干个环。

$\sum =n\times (n-1)/2$ 是$n$的倍数。

E - Bricks

题意:简单可见

假设一开始全部都是$1\times 1$的砖头去覆盖,那么就有$X$块(‘#’点的个数),要是相邻边合并x—,那么就是求在合法情况下最多能合并多少边。

这里可以把矩阵分成上边和右边,如果出现$L$行则表示不能合并某两个边,就是我如果合并,则另外一条垂直或者水平的边就不能合并。具体细节就是枚举4个$L$。这里就变成了最小点集合覆盖问题,显然垂直的边为一部分,水平一部分就变成了二分图。

答案就是总点数−(二分图中的点数−二分图最大匹配)