比赛的时候只切了 \(5\) 题，自闭了。
赛后抱着试一试的心态 F 交了一发 dfs，结果就过了？？？
看来比赛的时候还是要敢写敢交啊……
不过还好上青了……
A - A?C
简单字符串。
#include <bits/stdc++.h>
using namespace std;
const int N = 200003, M = N << 1;
int n, k;
int a[N], b[N];
char s[N];
int main()
{
scanf("%s", s + 1);
if (s[2] == 'R') s[2] = 'B';
else s[2] = 'R';
cout << s + 1 << endl;
return 0;
}
B - Trick or Treat
简单模拟，开个桶即可。
#include <bits/stdc++.h>
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int N = 103, M = N << 1;
int n, k;
int a[N], b[N];
int main()
{
n = gi(), k = gi();
for (int i = 1; i <= k; i+=1)
{
int d = gi();
for (int j = 1; j <= d; j+=1)
a[j] = gi(), ++b[a[j]];
}
int cnt = 0;
for (int i = 1; i <= n; i+=1) cnt += (b[i] == 0);
cout << cnt << endl;
return 0;
}
C - Peaks
建完图后枚举每个点判断是否满足条件。
#include <bits/stdc++.h>
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int N = 100003, M = N << 1;
int n, k;
int a[N];
int tot, head[N], ver[M], nxt[M];
inline void add(int u, int v)
{
ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
int main()
{
n = gi(), k = gi();
for (int i = 1; i <= n; i+=1) a[i] = gi();
for (int i = 1; i <= k; i+=1)
{
int u = gi(), v = gi();
add(u, v), add(v, u);
}
int cnt = 0;
for (int i = 1; i <= n; i+=1)
{
bool fl = true;
for (int j = head[i]; j; j = nxt[j])
{
int v = ver[j];
if (a[v] >= a[i]) {fl = false; break;}
}
if (fl) ++cnt;
}
cout << cnt << endl;
return 0;
}
D - I hate Factorization
一开始以为是一道因式分解的数学题，结果发现只需要确定一个范围后枚举就行了。
我把 \(A\) 和 \(B\) 的范围限定在 \([-7777,7777]\)，这样也可以过。
预处理负数的时候可以使用数组偏移的技巧。
注意开 \(\text{long long}\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int N = 100003, M = N << 1;
int n, k;
LL fac5[N];
int main()
{
n = gi();
LL now = 1;
for (int i = 1; i <= 20000; i+=1)
{
now = 1;
for (int j = 1; j <= 5; j+=1) now *= (i - 7778);
fac5[i] = now;
}
for (int i = -7777; i <= 7777; i+=1)
for (int j = -7777; j <= 7777; j+=1)
if (fac5[i + 7778] - fac5[j + 7778] == n)
{
printf("%d %d\n", i, j);
return 0;
}
return 0;
}
E - This Message Will Self-Destruct in 5s
我们假设选的两个数分别是 \(i\) 和 \(j\) \((i>j)\)。
根据题意可得：\(i-j=a_i+a_j\)。
移项：\(i-a_i=j+a_j\)。
那么我们对于每一个 \(i\)，开个桶记录一下区间 \([1,\ i-1]\) 中等于 \(i-a_i\) 的 \(j+a_j\) 的个数 \((j\in [1,\ i-1])\)。
注意到 \(i-a_i\) 最大为 \(199999\)，因此我们只需要记录 \(\leq 199999\) 的 \(j+a_j\) 的个数。
倒序循环计算答案即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int N = 200003, M = N << 1;
int n, k;
int a[N], b[N];
int s[N] /*i + a[i]*/, t[N] /*j - a[j]*/;
int ton[M];
LL ans;
int main()
{
n = gi();
for (int i = 1; i <= n; i+=1)
a[i] = gi(), s[i] = i + a[i], t[i] = i - a[i];
for (int i = 1; i <= n; i+=1)
if (s[i] < 200000) ++ton[s[i]];
for (int i = n; i >= 1; i-=1)
{
if (t[i] <= 0) continue;
if (t[i] >= 200000) continue;
ans += ton[t[i]];
if (s[i] < 200000) --ton[s[i]];
}
printf("%lld\n", ans);
return 0;
}
F - Three Variables Game
本来以为很复杂，要很多种分类讨论，于是比赛时一直没写出来。
赛后看见有人用 dfs 过了，于是我试着也写一写 dfs。
然后就过了？？？
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int N = 200003, M = N << 1;
int n, k;
int a, b, c;
string s[N];
string ans[N];
void dfs(int now, int a, int b, int c)
{
if (now > n)
{
puts("Yes");
for (int i = 1; i <= n; i+=1) cout << ans[i] << endl;
exit(0);
}
if (s[now] == "AB")
{
if (b > 0) ans[now] = "A", dfs(now + 1, a + 1, b - 1, c);
if (a > 0) ans[now] = "B", dfs(now + 1, a - 1, b + 1, c);
}
else if (s[now] == "AC")
{
if (c > 0) ans[now] = "A", dfs(now + 1, a + 1, b, c - 1);
if (a > 0) ans[now] = "C", dfs(now + 1, a - 1, b, c + 1);
}
else
{
if (c > 0) ans[now] = "B", dfs(now + 1, a, b + 1, c - 1);
if (b > 0) ans[now] = "C", dfs(now + 1, a, b - 1, c + 1);
}
}
int main()
{
n = gi(), a = gi(), b = gi(), c = gi();
for (int i = 1; i <= n; i+=1) cin >> s[i];
dfs(1, a, b, c);
puts("No");
return 0;
}