Codeforces Round 806 (Div. 4) A-G(补题)
A. YES or YES?
思路：一次判断三个字母是否是 y、e、s 的大小写即可。
这题是很久前写的，哈哈，马蜂改了不少。。
#include <bits/stdc++.h>
using namespace std;
int n;
char s[5];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
if (s[1] == 'Y' || s[1] == 'y')
if (s[2] == 'E' || s[2] == 'e')
if (s[3] == 'S' || s[3] == 's')
puts("YES");
else
puts("NO");
else
puts("NO");
else
puts("NO");
}
}
B. ICPC Balloons
思路：变量字符串，用一个 bool 数组记录是否是第一次出现，第一次出现加 2， 否则加 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
void solve() {
int n, cnt = 0;
string s;
cin >> n >> s;
vector<bool> v(27);
for (auto i : s) {
if (v[i - 'A' + 1])
++cnt;
else
cnt += 2;
v[i - 'A' + 1] = true;
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (; t--; )
solve();
}
C. Cypher
思路：可以算出向上向下的次数，之后进行运算即可，但是需要 +10，因为如果不加 10 会出现运算结果为负数的情况，但其实是向上，1->0, 0->9
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
void solve() {
int n;
cin >> n;
vector<int> v(n + 5);
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
string s;
cin >> s;
int cnt = 0;
for (auto i : s) {
if (i == 'D') ++cnt;
else --cnt;
}
cnt %= 10;
v[i] = (v[i] + cnt + 10) % 10;
}
for (int i = 1; i <= n; i++)
cout << v[i] << " ";
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (; t--; )
solve();
}
D. Double Strings
思路：可以发现，题目给的字符串长度只有 8，所以可以直接暴力解决，通过 substr 截取字符串，截取方式是分割线一个个移过去，因为字符串长度只有 8，所以比较快，之后判断两端字符串是否存在即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
void solve() {
int n;
cin >> n;
string str[n + 5];
vector<int> ans(n + 5);
map<string, bool> f;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
f[s] = true;
str[i - 1] = s;
}
for (int i = 1; i <= n; i++) {
int l = int(str[i - 1].size());
if (l == 1) {
ans[i] = 0;
continue;
}
l--;
bool ok = false;
for (int j = 0; j < l; j++) {
string s1 = str[i - 1].substr(0, j + 1);
string s2 = str[i - 1].substr(j + 1);
// if ((l + 1) & 1 || j + 1 != (l + 1) / 2) {
if (f[s1] && f[s2]) {
// cout << s1 << " " << s2 << "\n";
// cout << i << " " << "this\n";
ok = true;
continue;
}
// }
// else {
// if (f[s1] || f[s2]) {
// cout << s1 << " " << s2 << "\n";
// cout << i << " " << "there\n";
// ok = true;
// continue;
// }
// }
}
if (ok)
ans[i] = 1;
else
ans[i] = 0;
// cout << "\n";
}
for (int i = 1; i <= n; i++)
cout << ans[i];
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (; t--; )
solve();
}
E. Mirror Grid
思路：这道题的突破点就是需要推出坐标 (x, y) 经过 90度、180度、270度 会变成什么样，如果知道这个就好办了，只要看一下这个四个坐标的值是否相等，然后修改尽可能少的，遍历完二维数组就解出来了，因为数据范围较小，我没优化，遍历了整个矩阵也能过。
我的 string 是 0 开始存的，如果 1 开始存的可能需要变一下
原先的 v[x][y]
90度 v[y][n - 1 - x]
180度 v[n - 1 - x][n - 1 - y]
270度 v[n - 1 - y][x]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
void solve() {
int n;
cin >> n;
vector<string> v(n + 5, string(n + 5, ' '));
for (int i = 0; i < n; i++)
cin >> v[i];
/*
90: x: y y: n - 1 - x;
180: x: y:
90: x: y, y: -x(n - 1 - x)
180: x: -x(n - 1 - x), y: -y(n - 1 - y);
270: x: -y(n - 1 - y), y: x;
*/
int ans = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
int c1 = 0, c2 = 0;
if (v[x][y] == '1') ++c1; else ++c2;
if (v[y][n - 1 - x] == '1') ++ c1; else ++c2;
if (v[n - 1 - x][n - 1 - y] == '1') ++c1; else ++c2;
if (v[n - 1 - y][x] == '1') ++c1; else ++c2;
if (c1 == 4 || c2 == 4) continue;
if (c1 > c2)
v[x][y] = v[y][n - 1 - x] = v[n - 1 - x][n - 1 - y] = v[n - 1 - y][x] = '0';
else
v[x][y] = v[y][n - 1 - x] = v[n - 1 - x][n - 1 - y] = v[n - 1 - y][x] = '1';
ans += 4 - max(c1, c2);
// cout << c1 << " " << c2 << "| ";
}
// cout << "\n";
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (; t--; )
solve();
}
F. Yet Another Problem About Pairs Satisfying an Inequality
思路：如果暴力 O(n^2) 数据显然是会爆的，那怎么优化呢，可以发现，如果 a < b < c, (a,b) 符合，那么 (a,c) 必然也符合。所以可以统计前面的符合条件的有几对，就可以 O(1) 获取这个对数了。所以就优化到 O(n) 了。需要注意的是，可以这样的数对为 0。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
void solve() {
int n;
cin >> n;
vector<pair<int, int>> f(n + 5);
vector<int> cc(n + 5);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x < i) {
f[i] = {x, i};
// cnt[i] += ;
cc[i]++;
}
}
for (int i = 2; i <= n; i++)
cc[i] += cc[i - 1];
// for (int i = 1; i <= n; i++)
// cout << cc[i] << " ";
ll sum = 0;
// cout << "\n";
for (int i = 2; i <= n; i++) {
if (f[i].second) {
int idx = f[i].first - 1;
// cout << i << " " << f[i].first << " " << idx << " ";
// cout << cc[idx] << "\n";
if (idx >= 1)
sum += cc[idx];
}
}
cout << sum << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (; t--; )
solve();
}
G. Good Key, Bad Key
思路：这道题没看题解前确实没思路，看了官方的 Tutorial 后，发现，这个贪心应该是需要自己想出来的。考虑两个箱子的情况，可以发现，如果第一个箱子用好钥匙，第二个箱子用坏钥匙，那么可以获得的数量一共是
, 而如果第一个箱子用坏钥匙，第二个箱子用好钥匙，那么可以获得的数量一共是
, 可以发现，第一个式子显然大于第二个式子，于是，可以贪心，贪心规则就是先用好钥匙，再用坏钥匙，那还有一个问题，这样是 O(n^2) 的复杂度，显然是会爆的，但是发现题目规则，用了坏钥匙后面的箱子包括自己都要除 2，通过 python 计算可以发现，log2(1e9) = 29.897352853986263, 所以，坏钥匙只需要遍历最多 30 个就行，所以复杂度优化为了 O(n)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
void solve() {
int n, k;
cin >> n >> k;
vector<ll> v(n + 5), gd(n + 5);
for (int i = 1; i <= n; i++)
cin >> v[i];
ll ans = 0;
// cout << "v[0] " << v[0] << "\n";
for (int i = 0; i <= n; i++) {
ll good = 0, bad = 0;
good = v[i];
good -= k;
int idx = i + 1;
for (int j = 1; j <= min(n, 30); j++) {
// cout << i << " "<<idx << " " << "v[idx] = " << v[idx] << "\n" << pow(2, j) << " " << v[idx] / pow(2, j) << "\n";
// cout << pow(2, j) << "\n";
if (idx > n) break;
bad += v[idx++] / pow(2, j);
}
if (i >= 1)
gd[i] = gd[i - 1] + good;
// cout << good << " " << bad << " " << gd[i] << "\n";
ans = max(ans, gd[i] + bad);
}
// for (int i = 1; i <= n; i++)
// cout << gd[i] << " ";
// cout << "\n";
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (; t--; )
solve();
}