Codeforces Round #501 (Div. 3)

题目链接
AC时间(相对于比赛开始时间,F题为比赛时未通过)

A  00:04
B  00:28
C  00:34
D  01:08
E1 01:59
E2 01:58
F  ----

A. Points in Segments

A题求没有被线段覆盖的点
差分跑前缀和能过很大的数据范围,而且代码量上没有什么难度
不过100 \times 100的数据可以之间暴力跑区间的点
不过A题过的时间太慢,应该是很久没有写代码的问题,

    int n = read(), m = read();
    for(int i = 1 ; i <= n ; i ++){
        int l = read(), r = read();
        a[l] ++;
        a[r + 1] --;
    }
    int tot = 0;
    for(int i = 1 ; i <= m ; i ++){
         a[i] += a[i - 1];
         if(!a[i]) tot ++;
    }
    cout << tot << endl;
    for(int i = 1 ; i <= m ; i ++){
        if(!a[i]) cout << i << " ";
    }

B. Obtaining the String

B题你可以交换两个相邻的字符,问能否在10^4次操作里使s串和t串相同
因为本题不要求最小化交换次数并且n = 50因此可以对于每一个s[i]t[i]不同的就暴力去s[i + 1, n]里面去找能否替换
b题被卡了一个地方,递减循环写成j++,输出flag的发现flag特别大才发现的错误(身败名裂

    int n; cin >> n;
    string s,t; cin >> s >> t;
    for(int i = 0 ; i < n ; i ++){
        if(s[i] != t[i]){
            int flag = -1;
            for(int j = i + 1 ; j < n ; j ++){
                if(s[j] == t[i]){
                    flag = j;
                    break;
                }
            }
            if(flag == -1 || s[flag] != t[i]){
                cout << -1 << endl;
                return 0;
            }
            for(int j = flag - 1 ; j >= i ; j --) ans.push_back(j+1), swap(s[j], s[j + 1]);
            //cout << flag - 1 << " " <<  i << endl;
        }
       // cout << s << endl;
    }
    cout << Len(ans) << endl;
    for(auto x : ans) cout << x << " ";

C. Songs Compression

c题你有n对数[a_i,b_i](a_i > b_i)每对数里面选一个使选择的n个数之和小于m,最小化选择b的数量
显然这道题就优选全部选a_i,然后每次选择替换掉a_i-b_i最大的数换成b_i,其实只需要sort一遍,不过比赛的时候没有想这么多之间用了优先队列

    int n = read(), m = read();
    ll k = 0;
    int cnt = 0;
    for(int i = 1 ; i <= n ; i ++){
        a[i] = read();
        b[i] = read();
        k += a[i];
        q.push(make_pair(a[i] - b[i], i));
    }
    while(k > m && !q.empty()){
        auto Q = q.top().second; q.pop();
        k -= a[Q];
        k += b[Q];
        cnt ++;
    }
    if(k > m) cout << -1 << endl;
    else cout << cnt << endl;

D. Walking Between Houses

给你三个数n,k,s(2≤n≤10^9, 1≤k≤2⋅10^5, 1≤s≤10^{18})
你需要把s拆成k个[1~n-1]的数之和
看到这道题第一想法贪心
优先把s尽可能的拆成n-1
如果发现k有剩余那就把剩下来的那个数拆成若干个1,若是k还有剩余,那么就从最初的若干个n-1中拆出来1,这个使保证序列里面只有若干个n-1和1再加上一共非n-1和1的数,这样在n-1只是在序列端点反复横跳然后再往序列中间跳一个数接下来就一直在序列里面走即可,若是中间不止有一个非n-1和1则可能使本身有解的情况弄成无解的情况

int n = read(), k = read(), s = read();
    if(s < k || k * (n - 1) < s){
        cout << "NO" << endl;
        return 0;
    }
    int cnt = s;
    while(cnt >= n - 1){
        q.push(n - 1);
        cnt -= n - 1;
    }
    k -= Len(q);
    int tot = 0;
    if(cnt > k){
        tot = k - 1;
        q.push(cnt - k + 1);
        k = 0;
    }else if(cnt == k){
        tot = k;
        k = 0;
    }else if(cnt < k){
        tot = cnt;
        k -= cnt;
    }
    while(k && !q.empty()){
        auto Q = q.top(); q.pop();
        k ++;
        if(Q > k){
            tot += k - 1;
            q.push(Q - k + 1);
            k = 0;
        }else if(Q == k){
            tot += k;
            k = 0;
        }else if(Q < k){
            tot += Q;
            k -= Q;
        }
    }
    if(k){
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    int t = 1;
    while(!q.empty()){
        int Q = q.top(); q.pop();
        if(t + Q <= n) t = t + Q;
        else t = t - Q;
        cout << t << " ";
    }
    while(tot --){
        if(t + 1 <= n) t = t + 1;
        else t = t - 1;
        cout << t << " ";
    }

E. Stars Drawing

你需要用任意的星星去构建题目给定你的图,这个星星必须是十字形状,并且上下左右四边长度大于1(这里不算中间的那颗星星)
因为题目说放置的星星数量不超过n \times m因此一个格子只需要摆放一个最大的星星即可,因为较大的总会覆盖较小的
一开始我用的使二位前缀和来维护四边长度

    int l = a[i][j] - a[i - 1][j] - 1;
    int r = a[i][m] - a[i - 1][m] -(a[i][j] - a[i - 1][j]);
    int u = a[i][j] - a[i][j - 1] - 1;
    int d = a[n][j] - a[n][j - 1] - (a[i][j] - a[i][j - 1]);

不过wa5,发现这样维护的使这个点上下左右一共有多少个'*',不是题目中所描述的相连的星星
因此这个子问题就可以拆解成这个点上下左右各有多少相连的星星,
所以相当于维护四个方向的到一个点相连1的个数
这样就能尽可能的往每个'*'里面塞最大的星星
但是还有一个问题需要考虑的,就是如何查询所有是否和原图一模一样
首先能覆盖的'*'一定是从原图中找出来取min的所以说一定不会有原图是'.'的被计算成''*'
因此只需要记录原图'*'是否被我之前的所有操作全部覆盖即可
第一想法之间把每次修改的星星大小之间暴力覆盖
但是n和m都是10^3的这样写的复杂度是O(n^3)的显然不可写
因此差分就是很好的方法维护方式,只需要拆横行和纵行两个方向分别差分,这里的判断只需要判断在一个方向是能够被覆盖即可,不需要同时被覆盖,复杂度O(n^2)

int n, m; cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            cin >> c[i][j];
        }
    }
    for(int i = 1 ; i <= n ; i ++){
        int tot = 0;
        for(int j = 1 ; j <= m ; j ++){
            if(c[i][j] == '*') a[0][i][j] = tot ++;
            else tot = 0;
        }
        tot = 0;
        for(int j = m ; j >= 1 ; j --){
            if(c[i][j] == '*') a[1][i][j] = tot ++;
            else tot = 0;
        }
    }
    for(int i = 1 ; i <= m ; i ++){
        int tot = 0;
        for(int j = 1 ; j <= n ; j ++){
            if(c[j][i] == '*') a[2][j][i] = tot ++;
            else tot = 0;
        }
        tot = 0;
        for(int j = n ; j >= 1 ; j --){
            if(c[j][i] == '*') a[3][j][i] = tot ++;
            else tot = 0;
        }
    }
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            if(c[i][j] == '*'){
                int l = a[0][i][j];
                int r = a[1][i][j];
                int u = a[2][i][j];
                int d = a[3][i][j];
                //cout << i << " " << j << " " << l << r << u << d << endl;
                int mm = min(min(l, r), min(u, d));
                if(mm == 0) continue;
                ans.push_back({i, j, mm});
                va[i][j - mm] += 1;
                va[i][j + mm + 1] -= 1;
                vb[j][i - mm] += 1;
                vb[j][i + mm + 1] -= 1;
            }
        }
    }
    for(int i = 1 ; i <= max(n, m) ; i ++)
        for(int j = 1 ; j <= max(n, m) ; j ++)
            vb[i][j] += vb[i][j - 1];
    for(int i = 1 ; i <= max(n, m) ; i ++)
        for(int j = 1 ; j <= max(n, m) ; j ++)
            va[i][j] += va[i][j - 1];
    int flag = true;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            if(c[i][j] == '*'){
                if(vb[j][i] || va[i][j]) continue;
                flag = false;
            }
        }
    }
    if(!flag){
        cout << -1 << endl;
        return 0;
    }
    cout << Len(ans) << endl;
    for(auto x : ans)cout << x.a << " " << x.b << " " << x.c << endl;

F. Bracket Substring

写完E的时候还有一分钟比赛结束,就大致看了看F
emmmm
发现没看懂

点赞

发表评论

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