ABC 366 题解
AtCoder Beginner Contest 366 题解：
\(Problem \hspace{2mm} A - Election \hspace{2mm} 2\)
题目链接
opinion:
很显然，当一个人的票数大于等于 \(\lceil \frac{n}{2} \rceil\) 时此人一定当选。（或可理解为投票结果一定固定。）
依次判断两人即可。
code:
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
const int N = 1e6 + 10;
int n, t, a;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> t >> a;
int k = (n + 1) / 2;
if (t >= k || a >= k) cout << "Yes\n";
else cout << "No\n";
return 0;
}
\(\newline\)
\(\newline\)
\(Problem \hspace{2mm} B - Vertical \hspace{2mm} Writing\)
题目链接
opinion:
这题，呃，我竟然吃了发罚时……
试着把样例顺时针旋转 \(90^\circ\)，是不是与输出几乎一致？
为了方便，在每一个空位填上字符 *，又由于每个串结尾不能有 *，再将末尾连续的 * 去掉即可。
详见代码。
也就是按照题意模拟一下。
code:
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
const int N = 1e6 + 10;
int n, len[N];
string s[N], t[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
int m = 0;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
len[i] = s[i].size();
s[i] = " " + s[i];
m = max(m, len[i]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= len[i]; ++j) {
t[j] = t[j] + s[i][j];
}
//前面有字符的就直接copy
for (int j = len[i] + 1; j <= m; ++j) {
t[j] = t[j] + '*';
}
//否则加 '*'
}
for (int i = 1; i <= m; ++i) {
reverse(t[i].begin(), t[i].end());
int l = t[i].size();
int j = l - 1;
while (t[i][j] == '*') j --;
//找出末尾连续的 '*'，并将末尾更改
for (int k = 0; k <= j; ++k)
cout << t[i][k];
cout << "\n";
}
return 0;
}
\(\newline\)
\(\newline\)
\(Problem \hspace{2mm} C - Balls \hspace{2mm} and \hspace{2mm} Bag \hspace{2mm} Query\)
题目链接
opinion:
用一个数组记录每个数出现的次数，类似于一个桶。
对以下两种情况考虑：
- 增加一个数，若第一次出现，则
ans += 1。桶加加。 - 减少一个数，若减完后为 \(0\)，则
ans -= 1。桶减减。
code:
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
const int N = 1e6 + 10;
int q, cnt[N];
//cnt[i]表示i出现的次数
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> q;
int ans = 0;
//ans统计不同数的个数
while (q -- ) {
int op, x;
cin >> op;
if (op == 1) {
cin >> x;
cnt[x] ++;
if (cnt[x] == 1) ans ++;
//如果加一之后等于一，说明第一次出现，不同数的个数加一
} else if (op == 2) {
cin >> x;
cnt[x] --;
//这个数字出现次数减一
if (cnt[x] == 0) ans --;
//如果减一之后是零，不同数的个数减一
} else {
cout << ans << "\n";
}
}
return 0;
}
\(\newline\)
\(\newline\)
\(Problem \hspace{2mm} D - Reachability \hspace{2mm} in \hspace{2mm} Functional \hspace{2mm} Graph\)
题目链接
opinion:
三维前缀和模板题。类比二维前缀和。
就不细讲了，大家自己看代码吧，也可以上网学习哦~
code:
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
const int N = 110;
ll a[N][N][N];
ll pre[N][N][N];
inline ll query(int N1, int M1, int K1, int N2, int M2, int K2) {
return pre[N2][M2][K2] - pre[N1 - 1][M2][K2] - pre[N2][M1 - 1][K2] - pre[N2][M2][K1 - 1] + pre[N1 - 1][M1 - 1][K2] + pre[N1 - 1][M2][K1 - 1] + pre[N2][M1 - 1][K1 - 1] - pre[N1 - 1][M1 - 1][K1 - 1];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
cin >> a[i][j][k];
pre[i][j][k] = a[i][j][k] + pre[i - 1][j][k] + pre[i][j - 1][k] + pre[i][j][k - 1] - pre[i - 1][j - 1][k] - pre[i - 1][j][k - 1] - pre[i][j - 1][k - 1] + pre[i - 1][j - 1][k - 1];
}
}
}
int q; cin >> q;
while (q -- ) {
ll l[3], r[3];
cin >> l[0] >> r[0] >> l[1] >> r[1] >> l[2] >> r[2];
ll ans = query(l[0], l[1], l[2], r[0], r[1], r[2]);
cout << ans << "\n";
}
return 0;
}
\(\newline\)
\(\newline\)