首页 > 代码库 > Codeforces Round #375 (Div. 2) ABCDE
Codeforces Round #375 (Div. 2) ABCDE
A - The New Year: Meeting Friends
水
#include<iostream>#include<algorithm>using namespace std;int main(){ int a,b,c; cin>>a>>b>>c; cout<<max(a,max(b,c)) - min(a,min(b,c)) <<endl; return 0;}
B - Text Document Analysis
字符串暴力模拟,感觉还是需要一点技巧的,我写的太慢了。
#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <iostream>using namespace std;const int N = 260;char a[N];//37//_Hello_Vasya(and_Petya)__bye_(and_OK)bool is_s(char ch) { if (ch == ‘_‘ || ch == ‘(‘ || ch == ‘)‘ || ch == 0) return true; return false;}int read(char str[]) { int idx = 0; int ans = 0; while (!is_s(str[idx++])) ans++; return ans;}int main() { //freopen("in.txt", "r", stdin); int ans1 = 0, ans2 = 0, n = 12; scanf("%d", &n); scanf("%s", a); bool fg = false; for (int i = 0; i <= n;) { if (a[i] == ‘(‘) fg = true; if (a[i] == ‘)‘) fg = false; if (is_s(a[i])) { i++; } else { int tmp = read(a+i); if (!fg) ans1 = max(ans1, tmp); else ans2++; i += tmp; } } cout << ans1 << " " << ans2; return 0;}
C - Polycarp at the Radio
应该也是sb暴力题,map乱搞的(队友写的==
#include <cstdio>#include <map>#include <queue>using namespace std;const int maxn = 2010;map<int, int> mp;queue<int> q;int a[maxn], n, m;int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), mp[a[i]]++; int ans = n / m; for (int i = 1; i <= m; i++) if (mp[i] < ans) q.push(i); int cnt = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 1; i <= n; i++) { if (a[i] > m || mp[a[i]] > ans) mp[a[i]]--, a[i] = v, mp[v]++, cnt++; if (mp[v] >= ans) break; } } printf("%d %d\n", ans, cnt); for (int i = 1; i <= n; i++) printf("%d%c", a[i], i==n?‘\n‘:‘ ‘); return 0;}
D - Lakes in Berland
简单搜索。因为数据小,随便暴力。
#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <iostream>#include <queue>#include <vector>using namespace std;const int N = 60;char mp[N][N];int vis[N][N], n, m, k;int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};int dfs(int x, int y, int cnt) { if (x < 0 || x >= n || y < 0 || y >= m) return -1; if (mp[x][y] == ‘*‘ || vis[x][y]) return 0; vis[x][y] = cnt; int ans = 1; for (int i = 0; i < 4; ++i) { int tmp = dfs(x+dir[i][0], y+dir[i][1], cnt); if (ans != -1) { if (tmp == -1) ans = -1; else ans += tmp; } } return ans;}vector<pair<int, int> > g;int main() { while (~scanf("%d%d%d", &n, &m, &k)) { for (int i = 0; i < n; ++i) scanf("%s", mp[i]); int cnt = 0, tmp, ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (!vis[i][j] && mp[i][j] == ‘.‘) if ((tmp = dfs(i, j, ++cnt)) != -1) g.push_back(make_pair(tmp, cnt)); sort(g.begin(), g.end()); tmp = g.size() - k; for (int i = 0; i < tmp; ++i) ans += g[i].first; printf("%d\n", ans); for (int k = 0; k < tmp; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (vis[i][j] == g[k].second) mp[i][j] = ‘*‘; for (int i = 0; i < n; ++i) printf("%s\n", mp[i]); } return 0;}
E. One-Way Reform
给一个无向图,要求把每个边都变成有向边,使尽可能多的点入度等于出度,问最多能满足多少个点,并输出每条边。(任意顺序)
感觉很厉害的一道题。
无向图存在欧拉回路的充要条件:一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图。
有向图存在欧拉回路的充要条件:一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图。
首先可以知道奇数度的点是不可能到达要求的。找出奇数度的点,两两一对连接,记做虚边,这样就可以保证每个点的度数都是偶数,那么就可以找到一条欧拉回路,保证每个点入度等于出度。
因为总度数是偶数,所以奇数度的点一定是偶数个。
如果图不连通,对每一个连通图求欧拉回路就好了。
然后输出图中非虚边就ok了。
好难想到啊= =队友花了半天给我讲明白的……然后还是WA了好多好多次(我是有多蠢啊T^T
#include <bits/stdc++.h>using namespace std;const int N = 250;struct Edge { int next, from, to, fg; // fg: 0,2未处理 1选 -1不选} e[N*N];int head[N], cntE;void addedge(int u, int v, int fg) { e[cntE].to = v; e[cntE].from = u; e[cntE].next = head[u]; e[cntE].fg = fg; head[u] = cntE++;}int deg[N];void dfs(int u) { for (int i = head[u]; ~i; i = e[i].next) { if (e[i].fg == 0) { e[i].fg = 1; e[i^1].fg = -1; dfs(e[i].to); } else if (e[i].fg == 2) { e[i].fg = e[i^1].fg = -1; dfs(e[i].to); } }}int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif // ONLINE_JUDGE int T, n, m, u, v; scanf("%d", &T); while (T--) { memset(head, -1, sizeof head); cntE = 0; memset(deg, 0, sizeof deg); scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); addedge(u, v, 0); addedge(v, u, 0); deg[u]++, deg[v]++; } int last = 0, odd = 0; for (int i = 1; i <= n; ++i) { if (deg[i] & 1) { ++odd; if (last) addedge(last, i, 2), addedge(i, last, 2), last = 0; else last = i; } } for (int i = 1; i <= n; ++i) dfs(i); printf("%d\n", n - odd); for (int i = 0; i < cntE; ++i) if (e[i].fg == 1) printf("%d %d\n", e[i].from, e[i].to); } return 0;}
F. st-Spanning Tree
挖坑待填……
Codeforces Round #375 (Div. 2) ABCDE
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。