首页 > 代码库 > Codeforces Round #267 (Div. 2) solution
Codeforces Round #267 (Div. 2) solution
A.George and Accommodation
题目大意：给你n个宿舍的可以容纳的人数和现在已住的人数，问有几个宿舍可以安排两个人进去住。
解法：模拟，无trick。
代码：
1 #include <cstdio> 2 3 int main() { 4 int n; 5 while(scanf("%d", &n) != EOF){ 6 int a, b, ans = 0; 7 for(int i = 0; i < n; i++) { 8 scanf("%d%d", &a, &b); 9 if(b - a >= 2) ans++;10 }11 printf("%d\n", ans);12 }13 14 return 0;15 }
B.Fedor and New Game
题目大意：给你m+1个数，问前m个数的二进制和最后一个数不同的位数小于等于k个的数的个数。
解法：模拟，无trick。求不同的位数可先异或然后看有多少个1。
代码：
1 #include <cstdio> 2 3 int a[1010]; 4 5 int main() { 6 int n, m, k; 7 while(scanf("%d%d%d", &n, &m, &k) != EOF){ 8 int ans = 0; 9 for(int i = 0; i < m; i++) scanf("%d", &a[i]);10 scanf("%d", &a[m]);11 for(int i = 0; i < m; i++) {12 int p = a[i] ^ a[m], t = 0;13 while(p > 0) {14 if(p % 2 == 1) t++;15 p /= 2;16 }17 if(t <= k) ans++;18 }19 printf("%d\n", ans);20 }21 22 return 0;23 }
C.George and Job
题目大意：从n个数中选出m段不相交的子串，子串的长度均为k，问所有选出来的子串的所有数的和最大为多少。
解法：DP即可。dp[i][j]表示从前i个数选出j段的最大和，转移很明显。
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[5010];long long s[5010], dp[5010][5010];int main() { int n, m, k; while(scanf("%d%d%d", &n, &m, &k) != EOF){ int ans = 0; s[0] = 0; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); s[i] = s[i - 1] + a[i]; } for(int i = m; i <= n; i++) { for(int j = k; j >= 1; j--) dp[i][j] = max(dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i - m]); } printf("%I64d\n", dp[n][k]); } return 0;}
D.Fedor and Essay
题目大意：给你一篇由一些单词构成的文章，单词不区分大小写。再给你一些单词的转化关系，即单词a可以被单词b替换（注意是单向的,sb出题人写input里面算什么！）。你可以无限的进行替换操作，现在希望被替换后的文章r的数量最少，在此基础上总长度最短。
解法：显然如果是一个DAG的话我们就可以直接对每个点进行记忆化搜索来更新答案，对这道题显然可以进行缩点，新的点的属性由这个强联通分量里面r最小的情况下最短的单词决定。但是对于这道题的情况我们可以不缩点，按照点的大小关系(即先看r的数量最少的，r一样的情况下看最短的)进行dfs也是正确的（当然直接记忆化搜索是错的，在环的更新上会出现问题）。
代码：
#include <cstdio>#include <map>#include <cstring>#include <vector>#include <string>#include <algorithm>using namespace std;const int N = 100010;struct Node { int r, l, p;}g[5 * N];int ar[5 * N], al[5 * N], u[5 * N];map<string, int> mp;char s[5 * N], t[5 * N];vector<int> e[5 * N], lis;int calc(char q[]) { int res = 0; for(int i = 0; q[i] != ‘\0‘; i++) { if(q[i] >=‘A‘ && q[i] <= ‘Z‘) q[i] = q[i] - ‘A‘ + ‘a‘; if(q[i] == ‘r‘) res++; } return res;}bool cmp(const Node &a, const Node &b) { if(a.r != b.r) return a.r < b.r; if(a.l != b.l) return a.l < b.l; return a.p < b.p;}void dfs(int x, int r, int l) { if(u[x]) return; u[x] = 1; if(r == ar[x]) al[x] = min(al[x], l); if(r < ar[x]) { ar[x] = r, al[x] = l; } for(int i = 0; i < e[x].size(); i++) { int y = e[x][i]; dfs(y, r, l); }}int main() { int n, m; while( scanf("%d", &m) != EOF ) { int n = 0; for(int i = 0; i < m; i++) { scanf("%s", s); int temp = calc(s); if(mp[s] == 0) { mp[s] = ++n; g[n].r = temp; g[n].l = strlen(s); g[n].p = n; } lis.push_back(mp[s]); } int k = m; scanf("%d", &m); for(int i = 0; i < m; i++) { scanf("%s", s); int temp = calc(s); if(mp[s] == 0) { mp[s] = ++n; g[n].r = temp; g[n].l = strlen(s); g[n].p = n; } scanf("%s", t); temp = calc(t); if(mp[t] == 0) { mp[t] = ++n; g[n].r = temp; g[n].l = strlen(t); g[n].p = n; } e[mp[t]].push_back(mp[s]); } sort(g + 1, g + n + 1, cmp); for(int i = 1; i <= n; i++) { ar[g[i].p] = g[i].r; al[g[i].p] = g[i].l; } for(int i = 1; i <= n; i++) dfs(g[i].p, g[i].r, g[i].l); long long ov = 0, ol = 0; for(int i = 1; i <= k; i++) ov += ar[lis[i - 1]], ol += al[lis[i - 1]]; printf("%I64d %I64d\n", ov, ol); } return 0;}
E.Alex and Complicated Task
题目大意：给你n个数，你需要找到一个最长的子序列，使得这个子序列的第4k-4k+3项为a,b,a,b的形式(从0标号)。
解法：我们把数组记为a[]。我们考虑每一对儿相等的数。首先如果某个数出现了4次，那么这4个数可以构成一个答案。假设我以(l, r)表示一对儿相同的数，即a[l] = a[r]。我们按r从小到大对所有的相同数对进行排序。我们考虑开始的两个数对，假设一个为(a, b)，另一个为(c, d)，显然有d > b。如果c <= a，那么明显如果某个数对和(a, b)可以构成答案的话和(c, d)也可以构成答案，也就是说(a, b)是没有用的，我们把(a, b)删掉。如果a<c<=b，那么(a, b)和(c, d)可以构成一个答案。如果c > b的话，那么这是两个不相交的线段，我们同时保留(a, b)和(c, d)。我们照此模拟即可。一些细节和具体的思路可以参考代码。
代码：
#include <cstdio>#include <algorithm>#include <map>#include <vector>#include <string>#include <cstring>using namespace std;const int N = 500010;int a[N];struct P { int l, r, x;}p[N];map<int, int> cnt, pos;vector<int> o;int np = 0;void copy(int a, int b) { o.push_back(a); o.push_back(b); o.push_back(a); o.push_back(b); cnt.clear(); pos.clear(); np = 0;}int main() { int n; while( scanf("%d", &n) != EOF ) { for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) { int x = a[i]; if(cnt[x] != 0) cnt[x]++; else cnt[x] = 1; if(cnt[x] == 4) { copy(x, x); continue;} if(pos[x] == 0) { pos[x] = i; continue; } int l = pos[x], r = i; pos[x] = i; while(np > 0) { int nl = p[np - 1].l, nr = p[np - 1].r, nx = p[np - 1].x; if(nl < l && l < nr) { copy(nx, x); break; } else if(l <= nl) np--; else { p[np].l = l, p[np].r = r, p[np++].x = x; break; } } if(np == 0) p[np].l = l, p[np].r = r, p[np++].x = x; } printf("%d\n", (int)o.size()); for(int i = 0; i < (int)o.size(); i++) printf("%d%c", o[i], i == (int)o.size() - 1?‘\n‘:‘ ‘); } return 0;}
Codeforces Round #267 (Div. 2) solution
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。