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

篇首语：本文由编程笔记#小编为大家整理，主要介绍了第九届“图灵杯”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>&＃61;60) puts("jige,haoye!");
else puts("laoshi,caicai,laolao");
return 0;


G1024【签到】

#include
using namespace std;
typedef long long int LL;
int main()

int n,k; cin>>n>>k;
for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;)

int a,b; cin>>a>>b;
if(b-a>&＃61;n)

cout<<i;
return 0;


puts("G!");
return 0;


NEUQ【模拟】

#include
using namespace std;
typedef long long int LL;
string ss&＃61;"NEUQ";
int main()

int n; cin>>n;
string s; cin>>s;
int cnt&＃61;s.size();
for(int i&＃61;0,j&＃61;0;i<s.size();i&＃43;&＃43;)

if(s[i]&＃61;&＃61;ss[j]) j&＃43;&＃43;;
if(j&＃61;&＃61;4) j&＃61;0,cnt-&＃61;4;

cout<<cnt;
return 0;


小G的任务【签到】

#include
using namespace std;
typedef long long int LL;
LL n,sum;
int main()

cin>>n;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)

LL temp&＃61;i;
while(temp) sum&＃43;&＃61;temp%10,temp/&＃61;10;

cout<<sum;
return 0;


nn与游戏【bfs】

#include
using namespace std;
const int N&＃61;2010;
int a[N][N],st[N][N],n,m;
int dx[4]&＃61;-1,0,0,1;
int dy[4]&＃61;0,-1,1,0;
int bfs(int x,int y,int xx,int yy)

memset(st,-1,sizeof st);
st[x][y]&＃61;0;
queue< pair<int,int> >q; q.push(x,y);
while(q.size())

auto temp&＃61;q.front(); q.pop();
x&＃61;temp.first,y&＃61;temp.second;
if(x&＃61;&＃61;xx&&y&＃61;&＃61;yy) return st[x][y];
for(int i&＃61;0;i<4;i&＃43;&＃43;)

int tempx&＃61;x&＃43;dx[i],tempy&＃61;y&＃43;dy[i];
if(tempx<0||tempx>&＃61;n||tempy<0||tempy>&＃61;n) continue;
if(st[tempx][tempy]!&＃61;-1) continue;
if(a[tempx][tempy]) continue;
st[tempx][tempy]&＃61;st[x][y]&＃43;1;
q.push(tempx,tempy);


return -1;

int main(void)

cin>>n>>m;
for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)

int x,y; cin>>x>>y;
a[x][y]&＃61;1;

int t; cin>>t;
vector< pair<int,int> >ve1,ve2;
while(t--)

int x,y,xx,yy; cin>>x>>y>>xx>>yy;
a[x][y]&＃61;1,a[xx][yy]&＃61;1;
ve1.push_back(x,y);
ve2.push_back(xx,yy);

for(int i&＃61;0;i<ve1.size();i&＃43;&＃43;)

int x&＃61;ve1[i].first,y&＃61;ve1[i].second;
int xx&＃61;ve2[i].first,yy&＃61;ve2[i].second;
a[xx][yy]&＃61;0;
cout<<bfs(x,y,xx,yy)<<endl;
a[xx][yy]&＃61;1;

return 0;


第二大数【第二大】

#include
using namespace std;
const int N&＃61;1e6&＃43;10;
typedef long long int LL;
LL a[N],n,sum;
int main(void)

cin>>n;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) cin>>a[i];
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)

LL d1&＃61;a[i],d2&＃61;0;
for(int j&＃61;i&＃43;1;j<&＃61;n;j&＃43;&＃43;)

if(a[j]>&＃61;d1) d2&＃61;d1,d1&＃61;a[j];
else if(a[j]>d2) d2&＃61;a[j];
sum&＃43;&＃61;d2;


cout<<sum;
return 0;


Num【思维】

我们先不考虑(a&＃43;b)的值&＃xff0c;假如n&＃61;a*b 则我们枚举到sqrt(n)即可。加上了(a&＃43;b)多了点值&＃xff0c;我们多加一些即可。

#include
using namespace std;
typedef long long int LL;
int main()

LL n; cin>>n;
bool flag&＃61;0;
for(LL i&＃61;1;i<&＃61;sqrt(n)&＃43;5;i&＃43;&＃43;) //枚举a

LL a&＃61;i;
LL b&＃61;(n-a)/(a&＃43;1);//计算b
LL sum&＃61;a*b&＃43;a&＃43;b;
if(sum&＃61;&＃61;n&&b) flag&＃61;1;//满足

if(flag) puts("Yes");
else puts("No");
return 0;



评论区的思路。

#include
using namespace std;
vector<int>A,B,C;
const int N&＃61;1e5*6&＃43;10;
int s[N],ans[N];
int main(void)

string a; cin>>a;
int n&＃61;a.size();
a&＃61;"0"&＃43;a;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) s[i]&＃61;s[i-1]&＃43;(a[i]-&＃39;0&＃39;);
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) ans[i]&＃61;s[n&＃43;1-i];
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) ans[i&＃43;1]&＃43;&＃61;ans[i]/10,ans[i]&＃61;ans[i]%10;
if(ans[n&＃43;1]) cout<<ans[n&＃43;1];
for(int i&＃61;n;i>&＃61;1;i--) cout<<ans[i];
return 0;


最大公约数【思维】

评论区里的思路。

#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&＃61;1e5&＃43;10;
LL a[N],n,sum;
LL solve(LL x)

int cnt&＃61;0;
for(LL i&＃61;1;i<&＃61;x/i;i&＃43;&＃43;)

if(x%i&＃61;&＃61;0)

cnt&＃43;&＃43;;
if(x/i!&＃61;i) cnt&＃43;&＃43;;


return cnt;

int main(void)

cin>>n;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) cin>>a[i],sum&＃43;&＃61;a[i];
cout<<solve(sum);
return 0;


玄神的字符串【贪心】

分类讨论即可。

#include
using namespace std;
int main(void)

string s; cin>>s;
int a,b,c; cin>>a>>b>>c;
int cnt0&＃61;0,cnt1&＃61;0;
for(int i&＃61;0;i<s.size();i&＃43;&＃43;)
if(s[i]&＃61;&＃61;&＃39;0&＃39;) cnt0&＃43;&＃43;;
else cnt1&＃43;&＃43;;
int sum&＃61;0;
if(a<&＃61;b)//01 比单独的00 11优惠

int temp&＃61;min(cnt1,cnt0);
sum&＃43;&＃61;temp*a;
cnt1-&＃61;temp,cnt0-&＃61;temp;
sum&＃43;&＃61;max(cnt1,cnt0)*(min(b,a&＃43;c))/2;

else//00 11搭配

sum&＃61;( (cnt1/2)&＃43;(cnt0/2) ) * b;
cnt1&＃61;cnt1%2,cnt0&＃61;cnt0%2;
if(cnt1&&cnt0) sum&＃43;&＃61;min(a,c&＃43;b);

cout<<sum;
return 0;


WireConnection【最小生成树】

#include
using namespace std;
typedef long long int LL;
const int N&＃61;1e5&＃43;10;
struct nodeLL x,y,z;;
bool cmp(node a,node b)return a.z<b.z;
int n,p[N];
vector<node>ve,ans;
int find(int x)

if(x!&＃61;p[x]) p[x]&＃61;find(p[x]);
return p[x];

void solve()

for(int i&＃61;1;i<&＃61;ve.size();i&＃43;&＃43;) p[i]&＃61;i;
sort(ans.begin(),ans.end(),cmp);
LL sum&＃61;0;
for(int i&＃61;0;i<ans.size();i&＃43;&＃43;)

int a&＃61;ans[i].x,b&＃61;ans[i].y,c&＃61;ans[i].z;
if(find(a)&＃61;&＃61;find(b)) continue;
p[find(a)]&＃61;find(b);
sum&＃43;&＃61;c;

cout<<sum;

int main(void)

int n; cin>>n;
while(n--)

int x,y,z; cin>>x>>y>>z;
ve.push_back(x,y,z);

for(int i&＃61;0;i<ve.size();i&＃43;&＃43;)

LL x&＃61;ve[i].x,y&＃61;ve[i].y,z&＃61;ve[i].z;
for(int j&＃61;i&＃43;1;j<ve.size();j&＃43;&＃43;)

LL xx&＃61;ve[j].x,yy&＃61;ve[j].y,zz&＃61;ve[j].z;
LL c&＃61;