前言

由于本人比较菜，只会这十道题，如果哪里写的不对，请在评论区指出，剩下的三道题会尽力去补

比赛连接：https://ac.nowcoder.com/acm/contest/27302

更好的阅读体验：https://blog.csdn.net/m0_46201544/article/details/122527202

A.大学期末现状（语法）

思路

根据输入的成绩，输出相应的字符串即可

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
int n,a[N];

int main()
{
	int n;
	cin>>n;
	if(n >= 60) puts("jige,haoye!");
	else puts("laoshi,caicai,laolao");
    
	return 0;
}

B.G1024(语法)

思路

我们只需要判断是否有一天火车的位置能全部装下n个人数即可

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
int n,k,a[N],b[N];

int main()
{
	cin>>n>>k;
	int ans = 0;
	bool fg = true;
	for(int i = 1;i <= k; ++i) {
		cin>>a[i]>>b[i];
		if(b[i]-a[i] >= n && fg) {
			ans = i;
			fg = false;
		}
	}
	if(fg) puts("G!");
	else cout<<ans<<endl;
	return 0;
}

C.NEUQ（枚举）

思路

因为是删除其中字符，然后整体顺序不会发生改变，所以我们只需要统计一下有多少个不连续的NEUQ即可，注意这里要计算出完整的NEUQ个数，也就是说到了后面也许有个NE，这个不能算进去。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;

int main()
{
	string ch;
	string ss = "NEUQ";
	int n;
	cin>>n;
	cin>>ch;
	
	int cnt = 0;//计算不需要删除的字符数量
	int j = 0;
	for(int i = 0;i < n; ++i) {
		if(ch[i] == ss[j]){
			j++;
			j %= 4;
			cnt++;
		}
	}
	cnt -= cnt % 4;//将多余的字符减去
	cout<<n-cnt<<endl;
	return 0;
}

D.小G的任务(暴力)

思路

我们直接将一个数的每一位取出来，然后加在一起，将这个功能封装成函数，然后每次计算的时候就能直接调用

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;


ll get(ll x) {
	ll ans = 0;
	while(x){
		ans += x % 10;
		x/=10;
	}
	return ans;
}

int main()
{
	ll n;
	cin>>n;
	ll ans = 0;
	for(int i = 1;i <= n; ++i) {
		ans += get(i);
	}
	cout<<ans<<endl;
	
	return 0;
}

E.nn与游戏(BFS)

思路

我们将查询点存下来，然后离线处理，先把所有的我方、敌方、障碍物变成不可访问的地方，然后对于之前存储的查询点进行一个BFS求一个最短路，注意这里需要将起点和终点在地图上表现成可以访问

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 1e3+10;
bool a[N][N];
bool vis[N][N];
int n,m,t;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
struct Node{
	int x,y,step;
};

bool check(int x,int y){
	if(x >= 0 && x < n && y >= 0 && y < n){
		return true;
	}
	return false;
}

int bfs(int sx,int sy,int ex,int ey){
	queue<Node> que;
	memset(vis,0,sizeof vis);
	que.push({sx,sy,0});
	while(!que.empty()){
		Node p = que.front();
		que.pop();
		if(p.x == ex && p.y == ey) {
			return p.step;
		}
		if(vis[p.x][p.y]) continue;
		vis[p.x][p.y] = true;
		for(int i = 0;i < 4; ++i) {
			int nx = p.x + dx[i];
			int ny = p.y + dy[i];
			if(check(nx,ny) && vis[nx][ny] == false && a[nx][ny] == false){
				que.push({nx,ny,p.step+1});
			}
		}
	}
	return -1;
}
int Ssx[N],Ssy[N],Eex[N],Eey[N];

int main()
{
	cin>>n>>m;
	for(int i = 0;i < m; ++i) {
		int x,y;
		cin>>x>>y;
		a[x][y] = true;
	}
	int t;
	cin>>t;
	int sx,sy,ex,ey;
	for(int i = 0;i < t; ++i) {
		cin>>sx>>sy>>ex>>ey;
		Ssx[i] = sx;
		Ssy[i] = sy;
		Eex[i] = ex;
		Eey[i] = ey;
		a[sx][sy] = a[ex][ey] = true;
	}
	for(int i = 0;i < t; ++i) {
		a[Ssx[i]][Ssy[i]] = a[Eex[i]][Eey[i]] = false;
		cout<<bfs(Ssx[i],Ssy[i],Eex[i],Eey[i])<<endl;
		a[Ssx[i]][Ssy[i]] = a[Eex[i]][Eey[i]] = true;
	}
	
	return 0;
}

F.第二大数（滑动窗口）

思路

由于只是第二大，所以我们可以考虑使用滑动窗口来做，我们用一个循环去枚举窗口的大小，然后内部更新最大值和次大值，注意long long

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e4+10;

ll a[N];
ll ans,n,m,mx1,mx2;

int main()
{
	cin>>n;
	for(int i = 1;i <= n; ++i) {
		cin>>a[i];
	}
	for(int i = 1,j;i < n; ++i) {//枚举窗口长度
		mx1=max(a[i],a[i+1]);
		mx2=min(a[i],a[i+1]);
		ans+=mx2;
		for(j=i+2;j<=n;j++)
		{
			if(a[j]>=mx1)
			{
				mx2=mx1;
				mx1=a[j];
			}
			else if(a[j]>=mx2)
			{
				mx2=a[j];
			}
			
			ans+=mx2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

G.Num(数学)

思路

$a\times b + a + b = a(b+1)+b \ = \ N$

此时我们设 $x = b + 1$ ，则：

$a x + x - 1 = N$

$(a+1)\times x=N+1$

$(a+1)\times (b+1)=N+1$

所以我们只需要判断N+1是否是素数即可，如果是素数那么就输出No，否则输出Yes

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
ll n;

bool check(ll x){
	if(x == 0 || x == 1) return false;
	for(ll i = 2;i * i <= x; ++i) {
		if(x % i == 0) return false;
	}
	return true;
}


int main()
{
	cin>>n;
	if(check(n+1)) puts("No");
	else 
		puts("Yes");
	
	return 0;
}

H.特征值（模拟）

思路

不难发现对于个位的值，我们是将该数所有位的相加，对于十位则是去掉个位的值……，所以我们对该数的所有位置上进行一个求和处理，然后在相应的位置就等于该和的值，然后进位的时候减去当前这位的值即可，最后手动模拟一下进位

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 1e7+10;
vector<ll> a(N);
ll b[N];

int main()
{
	string ch;
	cin>>ch;
	ll sum = 0;
	ll n = ch.size();
	for(ll i = 0;i < n; ++i) {//求和,方便下面处理
		b[i]=ch[i]-'0';
		sum += b[i];
	}
	
	for(ll i = 0;i < n; ++i) {//进行各位赋值
		ll k = b[n-i-1];
		a[i] = sum;
		sum -= k;
	}
	ll len = 0;
	for(ll i = 0;a[i+1]; ++i,len++) {//手动模拟进位
		a[i+1] += a[i]/10;
		a[i] %= 10;
	}
	for(ll i = len;i >= 0; --i) {
		printf("%lld",a[i]);
	}
	putchar('\n');
	return 0;
}

I.最大公约数

思路

被卡了不会

代码

J.玄神的字符串(思维)

思路

对于这个问题我们先统计0的个数和1的个数，

如果其中最小值k是一个奇数，那么说明我们要剩下一对，这一对就要做先变化再删除，或者直接删除
- 对于剩下的全部相同的值，我们要么进行反转一半全部用不同的方式删除，或者直接使用相同的删除
如果是一个偶数，那么直接删除即可（注意这里的删除一种是不同删除，一种是相同删除）
- 对于剩下的全部相同的值，我们要么进行反转一半全部用不同的方式删除，或者直接使用相同的删除

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
string ch;
ll a,b,c;

int main()
{
	cin>>ch;
	cin>>a>>b>>c;
	int n = ch.size();
	int l = 0,r = 0;
	for(int i = 0;i < n; ++i) {
		if(ch[i]=='0')	l++;
		else r++;
	}
	ll ans = 0;
	int k = min(l,r);
	if(k & 1) {//奇数的情况会剩下一对
		ans += min((k-1) * a,(k-1) * b);
		l -= k-1;
		r -= k-1;
		ans += min(a,b+c);
		l = max(l,r);
		ans += min(l/2LL * b,(l/2LL * c) + (l/2LL) * a);
	}
	else {
		ans += min(k * a,k * b);
		l -= k;
		r -= k;
		l = max(l,r);
		ans += min(l/2LL * b,(l/2LL * c) + (l/2LL) * a);
	}
	cout<<ans<<endl;
	return 0;
}

L.WireConnection（最小生成树）

思路

因为点很少，只有2000个，所以我们直接处理一下这些点链连接的边大约是 $n\times(n+1)/2$ 条边，然后对这个边集求一个最小生成树即可，注意这里要爆int

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define N 2005

struct Point{
	int x,y,z;
}P[N];


int get(Point a, Point b) {
	int k = (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) + (a.z-b.z)*(a.z-b.z);
	return (int)(ceil((double)sqrt(double(1.0*k))));
}

struct node{
	int from,to;
	long long cost;
}E[N*N];

int fa[N],n;

bool cmp(node a,node b){
	return a.cost<b.cost;
}

int find(int x){
	int k = x;
	while(k != fa[k])
		k = fa[k]; 
	while(x != fa[x]) {
		int t =fa[x];
		fa[x] = k;
		x = t;
	}
	return x;
}

void init(){
	for(int i = 1; i <= n; ++i)
		fa[i] = i;
}

int same(int x,int y){
	return find(x) == find(y);
}

void merge(int a,int b){
	a = find(a);
	b = find(b);
	if(a != b)
		fa[b] = a;
}
long long kruskal(int m){
	long long ans = 0;
	sort(E+1,E+m+1,cmp);
	for(int i = 1; i <= m; ++i){
		if(same(E[i].from,E[i].to))
			continue;
		merge(E[i].from,E[i].to);
		ans += E[i].cost;
	}
	return ans;//返回的是最小生成树的代价 
}
signed main(){
	scanf("%lld",&n);
	init();
	for(int i = 1;i <= n; ++i) {
		scanf("%lld %lld %lld",&P[i].x,&P[i].y,&P[i].z);
	}
	int cnt = 1;
	for(int i = 1;i <= n; ++i) {
		for(int j = i + 1;j <= n; ++j) {
			E[cnt].from = i,E[cnt].to=j,E[cnt++].cost = get(P[i],P[j]);
		}
	}
	int k = kruskal(cnt);
	printf("%lld\n",k);
	return 0;
}

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

前言