【题解】2020牛客寒假算法基础集训营第五场

A. 模板

题目看起来是编辑距离的模板题，其实就是一个很简单的题目，贪心地考虑问题。先考虑两个字符串相同的部分，显然，只要把原字符串和新字符串不同的字符修改就行了；对于两个字符串后面不同的部分，如果原字符串比较长，就全部删掉；如果原字符串比较短，就对照第二个字符串添加字符。所以，只要按照两个字符串较大的长度进行遍历，比较两个字符串不同的字符有几个就可以了。如果一个字符串比较短，那么它后面的部分可以看成\0，同样可以参与字符串比较。

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;
char str[2][MAXN];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s%s", str[0], str[1]);
    int len = max(n, m);
    int cnt = 0;
    for (int i = 0; i < len; i++)
    {
        if (str[0][i] != str[1][i])
        {
            cnt++;
        }
    }

    printf("%d\n", cnt);

    return 0;
}

B. 牛牛战队的比赛地

题目要求最大距离最小，很容易想到使用二分或者三分的方法去做。

这题使用三分会比较简单，二分会比较麻烦。

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

struct p{
    int x,y;
}a[100005];
int n;
double check(double x)
{
    double max=0;
    for (int i=1;i<=n;i++)
    {
        double tmp=sqrt(a[i].y*a[i].y+(a[i].x-x)*(a[i].x-x));
        if (tmp>max) max=tmp;
    }
    return max;
}
double tsearch(double left,double right){
    int i;
    double mid,midmid;
    for(i=0;i<100;i++){
        mid=left+(right-left)/2;
        midmid=mid+(right-mid)/2;
        if(check(mid)>check(midmid)) //极大值求法
            left=mid;
        else
            right=midmid;
    }
    return mid;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    double max=tsearch(-10000,10000);
    printf("%.4lf\n",check(max));
    return 0;
}

EX：大家可以思考一下，二分怎么做呢

C. C语言IDE

不大不小的模拟，由于题目的情况不是很多，因此只需要匹配){}的组合即可，这样的组合最外层一定是函数，通过括号匹配，里面的do for while 等均直接被匹配消除~

一开始自己还想出结构体内的，后来发现太复杂了，就出了弱化版本~

#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;
                }
                //cout << now << s[i];
                tokens.push_back(now);
                now = "";
            }
            //else cout << s[i];
        }
        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;
                        //cout << tmp.outputType << " " << tmp.name << " ";
                        //cout << j << endl;
                        break;
                    }
                }
            }
            continue;
        }
        if (nowNamespace != "")
        {
            //cout << i << " " << nowNamespace << " " << cnt << endl;
            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. 牛牛与牛妹的约会

贪心。比较直接走和闪现哪一个可以走的更快，选择更快的方法去走即可。

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const double eps = 1e-8;
int main()
{
    int T; cin>>T;
    while(T--){
        int a, b; scanf("%d%d", &a, &b);
        double ans = 0;
        double ca = a, cb = b;
        double p = 1.0/3.0;
        while(1){
            double na;
            if(ca < 0) na = -pow(-ca,p);
            else na = pow(ca, p);
            if(abs(na-cb)+1.0 < abs(ca-cb)) ans += 1.0, ca = na;
            else {
                ans += abs(ca-cb); break;
            }
        }
        printf("%.9f\n", ans);
    }
}

E. Enjoy the game

找规律可以发现，当张数是的时候输出Alice，否则输出Bob。

如果不是，先手直接拿等同于其二进制最低位的数量的张数，后手将无力还击~

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

int main()
{ 
    long long n;
    scanf("%lld", &n);
    long long tmp = 2;
    for (int i = 1; i <= 60; i++)
    {
        if (tmp == n) 
        {
            printf("Alice\n");
            return 0;
        }
        tmp = tmp * 2;
    }
    printf("Bob\n");
    return 0;
}

F. 碎碎念

考虑到了第句话时候，这种状态可能由两种状态转移而来。

1. 直接一发AC，从第句话直接到达第句。
2. 如果,可以由一发RJ从句到达第i句。 构造，表示到了第句话，是从句话AC到达的方案数。表示到了第i句话，是由句话RJ过来的方案数。 由此可知转移条件
   • （前面一发是WA是AC无关紧要）
   • () (前面一发只能是AC)

易确定边界条件 ; ;

由于有次查询 ，查询数目较多，我们可以线性时间内预处理前项和即前缀和，然后用第项减去第项即可。

#include <bits/stdc++.h>
#define MAXN 100005
const int P = 1e9+7;
using namespace std;
typedef long long ll;
int dp[MAXN][4]={0};
int l,r;
int main() {
    int q,k;

    scanf("%d%d",&k,&q);

    dp[0][0]=1;

    for(int i=1;i<MAXN;i++)
    {
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%P;
        if(i>=k)
        {
            dp[i][1]=dp[i-k][0];
        }
    }

    dp[0][3]=1;

    for(int i=1;i<MAXN;i++)
    {
        dp[i][3]=((dp[i][0]+dp[i][1])%P+dp[i][2])%P;
//        printf("%d ",dp[i][3]);
        dp[i][3]+=dp[i-1][3];
        dp[i][3]%=P;
    }

    for(int i=0;i<q;i++)
    {
        scanf("%d%d",&l,&r);
        ll ans=dp[r][3]-dp[l-1][3];
        printf("%lld\n",((ans%P+P)%P));
    }

    return 0;
}

G. 街机争霸

因为所有僵尸的行走长度是一样的，所以周期长度应该为，所以在普通的bfs基础上加上一维表示时间，从当前位置和时间去更新周围位置时间的数组，并且加入队列，直到到达终点或者队列为空，即可求出最佳答案。

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define P pair<int,int>
using namespace std;
const int maxn = 505;
int n, m, p, k;
int dstx, dsty;
char mp[maxn][maxn];
int zmb[maxn][maxn][20];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int dz[2] = {-1, 1};
int vis[maxn][maxn][20][2];
struct node{
    int x, y, z, ud;
};
queue<node> q;
void init(){
    cin>>n>>m>>p>>k;
    memset(vis, -1, sizeof vis);
    assert(n <= 500 & n >= 3 && m >= 3 && m <= 500 && p <= 50 && p >= 0 && k <= 10 && k >= 2);
    for(int i = 0; i < n; ++i) {
        scanf("%s", mp[i]);
        for(int j = 0; j < m; ++j){
            if(mp[i][j] == 'A') dstx = i, dsty = j;
            else if(mp[i][j] == 'L'){
                q.push((node){i,j,0,0}); vis[i][j][0][0] = 0;
            }
        }
    }
    for(int i = 0; i < p; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        zmb[x][y][0] = 1;
        int dst;
        char cmd[10]; scanf("%s", cmd);
        if(cmd[0] == 'U') dst = 0;
        else if(cmd[0] == 'D') dst = 1;
        else if(cmd[0] == 'L') dst = 2;
        else if(cmd[0] == 'R') dst = 3;
        for(int i = 1; i < k; ++i){
            x = x + dx[dst]; y = y + dy[dst];
            zmb[x][y][i] = 1;
        }
    }
//    for(int t = 0; t < k; ++t){
//        cout<<endl;
//        for(int i = 0; i < n; ++i){
//            for(int j = 0; j < m; ++j) cout<<zmb[i][j][t]<<" ";cout<<endl;
//        }
//    }
}
bool ok(int x, int y, int z){//board && 障碍 && zombie
    if(x < 0 || x >= n) return 0;
    if(y < 0 || y >= m) return 0;
    if(mp[x][y] == '&') return 0;
    if(zmb[x][y][z]) return 0;
    return 1;
}
void sol(){
    int ans = -1;
    while(q.size()){
        node temp = q.front(); q.pop();
        int x = temp.x, y = temp.y, z = temp.z;
        //cout<<"x:"<<x<<" y:"<<y<<" z:"<<z<<endl;
        if(x == dstx && y == dsty){
            ans = vis[x][y][z][temp.ud]; break;
        }
        int xx, yy, zz, dst = temp.ud;
        if(z == 0 || z == k-1) dst ^= 1;
        for(int i = 0; i < 4; ++i){
            xx = x + dx[i];
            yy = y + dy[i];
            zz = z + dz[dst];
            if(ok(xx, yy, zz) && vis[xx][yy][zz][dst] == -1){
                vis[xx][yy][zz][dst] = vis[x][y][z][temp.ud]+1;
                q.push((node){xx,yy,zz,dst});
            }
        }
    }
    if(ans == -1) cout<<"Oh no"<<endl;
    else cout<<ans<<endl;
}
int main()
{
    init();
    sol();
}

H. hash

观察给的哈希函数可以轻松看出，这个哈希函数就仅仅是把一个只由小写字符组成的字符串当成了一个26进制的数，不取模的情况下，任意小写字符串和自然数是一一对应的。因此，只要把给的字符串转换成对应的26进制整数，加上模数后转换回字符串，一定可以得到一个最小字典序大于原串的字符串。只要这个新字符串长度为6即是满足要求的字符串。

#include <iostream>

using namespace std;

const int LEN = 6;
int mod;

char str[15];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("hash.in", "r", stdin);
    freopen("hash.out", "w", stdout);
#endif

    while (scanf("%s%d", str, &mod) != EOF)
    {
        long long res = 0;
        for (int i = 0; i < LEN; i++)
        {
            res = res * 26 + str[i] - 'a';
        }
        res += mod;
        for (int i = LEN - 1; i >= 0; i--)
        {
            str[i] = res % 26 + 'a';
            res /= 26;
        }
        if (res)
        {
            puts("-1");
        }
        else
        {
            printf("%s\n", str);
        }

    }

    return 0;
}

I. I题是个签到题

签到题。判断是否大于等于，或者排过序以后是否大于等于即可。

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

pair<int,int> problems[15];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int curcnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int t;
        scanf("%d", &t);
        problems[i] = {i, t};
        if (i == 9) curcnt = t;
    }
    int tmp;
    if (m % 5 != 0) tmp = (int)(m * 0.8) + 1;
    else tmp = m / 5 * 4;
    sort(problems + 1, problems + n + 1, [](const pair<int, int> a, const pair<int, int> b) -> bool{
        return a.second > b.second;
    });
    if (curcnt >= tmp || curcnt >= problems[3].second) printf("Yes\n");
    else printf("No\n");
    return 0;
}

J. 牛牛战队的秀场

先求一条边的边长。如图，边形对应的，边长就是。

再求i到j最短经过几条边：

最后答案就是

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

const double PI = acos(-1);

int main()
{
    int n;
    double r;
    scanf("%d%lf", &n, &r);
    int i, j;
    scanf("%d%d", &i, &j);
    i--, j--;
    double dis = min((i - j + n) % n, (j - i + n) % n);
    double deg = PI / n;
    double len = r * sin(deg) * 2;
    printf("%lf\n", len * dis);
    return 0;
}