Codeforces Round 784 (Div. 4)
题目链接
A. Division?
题意
思路
模拟即可
示例代码
void solve() {int n;cin >> n;int ans;if(n >= 1900) ans = 1;else if(n >= 1600) ans = 2;else if(n >= 1400) ans = 3;else ans = 4;cout << "Division " << ans << '\n';}
B. Triple
题意
思路
模拟即可
void solve() {map<int, int>mp;int n;cin >> n;fer(i, 0, n){int a;cin >> a;mp[a]++;}for(auto it : mp){if(it.second >= 3){cout << it.first << '\n';return;}}cout << -1 << '\n';
}
C. Odd/Even Increments
题意
思路
因为每次操作都是对所有的奇数位置或者所有的偶数位置+1，操作次数是不限的，所以只需要判断初始条件下所有奇数位置的元素奇偶性是否一致，和所有偶数位置的奇偶性是否一致。
示例代码
void solve() {int n;cin >> n;vector<int>arr(n);bool ok = true;fer(i, 0, n) cin >> arr[i];for(int i = 0; i + 2 < n; i += 2){if((arr[i] & 1) != (arr[i + 2] & 1)){ok = false;break;}}if(!ok){cout << "NO" << '\n';return;}for(int i = 1; i + 2 < n; i += 2){if((arr[i] & 1) != (arr[i + 2] & 1)){ok = false;break;}}if(ok) cout << "YES" << '\n';else cout << "NO" << '\n';
}
D. Colorful Stamp
题意
思路
经过分析验证，任意连续区间内同时包含R和B的字符串最终都可以实现。因此，我们只需要判断所有连续W之间的子串是否同时含有R和B即可。
示例代码
void solve() {int n;cin >> n;string s;cin >> s;s = "W" + s + "W";vector<int>arr;fer(i, 0, s.size())if(s[i] == 'W') arr.push_back(i);fer(i, 0, arr.size() - 1){int l = arr[i], r = arr[i + 1];int c1 = 0, c2 = 0;fer(j, l + 1, r){if(s[j] == 'R') c1++;else if(s[j] == 'B') c2++;}//cout << c1 << ' ' << c2 << '\n';if(c1 * c2 == 0 && !(c1 + c2 == 0)){cout << "NO" << '\n'; return;}}cout << "YES" << '\n';
}
E. 2-Letter Strings
题意
思路
题意要我们找出这样的字符串的对数：这两个字符串只有一个位置对应的字符不同。我们可以用二维数组记录每种字符串的个数，再模拟即可。
示例代码
void solve() {int n;cin >> n;string s;int mp[20][20]{};ll ans = 0;while(n--){cin >> s;fer(i, 0, 11){if(s[1] - 'a' != i) ans += mp[s[0] - 'a'][i];if(s[0] - 'a' != i) ans += mp[i][s[1] - 'a'];}mp[s[0] - 'a'][s[1] - 'a']++;}cout << ans << '\n';
}
也可以这样写，区别在于是否重复统计了次数，输入字符串时统计只统计之前的次数，全部输入完再统计会同时统计后面的次数，因此重复了
void solve() {int n;cin >> n;int mp[20][20]{};vector<string>arr(n);fer(i, 0, n) cin >> arr[i], mp[arr[i][0] - 'a'][arr[i][1] - 'a']++;ll ans = 0;fer(i, 0, n){fer(j, 0, 11){if(arr[i][1] - 'a' != j) ans += mp[arr[i][0] - 'a'][j];if(arr[i][0] - 'a' != j) ans += mp[j][arr[i][1] - 'a'];}}cout << ans / 2 << '\n';
}
F. Eating Candies
题意
思路
相向前后指针，注意边界的处理
示例代码
void solve() {int n;cin >> n;vector<int>arr(n + 1);fer(i, 1, n + 1) cin >> arr[i];int s1 = arr[1], s2 = arr.back();int cnt = 0;int l = 1, r = n;while(l < r){while(l < r - 1 && s1 < s2) l++, s1 += arr[l];while(l < r - 1 && s1 > s2) r--, s2 += arr[r];if(s1 == s2) cnt = l + (n - r + 1);l++, s1 += arr[l];}cout << cnt << '\n';
}
G. Fall Down
题意
思路
遍历每一列，从下往上找连续空单元格.，如果在这过程中遇到石头*就进行swap，如果遇到障碍物o，就需要归零空单元格数，重新向上查找.
示例代码
void solve() {int n, m;cin >> n >> m;vector<string> arr(n);fer(i, 0, n) cin >> arr[i];fer(col, 0, m){int row = n - 1, cnt = 0;while(row >= 0){while(row >= 0 && arr[row][col] == '.') cnt++, row--;if(row >= 0 && arr[row][col] == '*') swap(arr[row][col], arr[row + cnt][col]), row--;else cnt = 0, row--;}}for(auto c : arr) cout << c << '\n';cout << '\n';
}