首页 > 其他分享 >2019-2020 ACM-ICPC Brazil Subregional Programming Contest

2019-2020 ACM-ICPC Brazil Subregional Programming Contest

时间：2023-09-10 15:24:33浏览次数：47  
标签：Brazil cnt ch const Contest int Subregional mi mid

D. Denouncing Mafia

给定一颗树，然后给定\(k\)个起点，对于每个起点来说，从该点到根节点的一条链都会被染色，求最多有几个点会被染色

\(3 \leq n \leq 1e5, 1 \leq k \leq n\)

题解

  • 我们贪心的来看，起点一定会选择在叶子节点，假设叶子节点的数量为\(cnt\)，所以如果\(k \geq cnt\)，那么答案一定为\(n\)
  • 否则我们可以长链剖分，将每条链剖出来后排序取前\(k\)条链即可
const int N = 1e5 + 10, M = 4e5 + 10;

int n, k;
vector<int> g[N];
int hson[N], dep[N], mx_dep[N], fa[N], sz[N];
int l[N], r[N], id[N], idx, top[N];
int tot, w[N];

void dfs1(int u, int par)
{
    sz[u] = 1;
    hson[u] = -1;
    fa[u] = par;
    mx_dep[u] = dep[u] = dep[par] + 1;
    for (auto v : g[u])
    {
        if (v == par)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        mx_dep[u] = max(mx_dep[u], mx_dep[v]);
        if (hson[u] == -1 || mx_dep[v] > mx_dep[hson[u]])
            hson[u] = v;
    }
}

void dfs2(int u, int head)
{
    top[u] = head;
    l[u] = ++idx;
    id[idx] = u;
    if (hson[u] != -1)
        dfs2(hson[u], head);
    for (auto v : g[u])
    {
        if (v != fa[u] && v != hson[u])
            dfs2(v, v);
    }
    r[u] = idx;
}

void solve()
{
    cin >> n >> k;
    for (int i = 2; i <= n; ++i)
    {
        int u;
        cin >> u;
        g[u].push_back(i);
        g[i].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    int cnt_son = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (sz[i] == 1)
        {
            cnt_son++;
            w[++tot] = dep[i] - dep[top[i]] + 1;
        }
    }
    if (k >= cnt_son)
    {
        cout << n << endl;
        return;
    }
    sort(w + 1, w + tot + 1, greater<int>());
    int ans = 0;
    for (int i = 1; i <= k; ++i)
        ans += w[i];
    cout << ans << endl;
}

L. Less Coin Tosses

给定\(n, 2 \leq n \leq 1e18\)，将\(2^n\)个二进制字符串分别分配给两个人，使得两个人获胜的概率相同的情况下未被分配的字符串数量最少

题解

  • 显然只要某一次分配的字符串中\(1\)的个数相同，那么两个人获胜的胜率能够始终相同

  • 所以答案为\(\sum (C_n^i \& 1==1)\)

  • 显然对于组合数的奇偶性，我们知道结论：若\((n \& k==k)\)，则\(C_n^k\)为奇数，否则为偶数

  • 也就是说如果\(k\)的二进制是\(n\)的二进制的子集，那么答案贡献\(+1\)

  • 那么显然答案为\(n\)的二进制中\(1\)个数为\(x\)，答案为\(2^x\)

const int N = 2e5 + 10, M = 4e5 + 10;

int n;

void solve()
{
    cin >> n;
    int x = __builtin_popcountll(n);
    cout << (1ll << x) << endl;
}

M. Maratona Brasileira de Popcorn

题解

  • 考虑二分答案
  • \(check\)时检查需要几个人才能将所有的玉米吃完，然后与原有人数比较即可
const int N = 2e6 + 10;
int n,m,cnt;
int a[N];

bool check(int mid)
{
    int w=1;
    int x=mid*cnt;
    for(int i=1;i<=n;)
    {
        if(a[i]-x<=0) 
        {
            x-=a[i];
            i++;
        }
        else 
        {
            x=mid*cnt;
            w++;
            if(w>m) return false;
        }
    }
    if(w>m ) return false;
    else return true;
}

void solve()
{
    cin>>n>>m>>cnt;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=0,r=2e15;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
}

J. Jar of Water Game

image-20230907114515881

题解

  • 模拟即可
  • 注意细节：
  1. 拿到鬼牌后不能立刻传递
  2. 一开始的时候有可能已经存在获胜的玩家
  3. 每次判断胜利条件在传递牌之后，判断所有队伍是否胜利
const int N = 1e2 + 10, M = 4e5 + 10;

int n, k;
map<char, int> mp[N];
string cmp = "A23456789DQJK";

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        for (auto ch : s)
            mp[i][ch]++;
        if (i == k)
            mp[i]['W']++;
    }
    int now = k;
    bool flag = true;
    int cur = 4;
    while (true)
    {
        int nxt = now + 1;
        if (nxt > n)
            nxt = 1;
        if (mp[now]['W'] > 0 && flag == false)
            mp[nxt]['W']++, mp[now]['W']--, flag = true;
        else
        {
            if (mp[now]['W'] > 0 && flag == true)
                flag = false;
            int mi = INF;
            char ch;
            for (auto [x, y] : mp[now])
            {
                if (y == 0)
                    continue;
                if (x == 'W')
                    continue;
                if (y < mi)
                {
                    mi = y;
                    ch = x;
                }
                else if (y == mi)
                {
                    if (cmp.find(x) < cmp.find(ch))
                        ch = x;
                }
            }
            mp[now][ch]--;
            mp[nxt][ch]++;
        }
        int ans = -1;
        char ans_ch;
        for (int i = 1; i <= n; ++i)
        {
            int cnt = 0;
            bool ok = false;
            char c;
            for (auto [x, y] : mp[i])
            {
                cnt += (y > 0);
                if (y == 4)
                {
                    ok = true;
                    c = x;
                }
            }
            if (ok && cnt == 1)
            {
                if (ans == -1)
                {
                    ans = i;
                    ans_ch = c;
                }
                else if (cmp.find(c) < cmp.find(ans_ch))
                {
                    ans = i;
                    ans_ch = c;
                }
            }
        }
        if (ans != -1)
        {
            cout << ans << endl;
            return;
        }
        now = nxt;
    }
}

A. Artwork

image-20230907114751409

题解

  • \(O(n^2)\)将所有相交的监控用并查集合并，然后并查集中维护四种信息：是否与左墙接触\(left\)，\(right\)，\(up\)，\(down\)
  • 然后判断是否有监控集合同时接触左墙和右墙，上墙和下墙，左墙和上墙，右墙和下墙之一即可
const int N = 1e4 + 10;
const int K = 1010;
int n, m, k, x[K], y[K], R[K];
bool f[K][5]; //up 1 down 2 left 3 right 4
const int UP = 1;
const int DOW = 2;
const int LE = 3;
const int RI = 4;

bool check(int i){
    return ((f[i][UP] && f[i][LE]) || (f[i][UP] && f[i][DOW]) || (f[i][LE] && f[i][RI]) || (f[i][RI] && f[i][DOW]));
}

bool xiangjiao(int e1, int e2){
    int dis=(x[e1]-x[e2])*(x[e1]-x[e2])+(y[e1]-y[e2])*(y[e1]-y[e2]);
    int rr=(R[e1]+R[e2])*(R[e1]+R[e2]);
    return dis<=rr;
}

int fa[K];

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

void merg(int a, int b){
    a = find(a);
    b = find(b);
    if(a == b) return;
    f[b][UP] |= f[a][UP];
    f[b][DOW] |= f[a][DOW];
    f[b][LE] |= f[a][LE];
    f[b][RI] |= f[a][RI];
    fa[a] = b;
}

void solve()
{
    for(int i = 1;i < K;i++) fa[i] = i;
    bool ans = false;
    cin >> m >> n >> k;
    for(int i = 1;i <= k;i++){
        cin >> x[i] >> y[i] >> R[i];
        if(x[i] - R[i] <= 0) f[i][UP] = true;
        if(x[i] + R[i] >= m) f[i][DOW] = true;
        if(y[i] - R[i] <= 0) f[i][LE] = true;
        if(y[i] + R[i] >= n) f[i][RI] = true;

        if(check(i)) ans = true;
    }

    if(ans){
        cout << "N";
        return;
    }

    for(int i = 1;i <= k;i++){
        for(int j = i + 1;j <= k;j++){
            if(xiangjiao(i, j)){
                merg(i, j);
                if(check(find(j))){
                    cout << "N";
                    return;
                }
            }
        }
    }

    cout << "S";
}

F. Forests in Danger

给定\(n\)条平行于\(x\)轴或\(y\)轴的线段，每条线段能够覆盖的范围是一个矩阵，线段上每个点到矩阵边的最小距离都为\(r\)，给定一块矩阵区域\(p\)，请你确定一个最小的\(r\)，能够使得\(n\)条线段产生的矩阵与矩阵\(p\)的重合部分的面积至少是矩阵\(p\)面积的\(\%P\)

image-20230910150632558

题解：二分答案 + 矩形面积并

  • 显然二分答案
  • \(check\)时我们可以求出每个矩阵与矩阵\(p\)的交，交集同样也是一个矩阵
  • 然后对每一个交的矩阵求矩形面积并即可，最后和矩阵\(p\)的面积比较一下即可
  • \(tips\)：利用线段树计算矩形的长时，需要对长度\(-1\)，因为\([2,5]\)的长度在计算矩形面积时应该为\(3\)，但是线段树中会返回\(4\)
const int N = 2e5 + 10, M = 4e5 + 10;

int n, P, x3, x4, y3, y4, m = 2e5 + 5;
struct Line
{
    int x1, y1, x2, y2;
} line[N];
struct Mat : Line
{
} mat[N];

struct info
{
    int mi, cnt;
    friend info operator+(const info &a, const info &b)
    {
        info c;
        if (a.mi == b.mi)
        {
            c.mi = a.mi;
            c.cnt = a.cnt + b.cnt;
        }
        else if (a.mi < b.mi)
        {
            c.mi = a.mi;
            c.cnt = a.cnt;
        }
        else
        {
            c.mi = b.mi;
            c.cnt = b.cnt;
        }
        return c;
    }
    info(int mi = 0, int cnt = 0) : mi(mi), cnt(cnt) {}
};
struct SEG
{
    int lazy;
    info val;
} seg[N << 2];

void up(int id)
{
    seg[id].val = seg[lson].val + seg[rson].val;
}

void settag(int id, int tag)
{
    seg[id].val.mi += tag;
    seg[id].lazy += tag;
}

void down(int id)
{
    if (seg[id].lazy == 0)
        return;
    settag(lson, seg[id].lazy);
    settag(rson, seg[id].lazy);
    seg[id].lazy = 0;
}

void build(int id, int l, int r)
{
    seg[id].lazy = 0;
    if (l == r)
    {
        seg[id].val = info(0, 1);
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    up(id);
}

void modify(int id, int l, int r, int ql, int qr, int val)
{
    if (ql <= l && r <= qr)
    {
        settag(id, val);
        return;
    }
    down(id);
    int mid = l + r >> 1;
    if (qr <= mid)
        modify(lson, l, mid, ql, qr, val);
    else if (ql > mid)
        modify(rson, mid + 1, r, ql, qr, val);
    else
    {
        modify(lson, l, mid, ql, qr, val);
        modify(rson, mid + 1, r, ql, qr, val);
    }
    up(id);
}

bool check(int r)
{
    build(1, 1, m);
    vector<array<int, 4>> evt;
    vector<int> vec;
    for (int i = 1; i <= n; ++i)
    {
        auto [x1, y1, x2, y2] = line[i];
        mat[i] = {x1 - r, y1 - r, x2 + r, y2 + r};
    }
    for (int i = 1; i <= n; ++i)
    {
        auto [x1, y1, x2, y2] = mat[i];
        int lx = max(x1, x3), ly = max(y1, y3);
        int rx = min(x2, x4), ry = min(y2, y4);
        if (lx < rx && ly < ry)
        {
            // 别忘记右端点 -1
            evt.push_back({ly, -1, lx, rx - 1}); // 入边
            evt.push_back({ry, 1, lx, rx - 1});  // 出边
        }
    }
    sort(all(evt));
    int ans = 0;
    int sum = seg[1].val.cnt;
    int preY = 0;
    for (auto [y, op, l, r] : evt)
    {
        int len = sum;
        if (seg[1].val.mi == 0)
            len -= seg[1].val.cnt;
        ans += (y - preY) * len;
        if (op == -1)
            modify(1, 1, m, l, r, 1);
        else
            modify(1, 1, m, l, r, -1);
        preY = y;
    }
    int area = (x4 - x3) * (y4 - y3);
    return ans * 100 >= area * P;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        line[i] = {x1 + 1, y1 + 1, x2 + 1, y2 + 1};
    }
    cin >> P;
    cin >> x3 >> y3 >> x4 >> y4;
    x3++, y3++, x4++, y4++;
    int l = 0, r = 1e9;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << l << endl;
}

标签：Brazil,cnt,ch,const,Contest,int,Subregional,mi,mid
From： https://www.cnblogs.com/Zeoy-kkk/p/17691278.html

相关文章

  • 2022 Hubei Provincial Collegiate Programming Contest G. Brick（gym103729）
    大意给出底层高度，用1*2的砖块将总形状铺成等高矩形，使得高度最小（不能放在外面）题解奇妙做法当高度同奇偶时显然x可以的话x+2也可以，直接加一层竖的，所以首先分奇偶二分高度有解的必要条件1是，把矩形黑白方格染色之后未填的黑=白（一个1*2刚好覆盖1黑1白）然后从左往右放砖块，可以感受......
  • 2019 ICPC Universidad Nacional de Colombia Programming Contest
    A.Amazon给定\(n\)条直线（存在共线的情况），在每两条垂直的直线的交点处需要建一个交叉点，求交叉点的数量，注意需要去除共线时候的交叉点题解因为要除去共线的情况，我们考虑将一条直线以方向向量\(v\)，与\(x\)轴的交点的横坐标\(x\)的方式存储注意：对于\(v\)来说需要最简形......
  • 【题解】AtCoder Regular Contest 161
    评价：感觉这场题目质量不咋地啊，都是一些乱搞题A.MakeM题目描述：\(N\)是一个正奇数。我们称一个长度为\(N\)的序列\(S\)是M型序列，当前仅当对于所有的\(i=2,4,6,\dots,N-1\)（即偶数位），都有\(S_{i-1}<S_{i}\)且\(S_{i}>S_{i+1}\)。现在给定你一个长度为\(N\)的序列\(A......
  • 【题解】AtCoder Regular Contest 162
    A.EkidenRace题目描述：有\(n\)个人参加了往返赛跑，每个人有一个编号\(1\)到\(n\)。已知以下信息：如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第\(i\)个人在往路中排名第\(i\)。如果按照往返的成绩排序，那么任何两个人的成绩都不相同。同时第\(i\)个人......
  • AtCoder Grand Contest 041 F Histogram Rooks
    洛谷传送门AtCoder传送门神题！！！！！！！！！/bx全部格子都被覆盖不好处理，考虑钦定\(k\)个格子不被覆盖，容斥系数就是\((-1)^k\)。发现网格的行不一定连续，但是列是连续的。如果一列有格子被钦定，那么这一列就不能放棋子。由此想到枚举不能放棋子的列（至少有一个棋子被钦定的列）集合\(S\)，把......
  • AtCoder Beginner Contest 318 - D(状压 dp)
    目录D-GeneralWeightedMaxMatchingD-GeneralWeightedMaxMatching题意给定无向图，边有边权。让你选择一组边，满足任意两边不相交且总边权和最大。顶点数$\le16$思路状压DP求解该问题状态：利用n位二进制表示每个顶点是否已经被选择，0表示该顶点未选，1表示当前......
  • 2022 International Collegiate Programming Contest, Jinan Site AEKM
    2022InternationalCollegiateProgrammingContest,JinanSite-CodeforcesAEKMA.Tower思路：思维+贪心由于我们只能进行\(+1,-1\)和\\(2\)的操作。显然的，我们能大幅度改变一个数是除\(2\)的操作，并且最后化成的一样的那个数一定不会大于当且的任何一个数，因为这样肯定......
  • The 16-th BIT Campus Programming Contest - Onsite Round
    链接：https://codeforces.com/gym/104025A.Giftsinbox#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m,h;cin>>n>>m>&......
  • [题解] AtCoder Beginner Contest 308 A~G
    AtCoderBeginnerContest308A~GA.NewSchemevoidMain(){vector<i64>a(8);for(auto&x:a)cin>>x;if(!is_sorted(a.begin(),a.end())&&!all_of(a.begin(),a.end(),[](auto&x){returnx%25!=0||!(100......
  • The 2022 ICPC Asia Nanjing Regional Contest
    链接：https://codeforces.com/gym/104128A.Stop,YesterdayPleaseNoMore#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;voidsolve(){intn,m,k;cin>>n>>m>>k;strings;cin>>......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99