AtCoder Beginner Contest 184 题解

do_while_true · 2020-12-02 17:57:03 · 个人记录

\text{不一样的阅读体验}

ABC184 简要题解

A

输入 a,b,c,d，输出 a\times c - b\times d

//Code by do_while_true
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define re register
//#define int long long
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x + 1 : x; }
inline int read() {
    int r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        r = (r << 3) + (r << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? ~r + 1 : r;
}
//#undef int
int a, b, c, d;
signed main() {
    a = read(); b = read(); c = read(); d = read();
    printf("%d\n", a*d - b*c);
    return 0;
}

B

根据题意模拟，每一次读入判断要加还是减。

//Code by do_while_true
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define re register
//#define int long long
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x + 1 : x; }
inline int read() {
    int r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        r = (r << 3) + (r << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? ~r + 1 : r;
}
//#undef int
const int N = 2e5 + 10;
int n, ans;
char ch[N + 10];
signed main() {
    n = read(); ans = read();
    scanf("%s", ch + 1);
    for(int i = 1; i <= n; ++i) {
        if(ch[i] == 'o') ++ans;
        if(ch[i] == 'x' && ans) --ans;
    }
    printf("%d\n", ans);

    return 0;
}

C

分类讨论一下怎么走最优即可。

//Code by do_while_true
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define re register
//#define int long long
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x + 1 : x; }
inline int read() {
    int r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        r = (r << 3) + (r << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? ~r + 1 : r;
}
//#undef int
const int N = 2e5 + 10;
int a, b, c, d;
signed main() {
    a = read(); b = read(); c = read(); d = read();
    if(a == c && b == d) {
        puts("0");
        return 0;
    }
    if(a + b == c + d || a - b == c - d || Abs(a - c) + Abs(b - d) <= 3) {
        puts("1");
        return 0;
    }
    if(((d-c) & 1) == ((b-a) & 1)) {
        puts("2");
        return 0;
    }
    if(Abs(c + d - a - b) <= 3) {
        puts("2");
        return 0;
    }
    if(Abs(Abs(a-b) - Abs(c-d)) <= 3) {
        puts("2");
        return 0;
    }
    if(Abs(a - c) + Abs(b - d) <= 6) {
        puts("2");
        return 0;
    }
    puts("3");
    return 0;
}

下面才是正文(不会吧不会吧，不会真的有人ABC的前三题都要看题解的吗)

D

看到 100 的数据范围，考虑 n^3 的做法，显然是 dp，f_{i,j,k} 代表第一种选了 i 个，第二种选了 j 个，第三种选了 k 个的概率。

因为知道了选到 i,j,k，代价就是 (i+j+k-a-b-c)，期望就能根据概率推出来，而概率比期望更好 dp，所以选择概率作为状态。

这个时候就很好算了，显然的，可以从选第一种，选第二种，选第三种，这三种不同的选择方案转移而来，统计一下 i,j,k 其中有 100 的期望加起来即可。

转移方程见代码。

//Code by do_while_true
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define ld double
#define re register
//#define int long long
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x + 1 : x; }
inline int read() {
    int r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        r = (r << 3) + (r << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? ~r + 1 : r;
}
//#undef int
const int N = 110;
int a, b, c, d;
ld f[N][N][N], ans;
signed main() {
    a = read(); b = read(); c = read();
    for(int i = 1; i <= 100; ++i)
        for(int j = 1; j <= 100; ++j)
            for(int k = 1; k <= 100; ++k)
                f[i][j][k] = -1;
    f[a][b][c] = 1;
    for(int i = a; i <= 100; ++i)
        for(int j = b; j <= 100; ++j)
            for(int k = c; k <= 100; ++k) {
                if(i == a && j == b && k == c) continue;
                f[i][j][k] = 0;
                if(i > a && j != 100 && k != 100 && f[i-1][j][k] != -1) f[i][j][k] += f[i-1][j][k] * (i-1) / (i-1+j+k);
                if(j > b && i != 100 && k != 100 && f[i][j-1][k] != -1) f[i][j][k] += f[i][j-1][k] * (j-1) / (i+j-1+k);
                if(k > c && i != 100 && j != 100 && f[i][j][k-1] != -1) f[i][j][k] += f[i][j][k-1] * (k-1) / (i+j+k-1);
                if(i == 100 || j == 100 || k == 100) ans += (i - a + j - b + k - c) * f[i][j][k];
            }
    printf("%.6lf\n", ans);
    return 0;
}

E

直接广搜即可，有一个小优化就是每种类型的传送门只需要遍历一遍就行了，因为第一遍过后这一种的全部的传送门都会变成入过队的点。因为和这道题不一样，不是强制传送，所以每个点只入队的广搜是正确的。时间复杂度为 \mathcal{O}(HW)

//Code by do_while_true
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
#define ld double
#define re register
#define pb push_back
//#define int long long
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x + 1 : x; }
inline int read() {
    int r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        r = (r << 3) + (r << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? ~r + 1 : r;
}
//#undef int
const int N = 2010;
const int INF = 0x3f3f3f3f;
int n, m, sx, sy, f[N][N];
char ch[N][N];
bool vis[N][N];
bool viss[27];
struct Point {
    int x, y;
    Point(int xx, int yy) { x = xx; y = yy; }
};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0}; 
std::queue<Point>q;
std::vector<Point>vec[27];
signed main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            std::cin >> ch[i][j];
            if(ch[i][j] == 'S') {
                q.push(Point(i, j));
                vis[i][j] = 1;
            }
            if(ch[i][j] >= 'a' && ch[i][j] <= 'z') vec[ch[i][j]-'a'].pb(Point(i, j));
            if(ch[i][j] == 'G') {
                sx = i;
                sy = j;
            }
        }
    while(!q.empty()) {
        Point now = q.front(); q.pop();
        int x = now.x, y= now.y;
        if(f[sx][sy]) break;
        for(int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if(ch[tx][ty] == '#' || vis[tx][ty] || tx < 1 || ty < 1 || tx > n || ty > m) continue;
            q.push(Point(tx, ty));
            vis[tx][ty] = 1;
            f[tx][ty] = f[x][y] + 1;
        }
        if(ch[x][y] >= 'a' && ch[x][y] <= 'z') {
            int pos = ch[x][y] - 'a', siz = vec[pos].size();
            if(viss[pos]) continue;
            viss[pos] = 1;
            for(int i = 0; i < siz; ++i) {
                int tx = vec[pos][i].x, ty = vec[pos][i].y;
                if(!vis[tx][ty]) {
                    q.push(Point(tx, ty));
                    vis[tx][ty] = 1;
                    f[tx][ty] = f[x][y] + 1; 
                }
            }
        }
    }
    printf("%d\n", f[sx][sy] == 0 ? -1 : f[sx][sy]);
}

F

第一眼：这玩意不是NPC吗怎么可能解决。

看到 N\leq 40，哦，折半搜索啊。

把集合分成两个同等大小的集合，对其中一个集合进行爆搜/状压求出每一种子集的总和，排一下序。

对另一个集合进行爆搜/状压每一种子集的总和，在第一个集合的每一个子集的总和中二分出最优的方案，更新答案。

时间复杂度 \mathcal{O}(2^{\frac{N}{2}}\log {N})

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define re register
#define int long long
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x+1 : x; }
inline int read() {
    re int r = 0; re bool w = 0; re char ch = getchar();
    while(ch < '0' || ch > '9') w = ch == '-' ? 1 : w, ch = getchar();
    while(ch >= '0' && ch <= '9') r = (r << 3) + (r << 1) + (ch ^ 48), ch = getchar();
    return w ? ~r+1 : r;
}
#undef int
const int N = 41;
int n, cnt1, cnt2, cnt;
ll T, a[N], b[N], c[N], ans;
ll d[2100000];
signed main() {
    n = read(); T = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    cnt1 = n / 2; cnt2 = n - cnt1;
    for(int i = 1; i <= cnt1; ++i) b[i] = a[i];
    for(int i = 1; i <= cnt2; ++i) c[i] = a[n-i+1];
    for(int i = 0; i <= (1 << cnt1) - 1; ++i) {
        ++cnt;
        for(int j = 1; j <= cnt1; ++j)
            if((1 << (j-1)) & i)
                d[cnt] += b[j];
    }
    std::sort(d + 1, d + cnt + 1);
    for(int i = 0; i <= (1 << cnt2) - 1; ++i) {
        ll now = 0;
        for(int j = 1; j <= cnt2; ++j)  
            if((1 << (j-1)) & i)
                now += c[j];
        if(now > T) continue;
        int pos = std::upper_bound(d + 1, d + cnt + 1, T - now) - d;
        --pos;
        ans = Max(ans, now + d[pos]);
    }
    printf("%lld\n", ans);
}