第九届“图灵杯”NEUQ-ACM程序设计竞赛个人【题解】

https://ac.nowcoder.com/acm/contest/27302#question

• 大学期末现状【签到】
• G1024【签到】
• NEUQ【模拟】
• 小G的任务【签到】
• nn与游戏【bfs】
• 第二大数【第二大】
• Num【思维】
• 特征值【找规律 模拟】
• 最大公约数【思维】
• 玄神的字符串【贪心】
• WireConnection【最小生成树】

#include
using namespace std;
typedef long long int LL;
int main()
{
	int x; cin>>x;
	if(x>=60) puts("jige,haoye!");
	else puts("laoshi,caicai,laolao");
    return 0;
}

#include
using namespace std;
typedef long long int LL;
int main()
{
	int n,k; cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int a,b; cin>>a>>b;
		if(b-a>=n) 
		{
			cout< 
NEUQ【模拟】 
#include
using namespace std;
typedef long long int LL;
string ss="NEUQ";
int main()
{
	int n; cin>>n;
	string s; cin>>s;
	int cnt=s.size();
	for(int i=0,j=0;i
		if(s[i]==ss[j]) j++;
		if(j==4) j=0,cnt-=4;
	}
	cout< 
小G的任务【签到】 
#include
using namespace std;
typedef long long int LL;
LL n,sum;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		LL temp=i;
		while(temp) sum+=temp%10,temp/=10;
	}
	cout< 
nn与游戏【bfs】 
 
#include
using namespace std;
const int N=2010;
int a[N][N],st[N][N],n,m;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int bfs(int x,int y,int xx,int yy)
{
	memset(st,-1,sizeof st);
	st[x][y]=0;
	queue< pair >q; q.push({x,y});
	while(q.size())
	{
		auto temp=q.front(); q.pop();
		x=temp.first,y=temp.second;
		if(x==xx&&y==yy) return st[x][y];
		for(int i=0;i<4;i++)
		{
			int tempx=x+dx[i],tempy=y+dy[i];
			if(tempx<0||tempx>=n||tempy<0||tempy>=n) continue;
			if(st[tempx][tempy]!=-1) continue;
			if(a[tempx][tempy]) continue;
			st[tempx][tempy]=st[x][y]+1;
			q.push({tempx,tempy});
		}
	}
	return -1;
}
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y; cin>>x>>y;
		a[x][y]=1;
	}
	int t; cin>>t;
	vector< pair >ve1,ve2;
	while(t--)
	{
		int x,y,xx,yy; cin>>x>>y>>xx>>yy;
		a[x][y]=1,a[xx][yy]=1;
		ve1.push_back({x,y});
		ve2.push_back({xx,yy});
	}
	for(int i=0;i
		int x=ve1[i].first,y=ve1[i].second;
		int xx=ve2[i].first,yy=ve2[i].second;
		a[xx][yy]=0;
		cout< 
第二大数【第二大】 
 
#include
using namespace std;
const int N=1e6+10; 
typedef long long int LL;
LL a[N],n,sum;
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		LL d1=a[i],d2=0;
		for(int j=i+1;j<=n;j++)
		{
			if(a[j]>=d1) d2=d1,d1=a[j];
			else if(a[j]>d2) d2=a[j];
			sum+=d2;
		}
	}
	cout< 
Num【思维】 

 我们先不考虑(a+b)的值，假如n=a*b 则我们枚举到sqrt(n)即可。加上了(a+b)多了点值，我们多加一些即可。
 
#include
using namespace std;
typedef long long int LL;
int main()
{
	LL n; cin>>n;
	bool flag=0;
	for(LL i=1;i<=sqrt(n)+5;i++) //枚举a
	{
		LL a=i;
		LL b=(n-a)/(a+1);//计算b
		LL sum=a*b+a+b;
		if(sum==n&&b) flag=1;//满足
	}
	if(flag) puts("Yes");
	else puts("No");
    return 0;
}
 
评论区的思路。
 
 
特征值【找规律 模拟】 
 
#include
using namespace std;
vectorA,B,C;
const int N=1e5*6+10;
int s[N],ans[N];
int main(void)
{
	string a; cin>>a;
	int n=a.size();
	a="0"+a;
	for(int i=1;i<=n;i++) s[i]=s[i-1]+(a[i]-'0');
	for(int i=1;i<=n;i++) ans[i]=s[n+1-i];
	for(int i=1;i<=n;i++) ans[i+1]+=ans[i]/10,ans[i]=ans[i]%10;
	if(ans[n+1]) cout<=1;i--) cout< 
最大公约数【思维】 

 评论区里的思路。
 
 
#include
using namespace std;
typedef long long int LL;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int N=1e5+10;
LL a[N],n,sum;
LL solve(LL x)
{
	int cnt=0;
	for(LL i=1;i<=x/i;i++)
	{
		if(x%i==0)
		{
			cnt++;
			if(x/i!=i) cnt++;
		}
	}
	return cnt;
}
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	cout< 
玄神的字符串【贪心】 

 分类讨论即可。
 
#include
using namespace std;
int main(void)
{
	string s; cin>>s;
	int a,b,c; cin>>a>>b>>c;
	int cnt0=0,cnt1=0;
	for(int i=0;i
		int temp=min(cnt1,cnt0);
		sum+=temp*a;
		cnt1-=temp,cnt0-=temp; 
		sum+=max(cnt1,cnt0)*(min(b,a+c))/2;
	}
	else//00 11搭配 
	{
		sum=( (cnt1/2)+(cnt0/2) )  * b;
		cnt1=cnt1%2,cnt0=cnt0%2;
		if(cnt1&&cnt0) sum+=min(a,c+b);
	}
	cout< 
WireConnection【最小生成树】 
 
#include
using namespace std;
typedef long long int LL;
const int N=1e5+10;
struct node{LL x,y,z;};
bool cmp(node a,node b){return a.zve,ans;
int find(int x)
{
	if(x!=p[x]) p[x]=find(p[x]);
	return p[x];
}
void solve()
{
	for(int i=1;i<=ve.size();i++) p[i]=i;
	sort(ans.begin(),ans.end(),cmp);
	LL sum=0;
	for(int i=0;i
		int a=ans[i].x,b=ans[i].y,c=ans[i].z;
		if(find(a)==find(b)) continue;
		p[find(a)]=find(b);
		sum+=c;
	}
	cout<
	int n; cin>>n;
	while(n--)
	{
		int x,y,z; cin>>x>>y>>z;
		ve.push_back({x,y,z});
	}
	for(int i=0;i
		LL x=ve[i].x,y=ve[i].y,z=ve[i].z;
		for(int j=i+1;j
			LL xx=ve[j].x,yy=ve[j].y,zz=ve[j].z;
			LL c=ceil( sqrt(1.0*((x-xx)*(x-xx)+(y-yy)*(y-yy)+(z-zz)*(z-zz))) );
			ans.push_back({i+1,j+1,c});
		}
	}
	solve();
	return 0;
}