当前位置:   article > 正文

Codeforces Round 958 (Div. 2)

codeforces round 958 (div. 2)

C o d e f o r c e s R o u n d 958 ( D i v . 2 ) \Huge{Codeforces Round 958 (Div. 2)} CodeforcesRound958(Div.2)


比赛链接:https://codeforces.com/contest/1988

Problems A. Split the Multiset

题意

给出一个数组,每次可以选择数组中的一个数,并将其拆为不超过 k k k个数。

问最少需要几次可以构造出全 1 1 1数组(数组中只包含 1 1 1)。

思路

贪心的想,我们每次可以将选出的数字x拆为1+1+1+…+(x-k+1)。

那么结果即为:
⌈ n − 1 k − 1 ⌉ \left \lceil \frac{n-1}{k-1} \right \rceil k1n1

标程

#include<bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

void Solved() {
    int n, k; cin >> n >> k;

    n --;
    cout << (n + k - 2) / (k - 1) << endl;
}

signed main(void) {
    IOS

    int ALL = 1; 
    cin >> ALL;
    while(ALL -- ) Solved();
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

Problems B. Make Majority

题意

给出一个 01 01 01串,每次可以选择一个区间,若区间 s u m 0 ≥ s u m 1 sum_0\ge sum_1 sum0sum1,则将该区间变为一个数字 0 0 0,否则变为一个数字 1 1 1

求是否可以令 01 01 01串最后变为一个数字 1 1 1

思路

贪心的想,我们每次可以令全 0 0 0子串变为一个 0 0 0

然后容易发现,对比现在子串中的 0 , 1 0,1 0,1个数即可判断是否能构造出数字 1 1 1

标程

#include<bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define endl '\n'

void Solved() {
    int n; cin >> n;
    string s; cin >> s;

    int c0 = 0, c1 = 0;
    string s1;
    for(int i = 0; i < n;  i ++ ) {
        if(s[i] == '0') {
            c0 ++;
            if(i == 0 || (i && s[i - 1] == '1')) s1 = s1 + '0'; 
        }
        else {
            c1 ++;
            s1 = s1 + s[i];
        }
    }
    int x= 0, y = 0;
    for(int i = 0; i < s1.size(); i ++ ) {
        if(s1[i] == '0') x ++;
        else y ++;
    }
    
    if(c1 > c0) {
        cout << "YES\n"; return;
    }
    if(x < y) cout << "YES\n";
    else cout << "NO\n";
}

signed main(void) {
    IOS

    int ALL = 1; 
    cin >> ALL;
    while(ALL -- ) Solved();

    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

Problems C. Increasing Sequence with Fixed OR

题意

给出一个正整数 n n n,要求构造出一个序列:

  • a i ≤ n ( 1 ≤ i ≤ k ) a_i\le n(1\le i\le k) ain(1ik)

  • a i > a i − 1 ( 2 ≤ i ≤ k ) a_i>a_{i-1}(2\le i\le k) ai>ai1(2ik) a a a数组是严格递增的

  • a i   ∣   a i − 1 = n ( 2 ≤ i ≤ k ) a_i\,|\,a_{i-1}=n(2\le i\le k) aiai1=n(2ik) ∣ | 表示按位异或操作。

要求构造出一个符合要求的最长的序列并输出。

思路

考察位运算。

很明显能发现,构造出的数列的最后一项一定是 n n n,因此我们考虑从后往前构造。

为了符合递增和相邻数字异或和为 n n n,我们考虑从低位到高位,依次让二进制下为 1 1 1的位变为零;对于该题,这即是最优情况。

但是需要特判一下当二进制下只有 1 1 1 1 1 1时,能构造出来的序列只有其本身,特判即可。

标程

#include<bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long 
#define endl '\n'

void Solved() {
    int n; cin >> n;

    bitset<63> b(n);
    vector<int> a;

    int sum = 0, x = -1;
    for(int i = 0; i < 64; i ++ ) {
        if(b[i] == 1) {
            sum ++;
            a.push_back(i);
        }
        if(b[i] == 1 && x == -1) x = i;
    }
    x = 64 - x;
    if(sum == 1) {
        cout << "1\n" << n << endl; return;
    }

    int t = n, k = 0;
    vector<int> v;
    
    for(int i = a.size() - 1; i >= 0; i -- ) {
        k ++;
        t = t - (1ll << (a[i]));
        for(int j = i + 1; j < a.size(); j ++ ) {
            t |= (1ll << (a[j]));
        }
        v.push_back(t);
    }
    v.push_back(n);

    cout << k + 1 << endl;
    for(auto i : v) cout << i << ' ';
    cout << endl;

}

signed main(void) {
    IOS

    int ALL = 1; 
    cin >> ALL;
    while(ALL -- ) Solved();

    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

Problems D. The Omnipotent Monster Killer

题意

有一颗树,树上有若干的怪物,每个怪物有对应的攻击值;每回合都会按顺序发生下面两种情况:

  1. 所有存活的怪物攻击你,你的生命值将会减少其攻击值的总和。
  2. 选择若干怪物杀掉,选择的限制条件是:不能同时选择一条边上的两只怪物。

当杀死全部怪物后结束游戏。求最少受到的攻击值。

思路

树形DP

假设游戏进行的回合数为 L L L,怪物 i i i在第 S i S_i Si轮被杀死,并且满足同一条边上的两只怪物 i , j ( S i   ! = s j ) i,j(S_i ~!=s_j) i,j(Si !=sj),那么攻击值为:
∑ i = 1 L a i × S i \sum_{i=1}^{L}{a_i\times S_i} i=1Lai×Si
然后我们会发现本题的求解思路和这道题相同:P4395 [BOI2003] Gem 气垫车 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

关于树形DP练习,可以参考这一篇博客:树形dp(学习过程+刷题总结)

对于本题,我们可以用时间复杂度为 O ( n L 2 ) O(nL^2) O(nL2)来进行树形DP,用二维数组 f x , j f_{x, j} fx,j表示 S x = j S_x=j Sx=j时,以 x x x为根的子树价值之和的最小值,则有:
f x , j = S x × a x + ∑ i ∈ s o n ( x ) min ⁡ S J ! = S x ( f i , j ) f_{x,j}=S_x \times a_x+\sum_{i \in son(x)}\min_{S_J!=S_x}(f_{i,j}) fx,j=Sx×ax+ison(x)SJ!=Sxmin(fi,j)
那么答案即为:
min ⁡ 1 ≤ i ≤ L ( f 1 , i ) \min_{1\le i \le L}(f_{1, i}) 1iLmin(f1,i)
关于 L L L的范围: L ≤ ⌊ log ⁡ 2 n ⌋ + 1 L \le \left \lfloor \log_2n \right \rfloor +1 Llog2n+1

标程

#include<bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long 
#define endl '\n'

const int N = 3e5 + 10; 

vector<int> a(N), b[N], f[N];

void dfs(int x, int y) {
    for(int i = 1; i <= 20; i ++ ) {
        f[x][i] = i * a[x];
    }

    for(auto i : b[x]) {
        if(i == y) continue;
        dfs(i, x);
        for(int j = 1; j <= 20; j ++ ) {
            int mi = (j == 1 ? f[i][2] : f[i][1]);
            for(int k = 1; k <= 20; k ++ ) {
                if(j == k) continue;
                mi = min(mi, f[i][k]);
            }
            f[x][j] += mi;
        }
    }
}

void Solved() {
    int n; cin >> n;

    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        f[i].clear(); f[i].resize(21);
        b[i].clear();
    }

    for(int i = 1; i < n; i ++ ) {
        int x, y; cin >> x >> y;
        b[x].push_back(y); b[y].push_back(x);
    }

    dfs(1, 0);

    int res = f[1][1];
    for(int i = 1; i <= 20; i ++ ) {
        res = min(res, f[1][i]);
    }

    cout << res << endl;
}

signed main(void) {
    IOS

    int ALL = 1; 
    cin >> ALL;
    while(ALL -- ) Solved();

    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号