2023市北区程序设计竞赛题解

1.分糖果

原题：

解题思路：

这道题类似于辗转相除法，这道题是辗转相减，每次取余数，如果整除，直接计算答案，并退出，否则继续取余

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll a,b,ans=0;cin>>a>>b;
	while(a!=b){
		if(a<b)swap(a,b);
		if(a%b==0){
			ans+=a/b-1;
			break;
		}
		ans+=a/b;a%=b;
	}
	cout<<ans;
	return 0;
}

2.名侦探小S

原题：

解题思路：

这道题有三种解法：第一种，定义一个map，记录编号，查找差值为X的编号是否存在即可

                                第二种，二分查找差值为X的编号

                                第三种，双指针做法，定义两个指针，L和R，如果差值大了，R--，否则L++，最终判断a_R-a_L是否等于X

AC代码1：

map解法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;
int T,n,x,a[N];
int main(){
//	freopen("Find.in","r",stdin);
//	freopen("Find.out","w",stdout);
	cin>>T;
	while(T--){
		bool flag=0;
		map<int,int>mp;
		cin>>n>>x;
		for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]++;
		for(int i=1;i<=n;i++){
			if(mp[a[i]+x]||mp[a[i]-x]){
				cout<<"Yes\n";
				flag=1;
				break;
			}
		}
		if(!flag)cout<<"No\n";
	}
	return 0;
}

AC代码2：

二分解法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+255;
int n,x,a[N],T;
//int find(int x){
//	int l=1,r=n;
//	while(l<=r){
//		int mid=(l+r)/2;
//		if(a[mid]==x)return mid;
//		else if(a[mid]>x)r=mid-1;
//		else l=mid+1;
//	}
//	return 0;
//}
int main(){
	cin>>T;
	while(T--){
		set<int>st;
		bool flag=0;
		cin>>n>>x;
		for(int i=1;i<=n;i++)cin>>a[i],st.insert(a[i]);
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++){
			if(*(lower_bound(a+1,a+n+1,a[i]+x))-x==a[i]){
				cout<<"Yes\n";
				flag=1;
				break;
			}
		}
		if(!flag)cout<<"No\n";
	}
	return 0;
}

AC代码3：

双指针解法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;
int n,x,a[N];
int main(){
	int T;cin>>T;
	while(T--){
		bool flag=0;
		cin>>n>>x;
		for(int i=1;i<=n;i++)cin>>a[i];
		sort(a+1,a+n+1);
		int l=1;
		for(int r=2;r<=n;r++){
			while(a[r]-a[l]>x)l++;
			if(a[r]-a[l]==x){
				flag=1;
				cout<<"Yes\n";
				break;
			}
		}
		if(!flag)cout<<"No\n";
	}
	return 0;
}

3.小S的计算

原题：

解题思路：

大模拟，第一次输入一个数值，后面的都是输入一个符号，一个数字，遇到加法，保留数字*1，遇到减法，保留数字*-1，遇到乘法，前一个数乘上数字，最后排序，求和输出

AC代码1：

vector存储

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e7+5;
ll a;char c;
bool cmp(ll a,ll b){
	if(abs(a)!=abs(b))return abs(a)<abs(b);
	return a>b;
}
int main(){
	vector<ll>vec;
	cin>>a;vec.push_back(a);
	while(cin>>c>>a){
		if(c=='+')vec.push_back(a);
		else if(c=='-')vec.push_back(-a);
		else vec.back()*=a;
	}
	sort(vec.begin(),vec.end(),cmp);
	ll ans=vec[0];cout<<vec[0];
	for(int i=1;i<vec.size();i++){
		ans+=vec[i];
		if(vec[i]>0)cout<<'+'<<vec[i];
		else cout<<vec[i];
	}
	cout<<'='<<ans;
	return 0;
}

AC代码2：

数组存储

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;
ll a=0,ans=0,x[N],t=0,b;
bool flag=1;char p;
bool cmp(ll a,ll b){
	if(abs(a)==abs(b))return a>b;
	return abs(a)<abs(b);
}
int main(){
//	freopen("Solve.in","r",stdin);
//	freopen("Solve.out","w",stdout);
	cin>>a;x[++t]=a;
	while(cin>>p>>b){
		if(p=='*'){
			x[t]=x[t]*b;
		}else{
			if(p=='+'){
				x[++t]=b;
			}else{
				x[++t]=-b;
			}
		}
	}
	sort(x+1,x+t+1,cmp);
	for(int i=1;i<=t;i++){
		if(i==1)cout<<x[i];
		else{
			if(x[i]<0)cout<<x[i];
			else if(x[i]>0)cout<<"+"<<x[i];
		}
		ans+=x[i];
	}
	cout<<'='<<ans;
	return 0;
}

4.方块消除

原题：

解题思路：

尺取法，统计每种颜色出现的位置，定义L和R，计算最大长度

AC代码：

#include<bits/stdc++.h>
#define max(a,b)(a>b?a:b)
#define int long long
using namespace std;
const int N = 1e7+255;
vector<int>pos[N];
int n,m,k,ans=0;
signed main(){
	cin>>n>>m>>k;
	for(int x,i=1;i<=n;i++){
		cin>>x;
		pos[x].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int l=0,sum=0;
		for(int r=0;r<pos[i].size();r++){
			while(sum>k)sum-=pos[i][l+1]-pos[i][l]-1,l++;
			if(sum<=k)ans=max(ans,r-l+1);
			sum+=pos[i][r+1]-pos[i][r]-1;
		}
	}
	cout<<ans;
	return 0;
}