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

前言

由于本人比较菜，只会这十道题，如果哪里写的不对，请在评论区指出，剩下的三道题会尽力去补 比赛连接：https://ac.nowcoder.com/acm/contest/27302

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

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

代码

#include 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 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 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 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 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 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 × b + a + b = a ( b + 1 ) + b = N a\times b + a + b = a(b+1)+b \ = \ N a×b+a+b=a(b+1)+b = N

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

a x + x − 1 = N ax+x-1=N ax+x−1=N

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

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

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

代码

#include 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 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.最大公约数 思路

代码

#include 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,sum; ll slove(ll x){ ll ans = 0; for(int i = 1;i * i <= x; ++i) { if(x % i == 0) { if(x/i == i) ans++; else ans += 2; } } return ans; } int main() { ll a; cin>>n; for(int i = 1;i <= n; ++i) { cin>>a; sum+=a; } cout<<slove(sum)<<endl; return 0; } 

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

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

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

代码

#include 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 × ( n + 1 ) / 2 n\times(n+1)/2 n×(n+1)/2条边，然后对这个边集求一个最小生成树即可，注意这里要爆int

代码

#include 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; }