牛客周赛 Round 69

构造C的歪

思路

取 \(|a-b|+\max(a,b)\) 即可构造第三项。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    cin >> a >> b;

    int d = abs(a-b);

    cout << max(a,b) + d << "\n";

    return 0;
}

不要三句号的歪

思路

采用C语言 \(scanf\) 的模式串读取即可得到 \(a,b,c\)，然后输出 \(c-b-1\) 即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b, c;
    scanf("%lld,%lld,...,%lld", &a, &b, &c);
    printf("%lld\n", c - b - 1);

    return 0;
}

仰望水面的歪

思路

实际上就是将坐标按照水面对称后得到新的点与原点建立向量即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, h;
    cin >> n >> h;

    while (n --) {
        i64 x, y, z;
        cin >> x >> y >> z;

        z = h + abs(h - z);
        i64 nx = x, ny = y, nz = z;
        i64 g = gcd(nx, gcd(ny, nz));
        nx /= g,ny /= g,nz /= g;

        cout << nx << " " << ny << " " << nz << "\n";
    }


    return 0;
}

小心火烛的歪

思路

注意到 \(p\le 7\)，那么我们可以直接二进制枚举每个计划选还是不选即可，对选出的计划处理出最终的方案是否与草地互补即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<string> cs(n);
    for (auto &i : cs) {
        cin >> i;
        for (auto &j : i) {
            j = ((j - '0') ^ 1) + '0';
        }
    }

    vector has(q, vector<string>(n));
    for (auto &i : has) {
        for (auto &j : i) {
            cin >> j;
        }
    }

    int ans = -1;
    vector<int> res;

    auto check = [&](int x)->void{
        vector<string> now(n, string(m, '0'));
        vector<int> ok;
        for (int i = 0; i < q; i ++) {
            if (x >> i & 1) {
                ok.emplace_back(i + 1);
                for (int j = 0; j < n; j ++) {
                    for (int k = 0; k < m; k ++) {
                        if (has[i][j][k] == '1') {
                            now[j][k] = '1';
                        }
                    }
                }
            }
        }

        if (now == cs) {
            if (ans == -1 || ok.size() < ans) {
                ans = ok.size();
                swap(res, ok);
            }
        }
    };

    for (int i = 0; i < (1 << q); i ++) {
        check(i);
    }

    cout << ans << "\n";
    for (auto i : res) {
        cout << i << " ";
    }


    return 0;
}

喜欢切数组的红

思路

要分成和相等的三部分，那么总体的和也一定是三的倍数。

然后做个前缀和，对达到 \(\frac{sum}{3}\) 的再去遍历后续是否存在满足要求的划分即可。

赛时没想过这样暴力，后来看别人代码这样过了，我想这样可以做的原因大概是因为能满足前缀和等于 \(\frac{sum}{3}\) 的条件很少，所以第二个循环并不会跑太多次（但是假如塞一堆 \(0\) 去增加条件 \(1\) 的判定不知道会不会超时，不懂）。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<i64> pre(n + 1), has(n + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        pre[i] += pre[i - 1] + a[i];
        has[i] += has[i - 1] + (a[i] > 0);
    }

    if (pre[n] % 3 != 0 || has[n] < 3) {
        cout << 0 << "\n";
        return 0;
    }

    i64 avg = pre[n] / 3, ans = 0;
    for (int i = 1; i <= n; i ++) {
        if (!has[i] || pre[i] != avg) {
            continue;
        }
        for (int j = i + 1; j <= n; j ++) {
            if (pre[j] - pre[i] != avg || has[j] - has[i] == 0) {
                continue;
            }
            if (pre[n] - pre[j] != avg || has[n] - has[j] == 0) {
                continue;
            }
            ans ++;
        }
    }

    cout << ans << "\n";

    return 0;
}

研究red子序列的红

思路

唐了，刚开始看了一眼还以为树状数组能写，然后写到后面越发觉得不对劲，没想到线段树去维护，还是得多写orz

求区间内（实际上就是\([1,n]\)）的子序列 red 的数量，对于交换操作，实际上就是单点修改，所以可以用线段树维护 r,e,d,re,ed,red \(6\) 个子串的个数，往上传的时候 re=r \(\times\) e+左儿子re+右儿子re，其他同理。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

template<class Node>
struct SegmentTree {
#define lc u<<1
#define rc u<<1|1
	const int n, N;
	vector<Node> tr;

	SegmentTree(): n(0) {}
	SegmentTree(int n_): n(n_), N(n * 4 + 10) {
		tr.reserve(N);
		tr.resize(N);
	}
	SegmentTree(string &init) : SegmentTree(init.size() - 1) {
		function<void(int, int, int)> build = [&](int u, int l, int r) {
			tr[u].l = l, tr[u].r = r;
			if (l == r) {
				tr[u] = {l, r, {init[l] == 'r', init[l] == 'e', init[l] == 'd', 0, 0, 0}};
				return ;
			}
			i64 mid = (l + r) >> 1;
			build(lc, l, mid);
			build(rc, mid + 1, r);
			pushup(tr[u], tr[lc], tr[rc]);
		};
		build(1, 1, n);
	}

	void pushup(Node& U, Node& L, Node& R) { //上传
		U.l = L.l, U.r = R.r;
		for (int i = 0; i < 6; i ++) {
			U.res[i] = L.res[i] + R.res[i];
		}
		U.res[3] += L.res[0] * R.res[1];
		U.res[4] += L.res[1] * R.res[2];
		U.res[5] += L.res[0] * R.res[4] + L.res[3] * R.res[2];
	}

	void modify(int u, int x, char c, int k) {
		if (tr[u].l >= x && tr[u].r <= x) {
			if (c == 'r') tr[u].res[0] += k;
			else if (c == 'e') tr[u].res[1] += k;
			else if (c == 'd') tr[u].res[2] += k;
			return ;
		}
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (x <= mid)
			modify(lc, x, c, k);
		if (x > mid)
			modify(rc, x, c, k);
		pushup(tr[u], tr[lc], tr[rc]);
	}

	i64 get() {
		return tr[1].res[5];
	}
};

struct Node { //线段树定义
	int l, r;
	array<i64, 6> res;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	string s, t;
	cin >> s >> t;

	s = " " + s, t = " " + t;

	string pa = "red";
	SegmentTree<Node> st(s), tt(t);

	while (q--) {
		int x;
		cin >> x;

		if (pa.find(s[x]) != -1) {
			st.modify(1, x, s[x], -1);
		}
		if (pa.find(t[x]) != -1) {
			tt.modify(1, x, t[x], -1);
		}
		swap(s[x], t[x]);
		if (pa.find(s[x]) != -1) {
			st.modify(1, x, s[x], 1);
		}
		if (pa.find(t[x]) != -1) {
			tt.modify(1, x, t[x], 1);
		}

		cout << st.get() - tt.get() << "\n";

	}

	return 0;
}