首页 > 编程语言 >2025牛客寒假算法基础集训营1 ptlks的题解

2025牛客寒假算法基础集训营1 ptlks的题解

时间：2025-01-21 19:43:05浏览次数：1  
标签：int 题解 代码 long 牛客 数组 ans 集训营 define

A.茕茕孑立之影

题意：

给定序列，找出一个数x，满足x和数组中任意一个元素都互不为倍数关系

思路

x范围为1e18以内，序列元素范围为1e9以内，选大于1e9的质数即可，特判序列中有1的情况。

代码

点击查看代码 
void solve() {
	int n;
	cin>>n;
	int f=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==1)f=0;
	}
	if(f)cout<<1000000007ll<<endl;
	else cout<<-1<<endl;
	
}

B.一气贯通之刃

题意：

判断树是否为链。

思路

两端点度数为1，其余点度数为2。

代码

点击查看代码 
void solve() {
	int n;
	cin>>n;
	int f=1;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		a[x]++;
		a[y]++;
	}
	int s1=0,s2=0;
	for(int i=1;i<=n;i++){
		if(a[i]>2){
			cout<<"-1"<<endl;
			return;
		}
		if(a[i]==1){
			if(!s1){
				s1=i;
			}else{
				s2=i;
			}
		}
	}
	cout<<s1<<' '<<s2<<endl;
	
	
}

C.兢兢业业之移

题意：

给定01矩阵，将所有的1移至左上方。

思路

直接遍历，每次去找最近的1来填空，注意细节即可。

代码

点击查看代码 
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PIII pair<PII,PII>
#define endl '\n'
//#define int long long
//#define i64 long long
#define  lc p<<1
#define  rc p<<1|1
using namespace  std;
const int N = 103 + 10, mod = 998244353;
#define MAXN 200010
#define EXP 32//32
const int INF = 0x3f3f3f3f;
using namespace std;

int a[N][N], b[N][N], c[N][N];
//priority_queue<int,vector<int>,greater<int>>q;
priority_queue<PII, vector<PII>, greater<PII>>q1;
vector<int>g[N];

int xx[4] = {0, 1, 0, -1}, yy[4] = {1, 0, -1, 0};
int mn = 1e9, n;
vector<PII>q, ans;

vector<PIII>aaa;
void solve() {
	cin >> n;
	aaa.clear();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char x;
			cin >> x;

			if (x == '0') {
				a[i][j] = 0;
			} else {
				a[i][j] = 1;
			}
			b[i][j]=c[i][j] = 0;
		}
	}
	for (int i = 1; i <= n / 2; i++) {
		for (int j = 1; j <= n / 2; j++) {
			if (a[i][j] == 0) {
				int X=1000,Y=1000;
				for(int o=1;o<=n;o++){
					for(int p=1;p<=n;p++){
						if(!b[o][p]&&a[o][p]){
							if(abs(o-i)+abs(p-j)<abs(X-i)+abs(Y-j)){
								X=o;
								Y=p;
							}
						}
					}
				}
//				cout<<X<<' '<<Y<<endl;
				ans.clear();
				if(X>=i){
					if(Y>=j){
						for(int l=Y;l>=j;l--){
							ans.push_back({X,l});
						}
					}else{
						for(int l=Y;l<=j;l++){
							ans.push_back({X,l});
						}
					}
					for(int l=X-1;l>=i;l--){
						ans.push_back({l,j});
					}
				}else{
					for(int l=X;l<=i;l++){
						ans.push_back({l,Y});
					}
					if(Y>=j){
						for(int l=Y-1;l>=j;l--){
							ans.push_back({i,l});
						}
					}else{
						for(int l=Y+1;l<=j;l++){
							ans.push_back({i,l});
						}
					}
					
				}
				for (int l = 0; l +1<ans.size(); l++) {
					aaa.push_back({ans[l+1],ans[l]});
				}
				a[X][Y]=0;
				a[i][j]=1;
			}
			b[i][j] = 1;
			
		}
	}
	cout<<aaa.size()<<endl;
	for(auto [u,v]:aaa){
		cout<<u.first<<' '<<u.second<<' '<<v.first<<' '<<v.second<<endl;
	}
}



signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll t = 1;
	cin >> t;
//	euler(1e5);
	while (t--) {
		solve();
	}
}

D.双生双宿之决

题意：

定义一个数组是“双生数组”，当且仅当该数组大小为偶数，数组的元素种类恰好为2种，且这两种元素的出现次数相同。判断数组是否为双生数组。

思路

直接计数即可。

代码

点击查看代码 
void solve() {
	int n;
	cin >> n;
	map<int, int>hm;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		hm[x]++;
	}
	if (hm.size() == 2) {
		for (auto [u, v] : hm) {
			if (v != n / 2) {
				cout << "No\n";
				return;
			}
		}
	} else {
		cout << "No\n";
		return;
	}
	cout << "Yes\n";
}

E.双生双宿之错

题意：

可以进行若干次操作，每次操作将选择一个元素，使其加1或者减1。计算将该数组变成双生数组的最小操作次数。

思路

我蒙的，糊了个三分过了。

代码

点击查看代码 
无

F.双生双宿之探

题意：

计算数组有多少连续子数组是双生数组。

思路

首先不难想到先找元素种类个数为2的子数组，可以证明找出的子数组总长度是O(n)的，然后问题转化为1和-1数组中1和-1个数相同的区间个数，即区间和为0的区间个数，记录前缀和，然后对于相同前缀和进行计数即可。

代码

点击查看代码 
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PIII pair<PII,PII>
#define endl '\n'
#define int long long
//#define i64 long long
#define  lc p<<1
#define  rc p<<1|1
using namespace  std;
const int N = 2e5 + 10, mod = 998244353;
#define MAXN 200010
#define EXP 32//32
const int INF = 0x3f3f3f3f;
using namespace std;

int a[N], b[N], c[N];
//priority_queue<int,vector<int>,greater<int>>q;
priority_queue<PII, vector<PII>, greater<PII>>q1;
vector<int>g[N];
map<int, int>mp,mp1;
int n;
int ans=0;
void f(int l,int r){
	mp1.clear();
	b[l-1]=0;
	mp1[0]++;
	for(int i=l;i<=r;i++){
		if(a[i]==a[l]){
			b[i]=1;
		}else{
			b[i]=-1;
		}
		b[i]+=b[i-1];
		mp1[b[i]]++;
	}
	for(auto [u,v]:mp1){
		ans+=v*(v-1)/2;
	}
	
}

void solve() {
	srand(time(0));
	cin >> n;
	int s = 0;
	ans=0;
	mp.clear();
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int l = 1, r = 1;
	int cnt = 0;

	while (r <= n) {
		if (!mp[a[r]]) {
			if(cnt==2){
				f(l,r-1);
			}
			cnt++;
		}
		mp[a[r]]++;
		r++;
		while(cnt>2){
			mp[a[l]]--;
			if (!mp[a[l]]) {
				cnt--;
			}
			l++;
		}
	}
	if(cnt==2){
		f(l,n);
	}
	cout<<ans<<endl;
}



signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll t = 1;
	cin >> t;
//	euler(1e5);
	while (t--) {
		solve();
	}
}

G.井然有序之衡

题意：

可以进行任意次以下操作：选择两个元素，使得其中一个加1，另一个减1。求将数组变成一个排列需要的最小操作次数。

思路

先计算总和是否符合。然后保留数组内满足排列的数，将剩下的数与排列缺的数排序后一一对应，计数即可。

代码

点击查看代码 
void solve() {
	int n;
	cin>>n;
	int s=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s+=a[i];
		if(a[i]<=n&&a[i]>=1&&!b[i])b[a[i]]++;
		else{
			q.push_back(a[i]);
		}
	}
	if(s==n*(n+1)/2){
		int cnt=0;
		for(int i=1;i<=n;i++){
			if(!b[i]){
				q1.push_back(i);
			}
		}
		sort(q.begin(),q.end());
		sort(q1.begin(),q1.end());
		for(int i=0;i<q.size();i++){
			cnt+=abs(q[i]-q1[i]);
		}
		cout<<cnt/2<<endl;
	}else{
		cout<<-1<<endl;
	}
}

H.井然有序之窗

题意：

构造一个长度为n的排列，需要满足第i个元素的范围在\([l_i,r_i]\)范围内。

思路

以\(l_i\)为第一关键字，\(r_i\)为第二关键字排序。从1开始枚举，每次从可选项中选择\(r_i\)最小的即可。

代码

点击查看代码 
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PIII pair<PII,int>
#define endl '\n'
#define int long long
//#define i64 long long
#define  lc p<<1
#define  rc p<<1|1
using namespace  std;
const int N = 3e5 + 10, mod = 998244353;
#define MAXN 200010
#define EXP 32//32
const int INF = 0x3f3f3f3f;
using namespace std;

int a[N],b[N][2],c[N][2];
//priority_queue<int,vector<int>,greater<int>>q;
priority_queue<PII,vector<PII>,greater<PII>>q1;
vector<int>g[N];
vector<PIII>q;
void solve() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		q.push_back({{l,r},i});
	}
	sort(q.begin(),q.end());
	int p=1;
	int l=0,r=-1;
	int f=1;
//	cout<<r<<endl;
	while(p<=n&&r<(int)q.size()){
		while(r+1<q.size()&&q[r+1].first.first<=p){
			q1.push({q[r+1].first.second,r+1});
			r++;
		}
//		cout<<q.size()<<' '<<q1.size()<<endl;
		if(q1.size()){
			if(q1.top().first>=p){
				a[q[q1.top().second].second]=p;
				p++;
				q1.pop();
			}else{
				f=0;
				break;
			}
		}else{
			f=0;
			break;
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<a[i]<<" \n"[i==n];
//	}
	if(f){
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" \n"[i==n];
		}
	}else{
		cout<<-1<<endl;
	}
	
	
}



signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll t = 1;
//	cin >> t;
//	euler(1e5);
	while (t--) {
		solve();
	}
}

J.硝基甲苯之袭

题意：

给定数组，任取两个元素\(a_i\)和\(a_j(i<j)\) ，满足\(a_i\,xor\,a_j=gcd(a_i,a_j)\)的方案数有多少？

思路

枚举gcd，枚举gcd的倍数\(a_i\)，则\(a_j=gcd\,xor\,a_i\)，然后判断即可。

代码

点击查看代码 
void solve() {
	int n;
	cin>>n;
	int s=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a[x]++;
	}
	for(int i=1;i<=2e5;i++){
		for(int j=i;j<=2e5;j+=i){
			if(a[(j^i)]&&__gcd((j^i),j)==i){
				s+=a[(j^i)]*a[j];
			}
		}
	}
	cout<<s/2<<endl;

	
}

M.数值膨胀之美

题意：

进行恰好一次操作：选择一个非空区间，将其中所有元素都乘以2。最小化数组的极差。

思路

由于操作只会使最大值和最小值增大，所以每次只要考虑最小值即可，按照元素大小不断扩展区间。用线段树维护最大最小值。

代码

点击查看代码 
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<vector<int>,int>
#define PIII pair<PII,string>
#define endl '\n'
#define int long long
//#define i64 long long
#define  lc p<<1
#define  rc p<<1|1
using namespace  std;
const int N = 3e5 + 10, mod = 998244353;
#define MAXN 200010
#define EXP 32//32
const int INF = 0x3f3f3f3f;
using namespace std;

int a[N],b[N][2],c[N][2];
priority_queue<int,vector<int>,greater<int>>q;
priority_queue<int,vector<int>,less<int>>q1;
vector<int>g[N];
const int MAX_LEN =2e5 ;
int seg_tree[MAX_LEN << 2];
int seg_tree1[MAX_LEN << 2];
int Lazy[MAX_LEN << 2];
int arr[MAX_LEN];
//从下往上更新 节点
void push_up (int root) {
	seg_tree[root] = max(seg_tree[root << 1], seg_tree[root << 1 | 1]);      //最小值改min
	seg_tree1[root] = min(seg_tree1[root << 1], seg_tree1[root << 1 | 1]);
}
//从上向下更新，左右孩子
void push_down (int root, int L, int R) {
	if(Lazy[root]){
		Lazy[root << 1] += Lazy [root];
		Lazy[root << 1 | 1] += Lazy[root];
		int mid = (L + R) >> 1;
		seg_tree[root << 1] +=  Lazy[root] * (mid - L + 1);
		seg_tree[root << 1 | 1] += Lazy[root] * (R - mid);
		seg_tree1[root << 1] +=  Lazy[root] * (mid - L + 1);
		seg_tree1[root << 1 | 1] += Lazy[root] * (R - mid);
		Lazy[root] = 0;
	}
}
//建树
//[L,R]就是对应arr数组里面的数
void build (int root, int L, int R) {
	Lazy[root] = 0;
	if(L == R) {
		seg_tree[root] = arr[L];
		seg_tree1[root] = arr[L];
		return ;
	}
	int mid = (L + R) >> 1;
	build(root << 1, L, mid);
	build(root << 1 | 1, mid + 1, R);
	push_up(root);
}

//区间查询
//查找区间[LL,RR]的最大/小值
int querymax (int root, int L, int R, int LL, int RR) {
	if (LL <= L && R <= RR) return seg_tree[root];
	push_down(root, L, R);     //每次访问都去检查Lazy 标记
	int Ans = 0;
	int mid = (L + R) >> 1;
	if(LL <= mid) Ans = max(Ans, querymax(root << 1, L, mid, LL, RR));    //最小值改min
	if(RR > mid) Ans = max(Ans, querymax(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min
	return Ans;
}
int querymin (int root, int L, int R, int LL, int RR) {
	if (LL <= L && R <= RR) return seg_tree1[root];
	push_down(root, L, R);     //每次访问都去检查Lazy 标记
	int Ans = 1e18;
	int mid = (L + R) >> 1;
	if(LL <= mid) Ans = min(Ans, querymin(root << 1, L, mid, LL, RR));    //最小值改min
	if(RR > mid) Ans = min(Ans, querymin(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min
	return Ans;
}
//区间修改 +-某值
//使得区间[LL,RR]的值都加上val
void update_Interval(int root, int L, int R, int LL, int RR, int val){
	if (LL <= L && R <= RR) {
		Lazy[root] += val;
		seg_tree[root] += val * (R - L + 1);
		seg_tree1[root] += val * (R - L + 1);
		return ;
	}
	push_down(root, L, R);
	int mid = (L + R) >> 1;
	if (LL <= mid) update_Interval(root << 1, L, mid, LL, RR, val);
	if (RR > mid) update_Interval(root << 1 | 1, mid + 1, R, LL , RR, val);
	push_up(root);
}
//单点修改 可以改为某值，或者+-某值
//把pos位置的值改成val
void update(int root, int L, int R, int pos, int val) {
	if(L == R){
		seg_tree[root] = val;    //点直接变为某值
		seg_tree1[root] = val;    //点直接变为某值
		return ;
	}
	int mid = (L + R) >> 1;
	if(pos <= mid) update(root << 1, L, mid, pos, val);
	else update(root << 1 | 1, mid + 1, R, pos, val);
	push_up(root);
}
void solve() {
	int n;
	cin>>n;
	map<int,int>hm;
	int mn=1e9,mx=0;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		mn=min(mn,arr[i]);
		mx=max(mx,arr[i]);
	}
	build(1,1,n);

	int ans=1e9;
	int l=0,r=0;
	for(int i=1;i<=n;i++){
		if(arr[i]==mn){
			r=i;
			if(!l)l=i;
		}
	}

	for(int i=l;i<=r;i++){
		update(1,1,n,i,arr[i]*2);
		arr[i]*=2;
		ans=min(ans,querymax(1,1,n,1,n)-querymin(1,1,n,1,n));
//		cout<<querymax(1,1,n,1,n)<<' '<<querymin(1,1,n,1,n)<<endl;

	}
//	cout<<ans<<endl;
	l--,r++;
	while(l>=1||r<=n){
		if(l>=1&&r<=n){
			if(arr[l]<arr[r]){
				update(1,1,n,l,arr[l]*2);
				arr[l]*=2;
				ans=min(ans,querymax(1,1,n,1,n)-querymin(1,1,n,1,n));
				l--;
			}else if(arr[l]>arr[r]){
				update(1,1,n,r,arr[r]*2);
				arr[r]*=2;
				ans=min(ans,querymax(1,1,n,1,n)-querymin(1,1,n,1,n));
				r++;
			}else{
				update(1,1,n,l,arr[l]*2);
				arr[l]*=2;
				ans=min(ans,querymax(1,1,n,1,n)-querymin(1,1,n,1,n));
				l--;
			}
		}else if(l>=1){
			update(1,1,n,l,arr[l]*2);
			arr[l]*=2;
			ans=min(ans,querymax(1,1,n,1,n)-querymin(1,1,n,1,n));
			l--;
		}else{
			update(1,1,n,r,arr[r]*2);
			arr[r]*=2;
			ans=min(ans,querymax(1,1,n,1,n)-querymin(1,1,n,1,n));
			r++;
		}
	}		
	cout<<ans<<endl;
}



signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll t = 1;
//	cin >> t;
//	euler(1e5);
	while (t--) {
		solve();
	}
}

标签：int,题解,代码,long,牛客,数组,ans,集训营,define
From： https://www.cnblogs.com/ptlks/p/18684294

相关文章

  • 题解：洛谷 P4879 ycz的妹子
    题目https://www.luogu.com.cn/problem/P4879感觉还比较简单的线段树。首先我们先建立一棵线段树（范围：）。voidbuild(intk,intl,intr){ tr[k]={l,r}; if(l==r){ Tree[k]=a[l],c[k]=(l<=n); return; } intmid=(l+r)>>1ll; build(k<<1ll,l,mid); build((k<<1ll)|1l......
  • 题解：洛谷 P1351 [NOIP2014 提高组] 联合权值
    题目https://www.luogu.com.cn/problem/P1351我们可以发现，若点对  的距离为 ，则它们一定会经过一个中转点，因此我们考虑枚举中转点 ，然后枚举与  有直接边连接的两个点，按照题意统计答案即可。#include<bits/stdc++.h>usingnamespacestd;#pragmaG++optimisze(3,"Ofas......
  • 【题解】Luogu P4340 [SHOI2016] 随机序列
    简单手摸后发现，答案就是这么一个式子：\[(3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dotsa_{n-1}+a_1a_2\dotsa_n\]啊当然证明也是好证的，对于\(a_1\)这一项，它后面放+或-都会对系数加一，而放*不会影响系数，因此系数就是总数的三分之二。其它前缀......
  • 题解：P3823 [NOI2017] 蚯蚓排队
    题目链接https://www.luogu.com.cn/problem/P3823分析先解决队伍的合并与分离问题。使用链表结构，分别维护每只蚯蚓的前驱和后继即可。然后考虑如何统计答案。可以对每只蚯蚓的“向后\(k\)数字串”使用字符串哈希的方式获得哈希值，再用一个哈希表存储每个哈希值出现的次数。对......
  • 2024 (ICPC) Jiangxi Provincial Contest I 题 Neuvillette Circling题解
    简单思路一个圆套中了几个点，如果不断缩小这个圆，那么最终的结果有两种有两个点卡住了这个圆，且这两点一定是直径有三个或者三个以上的点卡住了这个圆，圆心在这三个点围成的三角形的外接圆圆心。因此我们枚举两点作为直径，或者枚举三个点作为圆的内接三角形，求这个三角形的外接圆......
  • 2024 (ICPC) Jiangxi Provincial Contest L 题 Campus 题解
    简单思路首先对于所有的出口求一遍最短路，由于出口只会打开并关闭一次，所以大门的开启状态是相当有限的（最多大概30种），我们对于每一种状态直接暴力求答案最后输出即可。复杂度大概\(O(knlogn)\)参考代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;type......
  • Codeforces Round 998 (Div. 3) 部分题解
    写题解的时候这场在评测，就不放代码了。E.GraphComposition题意给两个无向简单图，对图\(1\)添加若干条边或删除若干条边，使得两图的连通性一致，最少需要变更多少条边。题解求出图\(2\)的连通性，考虑图\(1\)的所有边，若违背了图\(2\)联通性的要删除（图\(2\)不联通但图\(......
  • 20250120 T2 simu题解
    简单模拟（simu）【题目描述】给定$a_1,a_2,\ldots,a_n$和$b_1,b_2,\ldots,b_n$。对于所有整数$x\in[l,r]$，模拟以下过程并求出变量$res$的最终的值。res=0fori=1ton:ifx>=a[i]:x=x-a[i]res=res+b[i]【输入格式】......
  • 「题解」二进制与一
    传送门：水滴、洛谷题目大意：给定一个正整数$n$，给出操作次数$p$。每次操作让$n$加上一个非负整数$x$，使得$n$的第$k$位为$0$（从右往左数）。如果本身为$1$就不用操作。且每次操作$n+x$回影响后续操作。问$x$的和是多少。首先我们要知道，判断$n$的第$k$位是否为$......
  • 题解：CF580B Kefa and Company
    CF580BKefaandCompany前言。其实本题与这道题极为相似，所以建议降橙。思路因为输入顺序不影响就结果，所以可以先给\(a\)按照工资从小到打排序一下序（这里\(a\)使用MAP）。然后再使用尺取法，只要\(a_{r+1}\)的值减\(a_l\)的值\(\ltk\)就将\(r\)加\(1\)。然后发现每......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99