链接：https://atcoder.jp/contests/abc420
A – What month is it?
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
int a, b;
cin >> a >> b;
cout << (a + b - 1) % 12 + 1;
}B – Most Minority
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<string> s(n + 10);
for (int i = 0; i < n; ++i)
cin >> s[i];
vector cnt(n, 0);
for (int j = 0; j < m; ++j)
{
ll cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; ++i)
{
if (s[i][j] == '1')
++cnt1;
else
++cnt0;
}
if (!cnt0 || !cnt1)
{
for (int i = 0; i < n; ++i)
++cnt[i];
}
else if (cnt0 > cnt1)
{
for (int i = 0; i < n; ++i)
{
if (s[i][j] == '1')
++cnt[i];
}
}
else if (cnt0 < cnt1)
{
for (int i = 0; i < n; ++i)
{
if (s[i][j] == '0')
++cnt[i];
}
}
}
ll maxx = ranges::max(cnt);
for (int i = 0; i < n; ++i)
{
if (cnt[i] == maxx)
cout << i + 1 << ' ';
}
cout << endl;
}C – Sum of Min Query
算法：
模拟。
思路：
每次只会影响到 \(x\) 点，所以每次查询重新计算一下这个点即可。
关键代码：
void solve()
{
int n, q;
cin >> n >> q;
vector<ll> a(n), b(n);
for (auto &x : a)
cin >> x;
for (auto &x : b)
cin >> x;
ll sum = 0;
for (int i = 0; i < n; ++i)
sum += min(a[i], b[i]);
while (q--)
{
char c;
ll x, v;
cin >> c >> x >> v;
--x;
sum -= min(a[x], b[x]);
if (c == 'A')
a[x] = v;
else
b[x] = v;
sum += min(a[x], b[x]);
cout << sum << endl;
}
}D – Toggle Maze
算法：
\(bfs\)。
思路：
每个门只在乎开过几次开关，\(bfs\) 多开一维维护开关开了奇偶数即可。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<string> s(n + 10);
for (int i = 0; i < n; ++i)
cin >> s[i];
int x1, x2, y1, y2;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (s[i][j] == 'S')
x1 = i, y1 = j;
else if (s[i][j] == 'G')
x2 = i, y2 = j;
}
}
vector dist(n + 10, vector<array<ll, 2>>(m + 10, {LLONG_MAX, LLONG_MAX}));
vector st(n + 10, vector<array<int, 2>>(m + 10, {0, 0}));
auto bfs = [&]() -> void
{
queue<array<int, 3>> q;
q.push({x1, y1, 0});
dist[x1][y1][0] = 0;
st[x1][y1][0] = 1;
while (q.size())
{
auto [x, y, cnt] = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && s[a][b] != '#' && !(s[a][b] == '?' ? st[a][b][(cnt + 1) % 2] : st[a][b][cnt % 2]))
{
if (s[a][b] == '?')
{
st[a][b][(cnt + 1) % 2] = 1;
q.push({a, b, (cnt + 1) % 2});
dist[a][b][(cnt + 1) % 2] = min(dist[a][b][(cnt + 1) % 2], dist[x][y][cnt % 2] + 1);
}
else if (s[a][b] == '.' || s[a][b] == 'S' || s[a][b] == 'G' || (s[a][b] == 'o' && !cnt) || (s[a][b] == 'x' && cnt))
{
st[a][b][cnt % 2] = 1;
q.push({a, b, cnt});
dist[a][b][cnt % 2] = min(dist[a][b][cnt % 2], dist[x][y][cnt % 2] + 1);
}
}
}
}
};
bfs();
ll ans;
if (dist[x2][y2][0] == LLONG_MAX && dist[x2][y2][1] == LLONG_MAX)
ans = -1;
else
ans = min(dist[x2][y2][0], dist[x2][y2][1]);
cout << ans << endl;
}E – Reachability Query
算法：
并查集。
思路：
并查集维护集合中黑点的数量即可。
关键代码：
vector<int> siz;
struct DSU
{
vector<int> f;
DSU() {}
DSU(int n) { init(n); }
void init(int n)
{
f.resize(n);
iota(f.begin(), f.end(), 0);
siz.assign(n, 0);
}
int find(int x)
{
while (x != f[x])
{
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
{
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};
void solve()
{
int n, q;
cin >> n >> q;
DSU dsu(n);
vector<int> st(n + 10, 0);
while (q--)
{
int op, u, v;
cin >> op;
if (op == 1)
{
cin >> u >> v;
--u, --v;
dsu.merge(u, v);
}
else if (op == 2)
{
cin >> u;
--u;
st[u] = !st[u];
int ff = dsu.find(u);
if (st[u])
++siz[ff];
else
--siz[ff];
}
else
{
cin >> u;
--u;
int ff = dsu.find(u);
if (siz[ff])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}F – kirinuki
还没补。
G – sqrt(n²+n+X)
算法：
神秘初中数学题。
思路：
无。
关键代码：
void solve()
{
ll x;
cin >> x;
ll d = 4 * x - 1;
ll dd = d < 0 ? -d : d;
vector<int> v;
for (ll i = 1; i * i <= dd; i += 2)
{
if (dd % i == 0)
{
v.push_back(i);
if (i * i != dd)
v.push_back(dd / i);
}
}
set<ll> ans;
for (auto x : v)
{
for (int s : {-1, 1})
{
ll a = s * x;
if (d % a)
continue;
ll b = d / a;
ll n = (a - b - 2) / 4;
ans.insert(n);
}
}
cout << ans.size() << endl;
for (auto x : ans)
cout << x << ' ';
cout << endl;
}
