HUNNU新生赛第二场2022/10/27
迅哥的签到题2
https://ac.nowcoder.com/acm/contest/45064/A
写在前前面：学姐写题解很累的，大家好好补题，尤其是学妹qwq
写在前面：有问题请私聊学姐
A.迅哥的签到题2
https://ac.nowcoder.com/acm/contest/45064/A * 思路：
遍历判断质数即可，记得特判0和1。这里用了一点点小小的优化：如果n为一个合数，那么必存在n=a*b（a，b都是整数），且a和b一个大于等于根号n，一个小于等于根号n，那么我们遍历查找到这个较小的因子即可，如果不存在，则是质数。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n==0||n==1){
printf("NO");
return 0;
}
bool ans=true;
for(int i=2;i*i<=n;i++)
{
if(n%i==0){
ans=false;
break;
}
}
if(ans) printf("YES");
else printf("NO");
return 0;
}
B.幼崽是op
https://ac.nowcoder.com/acm/contest/45064/B
思路：输入变量，然后计算答案并输出即可。注意float，double型变量，以及占位符%.nf就是保留n位小数输出的意思。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n=0,m=0,q=0,w=0,e=0,r=0,t=0,y=0;
scanf("%d%d%d%d%d%d%d%d",&n,&m,&q,&w,&e,&r,&t,&y);
float ans=1.0*n*(1+0.01*m*0.01*q)*(1+0.01*w)*0.01*e*0.01*r*(1-0.01*t)*0.01*y;
printf("%.6f\n",ans);
}
return 0;
}
C.幼崽的《壶》
https://ac.nowcoder.com/acm/contest/45064/C
思路：用sort函数将好感度由低到高排序，然后可摆放的原魔数为 最大容纳值和崽拥有数目的最小值，接着摆放原魔直至可使用的原魔用尽或者地块摆满，输出答案。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
int a[1000006];
while(t--)
{
int n,k,q;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&q);
sort(a+1,a+n+1);
ll ans=0;
q=min(q,k);
while(n>0&&q>0)
{
ans+=a[n];
q--;
n--;
}
printf("%d\n",ans);
}
return 0;
}
D.龙哥的字符串
https://ac.nowcoder.com/acm/contest/45064/D
思路：先找到给定串的起始点（4或1或9），若都不是，必不是419419......419的子串；若是，则遍历给定串是否符合...419...419...的规律，符合则为子串，否则不是子串。
代码：
#include<bits/stdc++.h>
using namespace std;
int fa[4]={'4','1','9',0};
int main()
{
string t;
cin>>t;
int len=t.length();//取string的长度
int now=11235;
bool ans=true;
if(t[0]=='4') now=0;
else if(t[0]=='1') now=1;
else if(t[0]=='9') now=2;
if(now==11235){//首字符不是4或1或9
printf("NO");
return 0;
}
for(int i=0;i<len;i++)
{
if(t[i]==fa[now]){
now=(now+1)%3;
continue;
}
ans=false;
}
if(ans) printf("YES");
else printf("NO");
return 0;
}
E.N色绘恋：仅存有『你』的颜色
https://ac.nowcoder.com/acm/contest/45064/E
hanhan学姐的位运算思路：了解二进制和位运算（位与&，左移<<,右移>>）的基础知识即可
hanhan的位运算代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n=0,p=0;
scanf("%d%d",&n,&p);
n--;
while(n>=0){
int op=(p&(1<<n))>>n;//取数字p的第n位
if(op==1) printf("N");//如为1，选择N
else if(op==0) printf("Y");//如为Y，选择Y
p=p-(op<<n);//舍去数字p的最高位
n--;
}
return 0;
}
VIH学姐的思路：暴力即可
VIH的代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, p;
scanf("%d %d", &n, &p);
int pow = 1;
for(int i=1; i<=n; ++i){
pow = pow*2;
}
while(pow!=1){
pow = pow/2;
if(p>=pow){
cout<<"N";
p-=pow;
}
else cout<<"Y";
}
return 0;
}
F.简单的计算题?
https://ac.nowcoder.com/acm/contest/45064/F
思路：很多同学的做法：遍历所有i和j，最坏情况运算约1 000 000*1 000 000次，必超时，所以这种做法只能得部分分。
可以遍历一遍a[n]~a[1]，求出每个位置的num——此元素至第n个元素的和。 然后遍历一遍a[1]~a[n],ans=ans+a[i]*num[i]。 最后输出ans即可 这样做最坏情况下运算次数约为1 000 000（计算后缀和）+ 1 000 000（相加答案）；
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long ans=0;
int n=0;
int a[1000100]={0};
long long num[1000100]={0};
scanf("%d",&n);
for(long long i=1;i<=n;i++) scanf("%d",&a[i]);
for(long long i=n;i>=1;i--) num[i]=num[i+1]+a[i];
for(long long i=1;i<=n;i++) ans+=(a[i]*num[i]);
printf("%lld",ans);
return 0;
}
G.横版闯关游戏
https://ac.nowcoder.com/acm/contest/45064/G
思路：不断尝试向左/向右扩展，如果能抵达出口则输出yes，当两侧都无法扩展而还未到达出口时陷入死局输出no 。
1.自k向左走，如果可以走到出口则ans=true,如果不可以走到出口则标记左旗（来时路线中生命值最大处）
- 自k向右走，如果可以走到出口则ans=true,如果不可以走到出口则标记右旗（来时路线中生命值最大处）
3.重复1.2，只是k分别变成了左旗和右旗。当1和2中没有旗帜的扩展时则无法再前进，ans=false;
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
ll a[202020];
int main()
{
cin>>t;
while(t--)
{
ll n,k;
scanf("%lld%lld",&n,&k);
for(ll i=0;i<=n+1;i++) a[i]=0;
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
if(k==1||k==n){
printf("YES\n");
continue;
}
ll maxn=a[k],now=a[k];//最大生命值，当前生命值
bool ans=false;
bool opl=true;//左侧是否扩展
bool opr=true;//右侧是否扩展
ll l=k-1,r=k+1;
while(opl||opr)//当左右都无法扩展，跳出循环
{
opl=false;
opr=false;
for(ll i=r;i<=n;i++)
{
if(now+a[i]<0) break;//无法前进，跳出循环
now+=a[i];
if(now>maxn) {//最大生命值更新
maxn=now;
opr=true;
r=i+1;//右旗更新
}
if(i==n&&now>=0) ans=true;
}
now=maxn;//以最大值继续扩展
for(ll i=l;i>=1;i--)
{
if(now+a[i]<0) break;//无法前进，跳出循环
now+=a[i];
if(now>maxn) {//最大生命值更新
maxn=now;
opl=true;
l=i-1;//左旗更新
}
if(i==1&&now>=0) ans=true;
}
now=maxn;//以最大值继续扩展
}
if(ans) printf("YES\n");
else printf("NO\n");
}
return 0;
}
H.排球爱打排球
https://ac.nowcoder.com/acm/contest/45064/H
思路：
判定合理性：1.小比分是否合理 2.对局大比分是否合理
判定胜者：比分3：几。
注意：当胜者得分25时分差大于等于两分即可，当胜者得分超过25时分差必须严格等于2才行
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n=0,x=0,y=0;
scanf("%d",&n);
bool ans=true;
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(x==3||y==3) ans=false;//已经有人赢达三局但比赛还在继续，不合理。
if(i==5){
if(a<15&&b<15) ans=false;//得分均小于15，不合理。
if(abs(a-b)<2) ans=false;//分差小于2，不合理。
if((a>15||b>15)&&abs(a-b)!=2) ans=false;//胜者分数超过15时分差不为2，不合理。
}
else if(i<5){
if(a<25&&b<25) ans=false;
if(abs(a-b)<2) ans=false;
if((a>25||b>25)&&abs(a-b)!=2) ans=false;
}
if(ans) a>b?(x++):(y++); //合理情况下，记录对局大比分
}
if(x<3&&y<3) ans=false;//没有赢家，不合理
if(ans) printf("%d",x==3?1:2);
else printf("0");
return 0;
}
查看10道真题和解析
