Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

水题笔记 CCPC前的刷水

Posted on Edited on In

最近感觉做不出什么有意义的题来, 就不单独发来恶心人了

计数器:

9

Kaka's Matrix Travels

K方格取数 别忘了拆点的套路

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define pii pair<int, int>
#define MAXN (5000)
#define MAXG (2500)
#define MAXK (50)
#define INF (0x7ffffff)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define dbh(i, j) (bh(i, j) + MAXG)
#define bh(i, j) (((i) - 1) * MAXK + (j))
using namespace std;
const int s = MAXN + 1, t = MAXN + 2;
struct edg {
	int from, to, next, flow, cap, cost;
	edg() {}
	edg(int f, int nt, int n, int fl, int ca, int co): from(f), to(nt), next(n), flow(fl), cap(ca), cost(co) {}
} b[MAXN * 100 + 5];
int pre[MAXN + 5], g[MAXN + 5], n, ans, kk, a[MAXN + 5], cntb;
void ade(int fr, int nt, int ca, int co) {
	b[++cntb] = edg(fr, nt, g[fr], 0, ca, co);
	g[fr] = cntb;
}
bool spfa() {
	int dis[MAXN + 5], xa[MAXN + 5];
	bool inq[MAXN + 5];
	memset(xa, 0, sizeof(xa));
	memset(inq, false, sizeof(inq));
	for (int i = 0; i < MAXN + 5; i++) dis[i] = -INF;
	queue<int> q;
	q.push(s);
	dis[s] = 0;
	xa[s] = INF;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		inq[now] = false;
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[b[i].to] < dis[now] + b[i].cost) {
				xa[b[i].to] = min(b[i].cap - b[i].flow, xa[now]);
				dis[b[i].to] = dis[now] + b[i].cost;
				pre[b[i].to] = i;
				if (!inq[b[i].to]) q.push(b[i].to), inq[b[i].to] = true;
			}
	}
	return xa[t];
}
void solve() {
	int x;
	while (x = spfa()) {
		for (int i = t; i != s; i = b[pre[i]].from)
			b[pre[i]].flow += x, b[rev(pre[i])].flow -= x, ans += b[pre[i]].cost * x;
	}
}
int main() {
	scanf("%d%d", &n, &kk);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[bh(i, j)]);
			ade(bh(i, j), dbh(i, j), 1, a[bh(i, j)]), ade(dbh(i, j), bh(i, j), 0, -a[bh(i, j)]);
			ade(bh(i, j), dbh(i, j), INF, 0), ade(dbh(i, j), bh(i, j), 0, 0);
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < n; j++)
			ade(dbh(i, j), bh(i, j + 1), INF, 0), ade(bh(i, j + 1), dbh(i, j), 0, 0);
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= n; j++)
			ade(dbh(i, j), bh(i + 1, j), INF, 0), ade(bh(i + 1, j), dbh(i, j), 0, 0);
	ade(s, bh(1, 1), kk, 0), ade(bh(1, 1), s, 0, 0);
	ade(dbh(n, n), t, INF, 0), ade(t, dbh(n, n), 0, 0);
	solve();
	printf("%d", ans);
	return 0;
}

[SDOI2009]晨跑

费用流跑跑跑

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (1000)
#define MAXG (200)
#define MAXM (200000)
#define INF (0x7ffffff)
#define nnum(i) ((i) + MAXG)
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
struct edg {
	int from, to, next, cap, flow, cost;
} b[MAXM * 2 + 5];
int n, m, g[MAXN + 5], cntb, s = MAXN + 1, t = MAXN + 2, ansf, ansc, pre[MAXN + 5];
void ade(int fr, int to, int ca, int co) {
	b[++cntb] = {fr, to, g[fr], ca, 0, co};
	g[fr] = cntb;
}
int spfa() {
	int dis[MAXN + 5], a[MAXN + 5];
	bool inq[MAXN +5];
	memset(dis, 0x7f, sizeof(dis));
	memset(a, 0, sizeof(a));
	memset(inq, false, sizeof(inq));
	queue<int> q;
	dis[s] = 0;
	a[s] = INF;
	q.push(s);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		inq[now] = false;
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[now] + b[i].cost < dis[b[i].to]) {
				dis[b[i].to] = dis[now] + b[i].cost;
				a[b[i].to] = min(a[now], b[i].cap - b[i].flow);
				pre[b[i].to] = i;
				if (!inq[b[i].to]) q.push(b[i].to), inq[b[i].to] = true;
			}
	}
	return a[t];
}
void solve() {
	int x;
	while (x = spfa()) {
		for (int i = t; i != s; i = b[pre[i]].from)
			ansc += b[pre[i]].cost, b[pre[i]].flow += x, b[rev(pre[i])].flow -= x;
		++ansf;
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, ai, bi, ci; i <= m; i++) {
		scanf("%d%d%d", &ai, &bi, &ci);
		ade(nnum(ai), bi, 1, ci), ade(bi, nnum(ai), 0, -ci);
	}
	for (int i = 2; i < n; i++) ade(i, nnum(i), 1, 0), ade(nnum(i), i, 0, 0);
	ade(1, nnum(1), INF, 0), ade(nnum(1), 1, 0, 0);
	ade(n, nnum(n), INF, 0), ade(nnum(n), n, 0, 0);
	ade(s, 1, INF, 0), ade(1, s, 0, 9);
	ade(nnum(n), t, INF, 0), ade(t, nnum(n), 0, 0);
	solve();
	printf("%d %d", ansf, ansc);
	return 0;
}

[ZJOI2010]network 网络扩容

费用流跑跑跑

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200000)
#define MAXM (500000)
#define INF (0x7ffffff)
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
struct edg {
	int from, to, next, cap, flow, cost;
} b[MAXM + 5];
int g[MAXN + 5], cntb, n, m, k, s, t, dis[MAXN + 5], a[MAXN + 5], pre[MAXN + 5], ansc, ansf,
	ui[MAXM + 5], vi[MAXM + 5], ci[MAXM + 5], wi[MAXM + 5];
bool inq[MAXN + 5];
void ade(int fr, int to, int ca, int co) {
	b[++cntb] = {fr, to, g[fr], ca, 0, co};
	g[fr] = cntb;
}
int spfa() {
	queue<int> q;
	memset(dis, 0x7f, sizeof(dis));
	memset(a, 0, sizeof(a));
	memset(inq, false, sizeof(inq));
	q.push(s);
	dis[s] = 0, a[s] = INF;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		inq[now] = false;
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[now] + b[i].cost < dis[b[i].to]) {
				dis[b[i].to] = dis[now] + b[i].cost;
				pre[b[i].to] = i;
				a[b[i].to] = min(a[now], b[i].cap - b[i].flow);
				if (!inq[b[i].to]) q.push(b[i].to), inq[b[i].to] = true;
			}
	}
	return a[t];
}
void solve() {
	int x;
	while (x = spfa()) {
		ansf += x;
		for (int i = t; i != s; i = b[pre[i]].from)
			b[pre[i]].flow += x, b[rev(pre[i])].flow -= x, ansc += b[pre[i]].cost * x;
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	s = 1, t = n + 1;
	ade(n, t, INF, 0), ade(t, n, 0, 0);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d%d", &ui[i], &vi[i], &ci[i], &wi[i]);
		ade(ui[i], vi[i], ci[i], 0), ade(vi[i], ui[i], 0, 0);
	}
	solve();
	b[1].cap = ansf + k;
	for (int i = 1; i <= m; i++)
		ade(ui[i], vi[i], INF, wi[i]), ade(vi[i], ui[i], 0, -wi[i]);
	solve();
	printf("%d %d", ansf - k, ansc);
	return 0;
}

[SCOI2007]蜥蜴

拆完点以后跑最大流就好了

一开始因为 把计算是否能够到汇点的函数的返回值当成距离了 调了好久...

太蠢了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (400000)
#define MAXX (20)
#define MAXG (400)
#define MAXM (500000)
#define INF (0x7ffffff)
#define nbh(i, j) (bh(i, j) + MAXG)
#define bh(i, j) (((i) - 1) * MAXX + (j))
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
struct edg {
	int from, to, next, cap, flow;
} b[MAXM + 5];
int s = MAXN + 1, t = MAXN + 2, n, m, dis[MAXN + 5], kk, hei[MAXG + 5][MAXG + 5], ans, cntb, g[MAXN + 5];
bool dist(int x, int y) {
	return (x <= kk || y <= kk || n - x < kk || m - y < kk);
}
void ade(int fr, int to, int ca) {
	b[++cntb] = {fr, to, g[fr], ca, 0};
	g[fr] = cntb;
}
int dinic(int now, int maxf) {
	if (now == t || !maxf) return maxf;
	int re = 0;
	for (int i = g[now]; i; i = b[i].next)
		if (b[i].cap > b[i].flow && dis[b[i].to] == dis[now] + 1) {
			int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
			re += zl;
			maxf -= zl;
			b[i].flow += zl, b[rev(i)].flow -= zl;
		}
	return re;
}
bool bfs() {
	queue<int> q;
	memset(dis, -1, sizeof(dis));
	dis[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[b[i].to] == -1)
				dis[b[i].to] = dis[now] + 1, q.push(b[i].to);
	}
	return (dis[t] != -1);
}
void solve() {
	while (bfs())
		ans -= dinic(s, INF);
}
int main() {
	scanf("%d%d%d", &n, &m, &kk);
	for (int i = 1; i <= n; i++) {
		char ss[MAXG + 5];
		scanf("%s", ss);
		for (int j = 1; j <= m; j++)
			hei[i][j] = ss[j - 1] - '0';
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (hei[i][j]) {
				ade(bh(i, j), nbh(i, j), hei[i][j]), ade(nbh(i, j), bh(i, j), 0);
				if (dist(i, j))
					ade(nbh(i, j), t, INF), ade(t, nbh(i, j), 0);
			}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int ii = 1; ii <= n; ii++)
				for (int jj = 1; jj <= m; jj++)
					if (abs(i - ii) + abs(j - jj) <= kk && (ii!= i || jj != j) && hei[i][j] && hei[ii][jj])
						ade(nbh(i, j), bh(ii, jj), INF), ade(bh(ii, jj), nbh(i, j), 0);
	for (int i = 1; i <= n; i++) {
		char ss[MAXG + 5];
		scanf("%s", ss);
		for (int j = 1; j <= m; j++)
			if (ss[j - 1] == 'L')
				ade(s, bh(i, j), 1), ade(bh(i, j), s, 0), ++ans;
	}
	solve();
	printf("%d", ans);
	return 0;
}

[Noi2012]随机数生成器

矩阵快速幂板子, 但是要用快速乘是真的毒瘤. 12年的NOI就那么恐怖了吗

一开始矩阵乘法还乘反了, 遥想三年前我还在马哥给学弟学妹们讲课的时候大声告诉他 他矩阵乘法乘反了, 没想到三年后马哥去清华写最短路板子了, 我在这犯三年前的错误 555

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
/*
x 1 * a 0
	  c 1
 */


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define int LL
using namespace std;
struct matrix {
	int n, m, a[2][2];
	matrix(): n(2), m(2) {a[0][0] = a[1][1] = 1, a[1][0] = a[0][1] = 0;}
} m1, mb, ma;
int g, mp, n;
int mul(int a, int b) {
	if (!b) return 0;
	if (b == 1) return a % mp;
	LL re = mul(a, b >> 1);
	re = (re + re) % mp;
	if (b & 1) re = (re + a) % mp;
	return re;
}
matrix multi(const matrix x, const matrix y) {
	matrix re;
	re.n = x.n, re.m = y.m;
	memset(re.a, 0, sizeof(re.a));
	for (int i = 0; i < x.n; i++)
		for (int k = 0; k < y.m; k++)
			for (int j = 0; j < x.m; j++)
				re.a[i][k] += mul((x.a[i][j] % mp), (y.a[j][k] % mp)) % mp, re.a[i][k] %= mp;
	return re;
}
matrix ksm(const matrix x, int b) {
	if (!b) return m1;
	matrix re = ksm(x, b >> 1);
	re = multi(re, re);
	if (b & 1) re = multi(re, x);
	return re;
}
main() {
	ma.n = 1, ma.m = 2;
	ma.a[0][1] = 1;
	scanf("%llu%llu%llu%llu%llu%llu", &mp, &mb.a[0][0], &mb.a[1][0], &ma.a[0][0], &n, &g);
	printf("%llu", multi(ma, ksm(mb, n)).a[0][0] % g);
	return 0;
}

[Sdoi2010]星际竞速

显然你要是直接模拟题意就GG了 我们发现这玩意可以拆点后转成个二分图

如果能被路径覆盖就被路径覆盖了, 如果不能就用什么能力爆发模式

不知道为啥少加了个反向边T了三发...

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (10000)
#define MAXM (50000)
#define MAXG (800)
#define INF (0x7ffffff)
#define bh(x) ((x) + MAXG)
#define rev(x) ((((x) - 1) ^ 1) + 1)
using namespace std;
struct edg {
	int from, to, next, cap, flow, cost;
} b[MAXM + 5];
int g[MAXN + 5], pre[MAXN + 5], cntb, dis[MAXN + 5], a[MAXN + 5], s = MAXN + 1, t = MAXN + 2, ss = MAXN + 3, ans, n, m;
bool inq[MAXN + 5];
void ade(int fr, int to, int ca, int co) {
	b[++cntb] = {fr, to, g[fr], ca, 0, co};
	g[fr] = cntb;
}
int spfa() {
	queue<int> q;
	memset(dis, 0x7f, sizeof(dis));
	memset(a, 0, sizeof(a));
	memset(inq, false, sizeof(inq));
	a[s] = INF, dis[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		inq[now] = false;
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[b[i].to] > dis[now] + b[i].cost) {
				dis[b[i].to] = dis[now] + b[i].cost;
				a[b[i].to] = min(a[now], b[i].cap - b[i].flow);
				pre[b[i].to] = i;
				if (!inq[b[i].to]) q.push(b[i].to), inq[b[i].to] = true;
			}
	}
	return a[t];
}
void solve() {
	int x;
	while (x = spfa()) {
		for (int i = t; i != s; i = b[pre[i]].from)
			ans += x * b[pre[i]].cost, b[pre[i]].flow += x, b[rev(pre[i])].flow -= x;
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, ai; i <= n; i++) {
		scanf("%d", &ai), ade(ss, i, 1, ai), ade(i, ss, 0, -ai);
		ade(i, t, 1, 0), ade(t, i, 0, 0);
		ade(s, bh(i), 1, 0), ade(bh(i), s, 0, 0);
	}
	for (int i = 1, ui, vi, ci; i <= m; i++) {
		scanf("%d%d%d", &ui, &vi, &ci);
		if (ui > vi) swap(ui, vi);
		ade(bh(ui), vi, 1, ci), ade(vi, bh(ui), 0, -ci);
	}
	ade(s, ss, INF, 0), ade(ss, s, 0, 0);
	solve();  
	printf("%d", ans);
	return 0;
}

[ZJOI2009]假期的宿舍

最大流跑跑跑

md, 先是忘了初始化一个数组WA了半天

然后bfs里把dis全初始化为0, 结果判断的时候写了个if (b[i].flow > b[i].cap && !dis[b[i].to])结果好家伙直接给我把源点的dis更新了

日

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (10000)
#define MAXM (50000)
#define MAXG (100)
#define INF (0x7ffffff)
#define bh(i) ((i) + MAXG)
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
struct edg {
	int from, to, cap, flow, next;
} b[MAXM * 2 + 5];
int g[MAXN + 5], cntb, n, ans, insch[MAXN + 5], dis[MAXN + 5], s = MAXN + 1, t = MAXN + 2;
void ade(int fr, int to, int ca) {
	b[++cntb] = {fr, to, ca, 0, g[fr]};
	g[fr] = cntb;
}
int dinic(int now, int maxf) {
	if (now == t || !maxf) return maxf;
	int re = 0;
	for (int i = g[now]; i; i = b[i].next)
		if (b[i].cap > b[i].flow && dis[b[i].to] == dis[now] + 1) {
			int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
			maxf -= zl;
			re += zl;
			b[i].flow += zl, b[rev(i)].flow -= zl;
		}
	return re;
}
bool bfs() {
	queue<int> q;
	memset(dis, -1, sizeof(dis));
	dis[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[b[i].to] == -1)
				dis[b[i].to] = dis[now] + 1, q.push(b[i].to);
	}
	return dis[t] != -1;
}
void solve() {
	while (bfs())
		ans -= dinic(s, INF);
}
int main() {
	int tt;
	scanf("%d", &tt);
	while (tt--) {
		cntb = ans = 0;
		memset(g, 0, sizeof(g));
		memset(insch, 0, sizeof(insch));
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &insch[i]);
			if (insch[i]) ade(bh(i), t, 1), ade(t, bh(i), 0);
			else  ade(s, i, 1), ade(i, s, 0), ++ans;
		}
		for (int i = 1, xi; i <= n; i++) {
			scanf("%d", &xi);
			if (!insch[i]) continue;
			if (!xi) ade(s, i, 1), ade(i, s, 0), ade(i, bh(i), 1), ade(bh(i), i, 0), ++ans;
		}
		for (int i = 1; i <= n; i++)
			for (int j = 1, xi; j <= n; j++) {
				scanf("%d", &xi);
				if (xi) ade(i, bh(j), 1), ade(bh(j), i, 0);
			}
		solve();
		puts(ans ? "T_T" : "^_^");
	}
	return 0;
}

方格取数

印象里好像做过, 但是没有系统的学习背后的原理, 导致现在屁都不会

这个东西, 首先我们把棋盘上相交的格子两两连边就发现这玩意其实让求得就是一个二分图带权的最大独立子集

那怎么处理这个权的问题呢, 我们就可以把一个点复制成a[i]个点, 然后按照原先的关系连边跑就可以了

后来我们又发现, 这个边数好像有点爆炸, 怎么办呢, 我们观察一下这张图发现, 我们可以把一个点复制出的a[i]个点再合并起来, 在左部只需要把s到这个点的cap改成a[i], 在右部就把到t的cap改成相应的权值, 然后两部之间的边cap设为INF即可(因为不是限制条件, 当然, 设成两边点权的 \(\max\) 也可以)

然后跑最大流就可以了

不过要注意一个问题, 因为这张二分图的cap不都是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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN 100000
#define MAXM 500000
#define INF 100000
#define bh(i, j) (((i) - 1) * 1000 + (j))
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
const int xy[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct edg {
	int from, to, next, flow, cap;
} b[MAXM * 2 + 5];
int g[MAXN + 5], cntb, n, dis[MAXN + 5], s = MAXN + 1, t = MAXN + 2, ans;
void ade(int fr, int to, int ca) {
	b[++cntb] = {fr, to, g[fr], 0, ca};
	g[fr] = cntb;
}
bool bfs() {
	queue<int> q;
	memset(dis, -1, sizeof(dis));
	q.push(s), dis[s] = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = g[now]; i; i = b[i].next)
			if (b[i].cap > b[i].flow && dis[b[i].to] == -1)
				dis[b[i].to] = dis[now] + 1, q.push(b[i].to);
	}
	return dis[t] != -1;
}
int dinic(int now, int maxf) {
	if (now == t || !maxf) return maxf;
	int re = 0;
	for (int i = g[now]; i; i = b[i].next)
		if (b[i].cap > b[i].flow && dis[b[i].to] == dis[now] + 1) {
			int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
			re += zl, maxf -= zl;
			b[i].flow += zl, b[rev(i)].flow -= zl;
		}
	return re;
}
void solve() {
	while (bfs()) ans -= dinic(s, INF * 1000);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1, aij; j <= n; j++) {
			scanf("%d", &aij);
			if ((i + j) & 1) ade(bh(i, j), t, aij), ade(t, bh(i, j), 0);
			else {
				ade(s, bh(i, j), aij), ade(bh(i, j), s, 0);
				// 注意这里连边一定要单向连边, 因为cap很大, 所以可能从左部流到右部再流到左部再流到右部...
				for (int k = 0; k < 4; k++) { 					
					int ni = i + xy[k][0], nj = j + xy[k][1];
					if (ni < 1 || nj < 1 || ni > n || nj > n) continue;
					ade(bh(i, j), bh(ni, nj), INF);
					ade(bh(ni, nj), bh(i, j), 0);
				}
			}
			ans += aij;
		}
	solve();
	printf("%d", ans);
	return 0;
}

鬼谷子的钱袋

为啥我省选碰不上这种题 不过yysy这玩意要是要求输出方案还是挺脑瘫的, 尤其是在那个两两不能相等的鬼要求下, 只能从大往小里分治, 而不能从小倍增

1
2
3
4
5
6
7
8
#include <cstdio>
int main() {
	int n, ans = 0;
	scanf("%d", &n);
	while (n > 1) n >>= 1, ++ans;
	printf("%d", ans + 1);
	return 0;
}

再贴一份输出方案的

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
using namespace std;
int n, re, a[100];
int main()
{
	scanf("%d", &n);
	while (n) a[++a[0]] = (n + 1) >> 1, n >>= 1;
	printf("%d\n", a[0]);
	for (int i = a[0]; i >= 1; i--) printf("%d ", a[i]);
	return 0;
}

By Cansult