2019.8.5 集训解题报告

2019 年 8 月 5 日 星期一
/ , , , , ,
7

2019.8.5 集训解题报告

考的不好没关系，明天还可以继续考不好。

考试

输油管道

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

我错的细节是：

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

然后 66.7 分 qwq

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

Test′sTest's CodeCode：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;
}
FixedFixed CodeCode：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≤n≤1000012 \leq n \leq 10000 ，很显然，不能把每一个数的位置都一起更新，不然光空间都已经爆掉了。但是需要得到的答案 1≤k≤10001\leq k \leq 1000 。所以，追踪需要的数字即可。

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

Test′sTest's CodeCode：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;
}
FixedFixed CodeCode：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≤H≤1091\leq H \leq 10^9），这种 O(n)O(n) 都跑不过的数据，肯定是有循环或者是公式之类的。

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

FixedFixed CodeCode：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. 平衡树 SplaySplay ？？

平衡树牛逼！

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

FixedFixed CodeCode：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;
}

总结

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

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...