分类导航

C&C++ 发布时间：2022-04-03 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了Codeforces Beta Round #19，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

#include <bits/stdc++.h>
using namespace std;
 
const int N = 60;
char name[n][n];
map<String,int> mp;
char s[n];
 
struct P {
    int id,point;
    int dif,goal;
    bool operator < (const P &rhs) const {
        if (point == rhs.point && goal - dif == rhs.goal - rhs.dif) return goal > rhs.goal;
        if (point == rhs.point) return goal - dif > rhs.goal - rhs.dif;
        return point > rhs.point;
    }
} p[n];
 
int main() {
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%s",name[i]);
        mp[name[i]] = i;
        p[i].id = i;
    }
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        int pp,qq;
        scanf("%s%d:%d",s,&pp,&qq);
        int j = 0;
        int len = strlen(s);
        char s1[50] = {};
        char s2[50] = {};
        int p1 = 0,p2 = 0;
        for (; s[j] != ‘-‘; j++) s1[p1++] = s[j];
        j++;
        for (; j < len; j++) s2[p2++] = s[j];
        int a = mp[s1],b = mp[s2];
        p[a].goal += pp,p[b].goal += qq;
        p[a].dif += qq; p[b].dif += pp;
        if (pp > qq) p[a].point += 3;
        else if (pp == qq) p[a].point++,p[b].point++;
        else p[b].point += 3;
    }
    sort(p,p + n);
    vector<String> ans;
    for (int i = 0; i < n / 2; i++)
        ans.push_BACk(name[p[i].id]);
    sort(ans.begin(),ans.end());
    for (auto x: ans)
        cout << x << ‘\n‘;
    return 0;
}

View Code

B. Checkout Assistant

有$n$个商品，每个商品价格$c_i$，售货员处理这件商品需要时间$t_i$，偷走一个商品需要$1$个单位时间，问怎么安排这些商品的结账顺序可以使的最后要还的钱最少。

如果让一件商品去结账，相当于花$c_i$块钱，能偷走买走至多$t_i + 1$个商品，要使最后总花费最小，那么就是01背包了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = 2020;
ll dp[n];
int w[n];
ll c[n];
 
int main() {
    memset(dp,0x3f,sizeof dp);
    dp[0] = 0;
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf("%d%lld",&w[i],&c[i]),w[i]++;
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= 1; j--) {
            dp[j] = min(dp[j],dp[max(j - w[i],0)] + c[i]);
        }
    }
    printf("%lld\n",dp[n]);
    return 0;
}

View Code

C. Deletion of Repeats

有一个序列，每种元素至多出现$10$次，如果有一个子串前一半等于后一半，那么把前一半及以前的字符全部删掉，要求从短的以及较左的地方开始删，问最后这个串长什么样。

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

const int N = 1e5 + 7;
int a[n],v[n];
vector<int> G[n];

int main() {
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        v[i] = a[i];
    }
    sort(v + 1,v + 1 + n);
    int cnt = unique(v + 1,v + 1 + n) - v - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(v + 1,v + 1 + cnt,a[i]) - v;
        G[a[i]].push_BACk(i);
    }
    int Now = 0;
    for (int i = 2; i <= n; i++) {
        bool flag = 0;
        for (auto pos: G[a[i]]) {
            flag = 1;
            if (pos >= i) conTinue;
            if (n - i + 1 < i - pos) conTinue;
            if (pos <= Now) conTinue;
            flag = 0;
            for (int j = 1; j < i - pos; j++) {
                if (a[i + j] != a[pos + j]) {
                    flag = 1;
                    break;
                }
            }
            if (!flag) break;
        }
        if (!flag) Now = i - 1;
    }
    printf("%d\n",n - Now);
    for (int i = Now + 1; i <= n; i++)
        printf("%d%c",v[a[i]]," \n"[i == n]);
    return 0;
}

View Code

D. Points

一个二维坐标系，有三个操作。

1.加点

2.删点

3.查询严格在$(x,y)$右上角的点，输出$x$坐标最小的那个点，如果有相同的，则输出$y$最小的，不存在输出$-1$

因为存在修改操作，那么就不能离线做了，用线段树维护$x$坐标下$y$坐标的最大值，然后就变成了查询$\left[x + 1,inf\right]$中最小的$x$其$y$大于要查询的$y$，那么就又是先查左及剪枝的那个写法了。然后找到对应$x$坐标后，加点删点用一个set维护每个$x$坐标出现过$y$的坐标，在这个set里面lower_bound一下就好了，刚开始都插入0以及所有$y$坐标都加个一会好操作很多。

@H_618_634@

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 7;
 
struct Seg {
    #define lp p << 1
    #define rp p << 1 | 1
    int mx[N << 2];
    void pushup(int p) {
        mx[p] = max(mx[lp],mx[rp]);
    }
    void update(int p,int l,int r,int x,int val) {
        if (l == r) {
            mx[p] = max(val,mx[p]);
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) update(lp,l,mid,x,val);
        else update(rp,mid + 1,r,val);
        pushup(p);
    }
    void change(int p,int val) {
        if (l == r) {
            mx[p] = val;
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) change(lp,val);
        else change(rp,val);
        pushup(p);
    }
    int query(int p,int y,int val) {
        if (x > y) return -1;
        if (mx[p] <= val) return -1;
        if (l == r) return l;
        int mid = l + r >> 1;
        if (x <= mid) {
            int temp = query(lp,y,val);
            if (temp != -1) return temp;
        }
        return query(rp,val);
    }
} seg;
 
struct OPT {
    int opt;
    int x,y;
} o[n];
int v[n];
set<int> st[n];
 
int main() {
//    freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) {
        char s[10] = {};
        scanf("%s%d%d",&o[i].x,&o[i].y);
        if (s[0] == ‘a‘) o[i].opt = 0;
        else if (s[0] == ‘r‘) o[i].opt = 1;
        else o[i].opt = 2;
        v[i] = o[i].x;
        o[i].y++;
    }
    sort(v + 1,v + 1 + n) - v - 1;
    for (int i = 1; i <= cnt; i++) st[i].insert(0);
    for (int i = 1; i <= n; i++) 
        o[i].x = lower_bound(v + 1,o[i].X) - v;
    for (int i = 1; i <= n; i++) {
        if (o[i].opt == 0) {
            st[o[i].x].insert(o[i].y);
            seg.update(1,1,cnt,o[i].x,o[i].y);
        } else if (o[i].opt == 1) {
            st[o[i].x].erase(o[i].y);
            set<int>::iterator it = st[o[i].x].end();
            it--;
            int res = 0;
            res = *it;
            seg.change(1,res);
        } else {
            int pos = seg.query(1,1,o[i].x + 1,o[i].y);
            if (pos == -1) printf("-1\n");
            else {
                int ans = *st[pos].upper_bound(o[i].y);
                printf("%d %d\n",v[pos],ans - 1);
            }
        }
    }
    return 0;
}