Codeforces Beta Round #71 （A～D）

A

直接模拟即可。10^6

 

B

【题目大意】

m*n的方格(m,n<=4*10^4)，有一些格子坏掉了(数目<=10^3)。然后以

for (int i=1;i<=m;i++)

  for (int j=1;j<=n;j++)

的顺序填好的格子，依次填上Carrots  Kiwis  Grapes.

然后有<=10^3个询问，问第i行第j列的格子是什么。waste表示坏格子。

【算法】

(i,j)->(i-1)*n+j

然后根据排序二分。得出<=自己的坏掉的格子的数目。

 

C

【题目大意】

给定一个10^5的串，然后给出10个小串，他们的长度都<=10。然后问你大串满足不包含小串的最长连续子串是多少。

【算法】

令C[i]表示以大串第i位为结尾和小串匹配时的最短小串长度。如果没有小串和大串在以i为结尾的地方匹配，那么C[i]=oo。

然后就i递增地扫描，然后记now为当前以i为结尾的最长匹配长度。如果now>=C[i],那么now=C[i]-1。记录过程中最大的now与位置即可。

【时间复杂度】

10^7 —暴力

10^6 —KMP

10^5 —自动机

 

D

【题目大意】

1..n个格子，有黑白，一开始全白。其中有k个不相同的key_blocks。然后有m种操作。每种操作为L[i]，表示可以选择一段长度为L[i]连续格子翻转。

问最少多少步使得所有key_blocks变黑，其他格子全白。

【算法】

看了解题报告、

这个模型的转换确实挺巧妙的。

令b[i]=a[i]^a[i-1]。其中a[i]就是原格子的黑白状态。那么b[i]=0表示a[i]==a[i-1]。否则不等。

添加a[0]=0。那么用b可以完整表示出a。(要添加a[n+1]=0,b[n+1]=a[n]^a[n+1]，key_blocks如果前后没有，就要1变2了)

然后翻转连续的一段，就会只更改b的两个值x和x+L[i]，1<=x<=n+1。这样模型就很适合反映情况了。

更改两个b的值表示两个点有边，那么问题变成我们选择一些边，使得key_blocks对应的点度为奇数，其它点度为偶数。

因此答案必然可以分割为若干条简单路径，每条简单路径的起始点和结束点都是key_blocks，而且每个key_blocks会被覆盖1次且仅1次。于是可以bfs算出各个key_blocks间的最短距离。然后SCDP取得最优解。

 

可见把模型转化成合适的形式是很重要的。

【时间复杂度】

mnk + 2^(2k) * k

 

这场之后rating达到新高1922。= =，希望接下来一场多人点的把我带红。

 

这两天缺席了一场TC，一场CF、据说这两场都很好涨rating？555555555555555