1024程序员日考试总结

~~大过节的，考什么试啊~~

今天的题在洛谷上都能找到，所以就不放题面了。。

数学题（math 1S 128M）

P3123 贝茜说哞Bessie Goes Moo

提交的时候电子教室卡死，拿u盘拷上去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，从左上角和右下角同时开始走，如果当前两个格子相同，状态就能转移。

i表示走了几步，j表示左上角出发的走到了第几行，i表示从右下角出发的走到了第几行

第几列可以通过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)

P3459 MEG-Megalopolis

~~这道题用沙拉查词带的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;
}