Codeforces Round #630 (Div.2)

比赛链接 / 官方题解链接

A. Exercising Walk

Solution

左右方向和上下方向分别考虑，以 $a>b$ 为例，最优走法显然是 左-右-左-右-……，所以终止位置在初始位置左边 $a-b$ 处，其余方向同理。

注意特判一步都不能走的情况。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, a, b, c, d, x, y, x_1, y_1, x_2, y_2;

int main(){
	read(T);
	while(T--){
		read(a, b, c, d);
		read(x, y, x_1, y_1, x_2, y_2);
		if(x - (a - b) < x_1 || x - (a - b) > x_2)	puts("NO");
		else if(y - (c - d) < y_1 || y - (c - d) > y_2)	puts("NO");
		else if(a == b && a > 0 && x_1 == x_2)	puts("NO");
		else if(c == d && c > 0 && y_1 == y_2)	puts("NO");
		else puts("YES");
	}
	return 0;
}

---

B. Composite Coloring

Solution

把每个数染成其最小质因数的颜色，小于 $\sqrt{1000}$ 的质数正好 $11$ 个。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 1005;

int T, n, a, col[N], id;
int p[15] = {-1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int c[15];

int main(){
	read(T);
	while(T--){
		id = 0;
		memset(col, 0, sizeof col);
		memset(c, 0, sizeof c);
		read(n);
		for(int i = 1; i <= n; i++){
			read(a);
			for(int j = 1; j <= 11; j++){
				if(a % p[j] == 0){
					if(c[j])	col[i] = c[j];
					else	col[i] = c[j] = ++id;
					break;
				}
			}
		}
		printf("%d\n", id);
		for(int i = 1; i <= n; i++)
			printf("%d ", col[i]);
		puts("");
	}
	return 0;
}

---

C. K-Complete Word

Solution

周期性+对称性=一个周期内部对称。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int T, n, k, cnt[30];
char s[N];

int main(){
	read(T);
	while(T--){
		read(n, k);
		scanf("%s", s+1);
		int ans = 0;
		for(int i = 1; i <= (k + 1) / 2; i++){
			int tot = 0;
			memset(cnt, 0, sizeof cnt);
			for(int j = i; j <= n; j += k)
				cnt[s[j]-'a']++, tot++;
			if(i != k - i + 1){
				for(int j = k - i + 1; j <= n; j += k)
					cnt[s[j]-'a']++, tot++;
			}
			int mark = -1, mx = -1;
			for(int j = 0; j <= 'z'-'a'; j++){
				if(mx < cnt[j]){
					mark = j;
					mx = cnt[j];
				}
			}
			ans += tot - mx;
		}
		printf("%d\n", ans);
	}
	return 0;
}

---

D. Walk on Matrix

Solution

设 $k$ 有 $b$ 位，$kk=(1<<b)|k$， 我构造的是：$\begin{pmatrix} kk & k & 0\\ kk & k & 0\\ 1<<b & kk & k \\\end{pmatrix}$.

但事实上，$\begin{pmatrix} 2^{17}+k & 2^{17} & 0\\ k & 2^{17}+k & k\\ \end{pmatrix}$ 足以。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int main(){
	int k;
	read(k);
	if(!k){
		puts("1 1");
		puts("1");
		return 0;
	}
	int b = 0;
	while((k >> b) != 0)	b++;
	int kk = (1 << b) | k;
	puts("3 3");
	printf("%d %d %d\n", kk, k, 0);
	printf("%d %d %d\n", kk, k, 0);
	printf("%d %d %d\n", 1 << b, kk, k);
	return 0;
}

---

E. Height All the Same

Solution

手玩一些例子，可以发现一些结论：

• 高度不重要，奇偶性是关键，所以我们在推结论时可以想象成平面上凸起一些高度为 $1$ 的小块。
• 若 $n\cdot m$ 为奇数，无论初始情况是怎么样的，都可以达到目标。
• 若 $n\cdot m$ 为偶数，若平面上凸起小块是奇数个，无法达成目标；否则，一定可以达成目标。

所以，对于奇数情况，答案就是 $(R-L+1)^{nm}$；对于偶数情况，我们要保证初始时所有高度之和为偶数，即选出偶数个位置放奇数，剩下偶数个位置放偶数。设 $[L,R]$ 内有 $a$ 个奇数，$b$ 个偶数，则答案为 $\sum\limits_{i=0}^{\frac{nm}{2}}C_{nm}^{2i}a^{2i}b^{nm-2i}=\frac{(b+a)^{nm}+(b-a)^{nm}}{2}$.

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const LL MOD = 998244353;

LL n, m, L, R;

inline LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int main(){
	read(n, m, L, R);
	if((n * m) & 1)
		printf("%lld\n", fpow(R - L + 1, n * m));
	else{
		LL a = (R - L + 1) / 2 + ((R - L + 1) % 2 && L % 2);
		LL b = (R - L + 1) / 2 + ((R - L + 1) % 2 && L % 2 == 0);
		printf("%lld\n", (fpow(b - a, n * m) + fpow(b + a, n * m)) * (MOD + 1) / 2 % MOD);
	}
	return 0;
}