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

AtCoder Beginner Contest 371

时间：2024-09-16 23:46:02浏览次数：9  
标签：AtCoder return Beginner int mid long pos 371 now

A - Jiro

输入 \(AB, BC, AC\) 的大小关系，输出中位数。

手动模拟一下。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

char c, a, b;

int main()
{
    scanf(" %c", &c);
    scanf(" %c %c", &a, &b);
    if(c == '<')
    {   
        if(a == '>' && b == '>') printf("A");
        if(a == '<' && b == '>') printf("C");
        if(a == '<' && b == '<') printf("B");
    }else
    {
        if(a == '>' && b == '>') printf("B");
        if(a == '>' && b == '<') printf("C");
        if(a == '<' && b == '<') printf("A");
    }
    return 0;
}

B - Taro

每家的第一个男孩子被命名为 \(\text{Taro}\)，按照出生顺序输出每个孩子所在家庭和性别，判断他是否被命名为 \(\text{Taro}\)。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 105;

int vis[N];

int main()
{
    int n = read(), m = read();
    int a;
    char c;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %c", &a, &c);
        if(c == 'M' && !vis[a])
        {
            vis[a] = 1;
            printf("Yes\n");
        }else printf("No\n");
    }
    return 0;
}

C - Make Isomorphic

给定两个 \(n\) 个点数的图 \(G, H\)，可以用 \(A_{i, j}\) 的代价删去或加上边 \((i, j)\)，问最小的花费使得图 \(G, H\) 同构。

同构的定义是，存在一个排列 \(p\)，使得 \(G\) 中存在边 \((i, j)\) 当且仅当 \(H\) 中存在边 \(（p_i, p_j）\)。

发现点数很小，暴力枚举排列 \(p\)计算代价即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 10;
int n, mG, mH;
int visG[N][N], visH[N][N];
int val[N][N];
int ans, now;
int p[N];
int main()
{
    ans = 0x7fffffff;
    n = read();
    mG = read();
    for(int i = 1; i <= mG; ++i)
    {
        int u = read(), v = read();
        visG[u][v] = 1;
    }
    mH = read();
    for(int i = 1; i <= mH; ++i)
    {
        int u = read(), v = read();
        visH[u][v] = 1;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            val[i][j] = read();
    for(int i = 1; i <= n; ++i) p[i] = i;
    do
    {
        now = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = i + 1; j <= n; ++j)
            {
                int u = p[i], v = p[j];
                if(u > v) swap(u, v);
                if(visG[i][j] ^ visH[u][v]) now += val[u][v];
            }
        ans = min(ans, now);
    }while(next_permutation(p + 1, p + n + 1));
    printf("%d\n", ans);
    return 0;
}

D - 1D Country

有 \(n\) 个位置 \(X_i\)，每个位置有 \(P_i\) 个人，每次询问位于 \([L_i, R_i]\) 位置中的人的个数。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 6e5 + 5;
int n, q, nn, m;
int X[N], L[N], R[N], a[N], b[N];

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

ll sum[N << 2];

void update(int k, int l, int r, int pos, int val)
{
    if(l == r){ sum[k] += val; return ; }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ls(k), l, mid, pos, val);
    else update(rs(k), mid + 1, r, pos, val);
    sum[k] = sum[ls(k)] + sum[rs(k)];
}

ll query(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return sum[k];
    int mid = (l + r) >> 1;
    if(R <= mid) return query(ls(k), l, mid, L, R);
    if(L > mid) return query(rs(k), mid + 1, r, L, R);
    return query(ls(k), l, mid, L, R) + query(rs(k), mid + 1, r, L, R);
}

int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) X[i] = read(), b[++m] = X[i];
    for(int i = 1; i <= n; ++i) a[i] = read();
    q = read();
    for(int i = 1; i <= q; ++i)
    {
        L[i] = read(), b[++m] = L[i];
        R[i] = read(), b[++m] = R[i];
    }
    sort(b + 1, b + m + 1);
    nn = unique(b + 1, b + m + 1) - (b + 1);
    for(int i = 1; i <= n; ++i) X[i] = lower_bound(b + 1, b + nn + 1, X[i]) - b;
    for(int i = 1; i <= q; ++i)
    {
        L[i] = lower_bound(b + 1, b + nn + 1, L[i]) - b;
        R[i] = lower_bound(b + 1, b + nn + 1, R[i]) - b;
    }
    for(int i = 1; i <= n; ++i) update(1, 1, nn, X[i], a[i]);
    for(int i = 1; i <= q; ++i) printf("%lld\n", query(1, 1, nn, L[i], R[i]));
    return 0;
}

E - I Hate Sigma Problems

给定序列 \(A\) ，求 \(A\) 的所有子序列的不同数值的种类数和。

考虑扫描线，每次扩展右端点，维护所有左端点的答案，记 \(last_x\) 表示值 \(x\) 上一次出现的位置，那么对于 \(r\)，\(a_r\) 是区间 \([last_{a_r} + 1, r]\)中的新数，对于这些左端点加 \(1\) 即可。

线段树维护一下区间加，求全局和即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int n, a[N], last[N];

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

ll sum[N << 2], lazy[N << 2], len[N << 2];

void pushdown(int k)
{
    if(lazy[k])
    {
        sum[ls(k)] += len[ls(k)] * lazy[k];
        sum[rs(k)] += len[rs(k)] * lazy[k];
        lazy[ls(k)] += lazy[k];
        lazy[rs(k)] += lazy[k];
        lazy[k] = 0;
    }
}

void build(int k, int l, int r)
{
    len[k] = r - l + 1;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(ls(k), l, mid), build(rs(k), mid + 1, r);
}

void update(int k, int l, int r, int L, int R, int val)
{
    if(L <= l && r <= R)
    {
        lazy[k] += val;
        sum[k] += len[k] * val;
        return ;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if(L <= mid) update(ls(k), l, mid, L, R, val);
    if(R > mid) update(rs(k), mid + 1, r, L, R, val);
    sum[k] = sum[ls(k)] + sum[rs(k)];
}

ll query(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return sum[k];
    pushdown(k);
    int mid = (l + r) >> 1;
    if(R <= mid) return query(ls(k), l, mid, L, R);
    if(L > mid) return query(rs(k), mid + 1, r, L, R);
    return query(ls(k), l, mid, L, R) + query(rs(k), mid + 1, r, L, R);
}

int main()
{
    n = read();
    ll ans = 0;
    build(1, 1, n);
    for(int i = 1; i <= n; ++i)
    {
        a[i] = read();
        update(1, 1, n, last[a[i]] + 1, i, 1);
        last[a[i]] = i;
        ans += sum[1];
    }
    printf("%lld\n", ans);
    return 0;
}

F - Takahashi in Narrow Road

有 \(n\) 个人站在一排位置上，第 \(i\) 次命令第 \(T_i\) 个人到达 \(G_i\) 位置，人与人之间不会站在同一位置，也不会跨过对方，也就是让第 \(1\) 个人到达第四个人所在的位置，需要第二三四个人都向右移动一些步。问最少需要多少步能完成所有命令，命令必须按顺序完成。

发现一个人会把其他人推到某个位置，然后排成连续的一列，如果位置很少的话可以考虑区间覆盖，区间求和的一系列操作，但是 \(1e8\) 的位置很可能会都被到达过，空间不允许。

若设 \(x_i' = x_i - i\)，那么排成一列的人会在同一个位置。

设 \(G_i' = G_i - i\)，不妨设 \(x_i' < G_i'\)，找到最大的 \(j\) 满足 \(i \le j\)，\(x_j' \le G_i\)，那么第 \(i\) 到第 \(j\) 个人就是完成此次命令需要挪步的人，总步数为 \(\sum_{l=i}^{j}(G_i'-X_l')\)，同时将这 \(j-i+1\) 个人的位置更新为 \(G_i'\)。

发现对于每个命令，每次最多出现一个新位置，空间允许。

先离散化，线段树维护每一段区间有多少人，所有人的位置之和，快速找到第 \(i\) 个所在位置，找到在第 \(i\) 个位置及之前的人的个数，区间清空，单点加。

线段树开4倍空间！！！

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 6e5 + 5;
int n, Q;
int X[N], x[N], b[N], T[N], G[N], g[N];

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

ll lazy[N << 2], sum[N << 2], cnt[N << 2]; // 区间赋0标记

void pushup(int k)
{
    sum[k] = sum[ls(k)] + sum[rs(k)];
    cnt[k] = cnt[ls(k)] + cnt[rs(k)];
}

void pushdown(int k)
{
    if(lazy[k])
    {
        sum[ls(k)] = sum[rs(k)] = 0;
        cnt[ls(k)] = cnt[rs(k)] = 0;
        lazy[ls(k)] = lazy[rs(k)] = 1;
        lazy[k] = 0;
    }
}

void update1(int k, int l, int r, int pos, int Size)
{
    if(l == r)
    {
        sum[k] += 1ll * Size * b[pos];
        cnt[k] += Size;
        return ;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if(pos <= mid) update1(ls(k), l, mid, pos, Size);
    else update1(rs(k), mid + 1, r, pos, Size);
    pushup(k);
}

void update2(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
    {
        sum[k] = cnt[k] = 0;
        lazy[k] = 1;
        return ;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if(L <= mid) update2(ls(k), l, mid, L, R);
    if(R > mid) update2(rs(k), mid + 1, r, L, R);
    pushup(k);
}

pair<ll, ll> query(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return pair<ll, ll>(sum[k], cnt[k]);
    pushdown(k);
    int mid = (l + r) >> 1;
    if(R <= mid) return query(ls(k), l, mid, L, R);
    if(L > mid) return query(rs(k), mid + 1, r, L, R);
    pair<ll, ll> s1 = query(ls(k), l, mid, L, R), s2 = query(rs(k), mid + 1, r, L, R);
    return pair<ll, ll>(s1.first + s2.first , s1.second + s2.second );
}

int get(int k, int l, int r, int id)
{
    if(l == r) return l;
    pushdown(k);
    int mid = (l + r) >> 1;
    if(cnt[ls(k)] >= id) return get(ls(k), l, mid, id);
    else return get(rs(k), mid + 1, r, id - cnt[ls(k)]);
}

int getcnt(int k, int l, int r, int pos)
{
    int mid = (l + r) >> 1;
    pushdown(k);
    if(pos == mid) return cnt[ls(k)];
    if(pos < mid) return getcnt(ls(k), l, mid, pos);
    if(pos > mid) return cnt[ls(k)] + getcnt(rs(k), mid + 1, r, pos);
}

int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) b[i] = X[i] = read() - i;
    Q = read();
    for(int i = 1; i <= Q; ++i)
    {
        T[i] = read(), G[i] = read();
        b[n + i] = G[i] = G[i] - T[i];
    }
    // for(int i = 1; i <= n; ++i) printf("%d ", X[i]);
    // printf("\n");
    // for(int i = 1; i <= Q; ++i) printf("%d ", G[i]);
    // printf("\n");
    // for(int i = 1; i <= n + Q; ++i) printf("%d ", b[i]);
    // printf("\n");
    sort(b + 1, b + n + Q + 1);
    int nn = unique(b + 1, b + n + Q + 1) - (b + 1);
    for(int i = 1; i <= n; ++i) x[i] = lower_bound(b + 1, b + nn + 1, X[i]) - b;
    for(int i = 1; i <= Q; ++i) g[i] = lower_bound(b + 1, b + nn + 1, G[i]) - b;
    for(int i = 1; i <= n; ++i) update1(1, 1, nn, x[i], 1);
    // for(int i = 1; i <= n; ++i) printf("%d ", x[i]);
    // printf("\n");
    // for(int i = 1; i <= Q; ++i) printf("%d ", g[i]);
    // printf("\n");
    // for(int i = 1; i <= n + Q; ++i) printf("%d ", b[i]);
    // printf("\n");
    ll ans = 0;
    for(int i = 1; i <= Q; ++i)
    {
        int pos = get(1, 1, nn, T[i]);
        if(pos == g[i]) continue;
        pair<ll, ll> now = pair<ll, ll>(0ll, 0ll);
        // printf("i = %d, T = %d, pos = %d, g = %d\n", i, T[i], pos, g[i]); 
        if(pos < g[i])
        {
            int CNT = getcnt(1, 1, nn, pos);
            now = query(1, 1, nn, pos + 1, g[i]);
            // printf("CNT = %d, sum = %lld, cnt = %lld\n", CNT, now.first , now.second );
            now.second += CNT - T[i] + 1, now.first += 1ll * (CNT - T[i] + 1) * b[pos];
            update1(1, 1, nn, pos, -(CNT - T[i] + 1));
            update2(1, 1, nn, pos + 1, g[i]);
            update1(1, 1, nn, g[i], now.second );
        }else
        {
            int CNT = 0;
            if(pos > 1) CNT = getcnt(1, 1, nn, pos - 1);
            now = query(1, 1, nn, g[i], pos - 1);
            // printf("CNT = %d, sum = %lld, cnt = %lld\n", CNT, now.first , now.second );
            now.second += T[i] - CNT, now.first += 1ll * (T[i] - CNT) * b[pos];
            update1(1, 1, nn, pos, -(T[i] - CNT));
            update2(1, 1, nn, g[i], pos - 1);
            update1(1, 1, nn, g[i], now.second );
        }
        // printf("now.first = %lld, second = %lld\n", now.first , now.second );
        ans += abs(b[g[i]] * now.second - now.first );
        // printf("add = %lld\n", abs(b[g[i]] * now.second - now.first ));
    }
    printf("%lld\n", ans);
    return 0;
}

G - Lexicographically Smallest Permutation

给定序列 \(A\) 和序列 \(p\)，一次操作是用 \(A_{p_i}\) 替换 \(A_i\)，问替换任意次后，字典序最小的 \(A\) 序列是什么？

容易发现对于每一个置换环，贪心的确定其在序列 \(A\) 上第一次出现的位置放哪个数即可。

对于第一个置换环，假设经过 \(x\) 次替换使得第一个数最小。

对于第二个置换环，按照每个数从小到大枚举，设需要 \(y_i\) 次替换使得第一个数是这个环中第 \(i\) 小的数。

设前面的置换环的长度的最小公倍数为 \(Y\)，那么只需要满足 \(kY + x \equiv y_i (\mod len)\)。

依次判断同余式能否成立即可。

至多每个数都被判断一次，判断一次是 \(\log\) 的 \(\operatorname{EXgcd}\)。

但是 \(\operatorname{lcm}\) 会很大，需要高精度。

标签：AtCoder,return,Beginner,int,mid,long,pos,371,now
From： https://www.cnblogs.com/wenqizhi/p/18416769

相关文章

  • 南沙C++信奥老师解一本通题 1371：看病
    ​ 【题目描述】有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判......
  • ABC371 Review
    ABC371ReviewA分类讨论题，过B模拟题，过C题意给出一张原始图\(G\)，和一张待修改图\(H\)，每次对\(H\)进行一次操作可以花费相应的代价删除已经存在的一条边或者是添加未存在的边。问使得两张图同构的最小代价\(W\)是多少。思路以为是什么高级的算法，但是又放在了C......
  • [ABC371D] 1D Country 线段树解法
    其实这题还可以用值域线段树来做的。。。考虑到\([-1e9,1e9]\)的数据范围，则一般的线段树绝对会MLE，但同时我们注意到点的个数只有\(2e5\)个，考虑使用动态开点线段树。即对于每个村庄，看做一个点，所以我们的线段树无需模拟满二叉树。由于\(log_2(2e9)\approx30\)，所以我们的线......
  • 题解：AT_abc371_c [ABC371C] Make Isomorphic
    题目大意有两个简单无向图，你每一次可以给第二个图添上或去掉一条边，有相应花费，问将两个图变为同构最少需要花费多少钱。思路观察数据范围，可以发现NNN非常小，可以考虑枚......
  • [ABC371D] 1D Country 题解
    这题，怎么说呢，\(STL\)大法好。前置芝士：lower_pound函数在结构体上的使用。那其实这题便是一个二分前缀和的水题了。结构体存储每个村庄的距离\(x\)，人口\(d\)。对于每个输入的\([l,r]\)二分查找其对应的村庄，进行一次答案的统计，输出即可。代码:#include<bits/stdc++.......
  • ABC371
    呜呜呜，第一次打完完整的ABC。才打了2000多名，太菜了。（A-Jiro十分简单，分讨即可。点击查看代码#include<iostream>#include<cstdio>usingnamespacestd;chara,b,c;intmain(){ cin>>a>>b>>c; if(a=='>'){ if(b=='>'){ if(c==&#......
  • AtCoder Beginner Contest 371
    A-Jiro(abc371A)题目大意三个人，给定他们相互之间的大小关系。问谁在中间。解题思路排个序，大小结果就是题目给的，因为问的是中间是谁，所以写的时候并没在意是升序排还是降序排。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmai......
  • AtCoder Beginner Contest 371
    ABC371总结AtCoderBeginnerContest371一些废话想着以后换一种方式写总结，不再以那种题解形式，写起来又累又难写，只对其中部分有意思的题目写出完整的题解。就是以随笔的形式，在打完比赛后写出自己的一些感悟，每道题做的过程中的一些思路、用时和需要改进的地方，就是类似随笔之类的......
  • AtCoder Beginner Contest 371
    https://atcoder.jp/contests/abc371C:暴力。思路是把1-8的点映射到全排列上面，然后把有的点去掉没的点加上取ans最小值。这题复杂度是\(8！\times7\times4\),暴力求全排列即可（第一次写暴力全排列思索了一会复杂度#include<bits/stdc++.h>usingnamespacestd;#definepiipai......
  • 题解 [ABC371G] Lexicographically Smallest Permutation（中文/English）
    本题解提供英文版，位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.官方题解竟然用Python来算高精度lcm，我来提供一个可以避免一切大整数运算的方法。考察\(u\getsP_u\)这张图的每个置换环。为了使答案字典序最小，显然需要从前往后......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99