A Division?
题意: 分段输出r a t i n g {rating}rating值所对应级别
void solve() { int n; cin >> n; int x = -1; if(n >= 1900) x = 1; else if(n >= 1600) x = 2; else if(n >= 1400) x = 3; else if(n <= 1399) x = 4; cout << "Division " << x << endl; }
B Triple
题意: 给定数组中某数出现 > = {>=}>= 3次就输出该数，否则输出− 1 {-1}−1
map<int, int> s; void solve() { s.clear(); int n; cin >> n; int o = 0; int res = 0; for (int i= 0; i < n; i++) { int x; cin >> x; s[x] ++; if(s[x] >= 3) o = 1, res = x; } if(o) cout << res << endl; else cout << -1 << endl; }
C Odd/Even Increments
题意: 要么对所有奇位，要么对所有偶位操作一次，问是否最后数组奇偶性能一致。
操作： + 1 或 + 0 { +1 或+0 }+1或+0
void solve() { int n; cin >> n; vector<int> v; v.resize(n); for (int i = 0; i < n; i++) cin >> v[i]; int x = (v[0] & 1); for (int i = 2; i < n; i += 2) { int j = (v[i] & 1); if(x != j) { cout << "NO" << endl; return ; } } int y = (v[1] & 1); for (int i = 3; i < n; i += 2) { int j = (v[i] & 1); if(y != j) { cout << "NO" << endl; return ; } } cout << "YES" << endl; }
D Colorful Stamp
题意: 长度为n的字符串，RB印章，判断该字符串是否合法。印章可以旋转，RB，BR，并且印会覆盖上一次，印的时候印章的R和B都要在字符串内部。
思路: 以W字符分隔出每一段RB序列。不符合的情况：长度为1，或者全R，或者全B。其它情况都可以满足，可证。
bool func(string s) { if(s == "") return true; if(s.sz == 1) return false; if(s.find("R") == -1 || s.find("B") == -1) return false; return true; } void solve() { int n = 1; cin >> n; string s; cin >> s; string t = ""; for (int i = 0; i < s.sz; i++) { if(s[i] == 'W') { if(!func(t)) { cout << "NO" << endl; return ; } t = ""; continue; } t += s[i]; } if(!func(t)) { cout << "NO" << endl; return ; } cout << "YES" << endl; }
E 2-Letter Strings
题意: 求这样的( i , j ) {(i, j)}(i,j)数对的个数，满足i < j 并 且 S i 与 S j 仅 有 一 个 字 符 不 同暴力求解。
代码一：
int st[30][30]; void solve() { memset(st, 0, sizeof st); int res = 0; int n; cin >> n; for (int i = 0; i < n; i++) { string s; cin >> s; int a = s[0] - 'a', b = s[1] - 'a'; for (int j = 0; j < 26; j++) { if(j != a) res += st[j][b]; if(j != b) res += st[a][j]; } st[a][b]++; } cout << res << endl; }
代码二：
map<string, int> mp; void solve() { mp.clear(); int n; cin >> n; int ans = 0; for (int i = 0; i < n; i++) { string s; cin >> s; string t = s; for (int j = 0; j < 26; j++) { if(s[0] != j + 'a') { t[0] = j + 'a'; ans += mp[t]; t = s; } if(s[1] != j + 'a') { t[1] = j + 'a'; ans += mp[t]; t = s; } } mp[s] ++; } cout << ans << endl; }
F Eating Candies
题意: 左右找到不相交的前后缀值相同，求最大的这种情况下，加起一共多少位数。
int a[N], b[N]; void solve() { int n = 1; cin >> n; for (int i = 0; i <= n; i++) a[i] = b[i] = 0; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i]; for (int i = 1; i <= n; i++) a[i] += a[i - 1]; for (int i = n - 1; i >= 1; i--) b[i] += b[i + 1]; for (int i = 1; i <= n / 2; i++) swap(b[i], b[n - i + 1]); int res = 0; for (int i = 1; i <= n; i++) { int d = lower_bound(b + 1, b + 1 + n, a[i]) - b; if(n - d < i) break; if(d <= n && b[d] == a[i]) { res = i + d; } } cout << res << endl; }
G Fall Down
题意: *向下下落，模拟就行
void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> cc[i][j]; int k = 1022; while (k--) { for (int i = n - 1; i >= 1; i--) { for (int j = 1; j <= m; j++) { if (cc[i][j] == '*' && cc[i + 1][j] == '.') cc[i][j] = '.', cc[i + 1][j] = '*'; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cout << cc[i][j]; cout << endl; } cout << endl; }
H Maximal AND
题意: k次操作，每次操作可选择数组中一个数在任意位（< = 30 {<=30}<=30）置1，求最后数组所有元素相与的最大值。
思路: 贪心， 从高位开始，在第i {i}i位能填满1就消耗k去填。
int n, m; int a[N]; int s[35]; void solve() { cin >> n >> m; memset(s, 0, sizeof s); for (int i = 1; i <= n; i++) { cin >> a[i]; for (int j = 30; j >= 0; j--) { if(a[i] >> j & 1) s[j]++; } } for (int i = 30; i >= 0; i--) { if(m + s[i] >= n) { for (int j = 1; j <= n; j++) a[j] |= (1ll << i); m -= n - s[i]; // Dbug(m); } } int res = 0; for (int i = 0; i <= 30; i++) res |= (1ll << i); // for (int i = 1; i <= n; i++) {cout << a[i] << ' '; } // cout << endl; for (int i = 1; i <= n; i++) res &= a[i]; cout << res << endl; }
