Atcoder Beginner Contest 289

Contest Result

做出了 \(\texttt{A} \sim \texttt{F}\)，\(\texttt{G}\) 题有点思路，但时间不够了。

\(\texttt{E}\) 题状态设计太慢，复杂度其实也没算明白，\(\texttt{F}\) 题大思路来的很快，但被 \(a=b \and c=d\) 的 Corner Case 创飞了。

Solution

A flip

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

char s[1000000];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 1; i <= n; i++) {
        if(s[i] == '0') putchar('1');
        else putchar('0');
    }
}

B V

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

const int MAXN = 100 + 7;

int N, M;
int a[MAXN];

vector <int> vec[MAXN];
int vis[MAXN];
int cnt;

void work(int x) {
    queue <int> Q;
    Q.push(x);
    vis[x] = x;
    while(Q.size()) {
        int y = Q.front();
        for(auto to : vec[y]) {
            if(vis[to]) continue;
            vis[to] = x;
            Q.push(to);
        }
        Q.pop();
    }
}
int main() {
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> a[i];
        vec[a[i]].push_back(a[i] + 1);
        vec[a[i] + 1].push_back(a[i]);
    }
    for(int i = 1; i <= N; i++) {
        if(vis[i]) continue;
        work(i);
        for(int j = N; j >= 1; j--) {
            if(vis[j] != i) continue;
            ++cnt;
            printf("%d%c", j, " \n"[cnt == N]);
        }
    }
}

C Coverage

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

int N, M;
int a[20];

int main() {
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int K; cin >> K;
        for(int j = 1; j <= K; j++) {
            int x; cin >> x;
            a[i] |= (1 << (x - 1));
        }
    }
    int ans = 0;
    for(int p = 0; p < (1 << M); p++) {
        int status = 0;
        for(int i = 1; i <= M; i++) {
            if(((p >> (i - 1)) & 1) == 0) continue;
            status |= a[i];
        }
        if(status == ((1 << N) - 1)) ++ans;
    }
    cout << ans << endl;
}

D Step Up Robot

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

const int MAXW = 100000 + 7;

bool trap[MAXW], f[MAXW];
int N, M, a[20], K;

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> a[i];
    cin >> M;
    for(int i = 1, x; i <= M; i++) {
        cin >> x;
        trap[x] = true;
    }
    f[0] = true;
    cin >> K;
    for(int i = 1; i <= K; i++) {
        for(int j = 1; j <= N; j++) {
            if(a[j] > i) continue;
            f[i] |= f[i - a[j]];
        }
        if(trap[i]) f[i] = false;
    }
    if(f[K]) puts("Yes");
    else puts("No");
    return 0;
}

E Swap Places

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

int T;
const int MAXN = 2000 + 7;
const int INF = 0x3f3f3f3f;
vector <int> vec[MAXN];
int N, M;
int f[MAXN][MAXN], c[MAXN];

void Reset(void) {
    for(int i = 1; i <= N; i++) {
        vec[i].clear();
    }
}

void Init(void) {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) f[i][j] = INF;
    }
    for(int i = 1; i <= N; i++) {
        scanf("%d", &c[i]);
    }
    for(int i = 1, x, y; i <= M; i++) {
        scanf("%d%d", &x, &y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
}

void Work(void) {
    f[1][N] = 0;
    queue < pair<int, int> > Q;
    Q.push(make_pair(1, N));
    while(Q.size()) {
        int x = Q.front().first, y = Q.front().second;
        Q.pop();
        // if(x == N && y == 1) break;
        for(auto tox : vec[x]) {
            for(auto toy : vec[y]) {
                if(c[tox] == c[toy]) continue;
                if(f[tox][toy] != INF) continue;
                f[tox][toy] = f[x][y] + 1;
                Q.push(make_pair(tox, toy));
                // if(tox == N && toy == 1) break;
            }
        }
        if(f[N][1] != INF) break;
    }
    if(f[N][1] == INF) puts("-1");
    else printf("%d\n", f[N][1]);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        Reset();
        Init();
        Work();
    }
}

F Teleporter Takahashi

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

int sx, sy, tx, ty, a, b, c, d;

void ot(void) {

}

vector <int> xx, yy;

int main() {
    cin >> sx >> sy >> tx >> ty >> a >> b >> c >> d;
    // if(a == b || c == d) {
    //     ot();
    //     // return 0;
    // }
    int dx = tx - sx, dy = ty - sy;
    int mx = sx + tx, my = sy + ty;
    if(dx % 2 != 0 || dy % 2 != 0) {
        puts("No"); return 0;
    }

    if(a == b && c == d) {
        if(mx / 2 == a && my / 2 == c) {
            puts("Yes");
            printf("%d %d\n", a, c);
        }
        else puts("No");
        return 0;
    }
    //2x - sx, 2y - sy  odd & even not change
    if(dx != 0 && a == b) {
        if((sx + tx) / 2 != a) {
            puts("No"); return 0;
        }
        xx.push_back(a);
        yy.push_back(c);
        sx = 2 * a - sx, sy = 2 * c - sy;
        dx = tx - sx, dy = ty - sy;
    }
    if(dy != 0 && c == d) {
        if((sy + ty) / 2 != c) {
            puts("No"); return 0;
        }
        xx.push_back(a);
        yy.push_back(c);
        sx = 2 * a - sx, sy = 2 * c - sy;
        dx = tx - sx, dy = ty - sy;
    }
    puts("Yes");
    for(int i = 0; i < (int)xx.size(); i++) {
        printf("%d %d\n", xx[i], yy[i]);
    }
    if(dx > 0) {
        while(dx > 0) {
            printf("%d %d\n%d %d\n", a, c, a + 1, c);
            dx -= 2;
        }
    }
    else {
        while(dx < 0) {
            printf("%d %d\n%d %d\n", b, c, b - 1, c);
            dx += 2;
        }
    }
    if(dy > 0) {
        while(dy > 0) {
            printf("%d %d\n%d %d\n", a, c, a, c + 1);
            dy -= 2;
        }
    }
    else {
        while(dy < 0) {
            printf("%d %d\n%d %d\n", a, d, a, d - 1);
            dy += 2;
        }
    }
    return 0;
}