AtCoder Regular Contest 115 (A~E)

发表于 | 分类于

AtCoder Regular Contest 115

AtCoder好难，根本不会

A. Two Choices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int x = 0, y = 0;
	for(int i = 0; i < n; i ++)
	{
		char s[25];
		scanf("%s", s);
		int tmp = 0;
		for(int j = 0; j < m; j ++) if(s[j] != '0') tmp ++;
		if(tmp % 2) x ++;
		else y ++;
	}
	printf("%lld\n", 1ll * x * y);
	
	return 0;
}

B. Plus Matrix

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 500 + 10;
int a[maxn][maxn];

int main()
{
	int n;
	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 ++)
	{
		for(int j = i + 1; j <= n; j ++)
		{
			int p = a[j][1] - a[i][1];
			for(int k = 1; k <= n; k ++)
			{
				if(a[j][k] - a[i][k] != p) return 0 * puts("No");
			}
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		for(int j = i + 1; j <= n; j ++)
		{
			int p = a[1][j] - a[1][i];
			for(int k = 1; k <= n; k ++)
			{
				if(a[k][j] - a[k][i] != p) return 0 * puts("No");
			}
		}
	}
	vector<int> x, y;
	x.push_back(0);
	y.push_back(a[1][1]);
	for(int i = 2; i <= n; i ++) 
		x.push_back(x.back() + a[i][1] - a[i - 1][1]);
	for(int i = 2; i <= n; i ++) 
		y.push_back(y.back() + a[1][i] - a[1][i - 1]);
	int p = 0;
	for(int i = 0; i < n; i ++) p = min(p, x[i]);
	if(p < 0)
	{
		for(int i = 0; i < n; i ++) x[i] -= p, y[i] += p;
		for(int i = 0; i < n; i ++) if(y[i] < 0) return 0 * puts("No");
	}
	p = 0;
	for(int i = 0; i < n; i ++) p = min(p, y[i]);
	if(p < 0)
	{
		for(int i = 0; i < n; i ++) x[i] += p, y[i] -= p;
		for(int i = 0; i < n; i ++) if(x[i] < 0) return 0 * puts("No");
	}
	puts("Yes");
	for(int i = 0; i < n; i ++) printf("%d%c", x[i], i == n - 1 ? '\n' : ' ');
	for(int i = 0; i < n; i ++) printf("%d%c", y[i], i == n - 1 ? '\n' : ' ');
	
	return 0;
}

C. ℕ Coloring

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;
int a[maxn], b[maxn];

int main()
{
	int n;
	for(int i = 2; i < maxn; i ++)
	{
		if(!a[i])a[i] = i;
		for(int j = i + i; j < maxn; j += i) if(a[j] == 0) a[j] = i;
	}
	b[1] = 1;
	for(int i = 2; i < maxn; i ++) b[i] = 2;
	for(int i = 2; i < maxn; i ++)
	{
		if(a[i] == i) continue;
		b[i] = b[i / a[i]] + 1;
	}
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) printf("%d%c", b[i], i == n ? '\n' : ' ');
	
	return 0;
}

D. Odd Degree

题意

给定一张图，求奇点个数为 $k(0 \le k \le n)$ 的生成子图的数量。

题解

首先考虑树的生成子图的奇点情况：对于一个固定的奇点点集，如果集合大小为偶数，生成子图唯一；如果集合大小为奇数，不存在生成子图。

证明：对于一棵有根树，首先判断叶子节点是否在集合中，如果在集合中，该叶子的父边一定在生成子图中；

去掉这样的叶子和父边，减去度数贡献后，有一个新的度数为奇数的点集，此时对于没有儿子在集合内的点，我们只能取它的父边（否则会选入不在集合内的结点）；

递归向上选取边集，因此树的生成子图的边集唯一确定。

因此对于一棵有 $n$ 个点的树，当k为偶数时，奇点个数为 $k$ 的生成子图的数量为 $C_n^k$ 。

然后考虑联通图：对于联通图，可以将它视为树+非树边；

那么如果我们首先确定一个非树边的边集，此时我们获得了一个奇点点集 $S’$。如果我们最终要获得一个大小为 $k$ 的奇点点集 $S$，那么我们对于树的生成子图所需的奇点集合唯一确定。因此，我们需要的 树的生成子图 唯一确定。

暴力枚举非树边是否被选，有 $2^{m-n+1}$ 种情况。因此当 $k$ 为偶数时，联通块的答案为 $2^{m-n+1}C_n^k$ 。

对于不同的联通块，dp合并计算答案即可。复杂度 $O(n^2)$ 。

代码

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 5000 + 10;
const int mod = 998244353;
ll C[maxn][maxn], dp[2][maxn], now[maxn], pow2[maxn];

void init() 
{
	C[0][0] = 1;
	for(int i = 1; i < maxn; i ++)
	{
		C[i][0] = 1;
		for(int j = 1; j <= i; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	}
	pow2[0] = 1;
	for(int i = 1; i < maxn; i ++) pow2[i] = pow2[i - 1] * 2 % mod;
}

int pre[maxn], es[maxn], sz[maxn];
int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	es[fy] ++;
	if(fx != fy) pre[fx] = fy, es[fy] += es[fx];
}

int main()
{
	init();
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) pre[i] = i;
	while(m --)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		merge(u, v);
	}
	vector<int> block; 
	for(int i = 1; i <= n; i ++) 
	{
		if(find(i) == i) block.push_back(i);
		sz[pre[i]] ++;
	}
	dp[0][0] = 1;
	int pos = 0, len = 0;
	for(auto x : block)
	{
		int p = sz[x], q = es[x];
		for(int i = 0; i <= p; i += 2) now[i] = pow2[q - p + 1] * C[p][i] % mod;
		for(int i = 0; i <= p + len; i ++) dp[pos ^ 1][i] = 0;
		for(int i = 0; i <= p; i ++)
			for(int j = 0; j <= len; j ++) (dp[pos ^ 1][i + j] += dp[pos][j] * now[i] % mod) %= mod;
		len += p;
		pos ^= 1;
	}
	for(int i = 0; i <= n; i ++) printf("%lld\n", dp[pos][i]);
	return 0;
}

E. LEQ and NEQ

题意

给定一个长度为 $n$ 的序列 $a_i$ ，求满足

  • $1 \le x_i \le a_i$

  • $x_i \neq x_{i+1}(1 \le i \le i - 1)$

的序列 $x_i$ 的数量。

题解

考虑容斥。令 $dp[i]$ 为前缀 $i$ 的答案。那么对于以 $i$ 结尾，满足 $x_{i-len+1}=x_{i-len+2}=…x_i$ 的序列的数量为 $dp[i-len+1]*min(x_{i-len+1},x_{i-len+2}…x_i)$ 。(相当于合并进一个 $dp[j]$ 的前缀，每次连接部分可能有相邻相等的答案，对这部分进行容斥）。

我们可以利用单调栈维护最小值，在枚举时，假设 $a_i$ 为最小值的左侧区间为 $[l,i-1]$ ，我们可以维护 $sum[i] = dp[i-1]-dp[i-2]+dp[i-3]…$ 进行容斥。

那么对于$a_i$ ：

  • 如果 $a_i \ge a_{top}$ ，那么以$[l,top-1]$ 为左端点， $i$ 为右端点的区间最小值为 $a_i$

  • 否则 $1-top$ 部分的贡献为 $pre[top]$ ，其中 $pre[top]$ 为 $1-top$ 中若干段区间×最小值的答案之和。

代码

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;
const int mod = 998244353;

int a[maxn], st[maxn];;
ll dp[maxn], sum[maxn], pre[maxn];

int main()
{
	int n, top = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	dp[0] = 1;
	for(int i = 1; i <= n; i ++)
	{
		dp[i] = dp[i - 1] * a[i] % mod;
		while(a[st[top]] > a[i])
		{
			(dp[i] += (i & 1 ? 1 : -1) * sum[st[top]] * a[i] % mod) %= mod;
			(sum[i] += sum[st[top --]]) %= mod;
		}
		(dp[i] += (i & 1 ? 1 : -1) * pre[st[top]]) %= mod;
		(sum[i] += (i & 1 ? 1 : -1) * dp[i - 1]) %= mod;
		pre[i] = (pre[st[top]] + sum[i] * a[i] % mod) % mod;
		st[++ top] = i;
	}
	printf("%lld\n", ((dp[n] % mod + mod) % mod));
	return 0;
}