1024 プログラマの日の試験のまとめ#
お祭りの日に、なぜ試験を受けるのか
今日の問題はすべて洛谷で見つけることができるので、問題文は掲載しません。。
数学問題（math 1S 128M）#
提出するときに電子教室がフリーズし、USB にコピーしたmath.cppが文字化けしました。。。たった 30 点しか書いていないのに
まず、この問題は直接的な列挙の複雑さが $500^7$ であり、通過できません。
しかし、余りの加算と乗算の性質から、7 で割った余りの状況を統計するだけで十分です。複雑さは $7^7$ で、非常に速く実行できます。
（洛谷の提高+/省選-の難易度は本気ですか）
7 つの for ループを使ったコードを載せるのは恥ずかしいです。。。
#include <cstdio>
long long qz[27][8];
int n;
int main(void) {
// freopen("math.in", "r", stdin);
// freopen("math.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
char T[2];
scanf("%s", T);
int t;
scanf("%d", &t);
++qz[T[0] - 'A'][(t + 700000) % 7];
}
long long res = 0;
for (int i = 0; i <= 6; ++i) {
for (int j = 0; j <= 6; ++j) {
for (int k = 0; k <= 6; ++k) {
for (int l = 0; l <= 6; ++l) {
for (int m = 0; m <= 6; ++m) {
for (int p = 0; p <= 6; ++p) {
for (int q = 0; q <= 6; ++q) {
if (((i + j * 2 + k * 2 + l) * (m + p + j + k) * (q + 2 * p)) % 7 == 0) {
res += (qz['B' - 'A'][i] * qz['E' - 'A'][j] * qz['S' - 'A'][k] * qz['I' - 'A'][l] * qz['G' - 'A'][m] * qz['O' - 'A'][p] * qz['M' - 'A'][q]);
}
}
}
}
}
}
}
}
printf("%lld\n", res);
// fclose(stdin);
// fclose(stdout);
return 0;
}
回文パス（path 1S 128M）#
P3126 回文的なパス Palindromic Paths
DFS を使って解いたら、8 点を獲得しました。
正しい解法は DP で、左上と右下から同時にスタートし、現在の 2 つのセルが同じ場合、状態を遷移できます。
iはステップ数を表し、jは左上から出発している行を表し、kは右下から出発している行を表します。
列はiとjまたはkから計算できます。
f[i][j][k]=f[i - 1][j - 1][k] + f[i - 1][j][k + 1] + f[i - 1][j][k] + f[i - 1][j - 1][ k - 1]
ただし、$500^3$ のデータサイズは 512M 以上のメモリ制限がないと超えるので、ビット圧縮が必要です。
新しい状態はi - 1、j、k、j - 1、k + 1にのみ依存するため、iを圧縮し、jを逆順で列挙し、kを順番に列挙します。
jとkの開始点とステップ数の関係に注意してください。
#include <cstdio>
#include <iostream>
const int MOD = 1000000007;
long long f[505][505];
char mp[505][505];
int n;
int main (void) {
#ifndef ONLINE_JUDGE
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
std::cin >> mp[i][j];
}
}
if (mp[1][1] != mp[n][n]) {
printf("0\n");
return 0;
}
f[1][n] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = i; j >= 1; --j) {
for (int k = n - i + 1; k <= n; ++k) {
if (mp[j][i - j + 1] == mp[k][2 * n - i - k + 1]) {
f[j][k] = f[j - 1][k + 1] + f[j - 1][k] + f[j][k + 1] + f[j][k];
f[j][k] %= MOD;
}
else {
f[j][k] = 0;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans += f[i][i];
ans %= MOD;
}
printf("%d\n", ans);
return 0;
}
大都市（city 1S 128M）#
この問題を Google 翻訳で翻訳すると本当に魔性です
hbh 大佬によると、これはdfs順のテンプレート問題であり、学んでみると本当にそうでした。
#include <cstdio>
const int MAXN = 5e5 + 5;
struct ed {
int to, nex, w;
} e[MAXN];
int head[MAXN];
int newp, n, m, time;
int l[MAXN], r[MAXN];//pを根とする部分木のdfs順の左右の端点
namespace sz {
int c[MAXN * 4];
inline int lowbit (int x) {
return x & (-x);
}
void add (int k, int x) {
for (int i = k; i <= n; i += lowbit(i)) {
c[i] += x;
}
}
int query (int x) {
int ans = 0;
for (int i = x; i >= 1; i -= lowbit(i)) {
ans += c[i];
}
return ans;
}
}
void insert (int p1, int p2) {
++newp;
e[newp].to = p2;
e[newp].nex = head[p1];
head[p1] = newp;
}
void dfs (int p, int fa) {
l[p] = ++time;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (y == fa) continue;
dfs(y, p);
}
r[p] = time;
}
int main (void) {
#ifndef ONLINE_JUDGE
freopen("city.in", "r", stdin);
freopen("city.out", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
int p1, p2;
scanf("%d%d", &p1, &p2);
insert(p1, p2);
insert(p2, p1);
}
dfs(1, 0);
for (int i = 2; i <= n; ++i) {
sz::add(l[i], 1);
sz::add(r[i] + 1, -1);
}
scanf("%d", &m);
for (int i = 1; i <= n + m - 1; ++i) {
char T[2];
int x, y;
scanf("%s %d", T, &x);
if (T[0] == 'W') {
printf("%d\n", sz::query(l[x]));
}
else {
scanf("%d", &y);
sz::add(l[y], -1);
sz::add(r[y] + 1, 1);
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return 0;
}