CodeTON Round 6 (Div 1 + Div 2, Rated, Prizes!)(A - E)

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)(A - E)

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

A. MEXanized Array（分类讨论）

可以发现当 n < k 或者 k > x + 1 的时候无法构成，其余的时候贪心的用 x 最大化贡献即可，注意特判 k == x 的情况。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n , k , x; 

signed main(){

	IOS
	cin >> t;
	
	while(t --) {
		cin >> n >> k >> x;
		if(n < k || k > x + 1) {
			cout << "-1n";
		} else {
			int res = 0;
			int now = k - 1;
			res += (now + 1) * now / 2;
			if(k == x) res += (x - 1) * (n - k);
			else res += x * (n - k);
			cout << res << "n";
		}
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

B. Friendly Arrays（位运算）

观察或运算发现，只有当前位为 1 的时候或运算才能对结果产生影响，且是把所有数当前位全部变成 1 ，不妨对 n 的奇偶进行讨论，模拟完可以发现这样的一个性质，当 n 为奇数的时候操作异或和会变大，偶数的时候操作异或和会变小，所以最大最小值一定是全操作和全不操作的，计算即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int n , m , t;
int a[N] , b[N];

signed main(){

	IOS
	cin >> t;
	
	while(t --) {
		
		cin >> n >> m;
		int mx = 0 , mn = 0 , k = 0;
		for(int i = 1 ; i <= n ; i ++) cin >> a[i];
		for(int i = 1 ; i <= m ; i ++) cin >> b[i] , k |= b[i];
		for(int i = 1 ; i <= n ; i ++) {
			mn ^= (a[i] | k);
			mx ^= a[i];
		}
		if(mn > mx) swap(mn , mx);
		cout << mn << " " << mx << "n";
	}
	

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

C. Colorful Table(思维，排序)

不难发现对于每个数来说，我们要找大于等于本身的最靠左的位置和最靠右的位置，考虑按照值的大小升序排序，这样问题就转化成找排序后每个值右边序号的最大值和最小值，逆序扫一遍，边扫便维护即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n , k , ans[N];
struct node {
	int x , id;
}a[N];

signed main(){

	IOS
	cin >> t;
	
	while(t --) {
		cin >> n >> k;
		for(int i = 1 ; i <= n ; i ++) {
			cin >> a[i].x ;
			a[i].id = i;
		}
		sort(a + 1 , a + 1 + n ,
			[&](node a, node b){
				return a.x < b.x;
			}
		);
		int mx = -9e18 , mn = 9e18;
		for(int i = n ; i >= 1 ; i --){
			int now = a[i].x;
			int id  = a[i].id;
			mx = max(mx , id);
			mn = min(mn , id);
			ans[now] = (mx - mn + 1) * 2;
		}
		
		for(int i = 1 ; i <= k ; i ++) {
			cout << ans[i] << " ";
			ans[i] = 0;
		}
		cout << "n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

D. Prefix Purchase(贪心)

首先不难想到，贪心的取次数最多且最靠右的位置，但这样显然不是最优的，因为有

3 4 5

11

这种情况，我们可以通过替换的方式更充分的利用余数，转化一下不难发现如何利用余数的问题和开始要求的问题是一样的(选 4 还是选 5去替换 3 就相当于 k = 2 时，选 1 还是选 2 能让字典序变大) ，不断贪心的选把余数用完即可.

例如：

3 4 5

11 第一次贪心之后会变成

0 1 2

2 第二次贪心之后会变成

0 0 1

0

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n , k;
int a[N] , pre[N] , b[N];

signed main(){

	IOS
	cin >> t;
	
	while(t --) {
		
		cin >> n;
		pre[0] = 0;
		for(int i = 1 ; i <= n ; i ++) cin >> a[i] , pre[i] = 0;
		cin >> k;
		
		int id = 0;
		
		while(k && id != -1) {
			int maxx = 0 , id1 = -1;
			for(int i = n ; i >= id + 1 ; i --) {
				if((k / a[i]) > maxx) {
					maxx = k / a[i];
					id1  = i;
				} 
			}
			k -= maxx * a[id1];
			for(int i = n ; i >= id1 + 1 ; i --) {
				a[i] -= a[id1];
			}
			pre[id]    += maxx;
			pre[id1]   -= maxx;
			id = id1;
		}
		
		
		
		int sum = 0;
		for(int i = 1 ; i <= n ; i ++) {
			sum += pre[i - 1];
			cout << sum << " ";
		}
		cout << "n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

E. Another MEX Problem(dp)

先考虑 O(n^3) 的解决方法

$d p [i] [j] 表示前 i 个数是否能表示出 j$

考虑转移

若当前位不选进区间 dp[i][j] = dp[i - 1][j]；

若当前位选进区间，枚举以当前位为右边界的区间，进行转移

dp[i][j] |= dp[l - 1][j ^ mex[l][i]]

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n ;

signed main(){

	IOS
	cin >> t;
	while(t --) {
			
		cin >> n;		
		vector<int>a(n + 1);
		for(int i = 1 ; i <= n ; i ++) {
			cin >> a[i];
		}
		
		vector<vector<int>>mex(n + 1 , vector<int>(n + 1));
		vector<vector<bool>>dp(n + 1 , vector<bool>(1 << 13));
		
		for(int i = 1 ; i <= n ; i ++) {
			int now = 0;
			vector<bool>vis(n + 1);
			for(int j = i ; j <= n ; j ++) {
				vis[a[j]] = 1;
				while(vis[now]) now += 1;
				mex[i][j] = now;	
			}
		}
		
		dp[0][0] = 1;
		
		for(int i = 1 ; i <= n ; i ++) {
			
			//从上一位自然转移
			dp[i] = dp[i - 1];	
			for(int l = 1 ; l <= i ; l ++) {
				for(int k = 0 ; k < (1 << 13) ; k ++) {
					if(dp[l - 1][k]) dp[i][k ^ mex[l][i]] = 1;
				}
			}
		}
		int res = 0;
		for(int i = 0 ; i < (1 << 13) ; i ++) {
			if(dp[n][i]) res = max(res , i);
		}
		cout << res << "n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

考虑优化：

1:首先对于相同的右边界，我们枚举左边界的时候从大到小，由于我们是先从大的范围开始枚举，所以每个 mex 只更新一次即可。

2.其次对于相同的左边界，每个 mex 更新一次即可。

显然能凑出来的mex的数量级是O(n)的，更新次数也是O(n)的

总复杂度

$O(n^2)$

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n ;

signed main(){

	IOS
	cin >> t;
	while(t --) {
		cin >> n;
		
		vector<int>a(n + 1);
		for(int i = 1 ; i <= n ; i ++) {
			cin >> a[i];
		}
		
		vector<vector<int>>mex(n + 1 , vector<int>(n + 1));
		vector<vector<bool>>dp(n + 1 , vector<bool>(1 << 13));
		
		for(int i = 1 ; i <= n ; i ++) {
			int now = 0;
			vector<bool>vis(n + 1);
			for(int j = i ; j <= n ; j ++) {
				vis[a[j]] = 1;
				while(vis[now]) now += 1;
				mex[i][j] = now;	
			}
		}
		
		dp[0][0] = 1;
		
		vector<vector<bool>>visl(n + 1 , vector<bool>(1 << 13));
		vector<vector<bool>>visr(n + 1 , vector<bool>(1 << 13));
		
		for(int i = 1 ; i <= n ; i ++) {
			
			//从上一位自然转移
			dp[i] = dp[i - 1];
			
			for(int l = i ; l >= 1 ; l --) {
				if(visr[i][mex[l][i]]) continue;
				if(visl[l][mex[l][i]]) continue;
				visl[l][mex[l][i]] = 1;
				visr[i][mex[l][i]] = 1;
				for(int k = 0 ; k < (1 << 13) ; k ++) {
					if(dp[l - 1][k]) dp[i][k ^ mex[l][i]] = 1;
				}
			}
		}
		int res = 0;
		for(int i = 0 ; i < (1 << 13) ; i ++) {
			if(dp[n][i]) res = max(res , i);
		}
		cout << res << "n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)(A - E)

A. MEXanized Array（分类讨论）

可以发现当 n < k 或者 k > x + 1 的时候无法构成 ， 其余的时候贪心的用 x 最大化贡献即可 ， 注意特判 k == x 的情况。

B. Friendly Arrays（位运算）

C. Colorful Table(思维 ，排序)

不难发现对于每个数来说 ， 我们要找大于等于本身的最靠左的位置和最靠右的位置 ， 考虑按照值的大小升序排序 ， 这样问题就转化成找排序后每个值右边序号的最大值和最小值 ， 逆序扫一遍 ， 边扫便维护即可。

D. Prefix Purchase(贪心)

首先不难想到，贪心的取次数最多且最靠右的位置 ， 但这样显然不是最优的 ， 因为有

3 4 5

11

例如 ：

3 4 5

11

第一次贪心之后会变成

0 1 2

2

第二次贪心之后会变成

0 0 1

0

E. Another MEX Problem(dp)

先考虑 O(n^3) 的解决方法

考虑转移

若当前位不选进区间 dp[i][j] = dp[i - 1][j]；

若当前位选进区间 ， 枚举以当前位为右边界的区间 ， 进行转移

dp[i][j] |= dp[l - 1][j ^ mex[l][i]]

考虑优化：

1:首先对于相同的右边界 ， 我们枚举左边界的时候从大到小 ， 由于我们是先从大的范围开始枚举 ， 所以每个 mex 只更新一次即可。

2.其次对于相同的左边界 ， 每个 mex 更新一次即可 。

显然能凑出来的mex的数量级是O(n)的 ， 更新次数也是O(n)的

总复杂度

可以发现当 n < k 或者 k > x + 1 的时候无法构成，其余的时候贪心的用 x 最大化贡献即可，注意特判 k == x 的情况。

C. Colorful Table(思维，排序)

不难发现对于每个数来说，我们要找大于等于本身的最靠左的位置和最靠右的位置，考虑按照值的大小升序排序，这样问题就转化成找排序后每个值右边序号的最大值和最小值，逆序扫一遍，边扫便维护即可。

首先不难想到，贪心的取次数最多且最靠右的位置，但这样显然不是最优的，因为有

例如：

若当前位选进区间，枚举以当前位为右边界的区间，进行转移

1:首先对于相同的右边界，我们枚举左边界的时候从大到小，由于我们是先从大的范围开始枚举，所以每个 mex 只更新一次即可。

2.其次对于相同的左边界，每个 mex 更新一次即可。

显然能凑出来的mex的数量级是O(n)的，更新次数也是O(n)的