只有 ABCDEFG 的题解。
A
模拟。
代码
void mian() {
string s;
cin >> s;
int pos = int(s.size()) / 2;
cout << s[pos] << endl;
}
B
模拟，注意 long long。
代码
void mian() {
ll x; scanf("%lld", &x);
const int P = 998244353;
printf("%lld\n", (x % P + P) % P);
}
C
垃圾计算几何。
代码
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator-(const Point a) const { return Point(x - a.x, y - a.y); }
double operator*(const Point a) const { return x * a.y - y * a.x; }
void read() { scanf("%lf%lf", &x, &y); }
} A, B, C, D;
bool check(Point A, Point B, Point C, Point D) {
double k1 = (B - A) * (D - A), k2 = (C - B) * (D - B), k3 = (A - C) * (D - C);
if (k1 * k2 < 0 || k1 * k3 < 0) return 1;
else return 0;
}
void mian() {
A.read(), B.read(), C.read(), D.read();
if (check(A, B, C, D) && check(B, C, D, A) && check(C, D, A, B) && check(D, A, B, C)) puts("Yes");
else puts("No");
}
D
简单 dp，设 \(f_{i,j}\) 表示当前时间是 \(i\)、位置为 \(j\) 时的答案。
代码
const int N = 1e5;
int n, a[N + 10][5];
ll f[N + 10][5];
void mian() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int t, p, x; scanf("%d%d%d", &t, &p, &x);
a[t][p] = x;
}
memset(f, 0xcf, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= N; i++)
for (int j = 0; j <= 4; j++) {
f[i][j] = max(f[i][j], f[i - 1][j] + a[i][j]);
if (j != 0) f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i][j]);
if (j != 4) f[i][j] = max(f[i][j], f[i - 1][j + 1] + a[i][j]);
}
ll ans = 0;
for (int i = 0; i <= 4; i++)
ans = max(ans, f[N][i]);
printf("%lld\n", ans);
}
E
这个题的关键在于如何理解最后一句话：
Find the expected value of your score when you play the game to maximize this expected value.
它其实就是说如果当前掷骰子比不掷要亏，那么我们就不掷，否则就掷。
于是设 \(f_i\) 为进行 \(i\) 轮游戏的答案，那么：
\[f_i=\sum_{j=1}^6\begin{cases}\frac 16f_{i-1},&j\lt f_{i-1}\\\frac 16j,&j\gt f_{i-1}\end{cases} \]代码
const int N = 100;
int n;
long double f[N + 10];
void mian() {
scanf("%d", &n);
f[1] = 3.5;
for (int i = 2; i <= n; i++) {
long double res = 0.0;
for (int j = 1; j <= 6; j++)
if (j < f[i - 1]) res += 1.0 / 6.0 * f[i - 1];
else res += 1.0 / 6.0 * j;
f[i] = res;
}
printf("%.10Lf\n", f[n]);
}
F
出这种题我也只能说呵呵了。
代码
const int N = 2e5;
struct Edge {
int to, nxt;
} e[N * 2 + 10];
int head[N + 10], tote;
void addEdge(int u, int v) {
e[++tote] = {v, head[u]};
head[u] = tote;
}
int n, m;
int found, path[N + 10], totp, visPath[N + 10], ring[N + 10], totr, onRing[N + 10];
int col[N + 10], totc;
void findRing(int u, int fa) {
if (found) return;
path[++totp] = u;
visPath[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (found) return;
if (v == fa) continue;
if (visPath[v]) {
found = 1;
ring[++totr] = v;
onRing[v] = 1;
while (path[totp] != v) {
ring[++totr] = path[totp];
onRing[path[totp]] = 1;
totp--;
}
return;
}
if (!found) findRing(v, u);
}
visPath[u] = 0;
totp--;
}
void dfs(int u, int fa) {
col[u] = totc;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v == fa || onRing[v]) continue;
dfs(v, u);
}
}
void mian() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int u, v; scanf("%d%d", &u, &v);
addEdge(u, v), addEdge(v, u);
}
findRing(1, 0);
for (int i = 1; i <= totr; i++) {
totc++;
dfs(ring[i], 0);
}
scanf("%d", &m);
while (m--) {
int u, v; scanf("%d%d", &u, &v);
if (col[u] == col[v]) puts("Yes");
else puts("No");
}
}
G
先转化一下问题：我们把所有的 RG 替换成一个 K，那么原问题就转化成了用 \(r-k\) 个 R、\(g-k\) 个 G、\(k\) 个 K、\(b\) 个 B 能组成多少个没有 RG 的串。
（令 \(r\gets r-k\)，\(g\gets g-k\)）
考虑容斥，只需对于每一个 \(i\)，求有多少个串至少有 \(i\) 个 RG（注意 K 不算 RG），也就是有 \(r-i\) 个 R、\(g-i\) 个 G、\(k\) 个 K、\(b\) 个 B、\(i\) 个 RG 组成的串的个数。这个问题的答案就是：
代码
const int N = 3e6, P = 998244353;
int fac[N + 10], ifac[N + 10];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1LL * res * a % P;
a = 1LL * a * a % P;
b >>= 1;
}
return res;
}
void init() {
fac[0] = 1;
for (int i = 1; i <= N; i++) fac[i] = 1LL * fac[i - 1] * i % P;
ifac[N] = qpow(fac[N], P - 2);
for (int i = N - 1; i >= 0; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
}
void mian() {
int r, g, b, k;
scanf("%d%d%d%d", &r, &g, &b, &k);
r -= k, g -= k;
int ans = 0;
for (int i = 0; i <= min(r, g); i++)
(ans += 1LL * (i & 1 ? -1 : 1) * fac[r - i + g - i + b + k + i] * ifac[r - i] % P * ifac[g - i] % P * ifac[b] % P * ifac[k] % P * ifac[i] % P) %= P;
printf("%d\n", (ans % P + P) % P);
}