http://codeforces.com/contest/1439

A2. Binary Table (Hard Version)

 

题意：给定一个01矩阵，每次操作选择一个 2∗22*2 的区域，翻转其中 3 个。要求在 nmnm 次操作内把矩阵变为全 0.

构造

观察发现对于一个 2∗22*2 的区域，总可以用不超过 4 次操作把所有点变为 0.

所以如果 n,mn,m 都为偶数，可以对一些不重叠的 2∗22*2 的区域分别操作变为全 0.

上限 nmnm 的本质是不超过一次操作把一点变为 0.

如果 n,mn,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
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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int T;
int n, m;
char s[110][110];
typedef pair<int, int>pii;
vector<pii>vc[2];
struct X
{
	pii a, b, c;
};
vector<X>ans;
void pr(pii a1, pii a2, pii a3) {
	ans.push_back(X{ a1,a2,a3 });
}
void pr1(X t) {
	printf("%d %d %d %d %d %d\n", t.a.first, t.a.second, t.b.first, t.b.second, t.c.first, t.c.second);
}
void inv(int x, int y) {
	if (s[x][y] == '0')s[x][y] = '1';
	else s[x][y] = '0';
}
int main() {
	scanf("%d", &T);
	while (T--) {
		ans.clear();
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)scanf("%s", s[i] + 1);
		if (n & 1) {
			for (int i = 1; i < m; i++) {
				if (s[n][i] == '1') {
					pr({ n, i }, { n - 1, i }, { n - 1, i + 1 });
					inv(n, i);
					inv(n - 1, i);
					inv(n - 1, i + 1);
				}
			}
			if (s[n][m] == '1') {
				pr({ n, m }, { n - 1, m - 1 }, { n - 1, m });
				inv(n, m);
				inv(n - 1, m - 1);
				inv(n - 1, m);
			}
			n--;
		}
		if (m & 1) {
			for (int i = 1; i < n; i++) {
				if (s[i][m] == '1') {
					pr({ i,m }, { i, m - 1 }, { i + 1, m - 1 });
					inv(i, m);
					inv(i, m - 1);
					inv(i + 1, m - 1);
				}
			}
			if (s[n][m] == '1') {
				pr({ n, m }, { n, m - 1 }, { n - 1, m - 1 });
				inv(n, m);
				inv(n, m - 1);
				inv(n - 1, m - 1);
			}
			m--;
		}
		for (int i = 1; i <= n; i += 2) {
			for (int j = 1; j <= m; j += 2) {
				vc[0].clear(); vc[1].clear();
				for (int p = i; p <= i + 1; p++)for (int q = j; q <= j + 1; q++)
					vc[s[p][q] - '0'].push_back({ p,q });
				if (vc[1].size() == 0)continue;
				else if (vc[1].size() == 1) {
					pr(vc[1][0], vc[0][0], vc[0][1]);
					pr(vc[1][0], vc[0][1], vc[0][2]);
					pr(vc[1][0], vc[0][0], vc[0][2]);
				}
				else if (vc[1].size() == 2) {
					pr(vc[0][0], vc[0][1], vc[1][0]);
					pr(vc[0][0], vc[0][1], vc[1][1]);
				}
				else if (vc[1].size() == 3) {
					pr(vc[1][0], vc[1][1], vc[1][2]);
				}
				else {
					pr(vc[1][0], vc[1][1], vc[1][2]);
					pr(vc[1][0], vc[1][1], vc[1][3]);
					pr(vc[1][0], vc[1][2], vc[1][3]);
					pr(vc[1][1], vc[1][2], vc[1][3]);
				}
			}
		}
		printf("%d\n", (int)ans.size());
		for (X t : ans)pr1(t);
	}
	return 0;
}

 

B. Graph Subset Problem

 

题意：给定一张简单无向图，要求找到：一个大小为 kk 的团，或者一张子图满足每个子图中的点在子图中都有至少 kk 个邻居。

类似拓扑排序

首先看要找一个满足第二个条件的子图，能够想到类似拓扑排序Kahn那样每次找到度小于 kk 的点，从图上去掉，如果最后剩下非空，则满足条件。

再看第一种，大小为 kk 的团中每个点的度都为 k−1k-1，如果存在这样的团，则边数为 k2k^2，所以 k≤mk\le \sqrt{m}。

其实大小为 kk 的团也可以看成 ”一张子图满足每个子图中的点在子图中都有至少 k−1k-1 个邻居“，所以也可以用和第二种相同的方法，处理直到剩下的度都大于等于 k−1k-1，这时如果最小的度大于 k−1k-1，则直接就满足第二种了，所以必定最小的度为 k−1k-1，这时直接暴力看它的 k−1k-1 个邻居，看它们这 kk 个点能否形成完全图，复杂度 k2k^2，而满足度大于等于 k−1k-1 的点的个数 ≤mk\le \frac{m}{k}，所以总复杂度为 O(mk)=O(mm)O(mk)=O(m\sqrt{m})。

但是由于要判断点是否在某点的邻居中，所以还多一个 log⁡\log，复杂度为 O(mmlog⁡n)O(m\sqrt{m}\log n)。

所以卡常卡的很紧！

奇怪的是如果用set存边，会超时，而用vector存再排序后二分查找就不会。

实现起来细节也挺多。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int T;
int n, m, k;
vector<int>G[N];
vector<int>vc;
int d[N], die[N];
struct X {
	int u;
	bool operator<(const X&b)const {
		return d[b.u] < d[u];
	}
};
priority_queue<X>q;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++)G[i].clear();
		for (int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		for (int i = 1; i <= n; i++)d[i] = (int)G[i].size(), die[i] = 0;
		while (!q.empty())q.pop();
		for (int i = 1; i <= n; i++)sort(G[i].begin(), G[i].end());
		for (int i = 1; i <= n; i++)if (d[i] < k) {
			q.push({ i });
		}
		bool ok2 = 0;
		while (!q.empty()) {
			int u = q.top().u; q.pop();
			if (die[u])continue;
			if (d[u] == k - 1) {
				vc.clear();
				for (int v : G[u])if (!die[v])vc.push_back(v);
				ok2 = 1;
				for (int i = 0; i < (int)vc.size(); i++) {
					int v = vc[i];
					for (int j = i + 1; j < (int)vc.size(); j++) {
						int p = vc[j];
						if (!binary_search(G[v].begin(), G[v].end(), p)) {
							ok2 = 0;
							break;
						}
					}
					if (!ok2)break;
				}
				if (ok2) {
					printf("2\n%d", u);
					for (int v : G[u])if (!die[v])printf(" %d", v);
					puts("");
					break;
				}
			}
			if (ok2)break;
			die[u] = 1;
			for (int v : G[u]) {
				d[v]--;
				if (d[v] < k && !die[v]) {
					q.push({ v });
				}
			}
		}
		if (ok2)continue;
		int cnt = 0;
		for (int i = 1; i <= n; i++)if (!die[i])cnt++;
		if (cnt) {
			printf("1 %d\n", cnt);
			for (int i = 1; i <= n; i++)if (!die[i])printf("%d ", i);
			puts("");
		}
		else puts("-1");
	}
	return 0;
}

 

C. Greedy Shopping

 

题意：给定一个数列满足 a1≥a2≥…≥ana_1 \geq a_2 \geq \ldots \geq a_n，两种操作：第一种操作对 i∈[1,x]i\in [1,x]，aia_i 变为 max(ai,y)max(a_{i}, y)。第二种操作给一个数 yy，从数列第一个开始向后遍历，遇到小于等于 yy 的就拿，并 y−=aiy-=a_i，问能拿几个。

势能线段树

势能线段树可以处理这种区间取min或max的操作。

本题由于数列有单调性，所以并不需要完整的势能线段树，但是复杂度与势能线段树类似。

第一种操作：

线段树维护区间最大值和最小值。

势能线段树与普通线段树的不同点在于普通区间修改线段树当查询或修改范围包含了当前树上的范围时，需要立即处理出结果并return，但是势能线段树允许继续下放，直到能够方便地处理。

在本题中，如果区间的min大于 y，则不需要修改，可以直接return。如果区间的max小于 y，则说明整个区间都要变成 y，这时直接修改整个区间，这也就是上面说的 “能够方便地处理” 的情况。否则继续下放。

第二种操作：

线段树再维护一个区间和。

当第一种操作修改时顺便修改。

查询时要判断如果 y 大于等于区间和，则直接买下整个区间。否则，如果 y 小于区间最小值min，则说明一个都卖不了，直接return0，否则继续下放。

由于要按顺序遍历买，所以要先查询左子树，再查询右子树。

势能线段树复杂度上限 O(nlog⁡2n)O(n\log^2 n)。

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
#include <bits/stdc++.h>
#define debug(x) cout << ##x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, q;
int a[N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int trmx[N << 2], trmn[N << 2], laz[N << 2];
ll trsum[N << 2];
void up(int rt) {
	trmx[rt] = max(trmx[rt << 1], trmx[rt << 1 | 1]);
	trmn[rt] = min(trmn[rt << 1], trmn[rt << 1 | 1]);
	trsum[rt] = trsum[rt << 1] + trsum[rt << 1 | 1];
}
void down(int l, int r, int rt) {
	int& x = laz[rt];
	if (x) {
		trmx[rt << 1] = trmx[rt << 1 | 1] = x;
		trmn[rt << 1] = trmn[rt << 1 | 1] = x;
		trsum[rt << 1] = 1ll * (mid - l + 1)*x;
		trsum[rt << 1 | 1] = 1ll * (r - mid)*x;
		laz[rt << 1] = laz[rt << 1 | 1] = x;
		x = 0;
	}
}
void build(int l, int r, int rt) {
	if (l == r) {
		trsum[rt] = trmx[rt] = trmn[rt] = a[l];
		return;
	}
	build(lson); build(rson);
	up(rt);
}
void upd(int ql, int qr, int x, int l, int r, int rt) {
	if (ql <= r && qr >= r) {
		if (trmn[rt] >= x)return;
		if (trmx[rt] < x) {
			laz[rt] = x;
			trmx[rt] = x;
			trmn[rt] = x;
			trsum[rt] = 1ll * (r - l + 1)*x;
			return;
		}
	}
	down(l, r, rt);
	if (ql <= mid)upd(ql, qr, x, lson);
	if (qr > mid)upd(ql, qr, x, rson);
	up(rt);
}
int qry(int ql, int qr, int& x, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		if (x >= trsum[rt]) {
			x -= trsum[rt];
			return r - l + 1;
		}
		if (x < trmn[rt])return 0;
	}
	down(l, r, rt);
	int res = 0;
	if (ql <= mid)res += qry(ql, qr, x, lson);
	if (qr > mid)res += qry(ql, qr, x, rson);
	return res;
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	build(1, n, 1);
	while (q--) {
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if (t == 1) {
			upd(1, x, y, 1, n, 1);
		}
		else {
			printf("%d\n", qry(x, n, y, 1, n, 1));
		}
	}
	return 0;
}