第七届传智杯初赛+重现赛总结

重现赛题目网站：(2条未读私信) 牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

1.吃糖果(B组、C组)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,count1=0,sum1=0;
int a[200010];
signed main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0;i<n;i++)
	{
		sum1+=a[i];
		if(sum1<=k)
		{
			count1++;
		}
		else
		{
			break;
		}
	}
	cout<<count1<<endl; 
	return 0;
}

2.汤姆和杰瑞(A组、C组)

#include<iostream>
#define int long long
using namespace std;
signed main()
{
	int a,b;
	cin>>a>>b;
	cout<<b-a<<" "<<b<<endl;
	return 0;
}

3.游游的重组偶数(A组、B组、C组)

发现偶数规律，如果用整形重组注意前导0的情况 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int q;
signed main()
{
	cin>>q;
	while(q--)
	{
		int x;
		cin>>x; //变为偶数，数位存在偶数就行
		int a=0,x1=0,temp=0;;
		bool found=false;
		string s,s1;
		while(x>0)
		{
			a=x%10;
			x/=10;
			if(a%2==0)
			{
				found=true;
				temp=a;
				break;
			}
			x1=x1*10+a;
			s=to_string(x1);
		}
		if(x!=0)
		{
			s1=s+to_string(x)+to_string(temp);	
		}
		else
		{
			s1=s+to_string(temp);
		}
		int temp1=0;
		for(int i=0;i<s1.size();i++)
		{
			temp1=temp1*10+(int)(s1[i]-'0'); 
		}
		if(found)
		{
			cout<<temp1<<endl;	
		}
		else
		{
			cout<<-1<<endl;
		}
	}
	return 0;
}

4.开心还是难过(B组、C组) 

注意处理空格字符串的方式：getline(cin,string);

#include<bits/stdc++.h>
#define int long long
using namespace std;
string str;
signed main()
{
	getline(cin,str);
	int s1=0,s2=0;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]==':'&&str[i+1]=='-'&&str[i+2]=='(')
		{
			s1++;
		}
		else if((str[i]==':'&&str[i+1]=='-'&&str[i+2]==')'))
		{
			s2++;
		}
	}
	if((s1==0)&&(s2==0))
	{
		cout<<"None"<<endl;
	}
	else if(s1<s2)
	{
		cout<<"Happy"<<endl;
	}
	else if(s1==s2)
	{
		cout<<"Just so so"<<endl;
	}
	else if(s1>s2)
	{
		cout<<"Sad"<<endl;
	}
	return 0;
}

5.小欧的平面连线(A组、B组、C组)

规律题，交叉对角象限权值2，交叉单坐标权值1

#include<iostream>
#define int long long
using namespace std;
int n,sum=0;
signed main()
{
	int x,y,sign1=0,sign2=0,sign3=0,sign4=0;
	cin>>n;
	while(n--)
	{
		cin>>x>>y;
		if(x>=0 && y>=0)
		{
			sign1++; //一象限
		}
		else if(x<=0 && y>=0)
		{
			sign2++;
		}
		else if(x<=0 && y<=0)
		{
			sign3++;
		}
		else
		{
			sign4++;
		}
	}
	int temp,temps,temp1,temp2;
	//1,3象限配对  2,4象限配对
	temp=min(sign1,sign3);
	temp1=max(sign1,sign3)-temp; //1,3象限剩余某单个象限点
	temps=min(sign2,sign4);
	temp2=max(sign2,sign4)-temps;
	sum=(temp+temps)*2;
	sum+=min(temp1,temp2); //权值为1配对
	cout<<sum<<endl;
	return 0;
}

6.小红的四子棋(A组、B组、C组)

遍历数组，注意if (a[i][j] == '.') continue; // 忽略

只需要判断有4个棋子相连即可，更多无意义

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[110][110];
signed main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			cin>>a[i][j];
		}
	}
	char a1='1';
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			if (a[i][j] == '.') continue; // 忽略
			if(a[i][j]==a[i+1][j] && a[i][j]==a[i+2][j] && a[i][j]==a[i+3][j])
			{
				if(a[i][j]=='r')
				{
					cout<<"kou"<<endl;
				}
				else
				{
					cout<<"yukari"<<endl;
				}
				return 0;
			}
			else if(a[i][j]==a[i][j+1] && a[i][j]==a[i][j+2] && a[i][j]==a[i][j+3])
			{
				if(a[i][j]=='r')
				{
					cout<<"kou"<<endl;
				}
				else
				{
					cout<<"yukari"<<endl;
				}
				return 0;
			}
			else if(a[i][j]==a[i+1][j+1] && a[i][j]==a[i+2][j+2] && a[i][j]==a[i+3][j+3])
			{
				if(a[i][j]=='r')
				{
					cout<<"kou"<<endl;
				}
				else
				{
					cout<<"yukari"<<endl;
				}
				return 0;
			}
			else if(a[i][j]==a[i+1][j-1] && a[i][j]==a[i+2][j-2] && a[i][j]==a[i+3][j-3] )
			{
				if(a[i][j]=='r')
				{
					cout<<"kou"<<endl;
				}
				else
				{
					cout<<"yukari"<<endl;
				}
				return 0;
			}
		}
	}
	cout<<"to be continued"<<endl;
	return 0;
}

7.小红的数组操作(A组、B组) 

二分思想，二分寻找 mid:数组尽可能小的最大值 ，注意可以是负数

#include<iostream>
#define int long long
using namespace std;
int a[100010];
int n,k,x;
bool check(int mid)
{
	int sum=0; //操作次数
	for(int i=1; i<=n; i++)
	{
		if(a[i]>mid) //计算将a[i]降到mid需要的操作次数
		{
			sum+=(a[i]-mid+x-1)/x; //总共操作次数
		}
	}
	return sum<=k; //非必等于k次，尽可能小的最大值（小于k次就能实现，剩余操作只要不去操作数组最大值就行）
}
signed main()
{
	cin>>n>>k>>x;
	for(int i=1; i<=n; i++) cin>>a[i];
	int l = -1e14, r = 1e9, mid, ans;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid)) //mid:数组尽可能小的最大值
		{
			ans=mid;
			r=mid-1; //寻找更小的mid
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<ans<<endl;
	return 0;
}