Educational Codeforces Round 25

B.Five-In-a-Row（模拟）

•题意

　　有个 $n imes n$ 的方格，Alice 和 Bob 轮流下棋；

　　Alice 下的棋子用字符 'X' 表示，Bob 的用 'O' 表示；

　　现给出你某个中间过程，判断如果 Alice 在下一个棋子，是否会出现五个或五个以上的 'X' 连在一起；

　　如果存在，输出 "YES"，反之，输出 "NO"；

•题解

　　类似与五子棋游戏，直接模拟即可；

　　我的写法比较 low，看了看巨巨的代码，好简洁啊，下面分享一下；

•巨巨Code

　　CodeForces825B.cpp

C.Multi-judge Solving（阅读理解+贪心）

•题意

　　给你 n 个问题，每个问题都有一个难度 $a_i$；

　　有多个评测系统，除了Decoforces 外，其他评测系统包含任意难度的习题；

　　对于难度为 $a_i$ 的问题，你想要解决他，当且仅当你解决了一道难度为 $d$ 的问题并满足$d ge frac{a_i}{2}$；

　　假设你当前解决的习题的最大难度为 d；

　　如果不满足 $d ge frac{a_i}{2}$，那么，你就需要用当前难度 $d$ 去其他评测系统种解决难度 $d$ 可以解决的问题；

　　并将这些问题放入你的解题集中；

　　初始，你解决了一道难度为 k 的习题；

　　问要在 Decoforces 解决这 n 道题目，至少需要在其他评测系统解决几道题？

•Code

　　CodeForces825C.cpp

D.Suitable Replacement（阅读理解+二分）

•题意

　　给你两个串 s,t；

　　s 串中的任意两个字符都可交换位置，并可交换任意次；

　　串s 中的 '?' 可以用任意小写字母填充，求填充后的 s 串使得其经过上述操作后包含尽可能多的 t 串；

　　输出填充后的 s 串；

•题解

　　二分最多可形成多少个 t 串；

•Code

　　CodeForces825D.cpp

F.String Compression（KMP求字符串循环节+DP）

•题意

　　给出一个字符串 S，你要把它压缩成尽可能短的一个字符串；

　　串 ababab 可以转化成 3ab，长度为 3；

　　串 bbbacacb 可以转化成 3b2ac1b，长度为 7；

　　串 aaaaaaaaaa 可以转化为 10a，长度为 3。

•题解

　　定义 $dp_i$ 表示串S 中字符 $S_0,S_1,cdots S_{i}$ 压缩后的最优解；

　　转移方程为：$ dp_i = min(dp_i,dp_j + F(j+1,i)) , j < i$；

　　其中 $F(j+1,i)$ 求解的是子串 $S_{j+1},S_{j+2},cdots ,S_{i}$ 压缩后的解，不一定是最优解；

•Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem(a,b) memset(a,b,sizeof(a))
 4 const int maxn=8e3+50;
 5 
 6 int n;
 7 char s[maxn];
 8 int dp[maxn];
 9 int f[maxn];///f[i]:i的位数
10 vector<int >nex[maxn];///nex[i]:s[i,n-1]对应的next数组
11 int Calc(int x)
12 {
13     int ans=0;
14     while(x)
15     {
16         ans++;
17         x /= 10;
18     }
19     return ans;
20 }
21 void getNext(int x)
22 {
23     nex[x].push_back(-1);
24     nex[x].push_back(0);
25     int index=2;
26     int cnt=0;
27     while(index+x <= n)
28     {
29         if(s[x+index-1] == s[x+cnt])
30         {
31             nex[x].push_back(++cnt);
32             index++;
33         }
34         else if(cnt != 0)
35             cnt=nex[x][cnt];
36         else
37         {
38             nex[x].push_back(0);
39             index++;
40         }
41     }
42 }
43 int F(int l,int r)
44 {
45     int len=r-l+1;
46     int x=r-l+1;
47     if(len%(len-nex[l][len]) == 0)
48         x=len-nex[l][len];
49     return x+f[len/x];
50 }
51 int Solve()
52 {
53     n=strlen(s);
54     for(int i=1;i < maxn;++i)
55         f[i]=Calc(i);
56     for(int i=0;i < n;++i)
57         getNext(i);
58 
59     dp[0]=2;
60     for(int i=1;i < n;++i)
61     {
62         dp[i]=F(0,i);
63         for(int j=0;j < i;++j)
64             dp[i]=min(dp[i],dp[j]+F(j+1,i));
65     }
66     return dp[n-1];
67 }
68 int main()
69 {
70     scanf("%s",s);
71     printf("%d
",Solve());
72 
73     return 0;
74 }

View Code