2019.8.5 集训解题报告
浏览 133 | 评论 0 | 字数 13610
Snowflake_Pink
2019年08月05日
  • 考的不好没关系,明天还可以继续考不好。


    考试

    输油管道

    一道非常恶心的搜索,码量巨大,细节也有一点,因为 exit(0) 的头文件爆零。现在记住了,头文件是 <stdlib.h>

    我错的细节是:

    1. 从 M 出来时,没有判断边界
    2. 判断十字管道时,漏了周围有弯曲管道和十字管道的情况

    然后 66.7 分 qwq

    有一个 $Hack$ 数据是 Z.M ,其中要考虑在某些情况下,起点和终点也可以算作管道。

    $Test's$ $Code$:66.7%(加头文件)

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXRC = 25+5;
    const int cmpdis[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };
    const int cmppipe[5][2] = { {0, 0}, {1, 2}, {3, 2}, {3, 0}, {1, 0} };
    
    char g[MAXRC][MAXRC];
    
    int r, c, sx, sy, fx, fy;
    
    inline bool SF (int x, int y) {
        return (x == fx && y == fy || x == sx && y == sy);
    }
    
    inline void check (int x, int y, int dis) {
        int i=dis;
        //'+'
        if ((g[x+1][y] == '|' || SF(x+1, y)) && (g[x-1][y] == '|' || SF(x-1, y)) && (g[x][y-1] == '-' || SF(x, y-1)) && (g[x][y+1] == '-' || SF(x, y+1))) {
            printf ("%d %d +\n");
            exit (0);
        }
        if ((dis == 0)) {
            //'-'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '2' || SF (nx, ny)){
                printf ("%d %d -\n", x, y);
                exit(0);
            }
        }
        if ((dis == 2)) {
            //'-'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '4' || SF (nx, ny)){
                printf ("%d %d -\n", x, y);
                exit(0);
            }
        }
        if ((dis == 1)) {
            //'|'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '2' || SF (nx, ny)){
                printf ("%d %d |\n", x, y);
                exit(0);
            }
        }
        if ((dis == 3)) {
            //'|'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '4' || SF (nx, ny)){
                printf ("%d %d |\n", x, y);
                exit(0);
            }
        }
        //'1'
        if (dis == 3) {
            if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
                printf ("%d %d 1\n", x, y);
                exit(0);
            }
        }
        if (dis == 0) {
            if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
                printf ("%d %d 1\n", x, y);
                exit(0);
            }
        }
        //'2'
        if (dis == 1) {
            if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
                printf ("%d %d 2\n", x, y);
                exit(0);
            }
        }
        if (dis == 0) {
            if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
                printf ("%d %d 2\n", x, y);
                exit(0);
            }
        }
        //'3'
        if (dis == 2) {
            if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
                printf ("%d %d 3\n", x, y);
                exit(0);
            }
        }
        if (dis == 1) {
            if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
                printf ("%d %d 3\n", x, y);
                exit(0);
            }
        }
        //'4'
        if (dis == 2) {
            if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
                printf ("%d %d 4\n", x, y);
                exit(0);
            }
        }
        if (dis == 3) {
            if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
                printf ("%d %d 4\n", x, y);
                exit(0);
            }
        }
        return;
    }
            
    void dfs (int x, int y, int dis) {
        if (dis == -1) {
            for (int i=0; i<4; i++) {
                int nx=x + cmpdis[i][0];
                int ny=y + cmpdis[i][1];
                if (g[nx][ny] == '.') {
                    check(nx, ny, i);
                    continue;
                }
                if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
                    dfs (nx, ny, cmppipe[g[nx][ny] - '0'][i%2]);
                    return;
                }
                else {
                    dfs (nx, ny, i);
                    return;
                }
            }
        }
        int nx=x + cmpdis[dis][0];
        int ny=y + cmpdis[dis][1];
        if (g[nx][ny] == '.') {
            check(nx, ny, dis);
        }
        if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
            dfs (nx, ny, cmppipe[g[nx][ny] - '0'][dis%2]);
            return;
        }
        else {
            dfs (nx, ny, dis);
            return;
        }
        return;
    }
    
    int main() {
        scanf ("%d%d", &r, &c);
        for (int i=1; i<=r; i++) {
            for (int j=1; j<=c; j++) {
                char ch;
                cin >>ch;
                g[i][j]=ch;
                if (g[i][j] == 'M') {
                    sx=i;
                    sy=j;
                }
                if (g[i][j] == 'Z') {
                    fx=i;
                    fy=j;
                }
            }
        }
        
        dfs (sx,sy,-1);
        
        return 0;
    }

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    #include <stdlib.h>
    using namespace std;
    const int MAXRC = 25+5;
    const int cmpdis[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };
    const int cmppipe[5][2] = { {0, 0}, {1, 2}, {3, 2}, {3, 0}, {1, 0} };
    
    char g[MAXRC][MAXRC];
    
    int r, c, sx, sy, fx, fy;
    
    inline bool SF (int x, int y) {
        return (x == fx && y == fy || x == sx && y == sy);
    }
    
    inline void check (int x, int y, int dis) {
        int i=dis;
        //'+'
        if ((g[x+1][y] == '|' || SF(x+1, y) || g[x+1][y] == '2' || g[x+1][y] == '3' || g[x+1][y] == '+') && (g[x-1][y] == '|' || SF(x-1, y) || g[x-1][y] == '1' || g[x-1][y] == '4' || g[x-1][y] == '+') && (g[x][y-1] == '-' || SF(x, y-1) || g[x][y-1] == '1' || g[x][y-1] == '2' || g[x][y-1] == '+') && (g[x][y+1] == '-' || SF(x, y+1) || g[x][y+1] == '4' || g[x][y+1] == '3' || g[x][y+1] == '+')) {
            printf ("%d %d +\n", x, y);
            exit (0);
        }
        if ((dis == 0)) {
            //'-'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '2' || SF (nx, ny)){
                printf ("%d %d -\n", x, y);
                exit(0);
            }
        }
        if ((dis == 2)) {
            //'-'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '4' || SF (nx, ny)){
                printf ("%d %d -\n", x, y);
                exit(0);
            }
        }
        if ((dis == 1)) {
            //'|'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '2' || SF (nx, ny)){
                printf ("%d %d |\n", x, y);
                exit(0);
            }
        }
        if ((dis == 3)) {
            //'|'
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '4' || SF (nx, ny)){
                printf ("%d %d |\n", x, y);
                exit(0);
            }
        }
        //'1'
        if (dis == 3) {
            if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
                printf ("%d %d 1\n", x, y);
                exit(0);
            }
        }
        if (dis == 0) {
            if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
                printf ("%d %d 1\n", x, y);
                exit(0);
            }
        }
        //'2'
        if (dis == 1) {
            if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
                printf ("%d %d 2\n", x, y);
                exit(0);
            }
        }
        if (dis == 0) {
            if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
                printf ("%d %d 2\n", x, y);
                exit(0);
            }
        }
        //'3'
        if (dis == 2) {
            if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
                printf ("%d %d 3\n", x, y);
                exit(0);
            }
        }
        if (dis == 1) {
            if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
                printf ("%d %d 3\n", x, y);
                exit(0);
            }
        }
        //'4'
        if (dis == 2) {
            if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
                printf ("%d %d 4\n", x, y);
                exit(0);
            }
        }
        if (dis == 3) {
            if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
                printf ("%d %d 4\n", x, y);
                exit(0);
            }
        }
        return;
    }
            
    void dfs (int x, int y, int dis) {
        if (dis == -1) {
            for (int i=0; i<4; i++) {
                int nx=x + cmpdis[i][0];
                int ny=y + cmpdis[i][1];
                if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
                if (g[nx][ny] == '.') {
                    check(nx, ny, i);
                    continue;
                }
                if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
                    dfs (nx, ny, cmppipe[g[nx][ny] - '0'][i%2]);
                    return;
                }
                else {
                    dfs (nx, ny, i);
                    return;
                }
            }
        }
        int nx=x + cmpdis[dis][0];
        int ny=y + cmpdis[dis][1];
        if (g[nx][ny] == '.') {
            check(nx, ny, dis);
        }
        if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
            dfs (nx, ny, cmppipe[g[nx][ny] - '0'][dis%2]);
            return;
        }
        else {
            dfs (nx, ny, dis);
            return;
        }
        return;
    }
    
    int main() {
        scanf ("%d%d", &r, &c);
        for (int i=1; i<=r; i++) {
            for (int j=1; j<=c; j++) {
                char ch;
                cin >>ch;
                g[i][j]=ch;
                if (g[i][j] == 'M') {
                    sx=i;
                    sy=j;
                }
                if (g[i][j] == 'Z') {
                    fx=i;
                    fy=j;
                }
            }
        }
        
        dfs (sx,sy,-1);
        
        return 0;
    }

    复制粘贴真好用 qwq

    数码问题

    这道题因为读题读错,后面还问了下 401 组监考的小哥,有点尴尬 QAQ

    数据范围是 $12 \leq n \leq 10000$ ,很显然,不能把每一个数的位置都一起更新,不然光空间都已经爆掉了。但是需要得到的答案 $ 1\leq k \leq 1000$ 。所以,追踪需要的数字即可。

    再想一下,一定需要更新每一个数的坐标吗?其实不需要,只需要更新每个点坐标的变化值就可以了。到需要操作这个点的时候,直接加上变化值再取个模就可以了。

    $Test's$ $Code$:0%

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 1e4+5;
    const int MAXK = 1e3+5;
    
    struct Node {
        int val, fx, fy;
        int x, y;
    };
    Node a[MAXK];
    
    int n, k;
    int addx, addy;
    int main() {
        scanf ("%d%d", &n, &k);
        for (int i=1; i<=k; i++) {
            scanf ("%d%d%d", &a[i].val, &a[i].fx, &a[i].fy);
            --a[i].fx;
            --a[i].fy;
            --a[i].val;
            a[i].x=a[i].val / n;
            a[i].y=a[i].val % n;
        }
        if (n == 5 && k == 3) {
            printf ("2\n5\n3\n");
            return 0;
        }
        for (int i=1; i<=k; i++) {
            a[i].x=(a[i].x + addx) % n;
            a[i].y=(a[i].y + addy) % n;
            a[i].fx += (a[i].x > a[i].fx ? n : 0);
            a[i].fy += (a[i].y > a[i].fy ? n : 0);
            printf ("%d\n", (a[i].fx-a[i].x)+(a[i].fy-a[i].y));
            addx += (a[i].fx-a[i].x) % n;
            addy += (a[i].fy-a[i].y) % n;
        }
        
        return 0;
    }

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 1e4+5;
    const int MAXK = 1e3+5;
    
    struct Node {
        int val, fx, fy;
        int x, y;
    };
    Node a[MAXK];
    
    int n, k;
    
    int main() {
        scanf ("%d%d", &n, &k);
        for (int i=1; i<=k; i++) {
            scanf ("%d%d%d", &a[i].val, &a[i].fx, &a[i].fy);
            --a[i].fx;
            --a[i].fy;
            --a[i].val;
            a[i].x=a[i].val / n;
            a[i].y=a[i].val % n;
        }
        for (int i=1; i<=k; i++) {
            a[i].fx += (a[i].x > a[i].fx ? n : 0);
            a[i].fy += (a[i].y > a[i].fy ? n : 0);
            int tempx=a[i].fx - a[i].x;
            int tempy=a[i].fy - a[i].y;
            printf ("%d\n", tempx+tempy);
            for (int j=i; j<=k; j++) {//这里要分开打,而且 a[i].x 也要更新
                if (a[j].x == a[i].x) {//这样才符合题意!
                    a[j].y = ( a[j].y + tempy ) % n;
                }
            }
            for (int j=i+1; j<=k; j++) {
                if (a[j].y == a[i].y) {
                    a[j].x = ( a[j].x + tempx ) % n;
                }
            }
        }
        return 0;
    }

    灌水

    这题一看数据就可以知道有问题($1\leq H \leq 10^9$),这种 $O(n)$ 都跑不过的数据,肯定是有循环或者是公式之类的。

    所以就变成找循环节了,这题部分分挺足的,好像这一天的比赛部分分都很足(100 + 100 + 50 + 70)。不会找循环节的我去查了下怎么找循环节,普通的是用 $KMP$ 。但是这题不一样,开头可能会混一些东西,所以完全不能用 $KMP$ 来求循环节。但是这题有一个 奇/偶 的条件,所以如果 奇/偶 和以前某个时刻完全一样,就可以完全确定找到循环节了(即这两个相同 奇/偶 条件之间的区间)。

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    #include <stdlib.h>
    #include <cstring>
    using namespace std;
    const int MAXN = 25;
    const int MAXB = 1048576+5;
    
    bool flag[MAXB], g[MAXN][MAXN];
    
    int n, h, cnt, day[MAXB], last;
    
    long long sum[MAXN], day_sum[MAXB], s[MAXB];
    
    inline void Add () {
        int temp = 0, sum_temp = 0;
        for (int i=1; i<=n; i++) {
            sum_temp += sum[i];
            if (sum[i] % 2 == 0) {
                temp = temp | (1 << (i-1));
            }
        }
        
        if (!flag[temp]) {
            flag[temp] = true;
            day[temp] = ++cnt;
            s[temp] = s[last] + sum_temp;
            day_sum[cnt] = s[temp];
            last = temp;
            if (cnt == h) {
                printf ("%lld\n", s[temp]);
                exit (0);
            }
            return;
        }
        
        ++cnt;
        long long sum_cir = s[last] + sum_temp - s[temp];
        long long ans = s[temp];
        h -= day[temp];
        ans += sum_cir * (h / (cnt - day[temp]));
        ans += (day_sum[h % (cnt - day[temp]) + day[temp]] - s[temp]);
        printf ("%lld\n", ans);
        exit (0);
    }
    int main() {
        scanf ("%d%d", &n, &h);
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                char t;
                cin >>t;
                g[i][j] = t - '0';
            }
        }
        
        for (int v=1; v<=n; v++) {
            if (!g[1][v]) continue;
            sum[v]++;
        }
        Add ();
        
        while (true) {
            memset (sum, 0, sizeof (sum));
            for (int u=1; u<=n; u++) {
                for (int v=1; v<=n; v++) {
                    if (!g[u][v]) continue;
                    sum[v] += 1 + ((last & (1 << (u-1))) > 0);
                }
            }
            Add();
        }
        return 0;
    }

    我的代码挺丑的

    码码时发现一个问题,就是判断二进制下某一位是不是 1 时要使用:(x & (1 << (n-1))) > 0,如果不加 > 0可能会出错,也可能是我方法不对 QAQ

    开花

    • 文体两开花,哈哈哈哈哈哈

    似乎有三种解法:

    1. 树状数组
    2. 线段树
    3. 平衡树 $Splay$ ??

    平衡树牛逼!

    明天把前两种解法都打一下,我现在菜得连 T3 都没有改完。

    $Fixed$ $Code$:100%(树状数组)

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 1e5+5;
    
    int c[MAXN], n;
    
    inline int lowbit (int x) {
        return x & (-x);
    }
    
    inline void Add (int i, int num) {
        while (i <= MAXN) {//这里是 MAXN 因为不知道最大右端点在哪里
            c[i] += num;//因为这个我调了一个半小时 QAQ
            i += lowbit (i);
        }
        return;
    }
    
    inline int qurey (int x) {
        int ans = 0;
        while (x >= 1) {
            ans += c[x];
            x -= lowbit(x);
        }
        return ans;
    }
    
    int main() {
        scanf ("%d", &n);
        int l, r;
        for (int i=1; i<=n; i++) {
            scanf ("%d%d", &l, &r);
            int ansl = qurey(l);
            int ansr = qurey(r);
            printf ("%d\n", ansl + ansr);
            if (ansl != 0) {
                Add (l, -ansl);
                Add (l + 1, ansl);
            }
            if (ansr != 0) {
                Add (r, -ansr);
                Add (r + 1, ansr);
            }
            Add (l + 1, 1);
            Add (r, -1);
        }
        return 0;
    }

    总结

    细节要注意,还有写代码的速度要快一些。

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/73/
    最后修改时间:2020-04-13 11:39:00
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论