热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

EducationalCodeforcesRound25题解

A.BinaryProtocol水题,模拟统计出连续的0隔开的每段1的个数即可。#includeusingnamespacestd;c

A. Binary Protocol

水题,模拟统计出连续的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);}}}
}


推荐阅读
author-avatar
樊赜思
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有