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

2023-09-21 20:15:00

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

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] 表示前 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<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 ) O(n^2) O(n2)

#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);
更多推荐

功能基础篇2——常用哈希和加密算法介绍及Python相关库与实现

加解密https://docs.python.org/3/library/crypto.html三方库推荐，https://cryptography.io/en/latest/Criptography，https://pypi.org/project/cryptography/PyCryptodome，aforkofP

月木学途开发 6.网址模块

概述效果图数据库设计网站类型表DROPTABLEIFEXISTS`website`;CREATETABLE`website`(`websiteId`int(11)NOTNULLAUTO_INCREMENT,`websiteImg`longtext,`websiteName`varchar(255)DEFAULTNULL

嵌入式Linux驱动开发（I2C专题）（七）

使用GPIO操作I2C设备_IMX6ULL参考资料：Linux文档Linux-5.4\Documentation\devicetree\bindings\i2c\i2c-gpio.yamlLinux-4.9.88\Documentation\devicetree\bindings\i2c\i2c-gpio.txtLin

Selenium-介绍下其他骚操作

ChromeDevTools简介ChromeDevTools是一组直接内置在基于Chromium的浏览器（如Chrome、Opera和MicrosoftEdge）中的工具，用于帮助开发人员调试和研究网站。借助ChromeDevTools，开发人员可以更深入地访问网站，并能够：检查DOM中的元素即时编辑元素和CSS检查和

【Java 基础篇】Java UDP通信详解

UDP（UserDatagramProtocol）是一种无连接的网络传输协议，它不像TCP那样需要建立连接和维护状态，因此更加轻量级。UDP适用于那些对数据传输的实时性要求较高，可以容忍一定数据丢失的场景。本文将详细介绍Java中如何使用UDP协议进行网络通信，包括UDP套接字、数据传输、服务器和客户端的创建等。1.U

云可观测性：提升云环境中应用程序可靠性

随着云计算的兴起和广泛应用，越来越多的企业将其应用程序和服务迁移到云环境中。在这个高度动态的环境中，确保应用程序的可靠性和可管理性成为了一个迫切的需求。云可观测性作为一种解决方案，针对这一需求提供了有效的方法和工具。本文将介绍云可观测性的概念、优势以及它如何提升云环境中应用程序的可靠性和可管理性。一、云可观测性概述掌动

ADB环境搭建和抓取Crash日志实践总结

一、adb下载1.1直接点击下载即可：http://adbshell.com/upload/adb.zip1.2网盘获取链接：https://pan.baidu.com/s/1P9nlRN0RQhPCPDaYg7Cgrg提取码：deng下载到本地解压，双击下图应用程序进行安装，其他文件不用动（与普通应用程序不同，adb

人工智能：ChatGPT与其他同类产品的优缺点对比

引言：自然语言处理技术的快速发展推动了聊天机器人的广泛应用。ChatGPT作为一种强大的语言模型，具有出色的生成能力和上下文理解能力。本文将对比ChatGPT与其他同类产品的优缺点，并展示使用ChatGPT进行对话生成的示例代码。ChatGPT简介ChatGPT是由OpenAI开发的语言模型，基于大规模的预训练数据和深

K8S pod资源、探针

目录一.pod资源限制1.pod资源限制方式2.pod资源限制指定时指定的参数（1）request资源（2）limit资源（3）两种资源匹配方式3.资源限制的示例（1）官网示例2）Pod和容器的资源请求和限制格式（3）CPU资源单位介绍（4）内存资源单位（5）资源限制示例1：（6）资源限制示例2：2.Probe支持三种

模式分类与“组件协作模式”

1.GOF-23模式分类从目的来看：创建型（Creational）模式：将对象的部分创建工作延迟到子类或者其他对象，从而应对需求变化为对象创建时具体类型实现引来的冲击。结构型（Structural）模式：通过类继承或者对象组合获得更灵活的结构，从而应对需求变化为对象的结构带来的冲击。行为型（Behavioral）模式：

Python+Requests+Pytest+YAML+Allure实现接口自动化

本项目实现接口自动化的技术选型：Python+Requests+Pytest+YAML+Allure，主要是针对之前开发的一个接口项目来进行学习，通过Python+Requests来发送和处理HTTP协议的请求接口，使用Pytest作为测试执行器，使用YAML来管理测试数据，使用Allure来生成测试报告一、项目说明本

热文推荐
  1. Go业务开发常用关注点

    本文对实际开发场景中面对高频的场景，总结出来的一些处理方案，希望能对业务开发的同学提供帮助！结构体转换实际开发中会面对一个相似的数据结构，由于引用不同的包，需要开发转换到对应的结构上，本质上这些数据结构是一致的，但是所在包不同所以不能直接赋值。常规的方案大致分为下面几种：直接转换struct这种适合结构完全一致的情况，

  2. 墨天轮专访星环科技刘熙：“向量热”背后的冷思考，Hippo如何打造“先发”优势？

    导读：深耕技术研发数十载，坚持自主可控发展路。星环科技一路砥砺前行、坚持创新为先，建设了全面的产品矩阵，并于2022年作为首个独立基础软件产品公司成功上市。星环科技在今年的向星力•未来技术大会上发布了分布式向量数据库TranswarpHippo以及两款领域大模型“无涯”和“求索”。关于星环科技在向量数据库领域的建树和背

  3. MES管理系统对印刷企业来说有什么优点

    在当今高度信息化的时代，许多企业，包括印刷企业，正在寻求更有效地管理其生产过程和运营的方式。在这种情况下，印刷企业MES管理系统成为了他们的首选。印刷企业MES系统在提升企业运营效率、优化生产过程、提升产品质量以及加强供应链管理等方面具有显著的优势。本文将详细探讨MES管理系统对印刷企业的优点。一、提升生产效率对于印刷

  4. 【UE 粒子练习】07——创建动画拖尾类型粒子

    效果步骤1.将动画序列“Idle_ModifyBones”添加到场景中2.新建一个材质，命名为“Mat_AnimTrails”材质混合模式设置为半透明，着色模型设置为无光照，设置材质为双面材质节点如下3.新建一个粒子系统，命名为“P_AnimTrail”打开“P_AnimTrail”，添加模块“类型数据-》新建动画拖尾

  5. 【深度学习】 Python 和 NumPy 系列教程（十七）：Matplotlib详解：2、3d绘图类型（3）3D条形图（3D Bar Plot）

    目录一、前言二、实验环境三、Matplotlib详解1、2d绘图类型2、3d绘图类型0.设置中文字体1.线框图2.3D散点图3.3D条形图（3DBarPlot）一、前言Python是一种高级编程语言，由GuidovanRossum于1991年创建。它以简洁、易读的语法而闻名，并且具有强大的功能和广泛的应用领域。Pyth

  6. 基于Java的高校竞赛管理系统设计与实现（亮点：发起比赛、报名、审核、评委打分、获奖排名，可随意更换主题如蓝桥杯、ACM、王者荣耀、吃鸡等竞赛）

    高校竞赛管理系统一、前言二、我的优势2.1自己的网站2.2自己的小程序（小蔡coding）2.3有保障的售后2.4福利三、开发环境与技术3.1MySQL数据库3.2Vue前端技术3.3SpringBoot框架3.4微信小程序四、功能设计4.1主要功能描述4.2系统角色五、系统主要功能展示5.1前端展示5.1.1赛事展示

  7. 进程地址空间(Linux虚拟内存机制)

    文章目录一.Linux进程地址空间的结构二.Linux管理进程地址空间的方式三.Linux进程使用物理内存的模型四.进程地址空间的存在意义本章理论基于32位平台的Linux–kernel2.6.32版本内核一.Linux进程地址空间的结构为了保证内存安全,现代操作系统不允许应用程序(进程)直接访问物理内存空间一般来说,

  8. 【C++模拟实现】map、set容器的模拟实现

    【C++模拟实现】map、set容器的模拟实现目录【C++模拟实现】map、set容器的模拟实现map、set模拟实现的代码（insert部分）部分一：红黑树的迭代器以及红黑树部分二：对set进行封装部分三：对map进行封装遇到的问题以及解决方案作者：爱写代码的刚子时间：2023.9.17前言：本篇博客有关map、se

  9. 基于数据驱动的成本洞察，趣丸科技的FinOps进阶之路~

    今年以来，我们注意到越来越多的单位开始积极实践FinOps，而随着FinOps的发展，大家对于其落地过程的关注也更加具体和深入，涉及了账单波动、FinOps的边际效应、成本模型、依赖工具等多个关键问题。本月「UGeek大咖说」线上直播活动，我们邀请到了FinOps实践成熟度非常高的趣丸科技，作为快速发展的互联网公司，趣