2017ACM萧山训练第4场(CTUO 2015)
D.Falcon Dive
计算左下角的像素移动的距离，直接模拟
|
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, m; string a[1005], b[1005], c[1005]; int x, y, p, q; int main() { while(1) { n = read(), m = read(); if(n == 0)break; if(a[0] != "")cout << endl; string str; cin >> str; for(int i = 0; i < n; i++) c[i] = ""; for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> b[i]; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(a[i][j] == str[1]) x = i, y = j; if(b[i][j] == str[1]) p = i, q = j; } x = p - x, y = q - y; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(a[i][j] != str[1])c[i] += a[i][j]; else c[i] += b[i][j]; } for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(b[i][j] == str[1] && i + x >= 0 && j + y >= 0 && i + x < n && j + y < m) c[i + x][j + y] = str[1]; for(int i = 0; i < n; i++) cout << c[i] << endl; } return 0; } |
F.The Fox and the Owl
贪心
如果 n 是负数，找 n 最低的非9的位加1
考虑在 n 的某一个高位减1，在之后的低位中加2
如果存在多个满足的高位，取最低的一个
若不存在，构造一个绝对值最小的负数
|
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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#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; string str; int main() { while(cin >> str) { if(str[0] == 'E')break; int l = str.length(); if(str[0] == '-') { bool flag = 0; for(int i = l - 1; i >= 1; i--) if(str[i] != '9') { str[i]++; flag = 1; break; } if(!flag) { str[0] = '1'; cout << '-'; } cout << str << endl; continue; } str = ' ' + str; bool flag = 0; int mn = 0, cnt = 0, sum = 0; for(int i = 1; i <= l; i++) sum += str[i] - '0'; for(int i = l; i; i--) { if(str[i] == '1' && i == 1)continue; if((str[i] != '0') && cnt >= 2) { mn = i; flag = 1; break; } cnt += '9' - str[i]; } if(flag) { cnt = 2; str[mn]--; sum = 2; for(int i = mn + 1; i <= l; i++) sum += str[i] - '0'; for(int i = mn + 1; i <= l; i++) { str[i] = '0' + min(sum, 9); sum -= min(sum, 9); } for(int i = 1; i <= l; i++) cout << str[i]; cout << endl; } else if(sum + 1 <= 9 * (l - 1)) { sum++; for(int i = 1; i <= sum / 9; i++) cout << '9'; if(sum % 9) { cout << sum % 9; l--; } l -= sum / 9; for(int i = 1; i <= l - 1; i++) cout << '0'; cout << endl; } else { sum++; printf("-"); if(sum % 9)cout << sum % 9; for(int i = 1; i <= sum / 9; i++) cout << '9'; cout << endl; } } return 0; } |
J.Jumping Yoshi
两个点连边的条件是 \(d_y – d_x = a_y + a_x, y > x\)
由于点对不超过10^6，扫一遍用 map 维护，把所有的边用并查集连起来
输出起点所在集合内最大的
|
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 |
#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; int a[1000005], fa[1000005]; map<int, vector<int> >mp; int find(int x) { return fa[x] == x? x: fa[x] = find(fa[x]); } int main() { while(1) { n = read(); if(n == 0)break; for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= n; i++) a[i] = read(); mp.clear(); mp[a[1] + 1].push_back(1); for(int i = 2; i <= n; i++) { vector<int> t = mp[i - a[i]]; for(int j = 0; j < t.size(); j++) fa[find(t[j])] = find(i); mp[a[i] + i].push_back(i); } for(int i = n; i >= 1; i--) if(find(i) == find(1)) { printf("%d\n", i - 1); break; } } return 0; } |
I.Lunch Menu
枚举前两个数，得出 O(n^2) 个数字后排序
后两个类似，然后两个序列排序后扫一下
对着暴力想了半天没什么改进，交上去发现过了
把 n^2 个数塞进桶里维护前缀和可以少 log，但是多个1e8，其实跑起来没什么差别
意义不明
|
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 |
#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 L, n[5]; int a[5][5005], t1, t2; int p[25000005], q[25000005]; int main() { while(1) { L = read(); for(int i = 1; i <= 4; i++) n[i] = read(); if(L == 0)break; for(int i = 1; i <= 4; i++) for(int j = 1; j <= n[i]; j++) a[i][j] = read(); t1 = t2 = 0; for(int x = 1; x <= n[1]; x++) for(int y = 1; y <= n[2]; y++) p[++t1] = a[1][x] + a[2][y]; for(int x = 1; x <= n[3]; x++) for(int y = 1; y <= n[4]; y++) q[++t2] = a[3][x] + a[4][y]; sort(p + 1, p + t1 + 1); sort(q + 1, q + t2 + 1); int r = t2; ll ans = 0; for(int i = 1; i <= t1; i++) { while(r >= 1 && p[i] + q[r] > L)r--; ans += r; } cout << ans << endl; } return 0; } |
O.The Owl and the Fox
递推出每个数字的数位和，暴力
|
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 |
#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; string str; int f[100005]; int main() { for(int i = 1; i <= 100000; i++) f[i] = f[i / 10] + (i % 10); while(cin >> str) { if(str[0] == 'E')break; int tmp = 0; for(int i = 0; i < str.length(); i++) tmp = tmp * 10 + (str[i] - '0'); for(int i = tmp - 1; i >= 0; i--) if(f[i] < f[tmp]) { printf("%d\n", i); break; } } return 0; } |
S.Hacking the Screen
先写个能算出简单表达式的模拟，然后类似的在外面套一个分式和根号
|
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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #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 R, C; string s[4]; int cal(int l, int r, int t) { while(s[t][l] == ' ')l++; while(s[t][r] == ' ')r--; stack<int> opt, num; int tmp = 0, bin = 1; for(int i = r; i >= l; i--) { if(s[t][i] == '-')opt.push(-1), i--; else if(s[t][i] == '+')opt.push(1), i--; else if(s[t][i] == '*')opt.push(0), i--; else if(s[t][i] <= '9' && s[t][i] >= '0') { tmp = tmp + bin * (s[t][i] - '0'); bin *= 10; } else { if(opt.size() && opt.top() == 0) { opt.pop(); int x = num.top(); num.pop(); num.push(x * tmp); } else num.push(tmp); tmp = 0; bin = 1; } } int ans = tmp; if(opt.size() && opt.top() == 0) { opt.pop(); int x = num.top(); num.pop(); ans *= x; } while(!opt.empty()) { ans += num.top() * opt.top(); num.pop(); opt.pop(); } return ans; } int f(int l, int r, int t) { stack<int> opt, num; int tmp = 0, bin = 1; for(int i = r, j; i >= l; i = j - 1) { j = i; if(t == 2 && s[t][i] == '=') { while(s[t][j - 1] == '=')j--; tmp = cal(j, i, 1) / cal(j, i, 3); } else if(t == 2 && s[t - 1][i] == '_') { while(s[t][j] != '\\')j--; tmp = cal(j + 2, i, 2); tmp = sqrt(tmp); } else if(s[t][i] == '-')opt.push(-1), j--; else if(s[t][i] == '+')opt.push(1), j--; else if(s[t][i] == '*')opt.push(0), j--; else if(s[t][i] <= '9' && s[t][i] >= '0') { tmp = tmp + bin * (s[t][i] - '0'); bin *= 10; } else { if(opt.size() && opt.top() == 0) { opt.pop(); int x = num.top(); num.pop(); num.push(x * tmp); } else num.push(tmp); tmp = 0; bin = 1; } } int ans = tmp; if(opt.size() && opt.top() == 0) { opt.pop(); int x = num.top(); num.pop(); ans *= x; } while(!opt.empty()) { ans += num.top() * opt.top(); num.pop(); opt.pop(); } return ans; } int main() { while(1) { R = read(); C = read(); if(R == 0)break; for(int i = 1; i <= R; i++) { getline(cin, s[i]); s[i] = " " + s[i]; } if(R == 1)cout << f(1, C, 1) << endl; else cout << f(1, C, 2) << endl; } return 0; } |
Subscribe
计数器 9773997
OI 课件=>
OI 课件=>