freee Programming Contest 2022(AtCoder Beginner Contest 264)
https://atcoder.jp/contests/abc264
FG待补
A - "atcoder".substr()
输出atcoder第L位和第R位上的字符
#include <bits/stdc++.h>
using namespace std;
int main () {
string s = "atcoder";
int x, y;
cin >> x >> y;
x --, y --;
for (int i = x; i <= y; i ++) cout << s[i];
}
B - Nice Grid
我是直接嗯模拟的
也可以找规律,看奇偶性
#include <bits/stdc++.h>
using namespace std;
int a[17][17]; //黑0白1
int main () {
int x, y;
cin >> x >> y;
for (int i = 2; i <= 14; i ++) a[2][i] = a[i][2] = a[i][14] = a[14][i] = 1;
for (int i = 4; i <= 12; i ++) a[4][i] = a[i][4] = a[i][12] = a[12][i] = 1;
for (int i = 6; i <= 10; i ++) a[6][i] = a[i][6] = a[i][10] = a[10][i] = 1;
a[8][8] = 1;
// for (int i = 1; i <= 15; i ++) {
// for (int j = 1; j <= 15; j ++)
// cout << a[i][j] << ' ';
// cout << endl;
// }
if (a[x][y]) cout << "white";
else cout << "black";
}
C - Matrix Reducing
题意:可以任选A矩阵的某行或某列删去,问能否构成B矩阵
分别按行和按列看能否凑齐B矩阵
也可以暴力枚举删行 / 列
#include <bits/stdc++.h>
using namespace std;
int a[15][15], b[15][15], x, y;
int main () {
int n1, m1, n2, m2;
cin >> n1 >> m1;
for (int i = 0; i < n1; i ++) {
for (int j = 0; j < m1; j ++)
cin >> a[i][j];
}
cin >> n2 >> m2;
for (int i = 0; i < n2; i ++) {
for (int j = 0; j < m2; j ++)
cin >> b[i][j];
}
if (n2 > n1 || m2 > m1) {
cout << "No";
return 0;
}
bool suc = false;
for (int i = 0; i < (1<<n1); i++)
for (int j = 0; j < (1<<m1); j++) {
vector <int> v1, v2;
for(int k = 0; k < n1; k++) if((i & (1<<k)) == 0) v1.push_back(k);
for(int k = 0; k < m1; k++) if((j & (1<<k)) == 0) v2.push_back(k);
if (v1.size() != n2 || v2.size() != m2) continue;
//确保没有偏移
bool match = true;
for (int ii = 0; ii < n2; ii++)
for (int jj = 0; jj < m2; jj++) {
if (a[v1[ii]][v2[jj]] != b[ii][jj]) {
match = false;
break;
}
}
if (match) {
cout << "Yes";
return 0;
}
}
cout << "No";
}
//能否去掉A的某行或某列,使得AB相等
//二进制暴力枚举
D - "redocta".swap(i,i+1)
题意:给一个串,每次能交换相邻的两个字符,问最少要多少次能把他变成"atcoder"
每个字符对应一个数字,不难得出,就是把现有序列变为有序的操作次数。
那么就是经典的求逆序对问题,直接上模板
#include <bits/stdc++.h>
using namespace std;
int a[10], tmp[10];
int merge_sort (int l, int r) {
if (l >= r)
return 0;
int mid = l + r >> 1;
int res = merge_sort (l, mid) + merge_sort (mid + 1, r);
int k = 0, i = l, j = mid + 1; //计数,左半段起点,右半段起点
while (i <= mid && j <= r) {
if (a[i] <= a[j])
tmp[k ++] = a[i ++]; //有序
else {
tmp[k ++] = a[j ++];
res += mid - i + 1; //夹着的那段就是逆序对的数量
}
}
while (i <= mid) tmp[k ++] = a[i ++];
while (j <= r) tmp[k ++] = a[j ++];
for (int i = l, j = 0; i <= r; i ++, j ++)
a[i] = tmp[j];
return res;
}
int main () {
string s;
cin >> s;
for (int i = 0; i < 7; i ++) {
if (s[i] == 'a') a[i] = 1;
else if (s[i] == 't') a[i] = 2;
else if (s[i] == 'c') a[i] = 3;
else if (s[i] == 'o') a[i] = 4;
else if (s[i] == 'd') a[i] = 5;
else if (s[i] == 'e') a[i] = 6;
else if (s[i] == 'r') a[i] = 7;
}
int ans = 0;
if (is_sorted(a, a + 7)) ans = 0;
else {
ans = merge_sort (0, 6);
}
cout << ans << endl;
}
//1234567
//求逆序对数量
E - Blackout 2
题意:\(1--n\) 的点为城市,\(n+1--n+m\)的点为供电站,城市能实现供电的条件是至少连了一个发电站。现连了E条边,有q次操作,每次操作删去一条边,问此时有多少个城市能供上电
删边等于反向加边,然后把所有供电站都连接到超级源点0上(因为所有供电站都是等价的),用并查集维护连通性,以及连通块内编号即可,每次 \(cnt_0\) 就是所需答案
#include <bits/stdc++.h>
using namespace std;
const int M = 5e5 + 5, N = 2e5 + 5;
int n, m, E, q;
bool vis[M]; //表示这边需要删
int fa[N], cnt[N]; //dsu
int query[M];
vector <int> ans;
struct Node {
int u, v;
}e[M];
int find (int x) {
if (x != fa[x]) {
fa[x] = find (fa[x]);
}
return fa[x];
}
int main () {
scanf ("%d%d%d", &n, &m, &E);
for (int i = 1; i <= n; i++) fa[i] = i, cnt[i] = 1; //连通块内点的个数
for (int i = n+1; i <= n+m; i++) fa[i] = 0; //发电站均看成连到0点
for (int i = 1; i <= E; i++) {
int u, v;
scanf ("%d%d", &u, &v);
e[i] = {u, v};
}
scanf ("%d", &q);
for (int i = 0; i < q; i++) scanf ("%d", &query[i]), vis[query[i]] = true;
//最终态,也就是反向增边时的最初态
for (int i = 1; i <= E; i ++) {
if (vis[i]) continue;
int a = e[i].u, b = e[i].v;
int pa = find (a), pb = find (b);
if (pa != pb) {
if (pa == 0) swap (pa, pb); //保证cnt累加到超级源点上
fa[pa] = pb;
cnt[pb] += cnt[pa];
}
}
for (int i = q-1; i >= 0; i--) {
int j = query[i];
int a = e[j].u, b = e[j].v;
ans.push_back (cnt[0]);
int pa = find (a), pb = find (b);
if (pa != pb) {
if (pa == 0) swap (pa, pb);
fa[pa] = pb;
cnt[pb] += cnt[pa];
}
}
reverse (ans.begin(), ans.end());
for (auto i : ans) printf ("%d\n", i);
}
//删边=反向加边