补题报告：Codeforces Round #767 (Div. 2)

补题报告：Codeforces Round #767 Div. 2

A. Download More RAMB. GCD ArraysC. Meximum ArrayD. Peculiar Movie PreferencesE. Grid XorF1. Game on Sum (Easy Version)F2. Game on Sum (Hard Version)

A. Download More RAM

https://codeforces.com/contest/1629/problem/A

Problem

有两个序列 a a a 和 b b b ，开始时你有 k k k 资源，你可以花费 b i b_i bi​ 资源获得 a i + b i a_i + b_i ai​+bi​ 资源，最多可以到达多少资源？

Solution

贪心。
将序列 a a a 和 b b b 按 b b b 从小到大排序，然后依次购买，一旦遇到 b i > k b_i>k bi​>k（也就是买不起的时候）就 b r e a k break break，因为后面的你更买不起 ( b i < = b i + 1 ) (b_i<=b_{i+1}) (bi​<=bi+1​)

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
// #define int long long

const int N = 110;
PII a[N];

bool cmp(PII& a, PII& b){
	if(a.x!=b.x) return a.x> n >> k;
	for (int i=0; i> a[i].x;
	for (int i=0; i> a[i].y;
	sort(a,a+n,cmp);
	for (int i=0; i=a[i].x){
			k+=a[i].y;
		}
	}
	cout << k << 'n';
}

int main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

B. GCD Arrays

https://codeforces.com/contest/1629/problem/B

Problem

在序列 [ l , r ] [l,r] [l,r] 上进行至多 k k k 次操作，每次操作可以选择两个数，将这两个数从序列中删掉，然后再向序列中插入这两个数的乘积，序列的 G C D GCD GCD是否能大于 1 1 1（ g c d ( a 1 , a 2 , . . . , a r − l + 1 > 1 gcd(a_1,a_2, ... ,a_{r-l+1}>1 gcd(a1​,a2​,...,ar−l+1​>1）

Solution

若序列的 G C D > 1 GCD>1 GCD>1，说明这个序列的每一个数都有一个大于 1 1 1的公因子。题意中的操作，可以理解为，让 a a a获得 b b b的所有因数， b b b获得 a a a的所有因数，那么怎么通过最少操作让所有数都获得同一个因数呢？显然让所有数获得 2 2 2这个因数时，操作次数最少，因为已经有一半的数含这个因数。
通过以上分析，若长度为偶数，只要 k > = ⌊ r − l + 1 2 ⌋ k>= lfloor frac {r-l+1} 2 rfloor k>=⌊2r−l+1​⌋即可。当长度为奇数时，分两种情况：

l , r l,r l,r为偶数时，假设 l = 4 , r = 6 l=4,r=6 l=4,r=6，序列 [ 4 , 5 , 6 ] [4,5,6] [4,5,6]通过一次操作后变为 [ 20 , 6 ] [20,6] [20,6]，此时没操作的" 6 6 6"本身含有因数 2 2 2，因此不需要再进行操作，所以这种情况也是 k > = ⌊ r − l + 1 2 ⌋ k>= lfloor frac {r-l+1} 2 rfloor k>=⌊2r−l+1​⌋即可 l , r l,r l,r为偶数时，假设 l = 5 , r = 7 l=5,r=7 l=5,r=7，序列 [ 5 , 6 , 7 ] [5,6,7] [5,6,7]通过一次操作后变为 [ 30 , 7 ] [30,7] [30,7]，此时没操作的" 7 7 7"不含有因数 2 2 2，因此需要再进行一次操作，序列变为 [ 210 ] [210] [210]，所以这种情况是 k > = ⌊ r − l + 1 2 ⌋ + 1 k>= lfloor frac {r-l+1} 2 rfloor + 1 k>=⌊2r−l+1​⌋+1即可

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
// #define int long long

const int N = 110;

void sol() {
	int l,r,k;
	cin >> l >> r >> k;
	if(k==0){
		if(l==r && l!=1) puts("YES");
		else puts("NO");
	}
	else if((r-l+1)%2==0){
		if(k>=(r-l+1)/2) puts("YES");
		else puts("NO");
	}else{
		if(l%2==0) {
			if(k>=(r-l+1)/2) puts("YES");
			else puts("NO");
		}else{
			if(k>=(r-l+1)/2+1) puts("YES");
			else puts("NO");
		}
	}
}

int main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

C. Meximum Array

https://codeforces.com/contest/1629/problem/C

Problem

给你一个序列 a a a，和一个空序列 b b b，你可以将 a a a分割为若干连续子序列，每一段子序列得到一个 M E X MEX MEX值，然后放到序列 b b b的末尾，希望得到的序列 b b b的字典序尽可能大。
例如：a=[2 2 3 4 0 1 2 0]分割为两段 [2 2 3 4 0 1] 和 [2 0]，他们的 M E X MEX MEX值分别为 5 5 5和 1 1 1，所以得到的序列 b b b为[5 1]，此时序列 b b b的字典序最大。

Solution

贪心+模拟。

由于 a i a_i ai​比较小，我们可以存下来每个数出现的次数。然后从前向后看，为了得到最大的字典序，所以每一段都应得到尽可能大的MEX值。
假设当前位置为 i i i，若 M E X ( a [ i , . . . , j ] ) = 8 MEX(a[i,...,j])=8 MEX(a[i,...,j])=8， M E X ( a [ i , . . . , k ] ) = 7 ( k < j ) MEX(a[i,...,k])=7(k 基于这两点说明，应该比较容易写出如下代码。

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
// #define int long long

const int N = 200010;

void sol() {
	int n;
	cin >> n;
	vector a(n);
	for (int i=0; i> a[i];
	vector cnt(n+1);
	vector v;
	for (int i=0; i st(mex);
		int k = 0;
		while (i> T_T;
	while (T_T--) sol();

	return 0;
}

D. Peculiar Movie Preferences

https://codeforces.com/contest/1629/problem/D

Problem

在 n n n个长度不超过 3 3 3的字符串中，能否通过若干个字符串的拼接形成一个回文串？（可以是一个字符串的拼接）要求子串之间的相对顺序不变

Solution

思路很容易想到，显然我们不需要那么多的串来组成一个回文串，只需要一个或者两个串即可。首先说下 O ( N 2 ) O(N^2) O(N2)的做法，循环遍历两轮，看 s i s_i si​和 s j s_j sj​能否组成回文串。如果用 s e t set set或者 m a p map map集合来存的话，只需要 O ( N l o g N ) O(NlogN) O(NlogN)即可，因为每轮查询的复杂度为 O ( l o g N ) O(logN) O(logN)

Code

T神代码总能让我学到自己陌生的函数。

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
// #define int long long

const int N = 200010;

void sol() {
	int n;
	cin >> n;
	vector s(n);
	for (int i=0; i> s[i];
	set p;
	bool ok = 0;
	// 用s[i]和自己匹配
	for (int i=0; i=0; i--){
		string x = string(next(s[i].rbegin()),s[i].rend());
		if(p.find(x)!=p.end()){
			ok=1;
			break;
		}
		p.insert(s[i]);
	}
	if(ok) puts("YES");
	else puts("NO");
}

int main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

E. Grid Xor

https://codeforces.com/contest/1629/problem/E

Problem

给你一个矩阵a，希望你利用矩阵a求出矩阵b中各元素的异或。其中 a [ i ] [ j ] a[i][j] a[i][j]的含义为 b [ i − 1 ] [ j ] b[i-1][j ] b[i−1][j] ^ b [ i + 1 ] [ j ] b[i+1][j] b[i+1][j] ^ b [ i ] [ j − 1 ] b[i][j-1] b[i][j−1] ^ b [ i ] [ j + 1 ] b[i][j+1] b[i][j+1]

Solution

构造题。

类似于“黑白迭代”游戏的解法。先抛开题目，来想这么一个游戏，在一个 n ∗ n n*n n∗n的网格图中，开始时网格都是白色，每次点击方格 ( i , j ) (i,j) (i,j)时，它的上下左右四个方格都会变成相反的颜色（黑变白，白变黑），怎么把网格图变为全黑呢？有一个通解：枚举第一行的染色方案，从第二行开始，第 j j j个格子是否点击，取决于 ( i − 1 , j ) (i-1,j) (i−1,j)是否为黑色，如果是白色，那么第j个格子一定要点击（如果再不操作，那么 ( i − 1 , j ) (i-1,j) (i−1,j)将再也不可能变为黑色）。
这个题目和游戏有什么关系呢？其实做一个简单转化，将颜色想成 0 / 1 0/1 0/1，每次点击时，都是对上下左右四个格子的值与 1 1 1异或（ 1 1 1变 0 0 0， 0 0 0变 1 1 1），然后将一个全 0 0 0的网格图变为全 1 1 1。
然后只需要将所点击过的格子的 a [ i ] [ j ] a[i][j] a[i][j]异或到一起就可以了！
可是 n < = 1000 n<=1000 n<=1000，不允许我们去枚举第一行的状态。所以继续考虑，对于第一行任意状态，上述通解是否还能奏效呢？（下面的证法来自Everule和AnandOza）
显然第一行存在某种颜色状态，通过上述通解得到全 1 1 1。假设 ( 1 , x ) (1,x) (1,x)格子未被点击过，将其修改为点击过，那么进而会影响 ( 2 , x + 1 ) , ( 2 , x − 1 ) (2,x+1),(2,x-1) (2,x+1),(2,x−1)的点击状态，进而影响 ( 3 , x + 2 ) , ( 3 , x ) , ( 3 , x − 2 ) (3,x+2),(3,x),(3,x-2) (3,x+2),(3,x),(3,x−2)的点击状态…然后传递到最后一行。我们发现，通过修改上述格子的点击状态，依然可以保证网格图为全 1 1 1，为什么呢？因为被影响过颜色状态的格子改变了偶数次（注意染色状态和点击状态不同，点击状态会影响上下左右四个格子的颜色状态）

所以第一行任意状态，都可以通过上述通解来得到答案。

呼~终于说完了，虽然有CF大佬的讲解，但本蒟蒻还是看了很久才想明白（总是将点击状态和颜色状态混淆），果然还是太菜了 T_T

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
// #define int long long

const int N = 1010;
int g[N][N];
int a[N][N];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

void light(int x, int y){
	for (int i=0; i<4; i++){
		int nx=x+dx[i],ny=y+dy[i];
		g[nx][ny]^=1;
	}
}

void sol() {
	int n;
	cin >> n;
	int ans = 0;
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) g[i][j]=0;
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cin >> a[i][j];

	for (int i=2; i<=n; i++){
		for (int j=1; j<=n; j++){
			if(!g[i-1][j]){
				light(i,j);
				ans ^= a[i][j];
			}
		}
	}
	cout << ans << 'n';
}

int main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

F1. Game on Sum (Easy Version)

https://codeforces.com/contest/1629/problem/F1

Problem

又是Alice和Bob在玩游戏，游戏一共进行 n n n轮，每轮Alice从 0 ∼ k 0 sim k 0∼k中选择一个数 x x x，Bob选择将游戏分数加上 x x x或者减去 x x x，但是Bob至少要增加游戏分数m轮。Alice的目的是最大化游戏分数，Bob的目的是最小化游戏分数。
（ 1 < = m < = n < = 2000 ) （1<=m<=n<=2000) （1<=m<=n<=2000)

Solution

状态方程 f [ i ] [ j ] f[i][j] f[i][j]表示前i轮中，Bob选择 j j j次增加时的游戏分数。由于Bob要最小化游戏分数，所以 f [ i ] [ j ] = m i n ( f [ i − 1 ] [ j − 1 ] + x , f [ i − 1 ] [ j ] − x ) f[i][j]=min(f[i-1][j-1] + x, f[i-1][j] - x) f[i][j]=min(f[i−1][j−1]+x,f[i−1][j]−x)，而Alice要最大化游戏分数，所以要最大化 m i n ( f [ i − 1 ] [ j − 1 ] + x , f [ i − 1 ] [ j ] − x ) min(f[i-1][j-1] + x, f[i-1][j] - x) min(f[i−1][j−1]+x,f[i−1][j]−x)，显然取中间值时是最优选择。（否则Bob永远选择 f [ i − 1 ] [ j − 1 ] + x f[i-1][j-1] + x f[i−1][j−1]+x和 f [ i − 1 ] [ j ] − x f[i-1][j] - x f[i−1][j]−x中较小的一个）

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
#define int long long

const int N = 2010;
int f[N][N];

int ksm(int a, int b, int p){
	int res = 1;
	while (b){
		if(b&1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}

void sol() {
	int n,m,k;
	cin >> n >> m >> k;
	//初始化
	for (int i=1; i<=n; i++){
		f[i][0]=0;
		f[i][i]=k*i%mod;
	}
	
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if(i==j) continue;
			if(j==0) continue;
			f[i][j]=(f[i-1][j-1]+f[i-1][j])*ksm(2,mod-2,mod)%mod;
		}
	}
	cout << f[n][m] << 'n';
}

signed main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

F2. Game on Sum (Hard Version)

https://codeforces.com/contest/1629/problem/F2

Problem

同F1 ( 1 < = m < = n < = 1 0 6 ) (1<=m<=n<=10^6) (1<=m<=n<=106)

Solution

观察F1中的状态转移方程： f [ i ] [ j ] = ( f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − 1 ] ) / 2 f[i][j]=(f[i-1][j]+f[i-1][j-1])/2 f[i][j]=(f[i−1][j]+f[i−1][j−1])/2，需要求的是 f [ n ] [ m ] f[n][m] f[n][m]，如果不考虑除以 2 2 2，是不是很像路径方案数的状态转移方程？的确是这样，与 ( 1 , 1 ) (1,1) (1,1)到 ( n , m ) (n,m) (n,m)的方案数求法的一点区别不同就是初始值的不同， f [ i ] [ i ] = i ∗ k f[i][i]=i*k f[i][i]=i∗k（由F1可知），而从 ( i , j ) (i,j) (i,j)到 ( n , m ) (n,m) (n,m)的方案数为 ( n − 1 m − 1 ) {n-1 choose m-1} (m−1n−1​)。我们考虑从 ( i , i ) (i,i) (i,i)到 ( n , m ) (n,m) (n,m)的贡献值即可，贡献值为 ( n − i − 1 m − i ) ∗ f [ i ] [ i ] ∗ 1 2 n − i {n-i-1 choose m-i} * f[i][i]* frac 1 {2^{n-i}} (m−in−i−1​)∗f[i][i]∗2n−i1​ （因为中间状态转移时被除了 n − i n-i n−i个 2 2 2），将这些贡献值加起来即可。

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
#define eps 1e-6
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
typedef long long ll;
#define int long long

const int N = 1000010;
int fac[N],ifac[N],ipw[N];

int ksm(int a, int b, int p){
	int res = 1;
	while (b){
		if(b&1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}

void init(){
	fac[0]=1;
	ipw[0]=1;
	ifac[0]=1;
	for (int i=1; i<=1000000; i++) fac[i]=fac[i-1]*i%mod;
	ifac[1000000]=ksm(fac[1000000],mod-2,mod);
	for (int i=999999; i>=0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	for (int i=1; i<=1000000; i++) ipw[i]=ipw[i-1]*(mod+1)/2%mod;
}

int C(int n, int m){
	if(n<0||m<0||n> n >> m >> k;
	int ans = 0;
	if(n==m){
		cout << k * m % mod << 'n';
		return;
	}
	for (int i=1; i<=m; i++){
		ans = (ans + C(n-i-1,m-i)*i%mod*k%mod*ipw[n-i])%mod;
	}
	cout << ans << 'n';
}

signed main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	init();
	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}