首页 > 其他分享 >AtCoder Beginner Contest 294

AtCoder Beginner Contest 294

时间：2023-03-19 22:55:40浏览次数：48  
标签：AtCoder Beginner int LL cin mid vector 294 root

A - Filter (abc294 a)

题目大意

给定一个数组，不改变原顺序，输出是偶数的数。

解题思路

模拟即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        if (!(x & 1))
            cout << x << ' ';
    }
    cout << '\n';

    return 0;
}

B - ASCII Art (abc294 b)

题目大意

给定一个二维数组，将其中的0变成.，其余的\(1 \sim 26\)则变成\(A \sim Z\)，输出变换后的数组。

解题思路

模拟即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int h, w;
    cin >> h >> w;
    while(h--){
        string s;
        for(int i = 0; i < w; ++ i){
            int x;
            cin >> x;
            if (x == 0)
                s += '.';
            else 
                s += 'A' + (x - 1);
        }
        cout << s << '\n';
    }

    return 0;
}

C - Merge Sequences (abc294 c)

题目大意

给定两个严格升序数组\(A,B\)，且两两互不相同。令 \(C\)为 该两个数组合并后并重新升序排序。

输出原在数组\(A,B\) 的每个元素在数组\(C\)的位置。

解题思路

即对每个元素求，有多少个数比它小。

对于\(A\)中的每个元素 \(i\)，首先在 \(A\)中有 \(i-1\)个元素比它小。其次对于在 \(B\)数组中，求 出前 \(x\)个都比它小。

当 \(i\)递增时，因为大小关系具有连续性，因此在 \(B\)数组中比它小的数可以在上次状态的基础上继续求。

即双指针法，时间复杂度为 \(O(n+m)\)

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(auto &i : a)
        cin >> i;
    for(auto &i : b)
        cin >> i;
    int cur = 0;
    for(int i = 0; i < n; ++ i){
        while(cur < m && a[i] > b[cur])
            ++ cur;
        cout << (i + 1) + cur << ' ';
    }
    cout << '\n';
    cur = 0;
    for(int i = 0; i < m; ++ i){
        while(cur < n && b[i] > a[cur])
            ++ cur;
        cout << (i + 1) + cur << ' ';
    }
    cout << '\n';

    return 0;
}

D - Bank (abc294 d)

题目大意

有\(n\)个人编号 \(1 \sim n\)，依次发生 \(q\)次事件，分三种：

  • 1 呼叫编号最小的未叫到的号
  • 2 x 标号为 \(x\)的人来报道
  • 3 呼叫已呼叫但未报道的标号最小的人

对于每个第三事件，回答叫到标号是多少。

解题思路

第一事件一定是递增的，所以用一个变量维护就好了。

而第三事件，我们只需记录下每个人的报道状态，其叫到的号也是递增的，所以也用一个变量维护就好了。

因为保证数据合法，其实就没别的要考虑的了。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> vis(n);
    int cur = 0;
    int noww = 0;
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            ++ cur;
        }else if (op == 2){
            int id;
            cin >> id;
            -- id;
            vis[id] = 1;
        }else{
            while(vis[noww] == 1)
                ++ noww;
            cout << noww + 1 << '\n';
        }
    }

    return 0;
}

E - 2xN Grid (abc294 e)

题目大意

给定两个长度均为\(L\)的数组\(a,b\)，求下标 \(i\)满足\(a_i = b_i\) 的数量。

每个数组以若干个二元组\((v,l)\)依次表示，即有连续 \(l\)个值为 \(v\)，不断延续。

解题思路

因为长度有\(10^{12}\)不能暴力匹配，但考虑到两个数组的切割点（就是二元组数量）只有 \(O(10^5)\)，因此我们就以切割点，每块每块考虑就可以了。

感觉非常暴力啊

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    LL l;
    int n, m;
    cin >> l >> n >> m;
    vector<array<LL, 2>> a(n), b(m);
    for(auto &i : a)
        cin >> i[0] >> i[1];
    for(auto &i : b)
        cin >> i[0] >> i[1];
    LL ans = 0;
    int aa = 0, bb = 0;
    while(true){
        LL minn = min(a[aa][1], b[bb][1]);
        if (a[aa][0] == b[bb][0])
            ans += minn;
        a[aa][1] -= minn;
        b[bb][1] -= minn;
        if (a[aa][1] == 0)
            ++ aa;
        if (b[bb][1] == 0)
            ++ bb;
        if (aa == n || bb == m)
            break;
    }
    cout << ans << '\n';

    return 0;
}

F - Sugar Water 2 (abc294 f)

题目大意

两排糖水，糖成份\(x\)和水成分 \(y\)。

从两排中各取一个糖水混合，得糖浓度 \(\frac{x_i + x_j}{x_i + x_j + y_i + y_j} \%\)。

问所有方案中，糖浓度第 \(k\)大是多少。

解题思路

考虑一经典问题：两个数组\(a,b\)选各选一个数，求其和是第\(k\)大的数。

其解法是二分，当我们二分这个第 \(k\)大的和是 \(x\)后，我们就看是否有 \(k - 1\)个\(a_i + b_j > x\)。

暴力验证的复杂度是\(O(n^2)\)，但可以优化，即对\(a,b\)排序，然后遍历每个 \(a_i\)，统计下\(b\)数组中大于\(x - a_i\)的数量。因为\(a_i\)递增，所以 \(x - a_i\)递减，其\(b\)数组中的数量会越来越多，且每次求解继承前一状态继续求即可。因此可以双指针求解。（与\(C\)题做法一致）

即\(b_i > x - a_i\)

因为有单调性的缘故，验证的复杂度可以降为\(O(n)\)，总的复杂度是 \(O(n\log n)\)

而对于此题，很明显就是将\(a_i+b_i\)替换成了上述分式。

同样考虑二分值\(mid\)，但此时 没有上述的单调性：一个份糖水与另一份糖水混合在一起后其浓度我们找不到某种单调性优化验证的复杂度，做不到 \(O(n)\)（暴力验证是\(O(n^2)\)）

但我们还是考虑是否存在某些单调性，我们考虑其比较式子：

\[\frac{x_i + x_j}{x_i + x_j + y_i + y_j} > mid \]

分母移项，得

\[x_i + x_j > mid \times (x_i + x_j + y_i + y_j) \]

然后我们将\(i,j\)分离，得

\[(1 - mid) \times x_i - mid \times y_i > (mid - 1) \times x_j + mid \times y_j \]

这个式子其实就跟上述经典问题转换后的原式子是一样的形式，从这个式子我们就可以窥见另一种单调性：

对于满足原式的\(i,j\)的数量，相当于新数组 \(tmpa[i] = (1 - mid) \times x_i - mid \times y_i, tmpb[j] = (mid - 1) \times x_j + mid \times y_j\)，满足\(tmpa[i] > tmpb[j]\)的数量。

而这很显然对\(tmpa,tmpb\)数组排个序后，枚举每个 \(tmpa\)，求出小于其的 \(tmpb\)的元素数量，累计就可以了。因为大小具有传递性，因此其 \(tmpb\)的元素数量是递增的，可以从上一个状态继续求解，即双指针法。

因此验证的复杂度就是 \(O(n \log n + m \log m)\)

因此总的时间复杂度就是\(O((n \log n + m\log m) \log 10^9)\)

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const double eps = 1e-12;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    LL k;
    cin >> n >> m >> k;
    vector<array<LL, 2>> a(n), b(m);
    for(auto &i : a)
        cin >> i[0] >> i[1];
    for(auto &i : b)
        cin >> i[0] >> i[1];
    double l = 0, r = 1;
    auto check = [&](double x){
        vector<double> tmpa(n), tmpb(m);
        for(int i = 0; i < n; ++ i){
            tmpa[i] = (1 - x) * a[i][0] - x * a[i][1];
        }
        for(int i = 0; i < m; ++ i){
            tmpb[i] = (x - 1) * b[i][0] + x * b[i][1];
        }
        sort(tmpa.begin(), tmpa.end());
        sort(tmpb.begin(), tmpb.end());
        LL cnt = 0;
        LL cur = 0;
        for(int i = 0; i < n; ++ i){
            while(cur < m && tmpb[cur] < tmpa[i])
                ++ cur;
            cnt += cur;
        }
        return cnt <= k;
    };
    -- k;
    while(r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else 
            l = mid;
    }
    cout << fixed << setprecision(11) << r * 100 << '\n';

    return 0;
}

G - Distance Queries on a Tree (abc294 g)

题目大意

给定一棵树，边有边权，维护一下两种操作：

  • 1 x w 将第\(x\)条边边权改为 \(w\)
  • 2 u v 问从\(u\)到 \(v\)的最短路径长度

解题思路

首先随便选个点作为根。

如果没有修改操作，我们可以维护每个点到根节点的距离\(dis\)，记u,v的lca(最近公共祖先)是x，那\(u -> v\)的距离就是 \(dis[u] + dis[v] - 2 dis[x]\)。

而如果有修改操作，每次修改则会影响到一棵子树的 \(dis\)值。从一棵树的 dfs序来看的话就是修改一个区间。

用线段树维护dfs序上的\(dis\)数组即可。

区间修改和单点查询。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

class segtree {
#define lson (root << 1)
#define rson (root << 1 | 1)

    int n;
    vector<LL> max;
    vector<LL> lazy;

    void build(int root, int l, int r, const vector<int> &v, const vector<LL> &val) {
        if (l == r) {
          lazy[root] = 0;
          max[root] = val[v[l - 1]];
          return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, v, val);
        build(rson, mid + 1, r, v, val);
        max[root] = std::max(max[lson], max[rson]);
        lazy[root] = 0;
    }

    inline void pushdown(int root){
        if (lazy[root]){
            lazy[lson] += lazy[root];
            max[lson] += lazy[root];
            lazy[rson] += lazy[root];
            max[rson] += lazy[root];
            lazy[root] = 0;
        }
    }

    void update(int root, int l, int r, int L, int R, LL val){
        if (L <= l && r <= R){
            lazy[root] += val;
            max[root] += val;
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update(lson, l, mid, L, R, val);
        if (R > mid)
            update(rson, mid + 1, r, L, R, val);
        max[root] = std::max(max[lson], max[rson]);
    }

    LL query(int root, int l, int r, int pos){
        if (l == r)
            return max[root];
        pushdown(root);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return query(lson, l, mid, pos);
        else 
            return query(rson, mid + 1, r, pos);
    }

    public:

    void build(const vector<int> &v, const vector<LL> &val){
        n = v.size();
        lazy.resize(4 * (n + 1), 0);
        max.resize(4 * (n + 1), 0);
        build(1, 1, n, v, val);
    }

    void update(int L, int R, LL val){
        assert(1 <= L && R <= n && L <= R);
        update(1, 1, n, L, R, val);
    }

    LL query(int pos){
        return query(1, 1, n, pos);
    }

};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<vector<array<LL, 2>>> edge(n);
    vector<array<int, 3>> raw(n);
    vector<int> deep(n);
    vector<LL> dis(n);
    vector<array<int, 31>> up(n);
    for(int i = 1; i < n; ++ i){
        int u, v, w;
        cin >> u >> v >> w;
        -- u, -- v;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
        raw[i] = {u, v, w};
    }
    vector<int> order;
    vector<int> first(n);
    vector<int> last(n);
    function<void(int, int)> dfs = [&](int u, int fa){
        first[u] = order.size();
        order.push_back(u);
        for(auto &[v, w] : edge[u]){
            if (fa == v)
                continue;
            dis[v] = dis[u] + w;
            deep[v] = deep[u] + 1;
            up[v][0] = u;
            dfs(v, u);
        }
        last[u] = order.size() - 1;
    };
    auto get_lca = [&](int u, int v){
        if (deep[u] < deep[v])
            swap(u, v);
        int t = deep[u] - deep[v];
        for(int i = 0; i < 31; ++ i){
            if (t & (1 << i))
                u = up[u][i];
        }
        for(int i = 30; i >= 0; -- i){
            int uu = up[u][i], vv = up[v][i];
            if (uu != vv){
                u = uu;
                v = vv;
            }
        }
        return u == v ? u : up[u][0];
    };
    deep[0] = 0;
    up[0][0] = 0;
    dfs(0, 0);
    segtree seg;
    seg.build(order, dis);
    for(int i = 1; i <= 30; ++ i){
        for(int j = 0; j < n; ++ j){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    int q;
    cin >> q;
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int id, val;
            cin >> id >> val;
            if (raw[id][2] == val)
                continue;
            auto [u, v, w] = raw[id];
            if (deep[u] < deep[v])
                swap(u, v);
            LL cval = val - w;
            seg.update(first[u] + 1, last[u] + 1, cval);
            raw[id][2] = val;
        }else{
            int u, v;
            cin >> u >> v;
            -- u;
            -- v;
            LL dis1 = seg.query(first[u] + 1);
            LL dis2 = seg.query(first[v] + 1);
            int lca = get_lca(u, v);
            LL dis3 = seg.query(first[lca] + 1);
            cout << dis1 + dis2 - 2 * dis3 << '\n';
        }
    }

    return 0;
}

Ex - K-Coloring (abc294 h)

题目大意

给定一张图，要求给点分配值域为\([1,k]\)的点权，问有多少种方案数，使得每条边的两个顶点的点权都不同。

解题思路

<++>

神奇的代码

标签：AtCoder,Beginner,int,LL,cin,mid,vector,294,root
From： https://www.cnblogs.com/Lanly/p/17234703.html

相关文章

  • 【题解】ABC294
    AtCoderBeginnerContest294AFilter无意义题，找出所有偶数。BASCIIArt无意义题，按题意模拟。CMergeSequences无意义题，离散化即可。DBank无意义题，set维护即......
  • AtCoder Beginner Contest 293
    A-SwapOddandEven#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){ strings; cin>>s; for(inti=0;i+1<s.size();i+=2) swap(......
  • AtCoder Beginner Contest 293
    上周因为GDKOI咕咕咕了A-SwapOddandEven(abc293a)题目大意给定一个字符串，交换每两个相邻字母，输出结果。解题思路模拟即可。神奇的代码#include<bits/std......
  • AtCoder Beginner Contest 293(C,D ,E,F)
    AtCoderBeginnerContest293(C,D,E,F)CC这道题其实还蛮好写的，就是一个\(dfs\),然后我看错了题意，就记录一下这道题的大意是我们需要从\((1,1)\)走到\((n,m)\),我们只......
  • [AtCoder Beginner Contest 281][G. Farthest City]
    和CF1657E的做法十分相似题目链接：G-FarthestCity题目大意：问有多少个\(n(3\len\le500)\)个点的无向连通图满足，若设\(1\)到\(i\)的最短路距离为\(dis_i\)，则......
  • AtCoder Regular Contest 158
    Preface这场比赛刚好周日晚上没事就打了，堪堪混过三道题，也算是小上了一波分吧但是由于A题脑抽了一波卡了30min，导致排名不高，也没时间看DE了，属实有点可惜A-+3+5+7显......
  • AtCoder Beginner Contest 293
    题解报告基本的一些理解和问题都在注释中A：SwapOddandEven//水题#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>usingnamespace......
  • AtCoder Beginner Contest 240 F
    ABC240F思路维护前缀和B，以及B的前缀和C，然后在每次添加连续y个x的时候，从中找出最大的\(C_i\)(用pre记录)，更新答案。有四种情况\(B\geq0,x>0\)那么新出现的\(C_i\)中......
  • atcoder ABC
    Ex-OptimalPathDecomposition题目只能给链染色，问你最短的（两点距离最大值），距离为不同颜色个数f[u],g[u]，f表示u可以和father同一个颜色，g表示不可以。转移记录三个值。......
  • AtCoder Beginner Contest 272（D,E)
    AtCoderBeginnerContest272（D,E)DD这个题最主要的是需要找出有哪些移动的距离对于题目给出的\(m\),我们的移动过程可以是\((i-ii)^2+(j-jj)^2=m\)这样的话，我们可以......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99