「Solution」2022-04-09-CQ2008 & ZJ2009踩坑祭

Posted on Edited on

属于是把能踩的坑都跳了一遍。。。

位统计

$\mathcal{Link}$

link

$\mathcal{Sol}$

把所有的操作累到一起。\
查询的是一段区间。

$\mathcal{Code}$

bit.cpp 
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int MAXK = 25;
const int Mod = 65536;

int n, m, d;

struct SegmentTree {
	struct Node {
		int l, r;
		int dat;
	} s[MAXN << 2];
	void build(int p, int l, int r) {
		s[p].l = l, s[p].r = r;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	}
	void update(int p, int pos) {
		if (s[p].l == s[p].r) {
			s[p].dat += 1;
			return;
		}
		int mid = (s[p].l + s[p].r) >> 1;
		if (pos <= mid) update(p << 1, pos);
		else update(p << 1 | 1, pos);
		s[p].dat = s[p << 1].dat + s[p << 1 | 1].dat;
	}
	int query(int p, int l, int r) {
		if (s[p].l >= l && s[p].r <= r) return s[p].dat;
		int mid = (s[p].l + s[p].r) >> 1, res = 0;
		if (l <= mid) res += query(p << 1, l, r);
		if (r > mid) res += query(p << 1 | 1, l, r);
		return res;
	}
} seg[MAXK];

int main() {

// 	freopen("bit.in", "r", stdin);
// 	freopen("bit.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 0; i <= 15; i++) seg[i].build(1, 0, Mod);
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		int num = 0;
		for (int w = 0; w <= 15; w++) {
			if ((x >> w) & 1) num |= (1 << w);
			seg[w].update(1, num);
		}
	}
	for (int i = 1, add, pos; i <= m; i++) {
		char opt[2]; scanf("%s", opt);
		if (opt[0] == 'C') {
			scanf("%d", &add);
			d = (d + add) % Mod;
		} else {
			scanf("%d", &pos);
			int l, r, ans = 0;
			l = (1 << pos) + (1 << pos + 1) - (d & ((1 << pos + 1) - 1));
			r = min((1 << pos + 2) - (d & ((1 << pos + 1) - 1)), Mod);
			ans += seg[pos].query(1, l, r);
			l = (1 << pos) - (d & ((1 << pos + 1) - 1));
			r = min((1 << pos + 1) - 1 - (d & ((1 << pos + 1) - 1)), Mod);
			ans += seg[pos].query(1, l, r);
			printf("%d\n", ans);
		}
	}

	return 0;
}

矩阵的个数

$\mathcal{Link}$

link

$\mathcal{Sol}$

看到其实前两行定了，第三行就会固定下来。\
一个 $n^5$ 的 dp 可以搞定

$\mathcal{Code}$

matrix.cpp 
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
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
#define int long long
using namespace std;
const int MAXN = 2e2 + 5;
const LL Mod = 1e17;

int n, a[MAXN], c1, c2, c3;
LL dp[MAXN][MAXN][MAXN];

signed main() {

	scanf("%lld %lld %lld %lld", &n, &c1, &c2, &c3);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

	dp[0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= c1; j++) {
			for (int k = 0; k <= c2; k++) {
				for (int x = 0; x <= a[i] && x + j <= c1; x++) {
					for (int y = 0; y + k <= c2 && y + x <= a[i]; y++) {
						dp[i][j + x][k + y] = (dp[i][j + x][k + y] + dp[i - 1][j][k]) % Mod;
					}
				}
			}
		}
	}

	printf("%lld\n", dp[n][c1][c2]);

	return 0;
}

传感器网络

$\mathcal{Link}$

link

$\mathcal{Sol}$

醉了，这个东西居然是个暴力

什么神奇题目。以为是个很厉害的构造，结果是网络流跑答案然后暴力连边判断。
强烈吐槽诈骗题目。

$\mathcal{Code}$

net 
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 55 * 55;
const int INF = 0x3f3f3f3f;

int n, l, r, mid, fa[MAXN];
char opt[MAXN][MAXN];
bool con[MAXN][MAXN];

int st, ed, head[MAXN], ver[MAXN], edge[MAXN], nxt[MAXN], tot, d[MAXN], cur[MAXN];
queue<int> q;

void AddEdge(int u, int v, int c) {
 	// printf("%d %d %d\n", u, v, c);
	ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
	ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs(int st) {
	memset(d, 0, sizeof(d));
	while (!q.empty()) q.pop();
	q.push(st), d[st] = 1, cur[st] = head[st];
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = nxt[i]) {
			int v = ver[i];
			if (!edge[i] || d[v] != 0) continue;
			q.push(v); cur[v] = head[v];
			d[v] = d[u] + 1;
			if (v == ed) return true;
		}
	}

	return false;

}

int dinic(int u, int flow) {
	if (u == ed) return flow;
	int res = flow, k, i;
	for (i = cur[u]; i && res; i = nxt[i]) {
		int v = ver[i];
		if (!edge[i] || d[v] != d[u] + 1) continue;
		k = dinic(v, min(res, edge[i]));
		if (k == 0) d[v] = 0;
		edge[i] -= k, edge[i ^ 1] += k;
		res -= k;
		cur[u] = i;
	}
	return flow - res;
}

int ind(int op, int x) { return x + op * n; }

bool check(int mid) {

	memset(head, 0, sizeof(head));
	tot = 1;
	for (int i = 1; i <= n; i++) {
		AddEdge(st, ind(0, i), 1);
		if (fa[i]) {
			if (fa[i] > n) AddEdge(ind(0, i), ed, 1);
			else AddEdge(ind(0, i), ind(1, fa[i]), 1);
		} else if (con[0][i]) {
			AddEdge(i, ed, 1);
		} else {
			for (int j = 1; j <= n; j++) if (con[i][j]) {
				AddEdge(ind(0, i), ind(1, j), 1);
			}
		}
		AddEdge(ind(1, i), ed, mid);
	}

	int res = 0, tmp = 0;
	while (bfs(st)) {
		while ((tmp = dinic(st, INF))) res += tmp;
	}
	// printf("%d %d\n", mid, res);

	return res == n;

}

int main() {

	// freopen("sensor.in", "r", stdin);
	// freopen("sensor.out", "w", stdout);

	scanf("%d", &n);
	st = (n << 1) + 1, ed = (n << 1) + 3;

	for (int i = 0; i <= n; i++) {
		scanf("%s", opt[i] + 1);
		for (int j = 1; j <= n; j++) {
			con[i][j] = (opt[i][j] == 'Y');
		}
	}
	for (int i = 1; i <= n; i++) con[n + 1][i] = con[0][i];

	l = 0, r = n;
	while (l < r) {
		mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	for (int i = 1; i <= n; i++) {

		bool flag = false;
		for (int j = 1; j <= n; j++) if (con[i][j]) {
			fa[i] = j;
			if (check(l)) {
				flag = true;
				break;
			}
		}
		if (!flag) printf("%d ", n), fa[i] = n + 1;
		else printf("%d ", fa[i] - 1);
		
	}

	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」