alt

A. 构造C的歪

思路

当 时，令 即可，如果 ，则交换两个的值，又变成 的情况。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 构造C的歪
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/96115/A
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e4 + 5, M = 17;

void solve()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
        swap(a, b);
    int c = b + b - a;
    cout << c;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

B. 不要三句号的歪

思路

把字符串中的三个数字提出来，输出后两个数字的差值即可。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 不要三句号的歪
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/96115/B
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e4 + 5, M = 17;

void solve()
{
    string s;
    cin >> s;

    vector<int> ar;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            int x = 0, j = i;
            while (isdigit(s[j]) && j < s.size()) {
                x = x * 10 + s[j++] - '0';
            }
            i = j;
            ar.push_back(x);
        }
    }
    cout << ar[2] - ar[1] - 1 << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

C. 仰望水面的歪

思路

思考一个经典问题：有一个点 ，现在从起点 出发，要求到达一次 轴，然后再到达 经过的最短路径长度。

因为两点之间直线距离最短，所以可以把 以 轴为对称轴翻转之后，变成 ，到 的直线距离即为需要经过的最短路径长度。

在这题中，反射不影响原来 轴的方向，影响的是 轴的方向，因此在 轴方向对终点 以 为对称轴进行翻转，得到 ，从到 的向量 就是可以射出后到达终点的向量方向。

题目要求输出的时候，向量三个数互质，因此需要把它们除去它们的最大公约数。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 仰望水面的歪
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/96115/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e4 + 5, M = 17;

int n, h;

void solve()
{
    cin >> n >> h;
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        int x1 = x, y1 = y, z1 = 2*h - z;
        int g = __gcd(__gcd(abs(x1), abs(y1)), abs(z1));
        if (g)
            x1 /= g, y1 /= g, z1 /= g;
        cout << x1 << ' ' << y1 << ' ' << z1 << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

D. 小心火烛的歪

思路

因为草地大小和计划数数量很小，所以可以枚举所有可能的计划执行情况，然后保留能使得所有有杂物的位置不燃放烟花，无杂物的位置燃放烟花的计划数最少的执行计划。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 小心火烛的歪
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/96115/D
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 10;

int n, m, q;
string g[N];
string g1[N][N];

void solve()
{
    cin >> n >> m >> q;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g1[i][j];
        }
    }
    int is = 0;
    vector<int> ans;
    for (int i = 0; i < (1 << q); i++) {
        vector<int> sel;
        int s[N][N] = { 0 };
        for (int j = 0; j < q; j++) {
            if ((i >> j) & 1) {
                sel.push_back(j);
                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < m; y++) {
                        int v = g1[j][x][y] - '0';
                        s[x][y] |= v;
                    }
                }
            }
        }
        int flag = 1;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                flag &= (s[x][y] != g[x][y] - '0');
            }
        }
        if (flag) {
            if (!is) {
                ans = sel;
            } else if (sel.size() < ans.size()) {
                ans = sel;
            }
            is = 1;
        }
    }
    if (!is) {
        cout << "-1";
    } else {
        cout << ans.size() << '\n';
        for (int i : ans)
            cout << i + 1 << ' ';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

E. 喜欢切数组的红

思路

令数组和为 ，如果 不是 的倍数，显然无论切分都无法满足要求，切分方案为 ，否则则可能存在切分方案。

令 为 的数之和，其实就是数组 的前缀和；为 中是否有正数的标记，如果 ，无正数，否则则有； 为 中正数的最大下标，如果不存在正数，。

考虑从小到大枚举切分的三个子数组中，第二个子数组的右端点 。

对于第二个子数组，它的右端点 处 的前缀和 必然为 ，且满足 ，即第三个数组能够含有正数。

如果 不为 ，那么第二个子数组的左端点范围就是 。 因为第二个子数组的左端点，其实就是第一个子数组的右端点加一，所以可以看 中，有哪些下标可以作为第一个子数组的右端点。

可以在枚举的时候，记录一个下标集合 ，里面的下标 ，满足 ，且 。这个下标就是已经遍历过的，可以作为第一个子数组的右端点的下标。

因为枚举顺序是从小到大的，所以这个下标集合 里面的下标按照先后顺序存放的话，也是递增的，可以二分找到集合中最大的小于 的下标的位置，在这个位置之前（包含这个位置）的下标，都是可以作为当前枚举的第二个子数组对应的第一个子数组的右端点，对应的数量可以通过这个位置得到，这些数量加和起来即为答案。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 喜欢切数组的红
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/96115/E
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 5, M = 17;

int n;
int a[N], b[N], c[N], ne[N];
vector<int> all;

void solve()
{
    cin >> n;
    int p = -1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = b[i - 1] + a[i];
        if (a[i] > 0)
            p = i;
        ne[i] = p;
    }
    for (int i = n; i >= 1; i--) {
        c[i] = c[i + 1] | a[i] > 0;
    }
    if (b[n] % 3 != 0) {
        cout << 0;
        return;
    }
    int ans = 0, val = b[n] / 3;
    for (int i = 1; i < n && c[i + 1]; i++) {
        if (i > 1 && ne[i] != -1 && b[i] == 2 * val) {
            if (b[i] == 2 * val && all.size()) {
                auto it = lower_bound(all.begin(), all.end(), ne[i]);
                ans += it - all.begin();
            }
        }
        if (ne[i]!=-1 && b[i] == val) {
            all.push_back(i);
        }
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

F. 研究red子序列的红

思路

经典的 子序列系列，和之前的 子序列系列题目一样，可以用线段树维护字符串中 的数量。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 研究red子序列的红
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/96115/F
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 5, M = 17;

int n, q;
string s[2];

struct node {
    int l, r;
    int v[6];
    // v[0] 为 r 的数量
    // v[1] 为 e 的数量
    // v[2] 为 d 的数量
    // v[3] 为 re 的数量
    // v[4] 为 ed 的数量
    // v[5] 为 red 的数量
} Tr[2][4 * N];

void pushup(int u, int op)
{
    node* tr = Tr[op];
    tr[u].v[0] = tr[u * 2].v[0] + tr[u * 2 + 1].v[0];
    tr[u].v[1] = tr[u * 2].v[1] + tr[u * 2 + 1].v[1];
    tr[u].v[2] = tr[u * 2].v[2] + tr[u * 2 + 1].v[2];
    tr[u].v[3] = tr[u * 2].v[3] + tr[u * 2 + 1].v[3]
        + tr[u * 2].v[0] * tr[u * 2 + 1].v[1];
    tr[u].v[4] = tr[u * 2].v[4] + tr[u * 2 + 1].v[4]
        + tr[u * 2].v[1] * tr[u * 2 + 1].v[2];
    tr[u].v[5] = tr[u * 2].v[5] + tr[u * 2 + 1].v[5]
        + tr[u * 2].v[0] * tr[u * 2 + 1].v[4]
        + tr[u * 2].v[3] * tr[u * 2 + 1].v[2];
}

string str = "red";

void build(int u, int l, int r, int op)
{
    node* tr = Tr[op];
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        int id = str.find(s[op][l]);
        if (id != -1)
            tr[u].v[id] = 1;
    } else {
        int mid = (l + r) >> 1;
        build(u * 2, l, mid, op);
        build(u * 2 + 1, mid + 1, r, op);
        pushup(u, op);
    }
}

void modify(int u, int p, char c, int op)
{
    node* tr = Tr[op];
    if (tr[u].l == tr[u].r) {
        tr[u].v[0] = tr[u].v[1] = tr[u].v[2] = 0;
        int id = str.find(c);
        if (id != -1)
            tr[u].v[id] = 1;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (p <= mid)
        modify(u * 2, p, c, op);
    else
        modify(u * 2 + 1, p, c, op);
    pushup(u, op);
}

void solve()
{
    cin >> n >> q;
    for (int i = 0; i < 2; i++) {
        cin >> s[i];
        s[i] = ' ' + s[i];
        build(1, 1, n, i);
    }
    while (q--) {
        int id;
        cin >> id;
        for (int i = 0; i < 2; i++) {
            modify(1, id, s[i ^ 1][id], i);
        }
        swap(s[0][id], s[1][id]);
        int ans = Tr[0][1].v[5] - Tr[1][1].v[5];
        cout << ans << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}