https://ac.nowcoder.com/acm/contest/5205/

A. 牛妹的游戏

题意：平面上有n个点，完全图中的每条边边被红方或蓝方占领，给出了蓝方占领的边。问是否有三条同一阵营的边连成三角形。

由拉塞姆结论得到如果平面上大于等于6个点，那么必定有至少一方形成三角形。

假设AB,AC,AD属于蓝方，则BC,BD,CD一定要属于红方，否则已经有三角形了。但是BC，BD，CD又形成了三角形。所以得证。

那么只要在5个点以内暴力判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int T;
int n, m;
int mp[100][100];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		memset(mp, 0, sizeof(mp));
		for (int i = 0; i < m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			if (n <= 5)mp[u][v] = mp[v][u] = 1;
		}
		if (n > 5) { puts("yes"); continue; }
		bool flg = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < i; j++) {
				for (int k = 1; k < j; k++) {
					if (mp[i][j] == mp[j][k] && mp[j][k] == mp[i][k])flg = 1;
				}
			}
		}
		puts(flg ? "yes" : "no");
	}
	return 0;
}

 

B. 病毒扩散

题意：初始时原点有一个病毒，每个病毒每秒向上或右扩散一个，问在第 t 秒点 (x,y) 有几个病毒。

有点类似路径数，一定和排列组合有关，打表或者推公式找规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int T;
int x, y, t;
ll CC[5010][5010];
ll C(int n, int k) {
	if (n < 0 || k < 0 || n < k)return 0;
	return CC[n][k];
}
int main() {
	scanf("%d", &T);
	for (int i = 0; i <= 5000; i++)CC[i][0] = CC[i][i] = 1ll;
	for (int i = 0; i <= 5000; i++) {
		for (int j = 0; j < i; j++)
			CC[i][j] = (CC[i - 1][j] + CC[i - 1][j - 1]) % mod;
	}
	while (T--) {
		scanf("%d%d%d", &x, &y, &t);
		printf("%lld\n", C(t, x)*C(t - x, y) % mod);
	}
	return 0;
}

 

C. 牛牛染颜色

 

题意：树上节点染黑白色，任意两个黑节点的LCA必须是黑的。问方案数。

树形dp

dp[u][0/1]dp[u][0/1] 表示u染白/黑色的子树的方案数。

父节点染黑色，则子节点随便什么颜色；

父节点染白色，则只能子树中所有节点都是白色或者有一棵子树随便染，其它都要全白。这里所有节点都是白色的情况被重复计算了，所以要减去 儿子个数-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
int to[N << 1], st[N], nx[N << 1], tot, d[N];
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot, d[u]++; }
ll dp[N][2], sn[N];
void dfs(int u, int _fa) {
	if (d[u] == 1 && u != 1) {
		dp[u][0] = dp[u][1] = 1ll;
		return;
	}
	dp[u][1] = 1ll;
	for (int i = st[u]; i; i = nx[i]) {
		int v = to[i];
		if (v == _fa)continue;
		sn[u]++;
		dfs(v, u);
		dp[u][1] = dp[u][1] * (dp[v][1] + dp[v][0]) % mod;
		dp[u][0] = (dp[u][0] + dp[v][0] + dp[v][1]) % mod;
	}
	dp[u][0] = (dp[u][0] + mod - sn[u] + 1) % mod;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	printf("%lld\n", (dp[1][0] + dp[1][1]) % mod);
	return 0;
}

 

D. 牛牛的呱数

 

题意：有n个数字，每个数字有无限多个，选出几个数字拼起来，问最短的是p的倍数的数。

对于一个数字只要维护它的长度，以及它模p的余数即可，把两个数字拼起来就是长度相加，余数为10的前面的数长度幂次乘以前一个数的余数，再加上后一个数的余数再取模。

维护10的长度幂次，以及模p的余数，在这两个相同的情况下长度最短，然后bfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, p;
int val[N], pw[N], le[N];
char s[N];
int d[300][300];
typedef pair<int, int>pii;
typedef pair<int, pii>ppii;
int bfs() {
	priority_queue<ppii, vector<ppii>, greater<ppii> >q;
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++) {
		if (d[pw[le[i]]][val[i]] > le[i]) {
			d[pw[le[i]]][val[i]] = le[i];
			q.push(ppii(d[pw[le[i]]][val[i]], pii(pw[le[i]], val[i])));
		}
	}
	while (!q.empty()) {
		ppii t = q.top(); q.pop();
		int di = t.first, x = t.second.first, y = t.second.second;
		if (y == 0)return d[x][y];
		if (di > d[x][y])continue;
		for (int i = 1; i <= n; i++) {
			int nx = x * pw[le[i]] % p, ny = (y*pw[le[i]] % p + val[i]) % p;
			int nd = d[x][y] + le[i];
			if (d[nx][ny] > nd) {
				d[nx][ny] = nd;
				q.push(ppii(d[nx][ny], pii(nx, ny)));
			}
		}
	}
	return -1;
}
int main() {
	scanf("%d%d", &n, &p);
	pw[0] = 1;
	for (int i = 1; i <= 1000000; i++)pw[i] = pw[i - 1] * 10 % p;
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		le[i] = strlen(s);
		for (int j = 0; s[j]; j++) {
			val[i] = (val[i] * 10 + (s[j] - '0')) % p;
		}
	}
	printf("%d\n", bfs());
	return 0;
}