2020 牛客寒假算法基础集训营 5 题解

发表于 2020-10-31 分类于算法，题解阅读次数：阅读次数： 10 Valine： 0 主题：本文字数： 11k

原题来自 2020 牛客寒假算法基础集训营 5，作以存档备查

A: 模板

输入

4 3
WXYZ
WXY

输出

只需找到两个字符串中不一样的字符替换，长度补齐即可

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a,b,ans=0;
char s1[100050],s2[100050];

int main(){
    scanf("%d%d%s%s",&a,&b,s1,s2);
    ans+=abs(a-b);
    if(a>b){swap(s1,s2);swap(a,b);}
    for(int i=0;i<a;i++)if(s1[i]!=s2[i])ans++;
    cout<<ans;
    return 0;
}

B: 牛牛战队的比赛地

在这里插入图片描述

输入

输出

说明

当在(0,0)(0,0)比赛时，到三个训练基地的最大距离是22。可以证明这是最小值。

我们设，从 x 坐标轴最左边向最右边移动的过程中最远点的距离为 f (x), 那么 f (x) 一定是一个先减后增的函数（仔细想一下，如果是先减后增后减后增那么一定第一次增加之前最远点就变了）所以可以直接使用三分看这里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define max(X,Y) (X>Y?X:Y)
#define min(X,Y) (X<Y?X:Y)
using namespace std;

const int INF=0x3f3f3f3f;
const int MAX_N=1e5+50;
const double esp=1e-5;

int n,x[MAX_N],y[MAX_N],max_x=-INF,min_x=INF;

double dis(double p){
    double dis_max=-INF;
    for(int i=0;i<n;i++){
        dis_max=max(dis_max,y[i]*y[i]+(p-x[i])*(p-x[i]));
    }
    return dis_max;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x[i],&y[i]);
        max_x=max(max_x,x[i]);
        min_x=min(min_x,x[i]);
    }
    double l=min_x,r=max_x,ml=l+(r-l)/3,mr=l+(r-l)/3*2;
    while(ml+esp<mr){
        if(dis(ml)<dis(mr))r=mr;
        else l=ml;
        ml=l+(r-l)/3.0;
        mr=l+(r-l)/3.0*2.0;
    }
    printf("%lf",sqrt(dis((ml+mr)/2)));
    return 0;
}

## C: C 语言 IDE

在这里插入图片描述

输入

#include <stdio.h>

int plus(int a, int b)
{
 return a + b;
}
int main()
{
 int a,b;
 scanf("%d%d", &a, &b);
 printf("%d\n", plus(a, b));
 return 0;
}

输出

int plus(int,int)
int main()

匹配括号，模拟即可

#include <bits/stdc++.h>
using namespace std;

string source;
void replaceAll(string &s, string oldstr, string newstr)
{
    for (string::size_type pos = 0; pos != string::npos; pos += newstr.length())
        if ((pos = s.find(oldstr, pos)) != string::npos)
            s.replace(pos, oldstr.length(), newstr);
        else
            break;
}
struct functions
{
    string inClass, name, outputType;
    vector<string> inputType;
    functions(string inClass = "", string name = "", string outputType = "void", vector<string> inputType = vector<string>(0))
        : inClass(inClass), name(name), outputType(outputType), inputType(inputType) {}
};
vector<functions> funs;
void solve(string &s)
{
    replaceAll(s, "/*", " /* ");
    replaceAll(s, "*/", " */ ");
    replaceAll(s, "//", " // ");
    replaceAll(s, "(", " ( ");
    replaceAll(s, ")", " ) ");
    replaceAll(s, "{", " { ");
    replaceAll(s, "}", " } ");
    replaceAll(s, "=", " = ");
    replaceAll(s, "\"", " \" ");
    replaceAll(s, "'", " ' ");
    replaceAll(s, ";", " ; ");
    replaceAll(s, ",", " , ");
    replaceAll(s, "+ = ", "+=");
    replaceAll(s, "- = ", "-=");
    replaceAll(s, "* = ", "*=");
    replaceAll(s, "/ = ", "/=");
    replaceAll(s, "^ = ", "^=");
    replaceAll(s, "| = ", "|=");
    replaceAll(s, "& = ", "&=");
    replaceAll(s, ":", " : ");
    replaceAll(s, " :  : ", "::");
    vector<string> tokens;
    string now = "";
    for (int i = 0; s[i]; i++)
    {
        if (s[i] == ' ' || s[i] == '\t' || s[i] == '\r' || s[i] == '\n' || s[i] == '\0')
        {
            if (now != "")
            {
                if (now == ":" && tokens.back() == ")")
                {
                    string tmpnow = "";
                    for (int j = i + 1; s[j]; j++)
                    {
                        if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0')
                        {
                            if (tmpnow == "{")
                            {
                                now = "{";
                                i = j - 1;
                                break;
                            }
                            tmpnow = "";
                        }
                        else
                            tmpnow += s[j];
                    }
                    continue;
                }
                if (now == "const")
                {
                    now = "";
                    continue;
                }
                if (now == "//")
                {
                    for (int j = i; s[j]; j++)
                    {
                        if (s[j] == '\n')
                        {
                            i = j - 1;
                            break;
                        }
                    }
                    now = "";
                    continue;
                }
                if (now == "/*")
                {
                    int num = 1;
                    string tmpnow = "";
                    for (int j = i + 1; s[j]; j++)
                    {
                        if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0')
                        {
                            if (tmpnow == "/*")
                                num++;
                            if (tmpnow == "*/")
                            {
                                num--;
                                if (num == 0)
                                {
                                    i = j - 1;
                                    break;
                                }
                            }
                            tmpnow = "";
                        }
                        else
                            tmpnow += s[j];
                    }
                    now = "";
                    continue;
                }
                tokens.push_back(now);
                now = "";
            }
        }
        else
            now += s[i];
    }
    int cnt = 0;
    string nowNamespace = "";
    for (int i = 1; i < (int)tokens.size(); i++)
    {
        if ((tokens[i] == "struct" || tokens[i] == "class") && tokens[i + 2] == "{")
        {
            cnt = 0;
            nowNamespace = tokens[i + 1];
            i += 2;
        }
        functions tmp(nowNamespace);
        if (tokens[i] == "{" && tokens[i - 1] == ")")
        {
            int num = 1;
            for (int j = i - 2; j >= 0; j--)
            {
                if (tokens[j] == ")")
                    num++;
                if (tokens[j] == "(")
                {
                    num--;
                    if (num == 0)
                    {
                        tmp.name = tokens[j - 1];
                        tmp.outputType = "";
                        for (int k = j - 2; k >= 0; k--)
                            if (tokens[k] != "}" && tokens[k] != "}" && tokens[k] != ";" &&
                                tokens[k].back() != ':' && tokens[k] != "inline" &&
                                tokens[k] != "static" && tokens[k][0] != '#' &&
                                tokens[k].back() != '\"' && tokens[k].back() != '>')
                                tmp.outputType = tmp.outputType == "" ? tokens[k] : tokens[k] + " " + tmp.outputType;
                            else
                                break;
                        int last = i - 2;
                        for (int k = i - 2; k >= j; k--)
                        {
                            if (tokens[k] == "(" || tokens[k] == ",")
                            {
                                string tt = "";
                                for (int t = k + 1; t < last; t++)
                                    tt = tt == "" ? tokens[t] : tt + " " + tokens[t];
                                if (tt != "")
                                    tmp.inputType.push_back(tt);
                                last = k - 1;
                            }
                            if (tokens[k] == "=" || tokens[k] == ")")
                                last = k - 1;
                        }
                        reverse(tmp.inputType.begin(), tmp.inputType.end());
                        break;
                    }
                }
            }
            funs.push_back(tmp);
            num = 1;
            for (int j = i + 1; j < (int)tokens.size(); j++)
            {
                if (tokens[j] == "{")
                    num++;
                if (tokens[j] == "}")
                {
                    num--;
                    if (num == 0)
                    {
                        i = j;
                        break;
                    }
                }
            }
            continue;
        }
        if (nowNamespace != "")
        {
            if (tokens[i] == "{")
                cnt++;
            if (tokens[i] == "}")
            {
                cnt--;
                if (!cnt)
                    nowNamespace = "";
            }
        }
    }
}
int main()
{
    char ch;
    while ((ch = getchar()) != EOF)
        source += ch;
    solve(source);
    for (auto &i : funs)
    {
        if (i.outputType != "")
            cout << i.outputType << " ";
        if (i.inClass != "")
            cout << i.inClass << "::";
        cout << i.name << "(";
        for (int j = 0; j < (int)i.inputType.size(); j++)
            cout << i.inputType[j] << (j == (int)i.inputType.size() - 1 ? ")" : ",");
        if ((int)i.inputType.size() == 0)
            cout << ")";
        cout << endl;
    }
    return 0;
}

D: 牛牛与牛妹的约会

在这里插入图片描述

输入

2
3 -1
1 2

输出

3.442249570
1.000000000

只需对于每一次枚举判断闪现是否比直接走值得就可以了，然后判断最后一次闪现过头后回头走是否比不闪现更快即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        double a,b;
        scanf("%lf%lf",&a,&b);
        if(a<0){a=-a;b=-b;}
        if(a<b)printf("%.9f\n",b-a);
        else{
            double ans=0,lstp=a;
            while(a>b&&(a-cbrt(a)>1)){ans+=1;lstp=a;a=cbrt(a);}
            ans=min(ans-1+abs(b-lstp),ans+abs(b-a));
            printf("%.9f\n",ans);
        }
    }
    return 0;
}

E: Enjoy the game

在这里插入图片描述

输入

输出

Alice

说明

先手必须拿走一张牌，然后后手拿走了另一张牌，游戏结束。

找规律可以发现，当张数是 $2^{n}$ 的时候输出 Alice，否则输出 Bob。如果不是 2^n ，先手直接拿等同于其二进制最低位的数量的张数，后手将无力还击～

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main(){
    long long t;
    cin>>t;
    if((t&(t-1))==0)cout<<"Alice";
    else cout<<"Bob";
    return 0;
}

F: 碎碎念

在这里插入图片描述

输入

输出

2
7
11

说明

第一组询问：可以是三个AC，或者一个RJ。
第二组询问：可以是1~4个AC，一个AC和一个RJ（共2种顺序），或者一个RJ。
第三组询问：可以有1~5个AC，两个AC和一个RJ（共3种顺序），一个AC和一个RJ（共2种顺序），或者一个RJ。

备注

AC RJ AC AC 和 AC AC AC RJ 虽然都是3个AC，1个RJ，但是因为提交顺序的不同，视为不同种类。

考虑动态规划，

dp [i][0] 表示一共说了 i 句话，最后的一次评测记录是 AC, 那么如果我说了 i 句话，最后一次是 AC，那么说之前一定是说了 i-1 句话，但是因为这一次是 AC，所以上一次 (i-1 句话时) 不论是 AC 还是 RJ 都可以转移到 i，即： dp [i][0]=dp [i-1][0]+dp [i-1][1]
dp [i][1] 表示一共说了 i 句话，最后的一次评测记录是 RJ, 那么如果我说了 i 句话，最后一次是 RJ，那么说之前一定是说了 i-k 句话，因为这一次是 RJ 所以上一次是 AC dp [i][1]=dp [i-k][0]
边界条件是 dp [0][0]=1,dp [0][1]=0 我们可以读入所有的 $l_{i} ， r_{i}$ 然后预处理 $0 \to m a x (r_{i})$ 的 dp 值，并计算前缀和 s，我们需要输出 $l_{i} \to r_{i}$ 直接输出 $s [r_{i}] - s [l_{i} - 1]$ 即可

#include <stdio.h>
const int N=1e5+100;
const int mod=1e9+7;

int dp[N][3];

int main(void){
    int x;
    scanf("%d",&x);
    dp[0][0]=1;
    for(int i=1;i<100100;++i){
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
        if(i>=x){
            dp[i][1]=dp[i-x][0];
        }
    }
    dp[0][2]=1;
    for(int i=1;i<100100;++i){
        dp[i][2]=(dp[i][0]+dp[i][1])%mod;
        dp[i][2]=(dp[i][2]+dp[i-1][2])%mod;
    }
    int q;
    scanf("%d",&q);
    while(q--){
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",(dp[r][2]-dp[l-1][2]+mod)%mod);
    }
    return 0;
}

G: 街机争霸

在这里插入图片描述

输入

3 3 1 3
&&A
###
&&L
2 1 RIGHT

输出

说明

如果用*代表僵尸的位置，则起始时状态为
&&A
*##
&&L
一个单位时间后，牛能上走，僵尸向右走，两者并没有碰上
&&A
#*L
&&#
再一个单位时间后，牛能向上走，追上牛牛，取得胜利。
&&L
##*
&&#

输入

4 4 1 2
L#&A
##&#
#&##
####
3 3 DOWN

输出

Oh no

说明

初始状态
L#&A
##&#
#&*#
####
一单位时间后
##&A
L#&#
#&##
##*#
二单位时间后
##&A
##&#
L&*#
####
三单位时间后
##&A
##&#
#&##
L#*#
四单位时间后
##&A
##&#
#&*#
#L##
牛能如果再向左走的话就会跟僵尸碰个正着，而且不论牛能怎么往回走，在（4,3）总能遇见僵尸，所以他失败了。

迷宫题，似乎用图论算法处理不了，于是想到 bfs，但是最毒瘤的是他可以走到他以前走过的空格... 那 BFS 是永远都走不完的！，但是我们发现这个题有一个特殊性质，僵尸的运动长度是固定的. 所以每隔 2k-2 个单位长度，僵尸的位置会重复一次，所以对于一个点，这个点在时间 t 的僵尸状态与 t+2k-2 的时候在这个点状态是重复的！！所以往回走的时候如果这个点在 t-n (2k-2) 访问过就算重复，所以不访问，否则访问。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int dx[10]={-1,0,1,0},dy[10]={0,1,0,-1};        //上右下左
int n,m,p,k,G[550][550],JS[100][3],sx,sy,ex,ey;
bool vst[550][550][120];
queue<pair<int,pair<int,int> > >q;

inline bool ok(int x,int y,int t){
    int tt=t%(2*k-2);
    // cout<<">>>>> Try "<<x<<" "<<y<<" "<<t<<endl;
    if(x<0||x>=n||y<0||y>=m||vst[x][y][tt]||G[x][y]=='&')return false;
    // cout<<">>>>> Pass 1 "<<endl;
    for(int i=0;i<p;i++){
        int pos_jsx=JS[i][0]+dx[JS[i][2]]*(tt>k-1?2*k-2-tt:tt);
        int pos_jsy=JS[i][1]+dy[JS[i][2]]*(tt>k-1?2*k-2-tt:tt);
        // cout<<"@ JS "<<i<<" jsx= "<<pos_jsx<<" jsy= "<<pos_jsy<<" xx= "<<(tt>k-1?2*k-2-tt:tt)<<endl;
        if(x==pos_jsx&&y==pos_jsy)return false;

    }
    // cout<<">>>>> Pass 2 "<<endl;
    vst[x][y][tt]=true;
    return true;
}

int bfs(int sx,int sy){
    q.push(make_pair(sx,make_pair(sy,0)));
    vst[sx][sy][0]=true;
    while(!q.empty()){
        int nx=q.front().first,ny=q.front().second.first,time=q.front().second.second;
        q.pop();
        // cout<<">>> "<<nx<<" "<<ny<<" "<<time<<endl;
        for(int i=0;i<4;i++){
            int tx=nx+dx[i],ty=ny+dy[i];
            if(tx==ex&&ty==ey)return time+1;
            if(ok(tx,ty,time+1))
                q.push(make_pair(tx,make_pair(ty,time+1)));
        }
    }
    return -1;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&p,&k);
    getchar();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%c",&G[i][j]);
            if(G[i][j]=='A'){ex=i;ey=j;}
            if(G[i][j]=='L'){sx=i;sy=j;}
        }
        getchar();
    }

    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++)
    //         cout<<G[i][j]<<" ";
    //     cout<<endl;
    // }


    for(int i=0;i<p;i++){
        char d[10];
        scanf("%d%d%s",&JS[i][0],&JS[i][1],d);
        JS[i][0]--;JS[i][1]--;
        if(d[0]=='U')JS[i][2]=0;
        else if(d[0]=='R')JS[i][2]=1;
        else if(d[0]=='D')JS[i][2]=2;
        else JS[i][2]=3;
    }

    // cout<<JS[0][2]<<"***********\n";

    int ans=bfs(sx,sy);
    if(ans==-1)cout<<"Oh no";
    else cout<<ans;
    return 0;
}

H: Hash

在这里插入图片描述

输入

abcdef 11

输出

abcdeq

实际上，可以看到这就是一个 26 进制数，但是，对于所有的排列，可以排满所有的数字吗？似乎不可以，于是最开始的思路是 dfs，但是 T 掉了但是实际上，他是可以完全覆盖所有的数字，所以直接写一个函数 26->10 进制，然后 + mod，转 26 进制

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

char s[10];
long long mod,n=0;

int main(){
    while(scanf("%s%d",s,&mod)==2){
        n=0;
        for(int i=0;i<=5;i++)n=n*26+s[i]-'a';
        n+=mod;
        for(int i=5;i>=0;i--){
            s[i]='a'+n%26;
            n/=26;
        }
        if(n)printf("-1\n");
        else printf("%s\n",s);
    }
    return 0;
}

I: I 题是个签到题

在这里插入图片描述

输入

9 100
100 100 100 100 100 100 100 100 100

输出

Yes

签到题，直接判定

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,num_i,a[50];

bool cmp(int a,int b){
    return a>b;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
    num_i=a[9];
    if(num_i>=0.8*m){cout<<"Yes";return 0;}
    sort(a+1,a+1+n,cmp);
    if(num_i>=a[3]){cout<<"Yes";return 0;}
    cout<<"No";
    return 0;
}

J: 牛牛战队的秀场

在这里插入图片描述

输入

4 1
1 2

输出

1.414214

用弧度的定义 $α = \frac{l}{r}$

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int r,n,i,j;
double pi=atan(1)*4;

int main(){
    scanf("%d%d%d%d",&n,&r,&i,&j);
    double l=2*sin(pi/n)*r;
    printf("%.6f",l*min(abs(i-j),n-abs(i-j)));
    return 0;
}