您的位置: 首页  >  文章  >  牛客寒假算法训练第四场

牛客寒假算法训练第四场

分类: 文章 • 2023-11-18 09:30:04

A题：https://ac.nowcoder.com/acm/contest/330/A
题解：博弈论，此题先手必胜

留坑待补更详细的解释

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];
typedef long long ll;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    printf("Applese\n");
    return 0;
}

B题：https://ac.nowcoder.com/acm/contest/330/B

题解：构造题，我觉得对于我的坑点数据是n=1,m>2或者m=1,n>2。没有注意特判

思路和官方题解差不多

牛客寒假算法训练第四场

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    if(n%2!=0&&m%2!=0){
        printf("-1\n");
    }
    else if((n==1&&m>2)||(m==1&&n>2)){
        printf("-1\n");
    }
    else {
        if(n%2!=0){
            for(int i=0;i<n-1;i++){
                printf("D");
            }
            for(int i=0;i<m-1;i++){
                printf("R");
            }
            for(int i=n-1;i>0;i--){
                printf("U");
            }
            for(int i=m-1-1;i>0;i--){
                printf("L");
                for(int j=0;j<n-2;j++){
                    if(i%2==0){
                        printf("D");
                    }
                    else printf("U");
                }
            }
            printf("L");
            printf("\n");
        }
        else{
            for(int i=0;i<m-1;i++){
                printf("R");
            }
            for(int i=0;i<n-1;i++){
                printf("D");
            }
            for(int i=m-1;i>0;i--){
                printf("L");
            }
            for(int i=n-1-1;i>0;i--){
                printf("U");
                for(int j=0;j<m-1-1;j++){
                    if(i%2==0){
                        printf("R");
                    }
                    else printf("L");
                }
            }
            printf("U");
            printf("\n");
        }
    }
    return 0;
}

C题：https://ac.nowcoder.com/acm/contest/330/C

题解：搜索题，求最短的路径，选择bfs最好。用一个三维数组记录每个点的状态vis[x][y][0/1],代表Applese以火或水属性是否走过点(x,y)。

#include <bits/stdc++.h>
using namespace std;
int n,m;
char maps[110][110];
int vis[110][110][2];
int sx,sy,tx,ty;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct pos
{
    int x,y,step,stute;
};
int bfs(int startx,int starty,int endx,int endy)
{
    queue <pos> q;
    vis[startx][starty][0]=1;
    struct pos t;
    t.x=startx,t.y=starty,t.step=0,t.stute=0;
    q.push(t);
    while(!q.empty()){
        struct pos now,next;
        now=q.front();
        q.pop();
        if(now.x==endx&&now.y==endy){
            return now.step;
        }
        for(int i=0;i<4;i++){
            int x1=now.x+dir[i][0];
            int y11=now.y+dir[i][1];
            int t1=now.step+1;
            int stute1=now.stute;
            if(maps[x1][y11]=='#'||x1>=n||y11>=m||x1<0||y11<0) continue ;
            if(stute1==0&&maps[x1][y11]!='w'&&vis[x1][y11][0]==0){
                vis[x1][y11][0]=1;
                next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
                q.push(next);
            }
            if(stute1==1&&maps[x1][y11]!='~'&&vis[x1][y11][1]==0){
                vis[x1][y11][1]=1;
                next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
                q.push(next);
            }
            /*if(maps[x1][y11]=='@'&&vis[x1][y11][stute1]==0){
                next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
                vis[x1][y11][stute1]=1;
                q.push(next);
            }
            if(maps[x1][y11]=='@'&&vis[x1][y11][stute1^1]==0){
                    next.x=x1,next.y=y11,next.step=t1+1,next.stute=stute1^1;
                    vis[x1][y11][stute1^1]=1;
                    q.push(next);
                }*/ //不能这样写
            if(maps[x1][y11]=='T'){
                return t1;
            }
        }
        if(maps[now.x][now.y]=='@'&&vis[now.x][now.y][now.stute^1]==0){
            next.x=now.x,next.y=now.y,next.step=now.step+1,next.stute=now.stute^1;
            vis[now.x][now.y][now.stute^1]=1;
            q.push(next);
        }
    }
    return -1;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",maps[i]);
        for(int j=0;j<m;j++){
            if(maps[i][j]=='S'){
                sx=i,sy=j;
            }
            else if(maps[i][j]=='T'){
                tx=i,ty=j;
            }
        }
    }
    printf("%d\n",bfs(sx,sy,tx,ty));
    return 0;
}

E题：https://ac.nowcoder.com/acm/contest/330/E

题解：因为左右相邻的都不能有相同颜色，明显当每一行的第一个都确定了颜色时，这一行的状态也就确定了，而每一个格子的颜色只有两种选择。所有答案即为牛客寒假算法训练第四场。因为n的数据大小到了牛客寒假算法训练第四场，要用欧拉降幂+快速幂。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define N 1000100
#define mod 1e9+7
using namespace std;
char b[N];
char n[N],m[N];
ll p[N];
ll a, c;
ll quick(ll a, ll b){ //快速幂
    ll k = 1;
    while(b){
        if(b%2==1){
            k = k*a;
            k %=c;
        }
        a = a*a%c;
        b /=2;
    }
    return k;
}
void priem(){
    memset(p, 0, sizeof(p));
    ll i, j;
    p[1] = 1;
    for(i=2; i<=sqrt(N); i++){
        for(j=2; j<=N/i; j++)
            p[i*j] = 1;
    }
}
ll ola(ll n){ //欧拉函数
    ll i, j, r, aa;
    r = n;
    aa = n;
    for(i=2; i<=sqrt(n); i++){
        if(!p[i]){
            if(aa%i==0){
                r = r/i*(i-1);
                while(aa%i==0)
                    aa /= i;
            }
        }
    }
    if(aa>1)
        r = r/aa*(aa-1);
    return r;
}
int main(){
        ll d, i, j;
        priem();
        scanf("%s %s",n,m);
        ll l = strlen(n);
        ll B=0;
        c=mod;
        ll oc = ola(c);
        for(i=0; i<l; i++){
            B = B*10+n[i]-'0';
            if(B>oc)
                break;
        }
        if(i==l)
            d = quick(2,B);
        else{
            B=0;
            for(i=0; i<l; i++){ 
                B = (B*10+n[i]-'0')%oc;
            }
            d = quick(2,B+oc);
        }
        printf("%lld\n",d);
        
    return 0;
}

还有强大的python解法:

print(pow(2, int(input().split()[0]), 10**9 + 7))

J题：https://ac.nowcoder.com/acm/contest/330/J

签到题就不说了，用公式就好了

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define pi 3.1415926
int main()
{
    double ans,f1,f2;
    int a;
    scanf("%lf %lf %d",&f1,&f2,&a);
    ans=f1*f1+f2*f2+2*f1*f2*cos(a*pi/180);
    ans=sqrt(ans);
    printf("%lf\n",ans);
    return 0;
}

 

相关推荐