「CF1214X」Codeforces Round #583
A. Optimal Currency Exchange
只有 1 美元和 5 欧元是有用的，直接枚举美元数即可通过
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, d, e; int main() { n = read(); d = read(); e = read(); e = e * 5; int ans = n; for(int i = 0; i <= n / 100 + 1; i++) if(n - i * e >= 0) ans = min(ans, (n - i * e) % d); cout << ans << endl; return 0; } |
B. Badges
枚举一下蓝色校徽的个数，并得出红色校徽的个数，这时判断一下有没有超过男女生人数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, g, b; int main() { g = read(); b = read(); n = read(); int ans = n + 1; for(int i = 0; i <= n; i++) if(i < n - g || i > b) ans--; cout << ans << endl; return 0; } |
C. Bad Sequence
我把这一题想复杂了。合法的括号序列判断方法是，把左括号看作 +1，右括号看作 -1，只要前缀和都大等于 0 就可以。
当不合法的括号序列使得前缀和为 -1 时，只要把这个右括号扔到最后去就行。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; char ch[200005]; bool check() { int sum = 0; bool flag = 0; for(int i = 0; i < n; i++) { if(ch[i] == '(') sum++; else if(ch[i] == ')') sum--; if(sum < 0) { if(flag) return 0; flag = 1; bool tmp = 0; for(int j = n - 1; j >= i; j--) if(ch[j] == '(') { ch[j] = '0'; sum = 0; tmp = 1; break; } if(!tmp) return 0; } } return sum==0; } int main() { n = read(); scanf("%s", ch); if(check()) puts("Yes"); else puts("No"); return 0; } |
D. Treasure Island
题意看起来很像一个网络流问题，分析性质后发现：
首先答案是 1 或 2，因为可以把起点直接堵上。斜着看成一个分层图，如果某一层只有一个结点和起点终点连通，答案就是 1，否则答案是 2。
这个判断只要从起点和终点各做一次 dp 就可以。
比赛的时候偷懒用 map，TLE#101
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<map> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m; string s[1000005]; vector<int> f[1000005], g[1000005]; int cnt[2000005]; int main() { n = read(); m = read(); for(int i = 0; i < n; i++) cin >> s[i]; for(int i = 0; i < n; i++) f[i] = vector<int>(m), g[i] = vector<int>(m); f[0][0] = 1; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(f[i][j] && s[i][j] != '#') { if(i + 1 != n) f[i + 1][j] = 1; if(j + 1 != m) f[i][j + 1] = 1; } g[n-1][m-1] = 1; for(int i = n-1; i >= 0; i--) for(int j = m-1; j >= 0; j--) if(g[i][j] && s[i][j] != '#') { if(i - 1 >= 0) g[i - 1][j] = 1; if(j - 1 >= 0) g[i][j - 1] = 1; } if(!f[n - 1][m - 1]) { puts("0"); return 0; } for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(f[i][j] && g[i][j] && s[i][j] != '#') cnt[i + j]++; for(int i = 1; i < n + m - 2; i++) if(cnt[i] == 1) { puts("1"); return 0; } puts("2"); return 0; } } |
E. Petya and Construction Set
这个构造很有趣。
考虑按深度从大到小排序依次满足每对结点，先把每对结点的前一个排成一条链，按照距离计算一下另一个结点在哪就行。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; pair<int, int> d[100005]; int a[200005]; int main() { n = read(); for(int i = 1; i <= n; i++) { int x = read(); d[i] = make_pair(x, i); } sort(d + 1, d + n + 1, greater<pair<int, int> >()); int m = d[1].first; a[0] = d[1].second * 2; a[m] = d[1].second * 2 - 1; for(int i = 1; i <= m - 1; i++) a[i] = d[i + 1].second * 2; for(int i = 2; i <= n; i++) { int x = 2 * d[i].second, D = d[i].first; if(i <= d[1].first) { if(i + D - 2 == m) { m++; a[m] = x - 1; } else cout << x - 1 << ' ' << a[i + D - 2] << endl; } else { cout << a[0] << ' ' << x << endl; if(D == 1) cout << x << ' ' << x - 1 << endl; else cout << x - 1 << ' ' << a[D - 2] << endl; } } for(int i = 0; i < m; i++) cout << a[i] << ' ' << a[i + 1] << endl; return 0; } |
Subscribe
计数器 9319386
OI 课件=>
OI 课件=>