Codeforces Round 912 (Div. 2) A~D1,E

#include &lt;bits/stdc++.h&gt;

typedef long long LL;
using namespace std;
const int N = 1e6 + 5;

int a[N];

void solve() {
    int n, k;
    cin &gt;&gt; n &gt;&gt; k;
    int flag = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0 &amp;&amp; a[i] < a[i - 1]) {
            flag = 0;
        }
    }
    if (flag == 0 &amp;&amp; k <= 1) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

B.StORage r oom（位运算）

题意：

给出一个

n times n

$n \times n$ 的矩阵

$M$ ，矩阵

$M$ 中第

$i$ 行第

$j$ 列的元素表示

∣

a_i | a_j

$a_{i} ∣ a_{j}$ 的结果，问能否找出矩阵对应的

$a$ 数组。

如果有多种答案，输出任意一个即可。

分析：

既然

M_{i,j}

$M_{i, j}$ 表示

∣

a_i | a_j

$a_{i} ∣ a_{j}$ ，且只要找到一组合法的答案即可，那么让

a_i

$a_{i}$ 就等于

M_{i, 1} & M_{i, 2} & … & M_{i, n}

$M_{i, 1} &a mp; M_{i, 2} &a m p;\dots&a m p; M_{i, n}$ ，再检查生成的

$a$ 数组是否满足

$M$ 矩阵即可。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e3 + 5;

int a[N][N], ans[N];

void solve() {
    memset(ans, -1, sizeof(ans));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (i != j) {
                if (ans[i] == -1) {
                    ans[i] = a[i][j];
                } else {
                    ans[i] &amp;= a[i][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && ((ans[i] | ans[j]) != a[i][j])) {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++) {
        cout << max(0, ans[i]) << ' ';
    }
    cout << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

C.Theo fanis’ Nightm are(贪心)

题意：

给出一个包含

$n$ 个元素的数组

$a$ ，你可以任意将该数组划分成若干个子段，然后统计划分完的结果为：

$sumlimits_{i = 1}^{k}i cdot sum_i i=1∑ki⋅sumi( k k k为子段数量， s u m i sum_i sumi为第 i i i个子段的数字总和)$

问划分的结果最大是多少。

分析：

先考虑每个子段的数字贡献，

⋅

i cdot sum_i

$i \cdot s u m_{i}$ 也可以转化为该子段中每个数字被加上了

$i$ 次。那么就可以把乘法转化为加法。

然后考虑怎么划分子段最优，如果从前往后考虑，很难判断是否该将当前数字划分为一个新子段的起点。

因此，需要从后往前遍历，统计

∼

i sim n

$i \sim n$ 之间的数字总和，为了使答案尽可能大，那么只要当前数字总和大于等于0，就可以将当前位置划分给一个新的子段起点。此时，划分出一个新的起点后，那么后面所有的数字均需要再被加上一次，不难发现，此时要加上的就是维护的数字总和。

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

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e5 + 5;

LL a[N];

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

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

D1. Maxi mum And Queries (easy version)(位运算)

题意：

给出一个长度为

$n$ 的数组

$a$ ，并进行

$q$ 次询问，每次询问为：

你可以进行

问：经过

$k$ 次操作后，

a_1 & a_2 & … & a_n

$a_{1} & a_{2} &\dots& a_{n}$ 的最大值是多少。

注：每次询问都是独立的，不会保留前面询问的操作结果。

分析：

由于每次询问都是独立的，那么修改不能在原数组上进行，需要将原数组元素复制到其他数组中再进行操作。

题目数据规定了

⋅

≤

n cdot q le 10^{5}

$n \cdot q \leq 1 0^{5}$ ，那么可以认为最大的数据就是对长度为

10^5

$1 0^{5}$ 的数组进行一次询问。

由于给出的

≤

k le 10^{18}

$k \leq 1 0^{18}$ ，那么当数组中只有一个元素时，最大可能的结果为

≈

10^{18} + 10^{6} app ro x 2^{60}

$1 0^{18} + 1 0^{6} \approx 2^{60}$ ，因此需要一个大于

$60$ 的数组记录与运算后的结果每位二进制数是多少。

对于每次询问，从二进制高位开始往低位进行遍历，每次检查当前剩余的

$k$ 是否还能将数组中所有数的当前二进制位修改为1，如果可以，进行修改，并记录在答案数组中，如果不行，继续遍历更低的二进制位。

结束修改后，将数组中记录的信息转化为十进制数即可。

hint：本题数据较大，需要注意使用左移运算需要使用

1ll

$1 ll$ 将

$1$ 转化为long long类型再进行运算，计算花费时也要考虑如果超过操作次数就该退出检查，避免数据溢出。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e5 + 5;

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

LL getCost(int x, LL k) {
    LL 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(LL 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
        LL 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));
                }
            }
        }
    }
    LL  res = 0;
    for (int i = 0; i <= 60; i++) {
        res |= (ans[i] << i);//这里ans[i]如果不是long long类型也会发生溢出
    }
    cout << res << endl;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (q--) {
        LL k;
        cin >> k;
        solve(k);
    }
    return 0;
}

E.Geo Game(构造)

题意：

注：本题是交互题。

给出一个二维平面和一个起点

(

)

(s_x, s_y)

$(s_{x}, s_{y})$ ，同时，有

$n$ 个点可以被选择，每个选手在每轮操作时可以选择

$n$ 个点中未被选过的一个，并在当前点与上一个点之间连一条线。

完成所有操作后，如果所有线段的长度和为偶数，那么先手获胜，否则，后手获胜。

问，该选择先手还是后手，并模拟选择棋子的过程。

分析：

由于奇数的平方也是奇数，偶数的平方也是偶数，且本题只在乎结果为奇数还是偶数，那么不需要对距离进行计算，根据奇偶性将距离分为

0, 1

$0, 1$ 两种情况，即：

a + b与 c + d奇偶性相同，距离为0
否则，距离为1

那么可以将所有点的

x,y

$x, y$ 坐标加在一起，并分为奇数和偶数两种情况存储。

然后考虑该怎么选择操作。

首先，推样例可以发现一个结论：

当一个子段端点相同时，无论往里面加入多少种不同的点，最后整个子段中的线段距离总和一定为偶数。

那么想要获胜，就可以构造一个这样的子段，如果是先手，那么需要最后结果为偶数，此时如果最后选择的点奇偶性与起点相同，就是必胜的，可以想到，当与起点奇偶性相同的点数量大于等于不同的点的数量，就可以每次都选择与起点奇偶性不同的点，使得最后后手只能选择一个奇偶性与起点相同的点，导致最后结果为偶数。

如果是后手，那么就是起点奇偶性相同的点数量小于不同的点的数量的情况下，每次选择与起点奇偶性相同的点，由于这部分点数量较少，被选完后，只能选择奇偶性不同的点导致结果由偶数变为奇数，而由于只有奇偶性不同的点之间连线才会改变结果的奇偶性，那么剩余的点无法再将结果变为偶数，此时后手必胜。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e5 + 5;

int n, op;
set<int> id[5];

void ask() {//给出当前决策
    if (!id[op].empty()) {
        cout << *(id[op].begin()) << endl;
        id[op].erase(id[op].begin());
    } else {
        cout << (*id[op ^ 1].begin()) << endl;
        id[op ^ 1].erase(id[op ^ 1].begin());
    }
    cout.flush();
}

void get() {//接受敌手决策
    int pos;
    cin >> pos;
    if (id[0].find(pos) != id[0].end()) id[0].erase(pos);
    else id[1].erase(pos);
}


void second_solve() {
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1) get();
        else ask();
    }
}

void first_solve() {
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1) ask();
        else get();
    }
}

void solve() {
    cin >> n;
    int sx, sy;
    cin >> sx >> sy;
    op = (sx + sy) % 1;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        id[(x + y) % 2].insert(i);
    }
    if (id[op].size() < id[op ^ 1].size()) {
        cout << "Second" << endl;
        second_solve();
    } else {
        op ^= 1;//先手选与起点奇偶不同的点
        cout << "First" << endl;
        first_solve();
    }
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}