Skip to content

2019-2020 ACM-ICPC Brazil Subregional Programming Contest

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K L M
11/13 O O - O - O O O O O O O O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

A.Artwork

Solved By Hsueh- & ltslts. 0:33(+)

题意：

一个 n \cdot m 的矩阵有 n 个半径为 R_i 的传感器，问能否从 (0,0) 走到 (n,m) 不碰到任何传感器。

思路：

并查集，将 n 个圆并起来，判断左上区域能否与右下区域连通。

Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

struct node {
    int x, y, r;

    void input() {
        scanf("%d %d %d", &x, &y, &r);
    }
} a[N];

int n, m, k;
int fa[N], sze[N];

int find(int x) {
    return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        if (sze[x] > sze[y])
            swap(x, y);
        fa[x] = y;
        sze[y] += sze[x];
    }
}

int sqr(int x) {
    return x * x;
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= k; ++i) {
        a[i].input();
    }
    for (int i = 1; i <= k + 2; ++i) {
        fa[i] = i, sze[i] = 1;
    }
    for (int i = 1; i <= k; ++i) {
        if (a[i].x + a[i].r >= n || a[i].y <= a[i].r)
            merge(i, k + 1);
        if (a[i].x <= a[i].r || a[i].y + a[i].r >= m)
            merge(i, k + 2);
    }
    for (int i = 1; i <= k; ++i) {
        for (int j = 1; j < i; ++j) {
            if (sqr(a[i].x - a[j].x) + sqr(a[i].y - a[j].y) <= sqr(a[i].r + a[j].r)) {
                merge(i, j);
            }
        }
    }
    puts(find(k + 1) == find(k + 2) ? "N" : "S");
    return 0;
}

B.Buffoon

Solved By Dup4. 0:07(+)

签到。

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

const int N = 1e4 + 10;
int n, a[N];

int main() {
    scanf("%d", &n);
    int Max = -1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        Max = max(Max, a[i]);
    }
    puts((a[1] == Max) ? "S" : "N");
    return 0;
}

C.Crossings With Danger

Solved By . 0:00(+)

题意：

思路：

D.Denouncing Mafia

Solved By Dup4 & Hsueh-. 1:39(+1)

题意：

给出一棵树，每次选择一个点，将该点到根的所有点都染色，现在可以选择 k 个点进行染色操作，问最多能染多少个点？

思路：

长链剖分，将每条链剖分出来，然后贪心取K条。

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

const int N = 1e5 + 10;
int n, K;
vector<vector<int>> G;

int fa[N], md[N], hson[N], deep[N], use[N];

void dfs(int u) {
    hson[u] = 0;
    for (auto &v : G[u]) {
        deep[v] = deep[u] + 1;
        dfs(v);
        if (!hson[u] || md[v] > md[hson[u]])
            hson[u] = v;
    }
    md[u] = md[hson[u]] + 1;
}

int main() {
    scanf("%d%d", &n, &K);
    G.resize(n + 1);
    fa[1] = 1;
    deep[1] = 0;
    for (int i = 2; i <= n; ++i) {
        scanf("%d", fa + i);
        G[fa[i]].push_back(i);
    }
    int cnt = 0;
    for (int i = 2; i <= n; ++i)
        if (G[i].empty()) {
            ++cnt;
        }
    if (K >= cnt) {
        printf("%d\n", n);
    } else {
        dfs(1);
        vector<int> vec;
        for (int i = 1; i <= n; ++i)
            if (hson[i])
                use[hson[i]] = 1;
        for (int i = 1; i <= n; ++i)
            if (use[i] == 0) {
                vec.push_back(md[i]);
            }
        sort(vec.begin(), vec.end(), [&](int x, int y) {
            return x > y;
        });
        int sum = 0;
        for (int i = 0; i < K; ++i) sum += vec[i];
        printf("%d\n", sum);
    }
    return 0;
}

E.Exhibition of Clownfish

Solved By . 0:00(+)

题意：

思路：

F.Forests in Danger

Solved By Dup4 & ltslts. 4:18(+)

题意：

给出若干条平行于坐标轴的线段和一个四条边都平行于坐标轴的矩形，然后给出一个 P，现在要选定一个最小的 r，对于每条线段找一个矩形覆盖它，并且保证矩形外的点到这条线段的最短距离为 r,要满足这些矩形的面积并和题目给定矩形的面积并大于等于题目给定矩形的面积的 $P % $。

思路：

二分r，然后就是求矩形面积并。

Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int n, rate;

struct P {
    int x, y;
    void scan() {
        scanf("%d%d", &x, &y);
    }
};

struct node {
    P s, e;
    void scan() {
        s.scan();
        e.scan();
    }
};

node li[N];
node Tri;

struct Hash {
    int a[N], tot;
    void init() {
        tot = 0;
        a[0] = 0;
    }
    void add(int x) {
        a[++tot] = x;
    }
    void gao() {
        sort(a + 1, a + 1 + tot);
        tot = unique(a + 1, a + 1 + tot) - a - 1;
    }
    int get(int x) {
        return lower_bound(a + 1, a + 1 + tot, x) - a;
    }
} hx, hy;

struct SEG {
    struct node {
        int cnt, len;
        void init() {
            cnt = len = 0;
        }
    } t[N << 2];
    void build(int id, int l, int r) {
        t[id].init();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void up(int id, int l, int r) {
        if (t[id].cnt > 0) {
            t[id].len = hy.a[r] - hy.a[l - 1];
        } else {
            if (l == r)
                t[id].len = 0;
            else {
                t[id].len = t[id << 1].len + t[id << 1 | 1].len;
            }
        }
    }
    void update(int id, int l, int r, int ql, int qr, int v) {
        if (ql > qr)
            return;
        if (l >= ql && r <= qr) {
            t[id].cnt += v;
            up(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid)
            update(id << 1, l, mid, ql, qr, v);
        if (qr > mid)
            update(id << 1 | 1, mid + 1, r, ql, qr, v);
        up(id, l, r);
    }
} seg;

node rec[N];
vector<vector<P>> add, del;

ll calc(int r) {
    hx.init();
    hy.init();
    for (int i = 1; i <= n; ++i) {
        node tmp;
        tmp.s.x = min(li[i].s.x, li[i].e.x) - r;
        tmp.s.x = max(tmp.s.x, Tri.s.x);
        tmp.s.y = min(li[i].s.y, li[i].e.y) - r;
        tmp.s.y = max(tmp.s.y, Tri.s.y);
        tmp.e.x = max(li[i].s.x, li[i].e.x) + r;
        tmp.e.x = min(tmp.e.x, Tri.e.x);
        tmp.e.y = max(li[i].s.y, li[i].e.y) + r;
        tmp.e.y = min(tmp.e.y, Tri.e.y);
        rec[i] = tmp;
        hx.add(tmp.s.x);
        hx.add(tmp.e.x);
        hy.add(tmp.s.y);
        hy.add(tmp.e.y);
    }
    hx.gao();
    hy.gao();
    for (int i = 1; i <= n; ++i) {
        rec[i].s.x = hx.get(rec[i].s.x);
        rec[i].e.x = hx.get(rec[i].e.x);
        rec[i].s.y = hy.get(rec[i].s.y);
        rec[i].e.y = hy.get(rec[i].e.y);
    }
    int cx = hx.tot, cy = hy.tot;
    add.clear();
    add.resize(cx + 5);
    del.clear();
    del.resize(cx + 5);
    for (int i = 1; i <= n; ++i) {
        add[rec[i].s.x].push_back({rec[i].s.y + 1, rec[i].e.y});
        del[rec[i].e.x].push_back({rec[i].s.y + 1, rec[i].e.y});
    }
    seg.build(1, 1, cy);
    ll res = 0;
    for (int i = 1; i <= cx; ++i) {
        res += 1ll * (hx.a[i] - hx.a[i - 1]) * seg.t[1].len;
        for (auto &it : add[i]) {
            seg.update(1, 1, cy, it.x, it.y, 1);
        }
        for (auto &it : del[i]) {
            seg.update(1, 1, cy, it.x, it.y, -1);
        }
    }
    return res * 100;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        li[i].scan();
    }
    scanf("%d", &rate);
    Tri.scan();
    ll area = 1ll * (Tri.e.x - Tri.s.x) * (Tri.e.y - Tri.s.y) * rate;
    int l = 0, r = 1e5, res = 1e5;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (calc(mid) >= area) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}

G.Getting Confidence

Solved By Hsueh-. 1:00(+)

题意： - n 个物品，n 个货架，a_{ij} 表示物品 i 放在货架 j 的权值，问最大的 \prod a(i, p_i)。

思路：

  • 取 log 转化为加法，跑费用流。
Code 
#include <bits/stdc++.h>

using namespace std;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

using db = double;

const int N = 2e4 + 10, M = 1e6 + 10, INF = 0x3f3f3f3f;

struct Edge {
    int to, nxt, cap, flow;
    db cost;
    Edge() {}
    Edge(int to, int nxt, int cap, int flow, db cost) : to(to), nxt(nxt), cap(cap), flow(flow), cost(cost) {}
} edge[M];

int head[N], tot;
int pre[N];
db dis[N];
bool vis[N];

void Init() {
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, int cap, db cost) {
    edge[tot] = Edge(v, head[u], cap, 0, cost);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], 0, 0, -cost);
    head[v] = tot++;
}

bool SPFA(int S, int T) {
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[S] = 0;
    vis[S] = true;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // dbg(u);
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    // for (int i = 1; i <= 11; ++i) {
    //     dbg(i, pre[i]);
    // }
    if (pre[T] == -1)
        return false;
    else
        return true;
}

int minCostMaxflow(int s, int t, db& cost) {
    int flow = 0;
    cost = 0;
    while (SPFA(s, t)) {
        int Min = INF;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            Min = min(Min, edge[i].cap - edge[i].flow);
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int n;
int res[N];

int main() {
    scanf("%d", &n);
    Init();
    int S = 2 * n + 1, T = 2 * n + 2;
    for (int i = 1; i <= n; ++i) {
        addedge(S, i, 1, 0);
        addedge(i + n, T, 1, 0);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            db x = 0;
            scanf("%lf", &x);
            x = log(x);
            addedge(i, j + n, 1, -x);
        }
    }
    db cost;
    minCostMaxflow(S, T, cost);
    for (int u = 1; u <= n; ++u) {
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (v != S && edge[i].cap == edge[i].flow) {
                res[v - n] = u;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", res[i], " \n"[i == n]);
    }
    return 0;
}

H.Hour for a Run

Solved By Hsueh-. 0:06(+)

题意：

操场一圈有 n 个标志，总共跑 v 圈，问 10 \% \cdots 90 \% 会遇到多少障碍物。

思路：

签到。

Code 
#include <bits/stdc++.h>

using namespace std;

int v, n;

int main() {
    scanf("%d %d", &v, &n);
    for (int i = 1; i <= 9; ++i) {
        int res = ((v * n * i) + 9) / 10;
        printf("%d%c", res, " \n"[i == 9]);
    }
    return 0;
}

I.Interplanetary

Solved By Hsueh-. 3:34(+)

题意：

n 个星球，每个星球又在自己的温度，有 Q 次查询，每次查询问指经过最累或最热的 K 个星球，从 a 到 b 的最短路。

思路：

离线后动态加点跑 Floyd。

Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 4e2 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

struct E {
    int a, b, x, id, op;
    E() {}

    E(int a, int b, int x, int id, int op) : a(a), b(b), x(x), id(id), op(op) {}

    bool operator<(const E& other) const {
        return x < other.x;
    }
};

struct node {
    int id, x;
    node() {}

    node(int id, int x) : id(id), x(x) {}

    bool operator<(const node& other) const {
        return x < other.x;
    }
};

int n, m, top;
int temp[N], res[M];
int G[N][N], _G[N][N];
int id[N];
vector<E> Q;
vector<node> vec;

void gao() {
    // T = 0 <= x
    for (int i = 1; i <= n; ++i) {
        vec.push_back(node(i, temp[i]));
    }
    sort(vec.begin(), vec.end());
    sort(Q.begin(), Q.end());

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            G[i][j] = _G[i][j];
        }
    }
    int pos = -1;
    for (auto it : Q) {
        while (pos < n - 1 && vec[pos + 1].x <= id[it.x]) {
            // dbg(pos);
            pos++;
            int k = vec[pos].id;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
        if (it.op == 0)
            res[it.id] = G[it.a][it.b];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            G[i][j] = _G[i][j];
        }
    }
    // T = 1 >= x
    reverse(vec.begin(), vec.end());
    reverse(id + 1, id + 1 + top);
    pos = -1;
    for (auto it : Q) {
        // dbg(it.id);
        while (pos < n - 1 && vec[pos + 1].x >= id[it.x]) {
            pos++;
            int k = vec[pos].id;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
        if (it.op == 1)
            res[it.id] = G[it.a][it.b];
    }
}

int main() {
    scanf("%d %d", &n, &m);
    memset(_G, INF, sizeof _G);
    for (int i = 1; i <= n; ++i) {
        _G[i][i] = 0;
    }
    set<int> se;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", temp + i);
        se.insert(temp[i]);
    }
    for (auto it : se) {
        id[++top] = it;
    }
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        _G[u][v] = _G[v][u] = w;
    }
    int q;
    scanf("%d", &q);
    for (int i = 1, a, b, x, t; i <= q; ++i) {
        scanf("%d %d %d %d", &a, &b, &x, &t);
        if (x > top)
            x = top;
        Q.push_back(E(a, b, x, i, t));
    }
    gao();
    for (int i = 1; i <= q; ++i) {
        if (res[i] == INF) {
            res[i] = -1;
        }
        printf("%d\n", res[i]);
    }
    return 0;
}

J.Jar of Water Game

Solved By Hsueh-. 2:02(+1)

题意：

一个游戏，总共有 A23456789DJQK 和 wildcard，14 种牌，按照规则问最后谁赢。

规则如下：

  • n 个人坐成一圈，第 k 个人先开始。
  • 每个人给自己的下一位，也就是 1 给 2 \cdots。
  • 如果刚拿到 wildcard 则不能将 wildcard 给下一家,否则一定给 wildcard。
  • 否则找到数量最小的给下一家。
  • 如果有多个数量最小的则拿出数字最下的。
  • 如果一个人手上四张牌都一样则获胜。

思路：

模拟

Code 
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int get(char c) {
    if (c == 'A')
        return 1;
    else if (c == 'D')
        return 10;
    else if (c == 'Q')
        return 11;
    else if (c == 'J')
        return 12;
    else if (c == 'K')
        return 13;
    else
        return c - '0';
}

struct E {
    bool First, wildcard;
    vector<int> card;
    int get() {
        if (wildcard) {
            if (First) {
                First = false;
            } else {
                wildcard = false;
                return -1;
            }
        }
        map<int, int> mp;
        for (auto it : card) {
            mp[it]++;
        }
        int Min = INF;
        for (auto it : mp) {
            Min = min(it.second, Min);
        }
        for (auto it : mp) {
            if (it.second == Min) {
                card.erase(find(card.begin(), card.end(), it.first));
                return it.first;
            }
        }
    }

    void insert(int x) {
        if (x == -1) {
            First = wildcard = true;
        } else {
            card.push_back(x);
        }
    }
} a[30];

bool win(int x) {
    if (a[x].wildcard)
        return false;
    if (a[x].card[0] != a[x].card[1])
        return false;
    if (a[x].card[1] != a[x].card[2])
        return false;
    if (a[x].card[2] != a[x].card[3])
        return false;
    return true;
}

int n, k;

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        char s[10];
        scanf("%s", s + 1);
        a[i].card.clear();
        for (int j = 1; j <= 4; ++j) {
            a[i].insert(get(s[j]));
        }
        a[i].First = a[i].wildcard = false;
    }
    a[k].First = a[k].wildcard = true;
    for (int i = 1; i <= n; ++i) {
        if (win(i)) {
            printf("%d\n", i);
            return 0;
        }
    }
    int cur = k;
    while (true) {
        int nxt = cur % n + 1;
        a[nxt].insert(a[cur].get());
        if (win(cur))
            break;
        cur = nxt;
    }
    printf("%d\n", cur);
    return 0;
}

K.Keep Calm and Sell Balloons

Solved By Dup4 & ltslts. 3:14(+)

题意：

  • 给出 2 \cdot N 的矩阵，矩阵上的数字从左往右，从上到下，依次为 1 - 2N。
  • 现在可以任选一个起点出发，每次可以上下左右对角线八个方向走到相邻的并且没有被访问过的点走，问访问完所有点的方案数。

思路：

令 f[n] 表示从 1 出发的方案数。

那么我们考虑怎么递推 f[n]：

  • 从 1 出发，如果最终回到 n + 1，那么每次往右可以选择走上边或者往下边，那么回来回到 n + 1 的路径是固定的，这部分贡献是 2^{n - 1}
  • 如果第二步走 n + 1，那么第三步可以走 2 或者 n + 2，容易发现这是一个子问题，方案数为 2f[n - 1]。
  • 再考虑第三步走 n + 1，那么走法是 1 \to 2 \to n + 1 \to n + 2 或者 1 \to n + 2 \to n + 1 \to 2，然后就是一个 n - 2 规模的子问题，贡献是 4f[n - 2]。

所以有：

\begin{eqnarray*} f[n] = 2f[n - 1] + 4f[n - 2] + 2^{n - 1} \end{eqnarray*}

那么四个角的贡献就是 4f[n]，我们再考虑中间的贡献。

容易发现，我们发现从第一层的第 i 列出发和从第二层的第 i 列出发的方案数是相同的，所以我们只考虑第一层的第 i 列：

  • 显然，它不可能在第二步走到 n + i。
  • 假设它往右走，方案数为 2^{n - i}，然后回到 n + i 这个位置，再往左边走，这部分的方案是 f[i - 1]，所以往右走的贡献是 \displaystyle f[i - 1] \cdot 2^{n - 1}。
  • 同理可得，往左边走的方案数为 f[n - i] \cdot 2^{i - 1}。

那么答案就是：

\begin{eqnarray*} f[n] &=& 4f[n - 2] + 2f[n - 1] + 2^{n - 1} \\ ans &=& 4(f[n] + \sum\limits_{i = 2}^{n - 1} (f[i - 1] \cdot 2^{n - i} + f[n - i] \cdot 2^{i - 1}) ) \end{eqnarray*}

令 \displaystyle g[n] = \sum\limits_{i = 2}^{n - 1} f[i - 1] \cdot 2^{n - i}，有

\begin{eqnarray*} g[n] = g[n - 1] \cdot 2 + f[n - 2] \cdot 2 \end{eqnarray*}

令\displaystyle h[n] = \sum\limits_{i = 2}^{n - 1} f[n - i] \cdot 2^{i - 1}，有

\begin{eqnarray*} h[n] = h[n - 1] \cdot 2 + f[n - 2] \cdot 2 \end{eqnarray*}

容易发现 g[n] 和 h[n] 是一样的，直接矩阵快速幂即可。

Code 
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

const int mod = 1e9 + 7;
int n;

inline void chadd(ll &x, ll y) {
    x += y;
    while (x >= mod) x -= mod;
    while (x < 0) x += mod;
}

struct node {
    ll a[4][4];
    node() {}
    ll *operator[](int x) {
        return a[x];
    }
    void init() {
        memset(a, 0, sizeof a);
    }
    node operator*(const node &other) const {
        node res = node();
        res.init();
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                for (int k = 0; k < 4; ++k) {
                    chadd(res.a[i][j], a[i][k] * other.a[k][j] % mod);
                }
            }
        }
        return res;
    }
};

node qpow(node base, node res, ll n) {
    while (n) {
        if (n & 1)
            res = res * base;
        base = base * base;
        n >>= 1;
    }
    return res;
}

ll gao() {
    if (n == 1)
        return 2;
    if (n == 2)
        return 24;
    node base = node();
    base.init();
    base[0][0] = 6, base[0][1] = 1, base[0][2] = 0, base[0][3] = 4;
    node res = node();
    res.init();
    res[0][0] = 2, res[0][1] = 1;
    res[1][0] = 4, res[1][2] = 2;
    res[2][2] = 2;
    res[3][0] = 1, res[3][3] = 2;
    swap(res, base);
    res = qpow(base, res, n - 2);
    return 4ll * (res[0][0] + 2ll * res[0][2] % mod) % mod;
}

int main() {
    scanf("%d", &n);
    ll res = gao();
    res = (res % mod + mod) % mod;
    printf("%lld\n", res);
    return 0;
}

L.Less Coin Tosses

Solved By Dup4 & ltslts. 1:07(+)

题意：

有一个硬币，它不是公平的，即掷出正面和反面的概率不同。

现在为了公平，有如下策略：

  • 选一个 n。
  • 那么有 2^n 个 01串，Alice 拿一部分，Bob 拿一部分，剩下的舍弃，然后将该硬币投掷 n 次，根据掷出的正反面形成一个长度为 n 的 01串，如果该串在 Alice 那部分中，Alice 获胜，如果在 Bob 那部分中，Bob 获胜，否则再来一次。

现在给定 n，现在问最少舍弃多少 01串，使得该玩法是公平的。

思路：

我们假设投出正面的概率为 x，投出反面的概率为 y，假设一个长度为 n 的字符串中有 a 个 0，有 b 个 1，那么掷出该 01串 的概率为 x^a \cdot y^b。

那么可以根据 (a, b) 这个二元组，将所有 01串 进行分类，同类的均分给两人，那么容易发现，如果某类字符串是奇数个，那么必然要留下一个。

所以答案就是 \displaystyle \sum\limits_{i = 0}^n {n \choose i} \% 2 = 2^p，其中 p 为 n 的二进制表示中 1 的个数。

Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n;
    cin >> n;
    cout << (1ll << __builtin_popcountll(n)) << "\n";
    return 0;
}

M.Maratona Brasileira de Popcorn

Solved By Dup4. 0:33(+)

题意：

有 n 袋爆米花，每袋有 p_i 个爆米花，有 C 个人，每个人每秒钟能够吃 T 个爆米花。

现在有两个限制条件：

  • 每个人只能吃一段袋子标号连续的爆米花
  • 同一袋里的爆米花只能被同一个人吃

问最少需要多少时间，使得爆米花能被吃完。

思路：

二分时间，贪心 check。

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

const int N = 1e5 + 10;
int n, m, T, a[N];

int calc(int x) {
    int tot = x * T;
    int res = 1, sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] > tot)
            return 1e9;
        if (a[i] + sum <= tot) {
            sum += a[i];
        } else {
            sum = a[i];
            ++res;
        }
    }
    return res;
}

int main() {
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    int l = 1, r = 1e9 / T + 5, res = 1e9;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (calc(mid) <= m) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}
Last update: March 27, 2022
Created: March 27, 2022
Back to top