IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Codeforces Round #744 (Div. 3)题解 【A~F】 -> 正文阅读

[数据结构与算法]Codeforces Round #744 (Div. 3)题解 【A~F】

目录

A

题意：

给出一个由 A、B、C 三个字母组成的字符串，每次可以删掉一个‘A’一个‘B’，或者一个‘B’一个‘C’，是否能把这个字符串全部删完

题解：

要全部删完，‘A’的数量+‘C’的数量要等于‘B’的数量

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;

#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		string s; cin>>s;
		int cnta=0,cntb=0,cntc=0,n=s.length();
		for(int i=0;i<n;i++){
			if(s[i]=='A')cnta++;
			else if(s[i]=='B')cntb++;
			else cntc++;
		}
		if(cntb==cnta+cntc)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

B

题意：

给出一个数组a[1…n]，每次可以选择一个区间 [ l , r ] [l,r] [l,r] ，将这个区间的元素都往左移 d d d 位，这种操作最多执行 n n n 次，找到一种方案，使数组最后非递减

题解：

既然不需要最小化操作数，那就操作 n n n 次，第 i i i 次在区间 [ i . . n ] [i..n] [i..n] 找到最小值的位置 P，然后把区间 [ i . . P ] [i..P] [i..P] 往左移 P-i 个，即每次都找到剩余元素的最小值并把它放在左边

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
int a[100],b[100];
#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		int n; cin>>n;
		vector<pair<int,int>>v;
		for(int i=1;i<=n;i++)cin>>a[i];
		int ans=0;
		for(int i=1;i<=n;i++){
			int p=-1,mi=INF;
			for(int j=i;j<=n;j++)if(a[j]<mi)mi=a[j],p=j;
			if(p==i)continue;//第i位已经是最小的就不用移了
			ans++,v.push_back(make_pair(i,p));
			int tmp=a[p];
			for(int j=p;j>=i;j--)a[j]=a[j-1];
			a[i]=tmp;
		}
		cout<<ans<<endl;
		for(int i=0;i<v.size();i++){
			cout<<v[i].first<<" "<<v[i].second<<" "<<v[i].second-v[i].first<<endl;
		}
	}
}

C

题意：

一个n*m的网格，每次可以选择一个点 ( i , j ) (i,j) (i,j) 和一个边长 d d d ，以 ( i , j ) (i,j) (i,j) 为底部，涂黑一个 V 形，现在给出一个终状态的图和一个边长最小限制K，问这个终状态是否能达到

题解：

枚举终状态每一个被涂黑的点，一直往上找边长的最大延伸，如下图所示
在这里插入图片描述

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
string s[100];
int vis[100][100];
int n,m,k;
#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		memset(vis,0,sizeof vis);
		cin>>n>>m>>k;
		for(int i=0;i<n;i++)cin>>s[i];
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(s[i][j]=='*'){
					int len=0;
					//i,j往上延伸，但是要保证坐标合法，判断左上和右上是不是'*'
					while(i-len>=0&&j-len>=0&&j+len<m&&s[i-len][j-len]=='*'&&s[i-len][j+len]=='*')
						len++;
					len--;//因为(i,j)不计入长度，所以 len要-1
					if(len<k)continue;//往上延伸的距离没达到最小限制就不标记
					for(int u=0;u<=len;u++)
						vis[i-u][j-u]=vis[i-u][j+u]=1;
				}
			}
		}
		int flag=1;
		//如果有涂黑的点但是没被标记过，说明到达不了
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(s[i][j]=='*'&&!vis[i][j])flag=0;
		cout<<(flag?"YES":"NO")<<endl;
	}
}

D

题意：

有 n n n 个人，第 i i i 个人的可谈话次数为 a i a_i ai?，谈话在两个人之间进行，进行一次对应的可谈话次数 ? 1 -1 ?1，求所有人谈话次数总和的最大值，并输出一种方案

题解：
每次必须选a最大的和其他的进行一次谈话，可以从反面想：
假如选的其中一个不是最大的，那么谈到最后，最大值可能有很多次剩余，因为能和最大值谈的都内部消化了，所以最大值必选
这里给两种写法：
优先队列选最大、次大

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;

#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		int n; cin>>n;
		priority_queue<pair<int,int>>q;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			q.push(make_pair(x,i));
		}
		vector<pair<int,int>>v;
		while(1){
			pair<int,int>x=q.top(); q.pop();
			pair<int,int>y=q.top(); q.pop();
			if(x.first==0||y.first==0)break;
			x.first--,y.first--;
			v.push_back(make_pair(x.second,y.second));
			q.push(x); q.push(y);
		}
		cout<<v.size()<<endl;
		for(auto i:v)
			cout<<i.first<<" "<<i.second<<endl;
	}
}

set选最大、最小（显然没第一种好写）

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;

#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	srand(time(0));
	int _; cin>>_;
	while(_--){
		int n; cin>>n;
		vector<pair<int,int>>v;
		set<pair<int,int>>s;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			if(x)s.insert(make_pair(x,i));
		}
		while(s.size()>1){
			set<pair<int,int>>::iterator it=s.end();it--;
			pair<int,int>x=*s.begin();
			pair<int,int>y=*it;
			if(x.second==0||y.second==0)break;
			v.push_back(make_pair(x.second,y.second));
			x.first--,y.first--;
			s.erase(s.begin());s.erase(it);
			if(x.first>0)s.insert(x);
			if(y.first>0)s.insert(y);
		} 
		cout<<v.size()<<endl;
		for(auto i:v)cout<<i.first<<" "<<i.second<<endl;
	}
}

E1

题意：

给出1~n的排列，模仿deque，只能在头部或者尾部插入元素，求最后字典序最小的序列

题解：

比头部小放头部，否则放尾部

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;

#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		int n; cin>>n;
		deque<int>q;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			if(i==1) q.push_front(x);
			else{
				if(x<q.front())q.push_front(x);
				else q.push_back(x);
			}
		}
		while(!q.empty()){
			cout<<q.front()<<" "; q.pop_front();
		}
		cout<<endl;
	}
}

E2

题意：

给出一个序列 a [ 1... n ] a[1...n] a[1...n] ，构造一个序列使逆序对最小（插入方式和deque一样）

题解：

为啥会有这么板子的题。。显然局部最优解就是全局最优解，用树状数组计算当前元素放头部增加的逆序对和放尾部增加的逆序对，选最小的地方插入

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
int a[N],lsh[N];
int c[N],n;
void update(int x,int val){
	for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val;
}
int query(int x){
	int ans=0;
	for(int i=x;i;i-=lowbit(i)) ans+=c[i];
	return ans;
}
#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		cin>>n; for(int i=1;i<=n;i++)cin>>a[i],lsh[i]=a[i],c[i]=0;
		sort(lsh+1,lsh+1+n); int m=unique(lsh+1,lsh+1+n)-lsh-1;//离散化
		int ans=0;
		for(int i=1;i<=n;i++){
			int p=lower_bound(lsh+1,lsh+1+m,a[i])-lsh;
			int f=query(p-1),e=query(m)-query(p);
			//f:放头部增加的逆序对 e:放尾部增加的逆序对
			ans+=min(f,e); 
			update(p,1);
		}
		cout<<ans<<endl;
	}
}

F

题意：

给出一个01序列 a [ 1... n ] a[1...n] a[1...n] 和每次右移的距离 d d d ，每次操作把序列往右移 d d d 的距离（和B题一样），移完之后 a [ i + d ] ( 新 ) = a [ i ] ( 原 ) ? & ? a [ i + d ] ( 原 ) a[i+d](新)= a[i](原)\ \& \ a[i+d](原) a[i+d](新)=a[i](原)?&?a[i+d](原)，即一个数往右移了d个距离后，它的值会变为它的原值 & 这个地方原来的值
求最小需要几次才能让整个序列为0，若无解输出-1

题解：

首先显然，对于一个点，在移动一定的次数后会回到它最初的位置，即它是在一个圈上的
在这里插入图片描述

n=5，d=2时，只有一个圈 1–>3–>5–>2–>4–>1…
在这里插入图片描述

而n=6，d=2时，有两个圈
① 1–>3–>5–>1…
② 2–>4–>6–>2…

显然，当圈里的数有0的时候，圈内的1 & 0 之后会变成 0，到一定次数都会变成 0；
圈里没有0的时候，一直循环下去，圈内的1互相 & ，到最后还是1

所以只要枚举 1 的位置，看它离所在的圈里的 0 需要移动几次就好了

注意，要加个vis数组标记圈内被走过的点，如果每个点都跑一圈会超时，如果一个点被走过，说明之前有个点经过它且比它离 0 更远，它就没必要找了

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
int a[N],vis[N];
#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--){
		int n,d; cin>>n>>d;
		int ans=0,res=1;
		for(int i=0;i<n;i++)cin>>a[i],vis[i]=0;
		for(int i=0;i<n;i++){
			if(vis[i])continue;
			if(a[i]==1){
				int j=(i+d)%n,flag=1,cnt=1;
				while(a[j]==1){
					if(i==j){flag=0; break;}
					//回到了起点还没找到0，说明整个圈都是1
					vis[j]=1,cnt++,j=(j+d)%n;
				}
				if(!flag){res=0;break;}
				else ans=max(ans,cnt);
			}
		}
		if(!res){cout<<-1<<endl; continue;}
		cout<<ans<<endl;
	}
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-30 12:11:23  更:2021-09-30 12:12:08 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/17 13:47:59-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码