首页 > 编程语言 >第二届“重科杯”重庆科技大学程序设计竞赛（同步赛）ptlks的题解（2024.5.18）

第二届“重科杯”重庆科技大学程序设计竞赛（同步赛）ptlks的题解（2024.5.18）

时间：2024-05-18 19:09:29浏览次数：21  
标签：2024.5 int 题解 cin 重科杯 long oplus 200005 define

A.Alice 和 Bob

题意：

给定序列A和序列,m组信息\((i,j)\)，Alice可以交换\(A_i\)和\(A_j\)任意次，判断Alice是否能将序列A转变为序列B。

思路

由于Alice可以任意调整m组信息，所以题目所给m组信息\((i,j)\)不影响结果。先考虑k组信息，第i组为\((T_i,T_{i+1})\),\(1\leq T_1\lt T_2\lt...\lt T_{k+1}\le n\)，Alice可以任意次使用这k组信息，所以Alice可以任意排序\(A_{T_1},A_{T_2},...,A_{T_{k+1}}\)这k+1个数。所以可以根据B的排列，将A与B不同的数分为若干组，每组可以通过\({k_i}\)组信息来排序。用并查集分组即可。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   

int a[200005],b[200005],c[200005];
int fa[200005];

int find(int x) {
	return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

void merge(int i, int j) {
	fa[find(i)] = find(j);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	cin >> T;
	while (T--) {
		int n,m,s=0;
		
		cin>>n;
		for(int i=1;i<=n;i++){
			fa[i]=i;
			cin>>a[i];
			c[a[i]]=i;
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			if(b[i]!=a[i]){
				merge(i,c[b[i]]);
			}
		}
		for(int i=1;i<=n;i++){
			
			if(find(i)!=i){
				s++;
			}
		}
		//cout<<s<<endl;
		cin>>m;
		for(int i=0;i<m;i++){
			int x,y;
			cin>>x>>y;
			
		}
		if(s>m){
			cout<<"No\n";
		}else{
			cout<<"Yes\n";
		}
	}
	return 0;
}

B.Haoo的异或

题意：

求x，使得\((1\oplus x)\oplus(2\oplus x)\oplus...\oplus(n\oplus x)\)最小。

思路

由异或性质可得，n为奇数时，\((1\oplus x)\oplus(2\oplus x)\oplus...\oplus(n\oplus x)=(1\oplus2\oplus...\oplus n)\oplus x\)，n为偶数时，\((1\oplus x)\oplus(2\oplus x)\oplus...\oplus(n\oplus x)=(1\oplus2\oplus...\oplus n)\)，预处理\(1\oplus2\oplus...\oplus n\)即可

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   

int a[200005],b[200005],c[200005];
int fa[200005];

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	for(int i=1;i<=1e5;i++){
		a[i]=i;
		a[i]^=a[i-1];
	}
	int T = 1;
	cin >> T;
	while (T--) {
		int n;
		cin>>n;
		if(n%2){
			cout<<a[n]<<endl;
		}else{
			cout<<"no one"<<endl;
		}
	}
	return 0;
}

C.死亡左轮

题意：

有Q次询问，每次询问一个区间[l,r]表示，从第l个人开始到第r个人，玩死亡左轮，每人依次开一枪，请问第几个人最先死亡？

思路

求从\(i\)开始游戏第一个死的人，用一个偏移量来维护当前的弹巢位置，每次对有子弹的弹巢位置遍历即可。对于每个\(l\),查找从\(l\)开始游戏第一个死的人，若小于等于\(r\)，则输出此人，否则无人死亡。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   
int mx=1000005;
int a[1000005],b[1000005],c[100005];
vector<int>d[100];
priority_queue<PII,vector<PII>,greater<PII>>qq;
string s;
vector<PII>q,p;
vector<int>ans;


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	//cin >> T;
	while (T--) {
		int n,m,k,sum=0;
		cin>>m>>n>>k;
		for(int i=0;i<n;i++){
			c[i]=-1;
		}
		for(int i=0;i<m;i++){
			cin>>b[i];
		}
		int pk=0;
		for(int i=0;i<n;i++){
			cin>>a[i];
			for(int j=0;j<m;j++){
				if(b[((pk-j)%m+m)%m]){
					for(int k=0;k<d[j].size();k++){
						c[d[j][k]]=i;
					}
					d[j].clear();
				}
			}
			d[(pk)%m].emplace_back(i);
			pk+=a[i];
		}

		for(int i=0;i<k;i++){
			int l,r;
			cin>>l>>r;
			l--;
			if(b[0]==1){
				cout<<1<<endl;
			}else{
				if(c[l]!=-1&&r>=c[l]+1){
					cout<<c[l]+1<<endl;
				}else{
					cout<<"No one died"<<endl;
				}
			}
		}
	}
	return 0;
}

D.构造字符串

题意：

构造一个长度最短的字符串，满足 cqust 和 tsuqc 这两个字串在字符串中分别出现了x次和y次。

思路

模拟即可

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   

int a[200005],b[200005],c[200005];
int fa[200005];


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	cin >> T;
	while (T--) {
		int x,y;
		string s,s1="cqust",s2="tsuqc",s3="cqustsuq",s4="tsuqcqus";
		cin>>x>>y;
		if(x>y){
			for(int i=0;i<min(x,y);i++){
				s+=s3;
			}
			for(int i=0;i<x-min(x,y);i++){
				s+=s1;
			}
		}else if(x<y){
			for(int i=0;i<min(x,y);i++){
				s+=s4;
			}
			for(int i=0;i<y-min(x,y);i++){
				s+=s2;
			}
		}else{
			for(int i=0;i<min(x,y);i++){
				s+=s3;
			}
			s+='c';
		}
		cout<<s<<endl;
	}
	return 0;
}

E.奇怪的排序

题意：

略。

思路

找连续的不相交的区间[l,r]满足\(\forall i，a[i]\neq i\)的个数。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   

int a[1000005],b[200005],c[200005];
int fa[200005];
string s;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	cin >> T;
	while (T--) {
		int n,f=0,sum=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]!=i){
				f=1;
			}else{
				sum+=f;
				f=0;
			}
		}
		sum+=f;
		cout<<sum<<endl;
	
	}
	return 0;
}

F.画画的 baby

思路

模拟。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   
int mx=1000005;
int a[1000005],b[1000005],c[1000005],d[1000005];

string s;
vector<PII>q,p;
vector<int>ans;



int lowbit(int x){
	return x&-x;
}
int getsum1(int x) { 
	int ans = 0;
	while (x > 0) {
		ans = ans + c[x];
		x = x - lowbit(x);
	}
	return ans;
}
void add1(int x, int k) {
	while (x <= mx) {
		c[x] = c[x] + k;
		x = x + lowbit(x);
	}
}


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	//cin >> T;
	while (T--) {
		int n,sum=0;
		cin>>n;
		for(int i=0;i<n;i++){
			int x,y,f=1;
			cin>>x>>y;
			q.emplace_back(PII{x,y});
			if(!a[y])add1(y,1);
			a[y]++;
		}
		sort(q.begin(),q.end());
		int qx,qy,l=0;
		for(int i=0;i<n;i++){
			int x=q[i].first,y=q[i].second;
			if(x==qx&&y==qy){
				a[y]--;
				if(!a[y])add1(y,-1);
				continue;
			}
			//cout<<x<<' '<<y<<endl;
			if(i){
				if(x==qx){
					sum+=y-qy;
					sum+=x-l-1;
					sum+=(getsum1(y-1)-getsum1(qy))*(x-l-1);
					//cout<<"getsum1(y-1)-getsum1(qy) "<<getsum1(y-1)-getsum1(qy)<<endl;
				}else{
					sum+=(getsum1(1e6)-getsum1(qy))*(qx-l);
					l=qx;
					sum+=y;
					sum+=x-l-1;
					sum+=getsum1(y-1)*(x-l-1);
					//cout<<"getsum1(y-1) "<<getsum1(y-1)<<endl;
				}
			}else{
				sum+=x+y-1;
				sum+=getsum1(y-1)*(x-1);
			}
			qx=x,qy=y;
			//cout<<sum<<endl;
			a[y]--;
			if(!a[y])add1(y,-1);
		}
		cout<<sum<<endl;
	}
	return 0;
}

G.魔王降世

题意：

给定n个村庄的坐标位置和m个火山的坐标位置，有Q次询问，每次询问第\(t_i\)秒的时候，有多少个村庄遭到破坏？。

思路

计算每个村庄离最近的火山的距离，排序，二分查找即可

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   

int a[1000005],b[200005],c[200005];
int fa[200005];
string s;
vector<PII>q,p;
vector<int>ans;





int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	//cin >> T;
	while (T--) {
		int n,m,Q;
		cin>>n>>m>>Q;
		for(int i=0;i<n;i++){
			int x,y;
			cin>>x>>y;
			q.emplace_back(PII{x,y});
		}
		for(int i=0;i<m;i++){
			int x,y;
			cin>>x>>y;
			p.emplace_back(PII{x,y});
		}
		for(int j=0;j<n;j++){
			int mn=INT64_MAX;
			for(int i=0;i<m;i++){
				mn=min(mn,(p[i].first-q[j].first)*(p[i].first-q[j].first)+(p[i].second-q[j].second)*(p[i].second-q[j].second));
			}
			ans.emplace_back(mn);
		}
		sort(ans.begin(),ans.end());
		for(int i=0;i<Q;i++){
			int t;
			cin>>t;
			int pos=upper_bound(ans.begin(),ans.end(),t*t)-ans.begin();
			cout<<pos<<endl;
		}
	}
	return 0;
}

H.波峰交叉 k 序列

思路

不会

代码

I.礼物商店

题意：

每次购买物品后价格会由\(x\)变为\((x+k)|(x\&k)\)，最少花多少钱能买到n件商品。

思路

因为\((x+k)|(x\&k)\geq(x+k)\)，贪心，每次选取价格最小的物品，最后注意购买次数即可。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   
int mx=1000005;
int a[1000005],b[1000005],c[1000005],d[1000005];
priority_queue<PII,vector<PII>,greater<PII>>qq;
string s;
vector<PII>q,p;
vector<int>ans;



int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	//cin >> T;
	while (T--) {
		int n,m,k,sum=0;
		cin>>n>>m>>k;
		for(int i=0;i<m;i++){
			cin>>a[i];
		}
		for(int i=0;i<m;i++){
			int x;
			cin>>x;
			qq.push(PII{x,i});
		}
		for(int i=0;i<n;i++){
			if(a[qq.top().second]){
				a[qq.top().second]--;
				sum+=qq.top().first;
				int t=(qq.top().first+k)|(qq.top().first&k);
				int ii=qq.top().second;
				qq.pop();
				qq.push(PII{t,ii});
			}else{
				qq.pop();
				i--;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

J.切割 01 串

题意：

求切割的最大次数

思路

每次切割可以删去一个0或1，所以最大次数为n-1，判断字符串内是否有1即可。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define MOD 10000000000ll
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'

using namespace std;   

int a[200005],b[200005],c[200005];
int fa[200005];
string s;


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	cin >> T;
	while (T--) {
		cin>>s;
		int sum=0,f=0;
		for(int i=0;i<s.length();i++){
			if(s[i]=='1'){
				f=1;
			}
		}
		if(f)cout<<s.length()-1<<endl;
		else cout<<0<<endl;
	
	}
	return 0;
}

标签：2024.5,int,题解,cin,重科杯,long,oplus,200005,define
From： https://www.cnblogs.com/ptlks/p/18199647

相关文章

  • [ABC353F] Tile Distance 题解
    [ABC353F]TileDistance题解题目传送门：洛谷,AtcoderSolution很恶心人的分类讨论题。很显然走大格子大概率比走小格子快。对终点和起点向上下左右枚举大格子，我们就把问题转化为给两个大格子\((a,b)\)、\((c,d)\)，求怎样走最快。对角的大格子可以通过\(2\)步相互到达，如下......
  • CF527E Data Center Drama 题解
    @目录题目题意题解思路详解注意事项代码AC记录尾声题目CF527EDataCenterDrama·戳这里题意给定一张$n$个点$m$条边的连通无向图。你需要加尽可能少的边，然后给所有边定向，使得每一个点的出入度都是偶数。边可以是自环，也可以有重边。$n\le10^5$，$m\le2\times1......
  • Codeforces 769B News About Credit 题解
    题目简述波利卡普在由$n$名学生（包括他自己）组成的小组中学习，编号为$1$到$n$，波利卡普的编号始终是$1$。他们都在社交网络上注册，每个学生都有一个值$a_i$，表示第$i$名学生每天能发送的最大信息数。清晨，波利卡普知道了一个重要消息，他认为有必要通过私人消息紧急通知所有组员......
  • 安装vue/cli报错问题解决
    在管理员终端中输入命令:npmi-g@vue/cli错误原因证书已过期，需要安装淘宝镜像npmconfigsetregistryhttps://registry.npmmirror.com使用cnpm安装脚手架报错cnpmi-g@vue/cli 这个错误表明你尝试执行的 cnpm 命令无法加载，因为PowerShell策略不允许执......
  • P10125 「Daily OI Round 3」Simple 题解
    题目传送门简单模拟，主要考察字符串。首先输入一个char类型的数组，然后直接遍历每一位是否为Acoipp或Svpoll即可。//Simple//codeby:cq_irritater//time:2024/02/04#include<bits/stdc++.h>usingnamespacestd;chara[10];intmain(){//freopen("......
  • P8684 [蓝桥杯 2019 省 B] 灵能传输 题解
    题目传送门本题涉及到了\(3\)种算法：前缀和，排序以及贪心。（1）前缀和本题实际上要求通过某种灵能传输可以使得该序列的最大值最小。而由前缀和可知，当某一个前缀和序列保持有序（或前缀和序列表示的函数单调）时，其\(s[i]-s[i-1]\)的最大值可以达到最小。通过对几个样例的观察......
  • P9686 Judg. 题解
    题目传送门一道简单模拟。这道题最简单的方法就是直接在for循环中判断题目给出状态是否为AC，如果不是则输出当前\(i\)的值，否则就不输出。#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+10;intn;stringa[MAXN];intmain(){ scanf("%......
  • P8741 [蓝桥杯 2021 省 B] 填空问题 题解
    题目传送门试题A：空间【解析】本题考察计算机存储的基础知识，只要掌握空间存储的换算方法，就能够算出答案。【程序】#include<bits/stdc++.h>usingnamespacestd;intmain(){printf("%d\n",256*8/32*1024*1024);return0;}【答案】67108864......
  • P8679 [蓝桥杯 2019 省 B] 填空问题 题解
    题目传送门试题A：组队【解析】本题是一道经典的DFS搜索题，每次对各号位的选手进行DFS，找到各号位上有成绩的选手时再进行进一步搜索即可。【程序】#include<bits/stdc++.h>usingnamespacestd;intteam[20][6];intmax_sum;boolvis[20];voiddfs(intu,intsu......
  • P9517 drink 题解
    题目传送门这道题考场上用的查找做的。先用一个结构体分别表示firstlast，然后进行查找即可，两个for循环分别计算出first和last，最后计算它们的差值。（注意，计算差值时要加1）然后你就会发现一个问题：只有\(90\)分。所以我们来思考一下哪里出现了问题。你会发现：如果全都是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99