alt

A. lz的吃饭问题

思路

比较 $a_1*b_1$ 和 $a_2*b_2$ 的大小后输出即可。

复杂度

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$

代码实现

// Problem: lz的吃饭问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/A
// 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;

void solve()
{
    int a[4];
    for (int i = 0; i < 4; i++) {
        cin >> a[i];
    }
    if (a[0] * a[1] < a[2] * a[3]) {
        cout << "lz";
    } else {
        cout << "gzy";
    }
}

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

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

B. lz的数字问题

思路

把数字分割成小数点前后的两部分，如果小数点后部分长度小于 $6$ ，则补 $0$ 补到长度为 $6$ 。

先对整数部分进行比较，如果不相同则输出 $NO$ ，否则比较小数点部分的前 $6$ 位，如果存在不同输出 $NO$ ，不然就是 $YES$ 。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: lz的数字问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/B
// 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;

void solve()
{
    vector<array<string, 2>> all;
    for (int i = 0; i < 2; i++) {
        string s;
        cin >> s;
        int op = 0;
        array<string, 2> ar = { "", "" };
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '.')
                op++;
            else {
                ar[op] += s[i];
            }
        }
        all.push_back(ar);
    }
    if (all[0][0] != all[1][0]) {
        cout << "NO\n";
    } else {
        for (int i = 0; i < 2; i++) {
            while (all[i][1].size() < 6)
                all[i][1] += '0';
        }
        int flag = 1;
        for (int i = 0; i < 6; i++) {
            if (all[0][1][i] != all[1][1][i]) {
                flag = 0;
                break;
            }
        }
        cout << (flag ? "YES" : "NO");
    }
}

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

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

C. lz的蛋挞问题

思路

符合条件的蛋挞为以下三种情况之一：

???(这三个中存在x，不同时都为.)
...
  
...
???(对称情况)

x.x
xxx

.x
xx

xx
x.
(单独的一个点)

..x
x.x

x..
x.x

(对角为x)

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: lz的蛋挞问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/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;
string s[2];

void solve()
{
    cin >> n;
    for (int i = 0; i < 2; i++) {
        cin >> s[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            if (s[j][i] == 'x')
                continue;

            if ((i <= 0 || s[j][i - 1] == 'x') && (i + 1 >= n || s[j][i + 1] == 'x') && (s[j ^ 1][i] == 'x')) {
                ans++;
            } else if (i > 0 && s[j][i - 1] == '.' && s[j ^ 1][i - 1] == 'x' && s[j ^ 1][i] == '.')
                ans++;
            else if (i > 0 && s[j][i - 1] == '.' && i + 1 < n && s[j][i + 1] == '.' && (s[j ^ 1][i] == 'x' || s[j ^ 1][i - 1] == 'x' || s[j ^ 1][i + 1] == 'x'))
                ans++;
            else if (i + 1 < n && s[j][i + 1] == '.' && s[j ^ 1][i + 1] == 'x' && s[j ^ 1][i] == '.')
                ans++;
        }
    }
    cout << ans;
}

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

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

D. lz的染色问题

思路

如果观察了 $(a,b)$ ， $(b,c)$ ，则 $a,b,c$ 都需要修改成同一种颜色，可以把需要修改为同种颜色的点相连，相连之后会构成多个联通块，同一个块内的点都要修改为同一种颜色。

对于一个联通块，要使得修改数量最少，修改成联通块内颜色最多的哪种颜色是最优的。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: lz的染色问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/D
// 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 = 2e5 + 5, M = 17;

int n, m;
int a[N];

int p[N], sz[N];
unordered_map<int, int> h[N];
// h[i] 为祖先节点为i的颜色集合，同时记录了联通块颜色的对应点数

int find(int x)
{
    return x == p[x] ? x : p[x] = find(p[x]);
}

void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x != y) {
        p[x] = y, sz[y] += sz[x];
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = i, sz[i] = 1;
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        h[find(i)][a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) {
            int ma = 0;
            for (auto it : h[i]) {
                ma = max(ma, it.second);
            }
            ans += sz[i] - ma;
            // 修改成最多的哪一种颜色，原先如果为最多的哪一种颜色则不需要修改
        }
    }
    cout << ans;
}

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

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

E. lz的括号问题

思路

先进行括号匹配，同时对于每个左括号记录下与它匹配的右括号下标，如果匹配时有无法匹配的右括号，或者最后剩下未匹配的左括号，则是无解，输出 $-1$ 。

对于一个括号，它无法在包含它的括号之前被删除，但是可以在被它包含的括号之前删除，以及与它并列的括号之前删除。

串  :(()(()))
序号:12234431

上面这一串括号中，括号 $1$ 包含了括号 $2$ ，因此括号 $2$ 无法在括号 $1$ 之前删除，但是括号 $2$ 可以在与它并列的括号 $3,4$ 之前删除，括号 $3$ 可以在被它包含的括号 $4$ 之前删除。

抽象化一些，就是一对括号 $(i,j)$ （ $i,j$ 分别为左右括号的下标）。

如果最近的包含它的括号为 $(l,r)$ ，那么区间 $[l 1,r-1]$ 中 $[l 1,i-1],[j 1,r]$ 的并集所涉及到的括号，都可以安排在区间 $[i,j]$ 内的括号之前删除。如果并集的长度为 $x$ ，在 $[i,j]$ 内的括号之前删除的括号对数量就包含了 $\frac{x}{2}$ 对，可以用差分的技巧，把这个数量加到 $[i,j]$ 这个区间上去。

对于 $(i,j)$ 这对括号，区间 $[i 1,j-1]$ 之间的括号可以安排在这对括号之前删除，对应的括号对数量为 $\frac{j-i-1}{2}$ ，可以加到 $i$ 这个点上，最后答案都统计在左括号的位置。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: lz的括号问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/E
// 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 = 1e6 + 5, M = 17;

int n;
string s;
int to[N], ans[N];

int check()
{
    stack<int> st;

    for (int i = 0; i < 2 * n; i++) {
        char c = s[i];
        if (c == '(') {
            st.push(i);
        } else {
            if (!st.size())
                return 0;
            int j = st.top();
            st.pop();
            to[i] = j, to[j] = i;
        }
    }
    return st.size() == 0;
}

void dfs(int l, int r)
{
    int len = r - l + 1;
    vector<array<int, 2>> all;
    for (int i = l; i <= r; i++) {
        if (s[i] == '(') {
            int j = to[i];
            int cur = j - i + 1;
            ans[i] += (len - cur) / 2;
            ans[j + 1] -= (len - cur) / 2;
            // len - cur 为 [l,r] 中除 [i,j] 外的长度
            ans[i] += (cur - 2) / 2;
            ans[i + 1] -= (cur - 2) / 2;
            // cur-2 为 [i+1,j-1] 的长度
            if (i + 1 != j)
                dfs(i + 1, j - 1);
            i = j;
            // 下标i跳到当前右括号位置j，j+1为下一对并列括号的左括号位置
        }
    }
}

void solve()
{
    cin >> n >> s;
    if (!check()) {
        cout << "-1";
        return;
    }
    dfs(0, 2 * n - 1);
    for (int i = 0; i < 2 * n; i++) {
        if (i)
            ans[i] += ans[i - 1];
        if (s[i] == '(')
            cout << ans[i] << ' ';
    }
}

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

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

F. lz的序列问题

思路

令 $f(l,r)$ 为 $\prod_{i=l}^r a_i$ , $g(l,r)$ 为 $\sum_{i=l}^r f(l,i)$ ， $g(l,r)$ 即为 $[l,r]$ 的美丽值。

可以发现， $f(l,r)，g(l,r)$ 可以通过子区间 $[l,m],[m 1,r]$ 计算得到，即 $f(l,r) = f(l,m)*f(m 1,r)$ ， $g(l,r) = g(l,m) f(l,m)*g(m 1,r)$ 。

当把区间 $[l,r]$ 都修改为 $x$ 时， $f(l,r) = x^{r-l 1}$ ， $g(l,r)=x x^2 x^3 ... x^{r-l 1}$ ，本质首项为 $x$ ，公比为 $x$ ，长度为 $r-l 1$ 的等比数列的求和。

将上面的计算方式应用于线段树的维护上，这样就可以在 $O(\log n)$ 的复杂度进行修改和查询。

注意计算结果要对 $10^9 7$ 取模，需要使用快速幂求逆元。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n\log n)$

代码实现

// Problem: lz的序列问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/F
// Memory Limit: 512 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e5 + 5, mod = 1e9 + 7;

int n, q;
int ar[N];

struct node {
    int l, r, add, v[2];
} tr[4 * N];

inline int qmi(int a, int b)
{
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

inline int inv(int x)
{
    return qmi(x, mod - 2);
}

void pushup(node& root, node& left, node& right)
{
    root.v[0] = left.v[0] * right.v[0] % mod;
    root.v[1] = (left.v[1] + (left.v[0] * right.v[1] % mod)) % mod;
}

void pushup(int u)
{
    pushup(tr[u], tr[u * 2], tr[u * 2 + 1]);
}

void pushdown(int u)
{
    if (tr[u].add) {
        auto &root = tr[u], &left = tr[u * 2], &right = tr[u * 2 + 1];

        int x = tr[u].add;
        int ln = left.r - left.l + 1;
        int rn = right.r - right.l + 1;
        left.v[0] = qmi(x, ln);
        right.v[0] = qmi(x, rn);
        if (x == 1) {
            left.v[1] = ln, right.v[1] = rn;
        } else {
            left.v[1] = (qmi(x, ln) + mod - 1) % mod * x % mod * inv(x - 1) % mod;
            right.v[1] = (qmi(x, rn) + mod - 1) % mod * x % mod * inv(x - 1) % mod;
        }
        left.add = right.add = x;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    if (l != r) {
        int mid = (l + r) >> 1;
        build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
        pushup(u);
    } else {
        tr[u].v[0] = tr[u].v[1] = ar[l];
    }
}

void modify(int u, int l, int r, int x)
{
    if (l <= tr[u].l && tr[u].r <= r) {
        int un = tr[u].r - tr[u].l + 1;
        tr[u].add = x;
        tr[u].v[0] = qmi(x, un);
        if (x == 1) {
            tr[u].v[1] = un;
        } else {
            tr[u].v[1] = (qmi(x, un) + mod - 1) % mod * x % mod * inv(x - 1) % mod;
        }
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(u);
    if (l <= mid)
        modify(u * 2, l, r, x);
    if (r > mid)
        modify(u * 2 + 1, l, r, x);
    pushup(u);
}

node query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u];
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(u);
    if (r <= mid) {
        pushup(u);
        return query(u * 2, l, r);
    }
    if (l > mid) {
        pushup(u);
        return query(u * 2 + 1, l, r);
    }
    pushup(u);
    node vl = query(u * 2, l, r);
    node vr = query(u * 2 + 1, l, r);
    node res;
    pushup(res, vl, vr);
    return res;
}

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> ar[i];
    }
    build(1, 1, n);
    while (q--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            int x;
            cin >> x;
            modify(1, a, b, x);
        } else {
            node ans = query(1, a, b);
            cout << ans.v[1] << '\n';
        }
    }
}

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

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

题解 | #牛客小白月赛105#

A. lz的吃饭问题

思路

复杂度

代码实现

B. lz的数字问题

思路

复杂度

代码实现

C. lz的蛋挞问题

思路

复杂度

代码实现

D. lz的染色问题

思路

复杂度

代码实现

E. lz的括号问题

思路

复杂度

代码实现

F. lz的序列问题

思路

复杂度

代码实现