Codeforces Round 912 Div2 • santisify Site

A Halloumi Boxes ↗#

题目大意#

给定一个数组A,我们可以对数组惊醒多次操作,操作如下: 我们可以将数组中的某一段倒置,但是长度不能超过K,例如:反转子数组意味着选择两个索引i和j(其中 1 <= i <= j <= n ) 并将数组 $a_1,a_2,\cdots,a_n$ 改为 $a_1,a_2,\cdots,a_{i−1},a_{j},a_{j−1},\cdots,a_{i},a_{j+1},…,a_{n-1},a_n \quad (j − i + 1 \le k )$ 。

分析#

由于可以操作多次,那么我们可以判断下k是否为1:

若k = 1时, 我们只能反转一个元素,显然是无效的, 我们就只需要判断数组是否为有序

若k > 1时,显然是可行的

代码#

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve () {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n, 0), b(n, 0);
    for(int i = 0 ; i < n ; i ++)
        std::cin >> a[i], b[i] = a[i];

    std::sort(b.begin (), b.end ());
    bool f = true;
    for(int i = 0 ; i < n ; i ++){
        if(a[i] != b[i]){
            f = false;
            break;
        }
    }
    if(f)
        std::cout << "YES" << endl;
    else {
        if(k > 1)
            std::cout << "YES" << endl;
        else
            std::cout << "NO" << endl;
    }
}


signed main () {
    std::ios::sync_with_stdio (false);
    std::cin.tie (nullptr), std::cout.tie (nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve ();
    return 0;
}

cpp

B StORage room ↗#

题目大意#

给定一个数n,和一个n*n的数组M,数组 $M_{i,j}$ 表示为: $M_{i,j} = \begin{cases} a_i|a_j,(i \not= j)\\\\ 0, (i == j)\end{cases}(M_{i,j} < 2 ^{30})$

让我们判断是否存在这样的一个数组a满足上式,若存在输出YES和数组a 否则输出NO

分析#

现在我有两个数x, y,如果我将这两个数进行或运算后(w = x | y), 在二进制状态下x和y在某一位上有一个为1,则该位为1通过这个我们可以发现在 $M_i$ 中, $M_{i,0} = a_i | a_0, M_{i,1} = a_i | a_1, ........, M_{i,n - 1} = a_i | a_{n - 1}$ , 我们可以通过与运算将 $a_i$ 计算出来, 但是在运算时我们需要排除 $M_{i,j}(i==j)$ ; 在计算完后我们可以遍历一次M数组,判断 $M_{i,j}=a_i|a_j(i \not= j)$

参考代码#

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve () {
    int n;
    std::cin >> n;
    std::vector<int> a(n, 0);
    std::vector<std::vector<int> > m(n, std::vector<int> (n, 0));
    for(int i = 0 ; i < n ; i ++){
        int x = -1;
        for(int j = 0;j < n;j ++){
            std::cin >> m[i][j];
            if(i != j){
                if(x == -1)
                    x = m[i][j];
                x &= m[i][j];
            }
        }
        a[i] = x;
    }
    if(n == 1){//特殊情况,可任意输出一个数
        std::cout << "YES" << endl << 1 << endl;
        return ;
    }
    auto check = [&] (){
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < n ; j ++){
                int x = a[i] | a[j];
                if(m[i][j] != x && i != j){
                    return false;
                }
            }
        }
        return true;
    };
    if(check()){
        std::cout << "YES" << endl;
        for(int i = 0 ; i < n ; i ++)
            std::cout << a[i] << " ";
        std::cout << endl;
    }
    else
        std::cout << "NO" <<endl;
}


signed main () {
    std::ios::sync_with_stdio (false);
    std::cin.tie (nullptr), std::cout.tie (nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve ();
    return 0;
}

cpp

C Theofanis’ Nightmare ↗(贪心)#

题目大意#

给定一个数组a,大小为n,现在将数组a分割成几个非空子数组,并且保证每个元素只在一个一个子数组中,例如，数组 [1,−3,7,−6,2,5]可以划分为 [1][−3,7][−6,2][5]。这种分割的值等于 $\sum_{i=1}^k i*sum_i$ ，其中k是我们将数组分割成的子数组的个数， $sum_i$ 是第i个子数组的和。这个数组的值为 $[1][−3,7][−6,2][5]=1\times 1+2\times (−3+7)+3\times (−6+2)+4\times5=17$ 现在让我们求分割的最大值为多少?

分析#

先考虑每个子段的数字贡献，i* sum_i也可以转化为该子段中每个数字被加上了i次。那么就可以把乘法转化为加法。

然后考虑怎么划分子段最优，如果从前往后考虑，很难判断是否该将当前数字划分为一个新子段的起点。因此，需要从后往前遍历，统计i∼n之间的数字总和，为了使答案尽可能大，那么只要当前数字总和大于等于0，就可以将当前位置划分给一个新的子段起点。

此时，划分出一个新的起点后，那么后面所有的数字均需要再被加上一次，不难发现，此时要加上的就是维护的数字总和。

由于第一个元素也可能被划分到一个新的子段中，为了避免重复计算，当遍历到第一个元素时，必须将当前元素视为子段起点，加上维护的数字总和。

代码#

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve () {
    int n;
    std::cin >> n;
    std::vector<int> a(n, 0);
    for(int i = 0 ; i < n ; i ++)
        std::cin >> a[i];
    int ans = 0, w = 0;
    for(int i = n - 1; i >= 0 ; i --){
        w += a[i];
        if(i == 0 || w > 0)
            ans += w;
    }
    std::cout << ans << endl;
}


signed main () {
    std::ios::sync_with_stdio (false);
    std::cin.tie (nullptr), std::cout.tie (nullptr);
    int Lazy_boy = 1;
    std::cin >> Lazy_boy;
    while (Lazy_boy--)
        solve ();
    return 0;
}

cpp

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve () {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1, 0ll), s(n + 1, 0ll);
    for(int i = 1 ; i <= n ; i ++)
        std::cin >> a[i], s[i] = s[i - 1] + a[i];
    int ans = 0, w = 0;
    for(int i = 1; i <= n ; i ++){
        if(i == 1 || s[n] - s[i - 1] >= 0)
            w ++;
        ans += w * a[i];
    }
    std::cout << ans << endl;
}


signed main () {
    std::ios::sync_with_stdio (false);
    std::cin.tie (nullptr), std::cout.tie (nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve ();
    return 0;
}

cpp

D1 Maximum And Queries (easy version) ↗#

题目大意#

给出一个长度为n的数组a，并进行q次询问，每次询问为：你可以进行k次操作，每次从数组a中选择一个元素，让这个元素 + 1。问：经过q次操作后, $a_1,a_2,.....,a_n$ 的与的最大值是多少注：每次询问都是独立的，不会保留前面询问的操作结果。

分析#

由于每次询问都是独立的，那么修改不能在原数组上进行，需要将原数组元素复制到其他数组中再进行操作。题目数据规定了 $n\times q≤10^5$ ，那么可以认为最大的数据就是对长度为 $10^5$ 的数组进行一次询问。由于给出的 $k≤10^{18}$ ，那么当数组中只有一个元素时，最大可能的结果为 $10^{18}+10^6≈2^{60}$ ，因此需要一个大于60的数组记录与运算后的结果每位二进制数是多少。对于每次询问，从二进制高位开始往低位进行遍历，每次检查当前剩余的k是否还能将数组中所有数的当前二进制位修改为1 如果可以，进行修改，并记录在答案数组中，如果不行，继续遍历更低的二进制位。结束修改后，将数组中记录的信息转化为十进制数即可。

本题数据较大，需要注意使用左移运算需要使用1ll将1转化为long long类型再进行运算，计算花费时也要考虑如果超过操作次数就该退出检查，避免数据溢出。

代码#

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
const int N = 1e5 + 5;

int a[N], b[N], ans[105];
int n, q;

int getCost(int x, int k) {
    int cost = 0;
    for (int j = 1; j <= n; j++) {
        if ((b[j] & (1ll << x)) == 0) {
            //使用位运算计算将b[j]的第x位二进制修改为1需要加上多少
            cost += (1ll << x) - ((1ll << (x + 1)) - 1ll & b[j]);
        }
        if (cost > k) return cost; //超过k就返回，避免数据溢出
    }
    return cost;
}

void solve() {
    std::cin >> n >> q;
    for(int i = 1; i <= n ; i ++)
        std::cin >> a[i];
    while(q --){
        int k;
        std::cin >> k;
        memset(ans, 0, sizeof(ans));
        for (int i = 1; i <= n; i++)
            b[i] = a[i];
        for (int i = 60; i >= 0; i--) {//检查第i位结果与运算的结果是否可能为1
            int cost = getCost(i, k);
            if (cost <= k) {//花费在操作次数范围内
                ans[i] = 1;//与运算结果可以为1
                k -= cost;
                for (int j = 1; j <= n; j++) {
                    if ((b[j] & (1ll << i)) == 0) {
                        //通过或运算将2^i位修改为1，再通过与运算将后面数字清0
                        b[j] = ((b[j] | (1ll << i)) & (1ll << i));
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= 60; i++)
            res |= (ans[i] << i);//这里ans[i]如果不是long long类型也会发生溢出
        std::cout << res << endl;
    }
}


signed main () {
    std::ios::sync_with_stdio (false);
    std::cin.tie (nullptr), std::cout.tie (nullptr);
    int Lazy_boy = 1;
    // std::cin >> Lazy_boy;
    while (Lazy_boy--)
        solve ();
    return 0;
}

cpp