2019/11/27 2019zzuli进阶组plus3题解

xqm的魔法棒

  • 题目链接
  • 题解：对于x > 3的所有情况，我们可以不断让它*3/2来使它变大，然后通过-1操作微调即可。对于x == 1，仅当y == 1时可将x变成y（不进行任何操作），其他情况均不可将x变为y。对于x == 2或x == 3，则可以变换成1、2或3，但对于大于3的y则无能为力。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #include<stdio.h>

    int main(){
        int t;
        scanf("%d", &t);
        while(t--){
            int x, y;
            scanf("%d%d", &x, &y);
            if(x == 1)
                printf("%s\n", y == 1 ? "YES" : "NO");
            else if(x == 2 || x == 3)
                printf("%s\n", y <= 3 ? "YES" : "NO");
            else
                printf("YES\n");
        }
        return 0;
    }

hw的支配子串

  • 题目链接
  • 题解：读题发现该题需要找的是最近的两个相同元素的距离，我们使用一个pre数组来记录元素上一次出现的位置，等到该元素再一次出现时维护一个最短的距离即可，若没有相同的元素，那么答案就是-1。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #include<stdio.h>
    #include<string.h>
    #define N 200100
    const int inf = 0x3f3f3f3f;

    int min(int a, int b){
        if(a < b)
            return a;
        return b;
    }

    int main(){
        int t;
        scanf("%d", &t);
        while(t--){
            int n, pre[N];//pre数组保存元素上一次出现的位置，-1代表未出现过
            int ans = inf;
            scanf("%d", &n);
            memset(pre, -1, sizeof(int) * (n+10));
            for(int i = 0; i < n; i++){
                int cas;
                scanf("%d", &cas);
                if(pre[cas] != -1)//若该元素出现过
                    ans = min(ans, i-pre[cas]+1);//更新最近距离
                pre[cas] = i;
            }
            printf("%d\n", ans == inf ? -1 : ans);
        }
        return 0;
    }

wjp的电子邮件

  • 题目链接
  • 题解：判断能否在满足条件的情况下遍历完字符串s，若中间跳出，说明未满足条件。注意处理好许多s中有许多连续相同字符时的情况。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include<stdio.h>
    #include<string.h>
    #define N 1000100

    int main(){
        int t;
        scanf("%d", &t);
        while(t--){
            char s[N], t[N];
            scanf(" %s %s", s, t);
            int n = strlen(s);//获得s的长度
            int m = strlen(t);//获得t的长度
            int cnt = 0;//记录s的下标
            int flag = 1;//标记变量
            for(int i = 0; i < m; i++){
                if(t[i] == s[cnt])//若当前位置的s与t相同，则s跳到下一个位置
                    cnt++;
                else{
                    if(cnt == 0){//如果开头便不相等则直接退出
                        flag = 0;
                        break;
                    }
                    else{
                        //因为可能跳过了许多连续相同的s
                        if(t[i] != s[cnt-1]){
                            flag = 0;
                            break;
                        }
                    }
                }
            }
            if(cnt == n && flag)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

hrs的宇宙飞船

  • 题目链接
  • 题解：题目数据范围小，暴力判断每个单元格能否按照行放置飞船或是按照列放置飞船，考虑要不重不漏，详见代码。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    #include<stdio.h>
    #include<string.h>
    #define N 110

    int n, k;
    char mp[N][N];
    int ans[N][N];

    void judge_row(int x, int y){//判断行能否容纳飞船
        for(int i = x; i < x+k && i < n; i++){
            if(mp[i][y] != '.')
                break;
            if(i == x+k-1)
                change_row(x, y);
        }
    }
    void judge_col(int x, int y){//判断列能否容纳飞船
        for(int j = y; j < y+k && j < n; j++){
            if(mp[x][j] != '.')
                break;
            if(j == y+k-1)
                change_col(x, y);
        }
    }
    void change_row(int x, int y){//修改行
        for(int i = x; i < x+k; i++)
            ans[i][y]++;
    }
    void change_col(int x, int y){//修改列
        for(int j = y; j < y+k; j++)
            ans[x][j]++;
    }

    int main(){
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; i++)
            scanf(" %s", mp[i]);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(mp[i][j] == '.'){
                    judge_row(i, j);//判断按行放置能否容纳
                    judge_col(i, j);//判断按列放置能否容纳
                }
        int x = 0, y = 0;//找最大容纳单元格
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(ans[i][j] > ans[x][y]){
                    x = i;
                    y = j;
                }
        printf("%d %d\n", x+1, y+1);
        return 0;
    }

lgc的公交车问题

  • 题目链接
  • 题解：真·签到题，模拟即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include<stdio.h>

    int main(){
        int n;
        scanf("%d", &n);
        int ans = 0, cnt = 0;
        while(n--){
            int a, b;
            scanf("%d%d", &a, &b);
            cnt += b-a;
            if(cnt > ans)
                ans = cnt;
        }
        printf("%d\n", ans);
        return 0;
    }

Kagarise的作业危机

  • 题目链接
  • 题解：本题有多种解法，在此只给出其中一种。为了满足总差异大于等于N，那么每个位置提供1的差异度即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include<stdio.h>

    int main(){
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            int cas;
            scanf("%d", &cas);
            printf("%d%c", n-cas+1, i == n-1 ? '\n' : ' ');
        }
        return 0;
    }