Codeforces Round #481 (Div. 3)

题目链接
A  00:03
B  00:06
C  00:14
D  00:31
E  00:40
F  00:48
G  01:07

A. Remove Duplicates

给你一个序列,你要把重复的数只保留最右边的

    int n = read();
    for(int i = 1 ; i <= n ; i ++){
        a[i] = read();
        b[a[i]] = i;
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(b[a[i]] == i) ans ++;
    }
    cout << ans << endl;
    for(int i = 1 ; i <= n ; i ++){
        if(b[a[i]] == i) cout << a[i] << " ";
    }

B. File Name

你需要让字符串里不出现"xxx",每次可以删除一个字符,让删除的字符数量最小
只需要统计"xxx"的个数输出即可

    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
    for(int i = 0 ; i < Len(s) - 2 ; i ++){
        if(s[i] == 'x' && s[i + 1] == 'x' && s[i + 2] == 'x') ans ++;
    }
    cout <<ans << endl;

C. Letters

按顺序给你每栋楼的房间数
问你i个房间是第几栋楼的第几个房间

    int n = read(), m = read();
    for(int i = 1 ; i <= n ; i ++){
        b[i] = read();
        a[i] = a[i - 1] + b[i];
    }
    for(int i = 1 ; i <= m ; i ++){
        int x = read();
        int y = lower_bound(a, a + n + 1, x) - a;
        x -= a[y - 1];
        cout << y << " " << x << endl;
    }

D. Almost Arithmetic Progression

你有一个序列,你可以对每个数+1或-1,让这个序列成为等差序列,求最小的操作次数
很显然你需要确认公差是什么,因此枚举序列前两项可能值,直接暴力维护后面的序列,统计合法的最小修改数

int minx(int a, int b){if(a == -1) return b; if(b == -1) return a; if(a < b) return a; return b;}
int a[200005];
int b[200005];
int res = -1, n;
void ddd(int t1, int t2){
    int sum = 0, d;
    sum += (bool)t1;
    sum += (bool)t2;

    b[1] = a[1] + t1;
    b[2] = a[2] + t2;
    d = b[2] - b[1];
    for(int i = 3 ; i <= n ; i ++){
        if(a[i] - b[i - 1] == d){
            b[i] = a[i];
        }else if(a[i] + 1 - b[i - 1] == d){
            b[i] = a[i] + 1;
            sum ++;
        }else if(a[i] - 1 - b[i - 1] == d){
            b[i] = a[i] - 1;
            sum ++;
        }else{
            sum = -1;
            break;
        }
    }
    res = minx(res, sum);
   // cout<<"xx" << sum << endl;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    clock_t c1ockck = clock();
    // ..........................................................
    n = read();
    for(int i = 1 ; i <= n ; i ++) a[i] = read();
    if(n <= 2){
        cout << 0 << endl;
        return 0;
    }
    for(int i = -1 ; i <= 1 ; i ++)
        for(int j = -1 ; j <= 1 ; j ++)
            ddd(i, j);
    cout << res << endl;
    // ..........................................................
    cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
    return ~~(0^_^0);
}

E. Bus Video System

你知道公交车总容纳人数和每站的上下人数量,你需要确认最初公交车上有多少人
显然动态维护一下最初的可容纳人数
统计最小人数的最大值和最大人数的最小值输出即可

    int n = read(), m = read();
    int l = 0, r = m, lx = 0, rx = m;
    for(int i = 1 ; i <= n ; i ++){
        int x = -read();
        r -= x;
        l -= x;
        lx = max(lx, l);
        rx = min(rx, r);
    }
    if(lx > rx) cout << 0 << endl;
    else cout << rx - lx + 1 << endl;

F. Mentors

你知道每个人的能力的值和那些人直接有矛盾,如何一个人想收另一个人为徒,必须是没有矛盾且能力值高
你需要输出每个人的能收的徒弟最大数量
只需要先让有矛盾的人能力值高的-1就好

    int n = read(), m = read();
    for(int i = 1 ; i <= n ; i ++){
        b[i] = a[i] = read();
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1 ; i <= m ; i ++){
        int u = read(), v = read();
        if(a[u] > a[v]) ans[u] --;
        if(a[v] > a[u]) ans[v] --;
    }
    for(int i = 1 ; i <= n ; i ++){
        int x = lower_bound(b + 1, b + 1 + n, a[i]) - b - 1;
        cout << ans[i] + x << " ";
    }

G. Petya's Exams

你在第s_i天知道了第i门课在第d_i天考试,你还需要c_i天复习时间,问你应该怎安排复习时间
贪心,每天选离考试最近的那一课的复习即可

    int n = read(), m = read(), flag = false;;
    for(int i = 1 ; i <= m ; i ++){
        int x = read(), y = read(), z = read();
        array<int, 3> tmp = {-y, i, z};
        a[x].push_back(tmp);
        ans[y] = m + 1;
    }
    for(int i = 1 ; i <= n ; i ++){
        for(auto x : a[i]) q.push(x);
        if(!q.empty() && ans[i] == 0){
            auto x = q.top(); q.pop();
            if(-x[0] < i){
                flag = true;
                break;
            }
            ans[i] = x[1];
            x[2] --;
            if(x[2]) q.push(x);
        }
    }
    if(flag || !q.empty()){
        cout << -1 << endl;
    }else{
        for(int i = 1 ; i <= n ; i ++){
            cout << ans[i] << " ";
        }
    }
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注