http://codeforces.com/contest/1207

B. Square Filling

 

题意：一个nm的01矩阵，要求在一个初始为0的nm矩阵中操作，每次选一个2*2的正方形置为1，问能否得到和给定矩阵一样的矩阵。

遍历，贪心地判断如果当前位置的正方形内都是1，则置为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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int a[100][100], b[100][100];
typedef pair<int, int> pii;
vector<pii>vc;
int cal() {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1]) {
				b[i][j] = b[i + 1][j] = b[i][j + 1] = b[i + 1][j + 1] = 1;
				vc.push_back(pii(i, j));
				ans++;
			}
		}
	}
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)
		if (a[i][j] != b[i][j])return -1;
	return ans;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	int ans = cal();
	if (ans == -1)puts("-1");
	else {
		printf("%d\n", ans);
		for (pii p : vc) {
			printf("%d %d\n", p.first, p.second);
		}
	}
	return 0;
}

 

C. Gas Pipeline

 

题意：一个线段按照整点分成了n格，每格是0或1，若是1，则这一格高度必须是2，问最小花费。

dp

dp[i][0/1]dp[i][0/1] 表示这格高度是0或1时最小花费，简单dp，要注意端点处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
int T, n; ll a, b;
ll dp[N][2];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%lld%lld", &n, &a, &b);
		for (int i = 1; i <= n; i++)dp[i][0] = dp[i][1] = inf;
		for (int i = 1; i <= n; i++) {
			char c;
			scanf(" %c", &c);
			if (c == '0')
				dp[i][0] = min(dp[i - 1][0] + b, dp[i - 1][1] + a + b);
			if (i != 1)dp[i][1] = min(dp[i - 1][1] + 2 * b, dp[i - 1][0] + a + 3 * b);
		}
		printf("%lld\n", dp[n][0] + n * a + b);
	}
	return 0;
}

 

D. Number Of Permutations

 

题意：给定一个pair数组，问有几种排列满足第一维不是非递减，且第二维也不是非递减。

容斥原理

总的排列数-第一维非递减-第二维非递减+第一第二维都非递减。

一个非递减数列，相同的数之间交换，仍然非递减，所以就是相同的数的个数的排列。至于第一第二维都非递减则要固定第一维相同，再看第二维。如果最大的数比下一段最小的数大，那一定不满足。

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 = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n;
typedef pair<int, int>pii;
pii a[N];
ll fac[N], ans = 1, cnt[2][N];
map<int, int>mp;
int main() {
	scanf("%d", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i%mod;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i].first, &a[i].second);
		cnt[0][a[i].first]++, cnt[1][a[i].second]++;
	}
	ll tmp1 = 1, tmp2 = 1, tmp3 = 1;
	for (int i = 1; i <= n; i++) {
		tmp1 = tmp1 * fac[cnt[0][i]] % mod;
		tmp2 = tmp2 * fac[cnt[1][i]] % mod;
	}
	sort(a + 1, a + n + 1);
	int mx = 0;
	for (int i = 1; i <= n; i++) {
		mp[a[i].second]++;
		if (a[i].second < mx) { tmp3 = 0; break; }
		if (a[i].first != a[i + 1].first) {
			mx = 0;
			for (pii p : mp) {
				tmp3 = tmp3 * fac[p.second]%mod;
				mx = max(mx, p.first);
			}
			mp.clear();
		}
	}
	ans = (fac[n] - tmp1 - tmp2 + tmp3 + 2 * mod) % mod;
	printf("%lld\n", ans);
	return 0;
}

 

E. XOR Guessing

 

题意：交互题，要猜一个数，0≤x<2140\leq x<2^{14}，最多两次询问，每次询问给出100个数字，评测机会随机挑1个，返回它和这个数的异或值。

被样例带歪了。。

其实很简单，只要先用前半部分全是0的数，得到答案的前半部分，再用后半部分全是0的数，得到答案的后边部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f;
int a, b;
int main() {
	cout << '?';
	for (int i = 1; i <= 100; i++)cout << ' ' << i;
	cout << endl;
	cin >> a;
	cout << '?';
	for (int i = 1; i <= 100; i++)cout << ' ' << (i << 7);
	cout << endl;
	cin >> b;
	int ans = 0;
	for (int i = 0; i < 7; i++)if (b&(1 << i))ans |= (1 << i);
	for (int i = 7; i < 14; i++)if (a&(1 << i))ans |= (1 << i);
	cout << "! " << ans << endl;
	return 0;
}

 

F. Remainder Problem

 

题意：一个长度为5e5的数组，两种操作：ax+=ya_x+=y；询问下标mod x=y的所有位置的值之和。

分块

如果询问的x大于105\sqrt{10^5}，则暴力统计，单次复杂度不超过 105\sqrt{10^5}。

预处理 sum[i][j]sum[i][j] 表示所有下标mod i=j的位置的值之和，每次操作1时更新所有i。单次更新复杂度为 105\sqrt{10^5}，询问时直接拿出来。

总的复杂度 O(q105)\mathcal{O}(q\sqrt{10^5})

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
int q, op, x, y;
ll sum[1010][1010];
int a[N];
int main() {
	scanf("%d", &q);
	int b = (int)sqrt(500000);
	while (q--) {
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			a[x] += y;
			for (int i = 1; i <= b; i++)
				sum[i][x%i] += y;
		}
		else {
			ll ans = 0;
			if (x <= b)ans = sum[x][y];
			else
				for (int i = y; i <= 500000; i += x)
					ans += a[i];
			printf("%lld\n", ans);
		}
	}
	return 0;
}