2019YPACM社团年终赛（暨实验室选拔赛）

By ouluy

🎈帅学长的爱心

题意

输出0或者1 ，0时输出0 ，1时输出指定的爱心

思路

给出了公式，按照公式输出就行

AC代码

#include<stdio.h>
int main()
{
    int n;
    while(~scanf("%d",&n)){
            if(n==1){
                for(double i=1.5;i>=-1.5;i-=0.1){
                    for(double j=-1.5;j<=1.5;j+=0.05){
                        double k=j*j+i*i-1.0;
                        if(k*k*k<=j*j*i*i*i){
                            printf("*");
                        }else{
                            printf(" ");
                        }
                    }
                    printf("\n");
                }
            }
            else{
                printf("0\n");
            }
    }
    return 0;
}

🎈秋姐妹鸣泣之时 秋日天空下

题意

输入n，给n行01字符串，每个0和1都可以变成0或者1，如果能全部变成0，输出qiurangzi，不能就输出qiujingye

思路

总有一种情况会全变成0，所以直接输出qiurangzi即可

<font color=#66CDAA><h3>AC代码</h3></font>

#include<stdio.h>
#include<string.h>
int main()
{
    int n;
    char s[1000];
    while(~scanf("%d",&n)){
        while(n--){
            scanf("%s",s);
            printf("qiurangzi\n");
        }
    }
    return 0;
}

🎈王韬韬学长之喝可乐

题意

输入一个数字n，代表可以拿到n个空瓶子，4个空瓶子可以换一瓶可乐，然后三个空瓶子可以问老板借一个，换完可乐后还完。

思路

因为三个空瓶子可以换完，所以直接除3即可

AC代码

#include<stdio.h>
#include<string.h>
int main()
{
    long long n;
    while(~scanf("%lld",&n)){
        printf("%lld\n",n/3);
    }
    return 0;
}

🎈Thanos sort 灭霸の无限手套

题意

数组三等分，然后获得最长非降序数组的大小是多少

思路

暴力模拟

AC代码

#include<stdio.h>
int a[88];
int main()
{
    int t,n;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
            }
            int minn=1;
            for(int i=3;i<=n;i*=3){
                for(int j=1;j<=n;j+=i){
                    int f=0;
                    for(int k=j+1;k<j+i;k++){
                        if(a[k-1]>a[k]){
                            f=1;
                            break;
                        }
                    }
                    if(!f){
                        minn=i;break;
                    }
                }
            }
            printf("%d\n",minn);
        }
    }
    return 0;
}

🎈云云姐的奇妙键盘

题意

键盘输入0，会输出两个1，现在给一串数字字符串，问有多少种输入情况

思路

斐波那契（参考跳阶梯）

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<functional>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;
const int maxn=1e5+10;
int dp[maxn];
char s[maxn];
int main(){
    while(~scanf("%s",s+1)){
         int l=strlen(s+1);
        dp[0]=1,dp[1]=1;
       for(int i=2;i<=l;i++){
        if(s[i]=='1' && s[i-1]=='1'){
            dp[i]=(dp[i-1]+dp[i-2])%mod;
        }
        else{
            dp[i]=dp[i-1];
        }
      }
      printf("%d\n",dp[l]);
    }
    return 0;
}

<font color=#1C86EE><h2>🎈云云姐想要染色</h2></font>

<font color=#66CDAA><h3>题意</h3></font>

给了1，2，3种颜色的位置，给1，2，3颜色的每个位置的价钱，求最小总价即可

<font color=#66CDAA><h3>思路</h3></font>

暴力模拟

AC代码

#include<stdio.h>
int min(int a,int b){
    return a<b?a:b;
}
int a[1010][3];
int q,p,n;
int jia[1010];
int main()
{
    while(~scanf("%d",&n)){
        for(int i=0;i<3;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&a[j][i]);
            }
        }
        for(int i=0;i<n;i++){
            scanf("%d",&jia[i]);
            jia[i]--;
        }
        int sum1=0,sum2=0,sum3=0,sum4=0,sum5=0,sum6=0;
        for(int i=0;i<n;i++){
            if(jia[i]==0){
                sum1+=a[i][0];
                sum2+=a[i][1];
                sum3+=a[i][2];
                sum4+=a[i][0];
                sum5+=a[i][1];
                sum6+=a[i][2];
            }
            else if(jia[i]==1){
                sum1+=a[i][1];
                sum2+=a[i][2];
                sum3+=a[i][0];
                sum4+=a[i][2];
                sum5+=a[i][0];
                sum6+=a[i][1];
            }
            else if(jia[i]==2){
                sum1+=a[i][2];
                sum2+=a[i][0];
                sum3+=a[i][1];
                sum4+=a[i][1];
                sum5+=a[i][2];
                sum6+=a[i][0];
            }
        }
        int mi=min(min(min(sum1,sum4),min(sum2,sum3)),min(sum5,sum6));
        printf("%d\n",mi);
    }
    return 0;
}

🎈 云云姐梦游仙境之决战史莱姆

题意

输入n，再输入n个数，再输出数字m，问n个数里面的一些数字可不可以组成m

思路

dfs或者dp都可以过

AC代码

#include<stdio.h>
const int maxn=1e4+10;
int a[15],m,n;
bool flag;
void dfs(int i,int sum){
    if(sum==m){
        flag=true;return;
    }
    if(i==n){
        return;
    }
    if(flag){
        return;
    }
    dfs(i+1,sum+a[i]);
    dfs(i+1,sum);
}
int main()
{
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        scanf("%d",&m);
        flag=false;
        dfs(0,0);
        if(flag){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

🎈王韬韬学长之买绳子

题意

题目说的比较清晰了，这里就不说了

思路

前缀和+求和公式

AC代码

#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=100005;
int main()
{
    int p[maxn],p1[maxn],n,m,q;
    while(~scanf("%d%d",&n,&m)){
        p[0]=0;
        memset(p1,0,sizeof(p1));
        for(int i=1;i<=n;i++){
            scanf("%d",&q);
            p[i]=(p[i-1]+q)%m;//统计每个数包括他之前所有数之后和m的余数
            p1[p[i]]++;//统计余数的数量
        }
        ll sum=0;
        for(int i=0;i<m;i++){
            if(!i){
                sum=sum+p1[0]+(ll)p1[0]*(p1[0]-1)/2;//当余数为0的时候，我们共有p1[0]+(ll)p1[0]*(p1[0]-1)/2种选择
            }
            else{
                sum=sum+(ll)p1[i]*(p1[i]-1)/2;//当余数不为0的时候，我们共有p1[i]*(p1[i]-1)/2种选择
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}

🎈Zxh学长的奇妙游戏

题意

这题题目也是比较清晰了，这里就不说了

思路

找下规律，前缀和，然后排序，加n-m

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=3e6+10;
int s[maxn];
int t,n,m,a,b;
int main()
{
    while(~scanf("%d%d",&n,&m)){
        scanf("%d",&a);
        int aa=a;
        if(n==1){
            printf("0\n");continue;
        }
        int t=0;
        for(int i=1;i<n;i++){
            scanf("%d",&b);
            s[t++]=b-a;
            a=b;
        }
        if(m==1){
            printf("%d\n",b-aa);continue;
        }
        sort(s,s+t);
        int sum=0;
        for(int i=0;i<n-m;i++){
            sum+=s[i];
        }
        printf("%d\n",sum);
    }
    return 0;
}

🎈众神所眷恋的幻想乡

题意

题目过长，emmm，就是有两个boss有特殊技能，也会横、竖技能，一个boss会地图全覆盖，但问题是boss的实体的会挡住boss的技能走向，另一个boss会斜着发射十字架的技能。问有没有地方可以全躲，如果有输出yes，横坐标最小，再选择纵坐标最小；如果无，输出no

思路

模拟

AC代码

#include<iostream>
#include<cstring>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
int g[110][110];
int n,m,k,sx,sy,t,xx,yy,ji;
void jiuheng(int x,int y){
    if(sx==x && sy==y){return;}
    for(int i=y;i<=m;i++){
        if(sx==x && sy==i){break;}
        g[x][i]=1;
    }
    for(int i=y;i>=1;i--){
        if(sx==x && sy==i){break;}
        g[x][i]=1;
    }
}
void jiuzhong(int x,int y){
    if(sx==x && sy==y){return;}
    for(int i=x;i<=n;i++){
        if(sx==i && sy==y){break;}
        g[i][y]=1;
    }
    for(int i=x;i>=1;i--){
        if(sx==i && sy==y){break;}
        g[i][y]=1;
    }
}
void er(int x,int y){
    int x1=x,y1=y;if(sx==x1 && sy==y1){return;}
    while(x1>0 && y1>0){
        g[x1][y1]=1;x1--;y1--;if(sx==x1 && sy==y1){break;}
    }
    x1=x,y1=y;
    while(x1<=n && y1>0){
        g[x1][y1]=1;x1++;y1--;if(sx==x1 && sy==y1){break;}
    }
    x1=x,y1=y;
     while(x1>0 && y1<=m){
        g[x1][y1]=1;x1--;y1++;if(sx==x1 && sy==y1){break;}
    }
    x1=x,y1=y;
    while(x1<=n && y1<=m){
        g[x1][y1]=1;x1++;y1++;if(sx==x1 && sy==y1){break;}
    }
}
void dd(int a,int b,int c){
    if(sx==a && sy==b){return;}
    if(c==1){
        jiuheng(a,b);
    }else if(c==2){
        jiuzhong(a,b);
    }else{
        if(k==9){
            for(int i=b;i<=m;i++){
                if(sx==a && sy==i){break;}
                jiuzhong(a,i);
            }
            for(int i=b;i>=1;i--){
                if(sx==a && sy==i){break;}
                jiuzhong(a,i);
            }
        }else{
            er(a,b);
        }
    }
}
int main(){
    while(~scanf("%d%d%d%d%d%d",&n,&m,&k,&sx,&sy,&t)){
        mem(g,0);
        g[sx][sy]=2;
        for(int i=0;i<t;i++){
            scanf("%d%d%d",&ji,&xx,&yy);
            dd(xx,yy,ji);
        }
        int aa=1;g[sx][sy]=2;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!g[i][j]){
                    printf("yes\n%d %d\n",i,j);
                    aa=0;break;
                }
            }
            if(!aa){break;}
        }
        if(aa){
            printf("no\n");
        }
    }
    return 0;
}

🎈顾十二的神秘数字

题意

这题是pat乙级的原题，题意很清楚

思路

模拟 或者 搜索

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<assert.h>
#include<cstring>
#include<map>
#include<stack>
#include<queue>
#define ll long long
using namespace std;
int xj(int x){
    int su=0;
    while(x){
        su+=x%10;
        x/=10;
    }
    return su;
}
bool prime(int a){
       if(a<3){
        return false;
    }
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            return false;
        }
    }
    return true;
}
struct node{
    int x,y;
};
node a[5000000];
bool cmp(node a,node b){
    if(a.x==b.x){
        return a.y<b.y;
    }
    else{
        return a.x<b.x;
    }
}
int gcd(int a,int b){
    return a%b==0?b:gcd(b,a%b);
}
int main()
{
    int t,k,m;
    int i;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d",&k,&m);
            int d=1;
            int e=0;
            for( i=1; i<k; i++){
                d*=10;
            }
            for(i=d+99;i<=d*10; i+=100){
                if(xj(i)==m&&prime(gcd(xj(i+1),xj(i)))){
                    a[e].x=xj(i+1);
                    a[e++].y=i;
                }
            }
            if(e==0){
                printf("N0 Solution\n");
            }
            else{
                sort(a,a+e,cmp);
                for(i=0;i<e;i++){
                    printf("%d %d\n",a[i].x,a[i].y);
                }
            }
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define ll long long
const int N = 100001;
const ll mod = 1000000007;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int isp(int n){
   if(n<=2)return 0;
   for(int i=2;i*i<=n;i++)
    if(n%i==0)return 0;
   return 1;
}
int fg;
int a[20];

void dfs(int l,int ed,int num,int n,int x){
    if(num<0)return ;
    if(l==ed){
        if(num>8)return ;
        cout<<x<<" ";
        for(int i=1;i<ed;i++)cout<<a[i];
        cout<<num;
        for(int i=0;i<n;i++)cout<<9;
        cout<<endl;
        fg=1;
        return ;
    }
    for(int i=0;i<10;i++){
        if(i==0&&l==1)continue;
        a[l]=i;
        dfs(l+1,ed,num-i,n,x);
    }
}
int main()
{
    int t,k,m;
    cin>>t;
    while(t--){
        fg=0;
        cin>>k>>m;
        for(int i=k-1;i>0;i--){
            int n=m-i*9+1;
            if(n<=0)continue;
            if(isp(gcd(n,m))){
                dfs(1,k-i,n-1,i,n);
            }
        }
        if(!fg)cout<<"N0 Solution"<<endl;
    }
    return 0;
}

记得补题，题目两小时半还是挺困难ak的，毕竟我验题也验了几天的时间，题目基本没有锅。题目基本属于简单题

我的三道题都是很基本的题目，希望大家补题

这些题解都是我写的，如果有疑问可以qq问我

所有的核心代码都是c语言构成，无除社团课之外的知识点。