http://codeforces.com/contest/1266

这场就是纯思维场啊！！

C. Diverse Matrix

 

题意：构造一个nm矩阵，使得每行的gcd和每列的gcd都不相等，且最大值最小。

增量构造

nm的矩阵可以由22矩阵构造出，先确定每列gcd，再确定行的gcd即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int ans[510][510];
int gr[510], gc[510];
int main() {
	cin >> n >> m;
	if (n == 1 && m == 1) { puts("0"); return 0; }
	if (n == 1) {
		for (int i = 1; i <= m; i++)ans[1][i] = i + 1;
	}
	else if (m == 1) {
		for (int i = 1; i <= n; i++)ans[i][1] = i + 1;
	}
	else {
		ans[1][1] = 4, ans[1][2] = 12, ans[2][1] = 2, ans[2][2] = 9;
		gr[1] = 4, gr[2] = 1, gc[1] = 2, gc[2] = 3;
		int tot = 4;
		for (int i = 3; i <= m; i++) {
			tot++;
			gc[i] = tot;
			for (int j = 1; j <= 2; j++) {
				ans[j][i] = tot * gr[j];
			}
		}
		for (int i = 3; i <= n; i++) {
			tot++;
			gr[i] = tot;
			for (int j = 1; j <= m; j++) {
				ans[i][j] = tot * gc[j];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printf("%d%s", ans[i][j], j == m ? "\n" : " ");
	}
	return 0;
}

 

D. Decreasing Debts

 

题意：有m份债务关系，u欠v x元💴，账面总和为所有债务关系的x之和，要求减小账面总和。

看着像是图论，画图发现就是把强连通分量所有边都减去分量里的最短边之后把链提出来，然后维护链上区间最小值，再分治改边，最终得到菊花图。但是这样的复杂度始终是 n2n^2。

但是换个角度看这题。

和实际情况一样，就是要尽量简化债务关系，那么就是A欠B钱，那么A就要尽量替B还💴，且要保证每个人不能多付少付，多拿少拿。

但是本题和实际情况又不太一样，本题1欠4了5元钱，2欠3了5元钱，1可以还给3钱，而2可以还4钱，（虽然他们可能都不认识）。

发现这点之后就简单了，只要保证每个人的收支总和不变，就可以随便给钱。

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 = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, ans;
int u[N], v[N]; ll w[N], c[N];
vector<int>vc;
queue<int>q;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		c[u] += w, c[v] -= w;
	}
	for (int i = 1; i <= n; i++) {
		if (c[i] > 0)vc.push_back(i);
		else if (c[i] < 0)q.push(i);
	}
	for (int i : vc) {
		while (c[i] > 0) {
			ll tmp = min(c[i], -c[q.front()]);
			c[i] -= tmp; c[q.front()] += tmp;
			u[++ans] = i; v[ans] = q.front(); w[ans] = tmp;
			if (c[q.front()] == 0)q.pop();
		}
	}
	printf("%d\n", ans);
	for (int i = 1; i <= ans; i++)printf("%d %d %lld\n", u[i], v[i], w[i]);
	return 0;
}

 

E. Spaceship Solitaire

 

题意：星际挖矿，有n种矿，速度都一样，每秒挖1克，但是有m个任务，拥有 t[i] 克 s[i] 的矿就可以得到 1 克 u[i] 的矿。完成任务不会消耗矿。问每增加一个任务，最少每种矿达到需求量 a[i] 要多久。

由于任务不会消耗矿，所以每个任务只能完成一次，且由于题目规定任务一定可以完成，所以每个任务奖励一定能且只能得到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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, q, a[N], t[N];
ll ans;
typedef pair<int, int>pii;
map<pii, int>mp;
void add(int u) { if (u && ++t[u] <= a[u])ans--; }
void del(int u) { if (--t[u] < a[u])ans++; }
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]), ans += a[i];
	scanf("%d", &q);
	while (q--) {
		int s, t, u;
		scanf("%d%d%d", &s, &t, &u);
		pii p = pii(s, t);
		if (!mp[p])add(mp[p] = u);
		else del(mp[p]), add(mp[p] = u);
		printf("%lld\n", ans);
	}
	return 0;
}