• 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
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 << "-1\n";
		} 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);

    • 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

    B. Friendly Arrays（位运算）

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

    #include
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);

    • 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

    C. Colorful Table(思维 ，排序)

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

    #include
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);

    • 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

    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
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);

    • 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

    E. Another MEX Problem(dp)

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

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

    考虑转移

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

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

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

    #include
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
    • 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

    考虑优化：

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

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

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

    总复杂度

    O ( n 2 ) O(n^2) O(n2)

    #include
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);

    • 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
    • 65
    • 66
    • 67
    • 68
  • 相关阅读:
    Python21天学习挑战赛Day(9）·操作MongoDB数据库
    猿创征文｜为了学习英语，我开发了一个单词对战系统
    canvas绘制时钟
    Spring框架系列 - 深入浅出SpringMVC请求流程和案例
    【Transformers】第 9 章：跨语言和多语言语言建模
    Servlet请求转发与重定向
    Windows平台下私有云盘搭建
    java毕业设计安防管理平台mybatis+源码+调试部署+系统+数据库+lw
    七天.NET 8操作SQLite入门到实战 - SQLite 简介
    免费享受企业级安全：雷池社区版WAF，高效专业的Web安全的方案
  • 原文地址：https://blog.csdn.net/woshilichunyang/article/details/133146864