Summary of the 1024 Programmer's Day Exam#
Why take an exam during the holiday season?
The questions for today's exam can all be found on Luogu, so I won't include them here...
Math Problem (math 1S 128M)#
When I submitted the code, the electronic classroom froze, and when I copied it to the USB drive, math.cpp became garbled...even though I only got 30 points
First of all, the complexity of directly enumerating all possibilities for this problem is $500^7$, which is not feasible.
However, due to the properties of addition and multiplication with remainders, we only need to count the cases of remainders when divided by 7, which has a complexity of $7^7$ and runs very quickly.
(I wonder if the difficulty of Luogu's "Advanced+/Provincial Selection-" problems is serious)
I'm too embarrassed to show the code with seven nested for loops...
#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;
}
Palindromic Paths (path 1S 128M)#
I used a depth-first search (DFS) and got 8 points.
The correct solution is dynamic programming (DP), starting from the top left corner and the bottom right corner at the same time. If the current two cells are the same, the state can be transferred.
i represents the number of steps, j represents the row reached starting from the top left corner, and k represents the row reached starting from the bottom right corner.
The column number can be calculated using i, j, or 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]
However, with a data scale of $500^3$, it will only not exceed the memory limit of 512M (tested) if the bits are compressed.
Since the new state only depends on i - 1, j, k, j - 1, and k + 1, we can compress i and enumerate j in reverse order and k in sequential order.
Pay attention to the relationship between the starting point of j and k and the number of steps.
#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;
}
Megalopolis (city 1S 128M)#
The translation from Google Translate using Saladict is really magical
hbh said this is a template problem for DFS order, and after studying it, it really is.
#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];//The left and right endpoints of the subtree rooted at p in the DFS order
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;
}