前言

自我感觉难度整体偏简单，但出的有点shi，BC做完感觉大家可能就想下机了，题解写的不明白的地方大家随时问，也可以去牛客竞赛b站官方账号查看鸡哥的视频讲解。

题解

A.lz的吃饭问题

出题人和他的室友总是不知道吃什么就有了这道题，比较一下和的大小即可。

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    int a1, b1, a2, b2;
    std::cin >> a1 >> b1 >> a2 >> b2;
    if (a1 * b1 < a2 * b2) {
        std::cout << "lz";
    }
    else {
        std::cout << "gzy";
    }
}  

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

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.lz的数字问题

如果没有小数点那就在字符串结尾加上，否则就加上，直接从小数点后6位截取对比相不相同即可。

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    std::string s, t;
    std::cin >> s >> t;
    if (s.find('.') == std::string::npos) {
        s += ".00000000000";
    }
    else {
        s += "00000000000";
    }
    if (t.find('.') == std::string::npos) {
        t += ".00000000000";
    }
    else {
        t += "00000000000";
    }
 
    s.erase(s.find('.') + 7);
    t.erase(t.find('.') + 7);
 
    if (s == t) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}  

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

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

C.lz的蛋挞问题

这题可以很清楚地发现是求图的割点和大小为1的联通块的个数，如果想方便的话可以直接tarjan，不然的话需要模拟以某个位置为中心的六个位置是否可以改变联通块数量。这里我给出tarjan的代码作为参考，模拟的代码偷的内测同学的。

#include<bits/stdc++.h>

using i64 = long long;

const int N = 400005;

std::vector<int> e[N];
int dfn[N], low[N], boo[N];
int cnt = 0, root = -1;

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    int flag = 0;
    for (auto v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                flag++;
                if (u != root || flag > 1) boo[u] = 1;//如果不是根就是割点，是根的话判断一下有几个儿子，如果超过了一个就是割点
            }
        }
        else {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
}

void solve() {
    int n;
	std::cin >> n;

	std::vector<std::vector<char> > mp(4, std::vector<char> (n + 2, 'x'));
	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= n; j++) {
			std::cin >> mp[i][j];
			if (mp[i][j] == '.') {
				if (j > 1) {
					if (mp[i][j - 1] == '.') {
						int u = 2 * (j - 1) - (i & 1), v = 2 * j - (i & 1);
						// std::cout << u << ' ' << v << '\n';
						e[u].push_back(v);
						e[v].push_back(u);
					}
				}
			}
			if (i == 2 && mp[i - 1][j] == '.' && mp[i][j] == '.') {
				int u = 2 * j - 1, v = 2 * j;
				// std::cout << u << ' ' << v << '\n';
				e[u].push_back(v);
				e[v].push_back(u);
			}
		}
	}

	for (int i = 1; i <= 2 * n; i++) {
		if (!dfn[i]) {
			root = i;
			tarjan(i);
		}		
	}

	int ans = 0;
	for (int i = 1; i <= 2 * n; i++) {
		if (boo[i] == 1) {
			ans++;
		}
	}
	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= n; j++) {
			if (mp[i][j] == '.' && mp[i + 1][j] == 'x' && mp[i - 1][j] == 'x' && mp[i][j - 1] == 'x' && mp[i][j + 1] == 'x') {
				ans++;
			}
		}
	}
	std::cout << ans << '\n';
}

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

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

#pragma GCC optimiaze("O3")
#pragma GCC optimiez("Ofast")

#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

string s[3];

void solve(){
    int n;
    cin >> n >> s[1] >> s[2];
    s[1] = "x" + s[1]+'x';
    s[2] = "x" + s[2]+'x';
    int ans = 0;
    int lst = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[1][i] == '.')
        {
            if (i < n && s[2][i + 1] == 'x' && s[1][i + 1] == '.' && s[2][i] == '.') ans++;
            else if (s[1][i + 1] == 'x' && s[1][i - 1] == 'x' && s[2][i] == 'x') ans++;
            else if (s[2][i] == 'x' && s[1][i - 1] == '.' && s[1][i + 1] == '.') ans++;
            else if (i >= 2 && s[2][i - 1] == 'x' && s[2][i] == '.' && s[1][i - 1] == '.')ans++;
        }
        if (s[2][i] == '.')
        {
            if (s[1][i + 1] == 'x' && s[2][i + 1] == '.' && s[1][i] == '.') ans++;
            else if (s[2][i + 1] == 'x' && s[2][i - 1] == 'x' && s[1][i] == 'x') ans++;
            else if (s[1][i] == 'x' && s[2][i - 1] == '.' && s[2][i + 1] == '.') ans++;
            else if (i >= 2 && s[1][i - 1] == 'x' && s[1][i] == '.' && s[2][i - 1] == '.')ans++;
        }
    }
    cout << ans << endl;
}

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

D.lz的染色问题

题面让我描述地像shi一样，后来偷了wida改写的题面，这个题由于要提前将所有的染色完成，那么就可以转化题意为求每个联通块的大小减去该联通块中出现最多的颜色数的累加，就变成了一道很板的并查集的题目了。

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 n, m;
    std::cin >> n >> m;

    std::vector<int> a(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        p[i] = i;
    }

    auto find = [&] (auto self, int x) ->int {
        if (x == p[x]) {
            return x;
        }
        else {
            return p[x] = self(self, p[x]);
        }
    };

    auto merge = [&] (int u, int v) -> void {
        int fx = find(find, u), fy = find(find, v);
        if (fx != fy) {
            p[fx] = fy;
        }
    };

    for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        merge(u, v);
    }

    std::vector<std::vector<int> > v(n + 1);
    for (int i = 1; i <= n; i++) {
        v[find(find, i)].push_back(a[i]);
    } 

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!v[i].size()) continue;
        std::map<int, int> mp;
        int mx = 0;
        for (auto it : v[i]) {
            mp[it]++;
            mx = std::max(mx, mp[it]);
        }

        ans += v[i].size() - mx;
    }

    std::cout << ans << '\n';
}  

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

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

E.lz的括号问题

括号匹配好玩！我们回想用栈来实现括号匹配要怎么写来着，遇到左括号入栈，遇到右括号出栈对吧，那这个题就可以遇到左括号入栈，遇到右括号出栈的时候同时记录一下这对括号的答案，也就是全部的括号数也就是你可以用你喜欢的任何方式对这对括号打上标记用来输出，这里给我的代码作为参考。

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    
    s = ' ' + s;
    std::stack<int> st;
    
    std::vector<int> ans(n + 1);
    int cnt = 0, flag = 0;
    for (int i = 1; i <= n * 2; i ++) {
        if (s[i] == '(') {
            st.push(++cnt);
        }
        else {
            if (!st.empty()) {
                ans[st.top()] = st.size();
                st.pop();
            }
            else {
                flag = 1;
                break;
            }
        }
    }
    if (flag) {
        std::cout << -1;
        return;
    }

    for (int i = 1; i <= n; i++) {
        std::cout << n - ans[i] << ' ';
    }
}  

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

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

F.lz的序列问题

此题考虑线段树维护，合并两棵子树时：

左子树的贡献为：

右子树的贡献为:

合并左右子树后该区间的贡献为:

考虑提取公因式：

我们发现，合并后该区间的贡献即为，左子树的贡献加上左子树最后一项的值乘上右子树的贡献

区间修改时，将该区间改为同一个数，该区间的贡献可以用等比数列求和公式求出，该区间的最后一项也可以用等比数列公式求出。

等比数列公式！要特殊处理公比为1的时候

剩下的就是套路性的东西。

#include <bits/stdc++.h>
#define lson (rt << 1)
#define rson (rt << 1 | 1)

using i64 = long long;

const int mod = 1000000007;

int a[200005];
struct node {
    i64 v, rmx, lz;
}tr[200005 << 2];

i64 ksm(i64 a, i64 b) {
    i64 res = 1;
    while(b) {
        if (b & 1) {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }

    return res;
}

node mer(node x, node y) {
    if (x.v == 0) return y;
    node res = {0, 0, 0};
    res.v = x.rmx * y.v % mod + x.v;
    res.v %= mod;
    res.rmx = x.rmx * y.rmx % mod;
    return res;
}

void push_down(int rt, int l, int r) {
    if (tr[rt].lz) {
        int mid = l + r >> 1;
        int x = tr[rt].lz;
        
        tr[lson].lz = x;
        tr[rson].lz = x;

        if (tr[rt].lz == 1) {
            tr[lson].v = mid - l + 1;
            tr[rson].v = r - mid;

            tr[lson].rmx = 1;
            tr[rson].rmx = 1;
        }
        else {
            tr[lson].v = (ksm(x, mid - l + 1) - 1) * x % mod * ksm(x - 1, mod - 2) % mod;
            tr[rson].v = (ksm(x, r - mid) - 1) * x % mod * ksm(x - 1, mod - 2) % mod;

            tr[lson].rmx = ksm(x, mid - l + 1);
            tr[rson].rmx = ksm(x, r - mid);
        }
        
        tr[rt].lz = 0;
    }
}

void build(int rt, int l, int r) {
    if (l == r) {
        tr[rt].v = a[l];
        tr[rt].rmx = a[l]; 
        return;
    }

    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    tr[rt] = mer(tr[lson], tr[rson]);
}

void update(int rt, int l, int r, int L, int R, int x) {
    if (l >= L && r <= R) {
        tr[rt].lz = x;
        if (x == 1) {
            tr[rt].v = r - l + 1;
            tr[rt].rmx = 1;
        }
        else {
            tr[rt].v = (ksm(x, r - l + 1) - 1) * x % mod * ksm(x - 1, mod - 2) % mod;
            tr[rt].rmx = ksm(x, (r - l + 1));
        }
        return;
    }

    push_down(rt, l, r);

    int mid = l + r >> 1;
    if (mid >= L)
        update(lson, l, mid, L, R, x);
    if (mid < R) {
        update(rson, mid + 1, r, L, R, x);
    }
    tr[rt] = mer(tr[lson], tr[rson]);
}

node query(int rt, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
        return tr[rt];
    }

    push_down(rt, l, r);
    node res = {0, 0, 0};

    int mid = l + r >> 1;
    if (mid >= L) {
        res = mer(res, query(lson, l, mid, L, R));
    }
    if (mid < R){
        res = mer(res, query(rson, mid + 1, r, L, R));
    }
    return res;
}

void solve() {
    int n, m;
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    build(1, 1, n);

    while (m--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int l, r, x;
            std::cin >> l >> r >> x;
            update(1, 1, n, l, r, x);
        }
        else {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(1, 1, n, l, r).v << '\n';
        }
    }
}

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

    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}