Codeforces Round 630 (Div. 2)

http://codeforces.com/contest/1332

B. Composite Coloring

 

题意：给定长为n的合数数组，给每个数涂色，要求相同颜色的数不能互质，颜色最多11种，$n\leq 1000,a_i\leq 1000$。

关键在于数字很小。第12个为33，33与33相乘得到大于1000，所以数组中每个数的最小质因数一定是前11个质因数中的一个，那么根据最小质因数给数字涂色。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
int prime[N];
bool is_prime[N];
int sieve(int n) {
	int p = 0;
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			prime[p++] = i;
			for (int j = 2 * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	return p;
}
int c[N], n, a[N], vis[N];
int mx;
int main() {
	scanf("%d", &T);
	int tot=sieve(1000);
	while (T--) {
		scanf("%d", &n);
		fill(vis, vis + 12, 0);
		mx = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			for (int j = 0; j < 11; j++) {
				if (a[i] % prime[j] == 0) {
					if (!vis[j])vis[j] = ++mx;
					c[i] = vis[j];
					break;
				}
			}
		}
		printf("%d\n", mx);
		for (int i = 1; i <= n; i++)printf("%d%s", c[i], i == n ? "\n" : " ");
	}
	return 0;
}

 

C. K-Complete Word

 

题意：给定字符串，可以修改成任意字符，要求构成回文串，且每个位置 $s_i=s_{i+k}$，问最少修改几个位置。

把要求相同的位置放在一个并查集里，不同集合之间没有要求，所以只要对每个集合贪心修改即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
int par[N];
int rk[N];
void init(int n) {
	for (int i = 0; i <= n; i++) {
		par[i] = i;
		rk[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int n, k;
char s[N];
int cnt[N];
vector<char>vc[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		scanf("%s", s + 1);
		init(n);
		for (int i = 1; i <= n; i++) {
			vc[i].clear();
			unite(i, n - i + 1);
			if (i <= n - k)unite(i, k + i);
		}
		for (int i = 1; i <= n; i++) {
			vc[find(i)].push_back(s[i]);
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (par[i] == i) {
				fill(cnt, cnt + 30, 0);
				for (char c : vc[i]) {
					cnt[c - 'a']++;
				}
				sort(cnt, cnt + 26, greater<int>());
				ans += (int)vc[i].size() - cnt[0];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

D. Walk on Matrix

 

题意：求矩阵问从左上角到右下角的最大与路径，给定错误程序，要求构造矩阵满足正确答案与错误程序的结果相差 $k$。

错误程序错在按位与不能直接dp，否则就会为了追求更高位，而最终反而得到0。

那么就可以构造出一个矩阵，满足错误程序结果为0，再凑出正确答案为k。

一个固定大小3*3的矩阵即可，设置一条路径结果为正确值k，其他地方都用 $(1<<16)$ 填充，那么错误程序为了追求高位，一定会走那些格子，再在终点把第16位取为0即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int k;
int mx = (1<<16);
int main() {
	cin >> k;
	int a[3][3]{ mx+k,k,k,
				 mx,mx+k,mx,
				 mx,mx+k,k };
	cout << 3 << ' ' << 3 << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++)printf("%d%s", a[i][j], j == 2 ? "\n" : " ");
	}
	return 0;
}

 

E. Height All the Same

 

题意：给定一个n*m的网格，在每一格上初始有一些大小相等的方块，两种操作：在一个格子上再放2个方块，或者选两个相邻的格子各放1个方块。规定初始每个格子的方块数 $L \le a_{i,j} \le R$，问有几种初始情况，可以通过重复以上操作使得每格的方块数相等。

组合数学

不会。

每次操作都是放2个方块，所以最终方块数和初始方块数奇偶性相同。当n*m 为奇数时，不论初始方块数为奇还是偶，都可以通过改变最终的高度使得最终奇偶性和初始相同；

而当nm为偶数，最终结果一定是偶数，所以初始为奇数的情况都不行，初始为偶数的情况都可以。

总的情况数 $(R-L+1)^{nm}$，当nm为偶数时，要去掉初始奇数的情况，可以发现当 $R-L+1$ 为奇数时，总的情况数为奇数，此时初始偶数比初始奇数的情况多1，所以总情况数+1再除2就是初始偶数的情况数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353, inv2 = (mod + 1) / 2;
ll n, m, l, r;
ll Pow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int main() {
	scanf("%lld%lld%lld%lld", &n, &m, &l, &r);
	ll k = r - l + 1;
	if (n*m & 1)
		printf("%lld\n", Pow(k, n*m));
	else {
		if (k & 1)printf("%lld\n", (Pow(k, n*m) + 1)*inv2%mod);
		else printf("%lld\n", Pow(k, n*m)*inv2%mod);
	}
	return 0;
}

 

F. Independent Set

 

题意：给定一棵树，求每一个边诱导子图上的独立集个数之和。

树上dp

$dp[u][0]$ 表示不取节点u。$dp[u][1]$ 表示取节点u。$dp[u][2]$ 表示u的所有子节点的子树组成的森林的独立集个数。

对于节点u，考虑保持原图的边，或者删除某些边。

如果保持原边，$dp[u][0]=\Pi (dp[v][0]+dp[v][1])$，$dp[u][1]=\Pi(dp[v][0])$。

如果删除某些边，则被断开连接的子节点的子树可以随便取，但是由于该子节点必须要出现在图上，也就要求至少有一条边连着它，所以该子节点新增的独立集数为 $p[v]=dp[v][0]+dp[v][1]-dp[v][2]$。

再考虑求 $dp[u][2]$，这其实就是每个子节点新增的那部分独立集数 $\Pi (p[v])$，每个子节点都断开连接，也就是u的所有子节点的子树单独构成森林。

最后结果就是 $dp[1][0]+dp[1][1]-dp[1][2]-1$，因为上面求得的是所有情况的独立集个数，也就包含空图，空图时独立集只有空集，所以-1。

像下面这样，计算 dp[u] 时只考虑了子节点v不会被置空，而没考虑u，所以 $dp[u][0]$ 和 $dp[u][1]$ 都包含三个子节点全部断开的情况，也就是空图，而 $-dp[u][2]$ 只去掉一个，还有一个，所以要再减 1。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 3e5 + 10;
int n;
vector<int>G[N];
ll dp[N][3], p[N];
void dfs(int u, int _fa) {
	dp[u][0] = dp[u][1] = dp[u][2] = 1ll;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs(v, u);
		p[v] = (dp[v][0] + dp[v][1] - dp[v][2] + mod) % mod;
		dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1] + p[v]) % mod;
		dp[u][1] = dp[u][1] * (dp[v][0] + p[v]) % mod;
		dp[u][2] = dp[u][2] * p[v] % mod;
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	printf("%lld\n", (dp[1][0] + dp[1][1] - dp[1][2] - 1 + mod) % mod);
	return 0;
}