EducationalCodeforcesRound25题解

A. Binary Protocol

水题&＃xff0c;模拟统计出连续的0隔开的每段1的个数即可。

#include
using namespace std;
char s[110];
int n;
int main()
{while(~scanf("%d", &n)){scanf("%s", s);int len &＃61; strlen(s);int t &＃61; 0;s[len] &＃61; &＃39;0&＃39;;for(int i&＃61;0; i<&＃61;len; i&＃43;&＃43;){if(s[i] &＃61;&＃61; &＃39;0&＃39;){printf("%d", t);t &＃61; 0;}else{t&＃43;&＃43;;}}printf("\n");}
}

B. Five-In-a-Row

把每个.位置用’X’替换之后去check即可&＃xff0c;注意替换之后要换回来。

#include
using namespace std;
char maze[12][12];
bool check(int x, int y){maze[x][y]&＃61;&＃39;X&＃39;;for(int i&＃61;0; i<10; i&＃43;&＃43;){for(int j&＃61;0; j<10; j&＃43;&＃43;){if(maze[i][j]&＃61;&＃61;&＃39;O&＃39;||maze[i][j]&＃61;&＃61;&＃39;.&＃39;) continue;int t1 &＃61; 0, t2 &＃61; 0, t3 &＃61; 0, t4 &＃61; 0;for(int k&＃61;j; k<10; k&＃43;&＃43;){if(maze[i][k] &＃61;&＃61; &＃39;X&＃39;) t1&＃43;&＃43;;else break;}for(int k&＃61;i; k<10; k&＃43;&＃43;){if(maze[k][j] &＃61;&＃61; &＃39;X&＃39;) t2&＃43;&＃43;;else break;}for(int k&＃61;0; i&＃43;k<10&&j&＃43;k<10; k&＃43;&＃43;){if(maze[i&＃43;k][j&＃43;k]&＃61;&＃61;&＃39;X&＃39;) t3&＃43;&＃43;;else break;}for(int k&＃61;0; i-k>&＃61;0&&j&＃43;k<10; k&＃43;&＃43;){if(maze[i-k][j&＃43;k]&＃61;&＃61;&＃39;X&＃39;) t4&＃43;&＃43;;else break;}if(t1>&＃61;5||t2>&＃61;5||t3>&＃61;5||t4>&＃61;5){maze[x][y] &＃61; &＃39;.&＃39;;return 1;}}}maze[x][y] &＃61; &＃39;.&＃39;;return 0;
}
int main()
{for(int i&＃61;0; i<10; i&＃43;&＃43;){scanf("%s", maze[i]);}for(int i&＃61;0; i<10; i&＃43;&＃43;){for(int j&＃61;0; j<10; j&＃43;&＃43;){if(maze[i][j]&＃61;&＃61;&＃39;.&＃39;){if(check(i,j)){puts("YES");return 0;}}}}puts("NO");return 0;
}

C. Multi-judge Solving

题意&＃xff1a;在codeforces上有n个不同难度的题目需要你去解决&＃xff0c;现在你在其他OJ上已经解决的最大难度的题目为k&＃xff0c;你要解决一个难度为s的问题的前提条件是你当前解决的所有问题的最大难度d要大于等于s&＃xff0c;现在cf上这些题目你需要全部去解决&＃xff0c;现在问你要通过其他OJ解决几道问题才行

解法&＃xff1a;当前的a[i]个问题中&＃xff0c;如果这个问题难度a[i]*2小于k&＃xff0c;那么k &＃61; max(k,a[i])&＃xff0c;因为我们可以解决这个问题并且更新k值&＃xff0c;否则的话我们就一直递增这个k去找a[i]&＃xff0c;这时候ans加加

#include
using namespace std;
int n, k, mx, a[1010];int main()
{while(~scanf("%d %d", &n,&k)){for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) scanf("%d", &a[i]);sort(a&＃43;1, a&＃43;n&＃43;1);mx &＃61; k;int ans &＃61; 0;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){if(mx>&＃61;(a[i]&＃43;1)/2){mx &＃61; max(mx, a[i]);}else{while(2*mx *&＃61;2;}mx &＃61; max(mx, a[i]);}}printf("%d\n", ans);}
}

D. Suitable Replacement

题意&＃xff1a;给了一个带有?的原串&＃xff0c;又给了一个文本串&＃xff0c;问把这些问号怎么替换可以使得文本串在原串的出现次数最多&＃xff1f;

解法&＃xff1a;贪心&＃xff0c;把所有的?存下来&＃xff0c;然后一个个的去补全一个完整的文本串肯定是最优的&＃xff0c;还要注意处理最后剩下的一段。

#include
using namespace std;
char s[1000010], t[1000010];
int cnt[30];
vector <int> v;
int main()
{scanf("%s", s);scanf("%s", t);for(int i&＃61;0; s[i]; i&＃43;&＃43;){if(s[i] &＃61;&＃61; &＃39;?&＃39;) v.push_back(i);else cnt[s[i]-&＃39;a&＃39;]&＃43;&＃43;;}int l &＃61; 0, st &＃61; 0, sz &＃61; v.size(), len &＃61; strlen(t);while(1){if(!cnt[t[st]-&＃39;a&＃39;]){if(lelse{break;}}else{cnt[t[st]-&＃39;a&＃39;]--;}st&＃43;&＃43;;if(st &＃61;&＃61; len) st &＃61; 0;}for(int i&＃61;l; i&＃39;a&＃39;;printf("%s\n", s);return 0;
}

E. Minimal Labels

题意&＃xff1a;1.对于原来编号u,v的两点&＃xff0c;若存在一条从u指向v的边&＃xff0c;那么重新编号后&＃xff0c;u的编号要小于v的编号。2.重新编号后&＃xff0c;新的编号恰好构成一个1~N的排列。从1到N&＃xff0c;依次输出该节点的新编号。如果有多种编号方案&＃xff0c;输出字典序最小的方案。

解法&＃xff1a;1.题目中给出边,那么存边时存&＃xff0c;并记录入度。2.执行Topsort标准操作&＃xff0c;压入大根堆中而不是栈中。 此时从N到1&＃xff0c;依次给取出的堆顶元素进行编号。当然还有一种对应的小根堆的做法&＃xff0c;为什么这种做法错了呢&＃xff1f;
举个栗子&＃xff1a;3 1 3 1 小根堆输出的是3 1 2而正确答案是2 3 1&＃xff0c;官方题解也给出了证明。

#include
using namespace std;
const int maxn &＃61; 2e6&＃43;7;
int n, m, lable[maxn], du[maxn];
vector <int> G[maxn];
priority_queue <int> q;int main()
{while(~scanf("%d%d", &n,&m)){for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){int u, v;scanf("%d %d", &u,&v);G[v].push_back(u);du[u]&＃43;&＃43;;}for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) if(du[i]&＃61;&＃61;0) q.push(i);int ans &＃61; n;while(!q.empty()){int x &＃61; q.top(); q.pop();lable[x] &＃61; ans--;for(auto i : G[x]){du[i]--;if(du[i] &＃61;&＃61; 0){q.push(i);}}}for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){printf("%d ", lable[i]);}printf("\n");}return 0;
}

F. String Compression
题意&＃xff1a;给了一个字符串&＃xff0c;然后我们可以执行折叠操作&＃xff0c;比如aaaa可以变成4a&＃xff0c;其中前面的数字用10进制表示&＃xff0c;然后要问这个字符串可能变成的字符串的最短长度。

解法&＃xff1a;KMP&＃43;DP。首先要懂一个东西&＃xff0c;就是如何利用KMP的nxt数组求出字符串的周期。(周期就是len-nxt[len])&＃xff0c;证明在白书上有&＃xff0c;非常简单&＃xff0c;不再赘述。这里讲讲这道题的做法&＃xff0c;DP[i]表示到i字符能够择出的最短长度。那么可以转移到什么地方呢&＃xff1f;我们通过枚举的方式&＃xff0c;计算枚举的串是否为周期串进行转移即可。看代码吧&＃xff0c;写的非常清楚。

复杂度O(n*n)

#include
using namespace std;
const int maxn &＃61; 8005;
int n,fail[maxn][maxn], num[maxn], dp[maxn];
char s[maxn];
void Getmin(int &x, int y){if(y}
void getFail(){for(int st&＃61;0; stint len&＃61;n-st, j&＃61;-1;fail[st][0]&＃61;-1;for(int i&＃61;1; iwhile(j>&＃61;0&&s[st&＃43;j&＃43;1]!&＃61;s[st&＃43;i]) j&＃61;fail[st][j];if(s[st&＃43;j&＃43;1]&＃61;&＃61;s[st&＃43;i]) j&＃43;&＃43;;fail[st][i]&＃61;j;}}
}
int main()
{scanf("%s", s);n &＃61; strlen(s);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) num[i]&＃61;num[i/10]&＃43;1;memset(dp, 0x3f, sizeof(dp));getFail();//dp[0]&＃61;0;for(int st&＃61;0; stfor(int len&＃61;1; st&＃43;len<&＃61;n; len&＃43;&＃43;){Getmin(dp[st&＃43;len-1],dp[st-1]&＃43;len&＃43;1);int loop&＃61;len-1-fail[st][len-1];if(len%loop&＃61;&＃61;0){Getmin(dp[st&＃43;len-1], dp[st-1]&＃43;loop&＃43;num[len/loop]);}}}printf("%d\n", dp[n-1]);return 0;
}

G. Tree Queries

题意&＃xff1a;给出一颗树&＃xff0c;两种操作一种是把某一个点涂成黑色&＃xff0c;另外一个是计算这个点到所有黑点的路径上的最小的点的标号。

解法&＃xff1a;参见官方题解。

#include
using namespace std;
const int maxn &＃61; 1000010;
int n, q, last, x, minn, f[maxn];
vector <int> G[maxn];
void dfs(int x, int val){f[x] &＃61; val;for(auto v : G[x]){if(!f[v]) dfs(v, min(val, v));}
}
int main()
{while(~scanf("%d %d", &n,&q)){for(int i&＃61;0; ifor(int i&＃61;1; iint u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}int op;scanf("%d %d", &op,&x);last &＃61; 0;x &＃61; (x&＃43;last)%n&＃43;1;minn &＃61; x;dfs(x, x);q--;while(q--){scanf("%d %d", &op,&x);x &＃61; (x&＃43;last)%n&＃43;1;if(op &＃61;&＃61; 1){minn &＃61; min(minn, f[x]);}else{last &＃61; min(minn, f[x]);printf("%d\n", last);}}}
}
#include
using namespace std;
const int maxn &＃61; 1000010;
int n, q, last, x, minn, f[maxn];
vector <int> G[maxn];
void dfs(int x, int val){f[x] &＃61; val;for(auto v : G[x]){if(!f[v]) dfs(v, min(val, v));}
}
int main()
{while(~scanf("%d %d", &n,&q)){for(int i&＃61;0; ifor(int i&＃61;1; iint u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}int op;scanf("%d %d", &op,&x);last &＃61; 0;x &＃61; (x&＃43;last)%n&＃43;1;minn &＃61; x;dfs(x, x);q--;while(q--){scanf("%d %d", &op,&x);x &＃61; (x&＃43;last)%n&＃43;1;if(op &＃61;&＃61; 1){minn &＃61; min(minn, f[x]);}else{last &＃61; min(minn, f[x]);printf("%d\n", last);}}}
}