https://acm.ecnu.edu.cn/contest/255/

B. 与矩阵

 

题意：给定矩阵 AijA_{ij} 表示 a[i]&a[j]a[i]\&a[j] 的值，要求构造出字典序最小的 aa 数列。

当 AijA_{ij} 某一位为1时，a[i],a[j]a[i],a[j] 这一位都要为1，否则就当作为0，那么遍历每个 jj ，确定 a[i]a[i] 即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[1010][1010];
int sum[1010];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		int ans = 0;
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < 30; k++) {
				if (a[i][j] & (1 << k))ans |= (1 << k);
			}
		}
		printf("%d%s", ans, i == n ? "\n" : " ");
	}
	return 0;
}

 

D. 钢琴演奏家

 

题意：n个按键，每个按键有值，每次操作会同时按下m个按键，得到的值为这m个按键值得最大值，问所有可能的操作的值之和。

考虑每个值的贡献，一次操作的结果为该值，表明所有值都小于等于该值，那么只要知道只选小于等于该值的按键中的m个按键的方案数，但还有去重的问题，只要把问题变为从所有小于等于该值的按键中选m个，且至少选一个等于该值的按键即可。

注意线性预处理出阶乘逆元，否则会超时！

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
unordered_map<int, int>mp;
int T;
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	} while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} return x * f;
}
int n, m;
ll fac[N], inv[N]; int a[N];
int Pow(ll a, int b) {
	int res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
ll C(int n, int k) {
	if (n <= 0 || k > n)return 0;
	return fac[n] * inv[k] % mod  * inv[n - k] % mod;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i %mod;
	}
	inv[N - 1] = Pow(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
int main() {
	scanf("%d", &T);
	init();
	while (T--) {
		mp.clear();
		n = read(); m = read();
		for (int i = 1; i <= n; i++) {
			a[i] = read();
			mp[a[i]]++;
		}
		sort(a + 1, a + n + 1);
		int cnt = 0; ll ans = 0;
		for (int i = 1; i <= n; i++) {
			cnt++;
			if (a[i] != a[i + 1]) {
				ans = (ans + (C(cnt, m) - C(cnt - mp[a[i]], m) + mod) % mod*a[i] % mod) % mod;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

 

A. 迷宫

 

题意：一个有向图，每条边有容量，经过一条边要一天时间，要从起点运k个人到终点，问最少要几天。

网络流24题里几乎是原题，甚至这题还简单一点。

分层图网络流，从小到大枚举最终结果天数，每天再建n个点，从每个点向新的点连INF边，表示不动，再从旧的u向新的v连边，容量为边容量，起点为第0天的起点S，终点为最新一天的终点T，在残量网络上跑，直到最大流大于等于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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
unordered_map<int, int>mp;
int k, n, m, S, T;
struct E
{
	int v, w;
};
vector<E>G[N];
struct mxfl
{
	int n = 0;
	int m = 0;
	int s, t;
	struct Edge
	{
		int from, to, cap, flow;
	};
	vector<Edge>edges;
	vector<int>G[N];
	void add_edge(int from, int to, int cap) {
		edges.push_back(Edge{ from,to,cap,0 });
		edges.push_back(Edge{ to,from,0,0 });
		m = (int)edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}
	bool vis[N];
	int d[N], cur[N];
	bool bfs() {
		memset(vis, 0, sizeof(vis));
		queue<int>Q;
		Q.push(s);
		d[s] = 0;
		vis[s] = 1;
		while (!Q.empty()) {
			int x = Q.front(); Q.pop();
			for (int i = 0; i < G[x].size(); i++) {
				Edge& e = edges[G[x][i]];
				if (!vis[e.to] && e.cap > e.flow) {
					vis[e.to] = 1;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int dfs(int x, int a) {
		if (x == t || a == 0)return a;
		int flow = 0, f;
		for (int& i = cur[x]; i < G[x].size(); i++) {
			Edge& e = edges[G[x][i]];
			if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
				e.flow += f;
				edges[G[x][i] ^ 1].flow -= f;
				flow += f;
				a -= f;
				if (a == 0)break;
			}
		}
		return flow;
	}
	int maxflow() {
		int flow = 0;
		while (bfs()) {
			memset(cur, 0, sizeof(cur));
			flow += dfs(s, INF);
		}
		return flow;
	}
}MF;
int tot, pre;
bool check(int t) {
	for (int i = 1; i <= tot; i++)
		MF.add_edge(i + (t - 1)*tot, i + t * tot, INF);
	for (int u = 1; u <= n; u++) {
		for (E e : G[u]) {
			int v = e.v, w = e.w;
			MF.add_edge(u + (t - 1)*tot, v + t * tot, w);
		}
	}
	MF.s = S, MF.t = tot * t + T;
	int nw = MF.maxflow();
	if (pre + nw >= k)return true;
	pre += nw;
	return false;
}
int main() {
	scanf("%d%d%d%d%d", &k, &n, &m, &S, &T);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(E{ v,w });
	}
	tot = n;
	for (int t = 1; t <= 10000; t++) {
		if (check(t)) {
			printf("%d\n", t);
			return 0;
		}
	}
	return 0;
}