牛客小白月赛86 A - F

发布时间:2024年01月21日

水盐平衡

  • 思维
  • 判断一下浓度大小,再选择加水还是加盐。
signed main() {

    int T = 1;
    T = read();
    while (T--) {
        vector<int> a(5);
        for (int i = 1; i <= 4; ++i) a[i] = read();
        int t1 = a[1] * a[4], t2 = a[2] * a[3];
        t1 > t2? puts("S"): puts("Y");
    }
    return 0;
}

水平考试

  • 思维
  • 无论多选还是单选,有错的选项 0 0 0 分,没选全满分(小灰灰会填满)。
signed main() {

    int T = 1;
    T = read();
    while (T--) {
        string s1, s2; cin >> s1 >> s2;
        bool f = 1;
        for (auto it: s1) {
            if (s2.find(it) == -1) {
                f = 0;
                break;
            }
        }
        if (s2.size() > 1) f? puts("10"): puts("0");
        else f? puts("10"): puts("0");
    }
    return 0;
}

数组段数

  • 前缀和
  • p r e f i pref_i prefi? 表示从 1 1 1 i i i 最少划分多少段。
  • 注意:如果 a i = = a l ? 1 a_i==a_{l-1} ai?==al?1? 你得保留从 a l a_l al? 开始的那段。
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), m = read();
        vector<int> a(n + 1), pref(n + 1);
        for (int i = 1; i <= n; ++i) a[i] = read();
        for (int i = 1; i <= n; ++i) {
            if (a[i] ^ a[i - 1]) pref[i] = 1;
            pref[i] += pref[i - 1];
        }
        while (m--) {
            int l = read(), r = read();
            writeln(pref[r] - pref[l - 1] + (a[l - 1] == a[l]));
        }
    }
    return 0;
}

剪纸游戏

  • d f s dfs dfs
  • 题目说明了剪下来的图案不会联通,那么跑 d f s dfs dfs 的时候就记录一下面积,同时筛选出最小的行,列和最大的行,列。如果是一个矩形那么 S = ( l i n e m a x ? l i n e m i n ) ? ( c o l u m n m a x ? c o l u m n m i n ) S = (line_{max}-line_{min})\cdot(column_{max}-column_{min}) S=(linemax??linemin?)?(columnmax??columnmin?) ,判断并记录答案即可。
string mp[SN];
int n, m;
int d[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};
bool vis[SN][SN];
tuple<int, int, int, int, int> dfs(int x, int y) {
    int x1 = x, y1 = y, x2 = x, y2 = y, sum1 = 1;
    for (int i = 0; i < 4; ++i) {
        int xx = x + d[i][0], yy = y + d[i][1];
        if (xx < 0 || yy < 0 || xx >= n || yy >= m || vis[xx][yy] || mp[xx][yy] == '*') continue;
        vis[xx][yy] = 1;
        auto [xs1, ys1, xs2, ys2, sum] = dfs(xx, yy);
        x1 = min(x1, xs1), y1 = min(y1, ys1);
        x2 = max(x2, xs2), y2 = max(y2, ys2);
        sum1 += sum;
    }
    return {x1, y1, x2, y2, sum1};
}
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        n = read(), m = read();
        for (int i = 0; i < n; ++i) cin >> mp[i];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < mp[i].size(); ++j) {
                if (mp[i][j] ^ '*' && !vis[i][j]) {
                    vis[i][j] = 1;
                    auto [x1, y1, x2, y2, sum] = dfs(i, j);
                    if ((x2 - x1 + 1) * (y2 - y1 + 1) == sum) ++ans;
                }
            }
        }
        write(ans);
    }
    return 0;
}

可口蛋糕

  • 前缀和 + 枚举 + 双指针 O ( n ) O(n) O(n) o r or or 线段树 + 二分 O ( n l o g n ) O(nlogn) O(nlogn)
  • 从左往右枚举右端点,在保证 W W W 的情况下,你可以得出区间 [ 1 ?? , ?? j ] [1\;,\;j] [1,j] ,在这个区间选择一个左端点然后减去 1 1 1 到左端点的前缀和,因为是减去所以左端点的选定是区间 [ 1 ?? , ?? j ] [1\;,\;j] [1,j] 的最小值的索引。
  • 双指针左端点就保证 W W W 的情况一直往右移动选出最小值就好,
  • 注意:更新答案一定是满足 W W W 的情况下才能更新。

线段树 c o d e code code

vector<int> w(N), d(N), prefd(N), prefw(N);
struct p {
    int l, r, Min;
}tr[N << 2];
void pushup(int i) { tr[i].Min = min (tr[ls].Min, tr[rs].Min); }
void build(int i, int l, int r) {
    tr[i] = {l, r, (int)1e18};
    if (l == r) {
        tr[i].Min = prefd[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(i);
}
int query(int i, int l, int r) {
    if (tr[i].l >= l && tr[i].r <= r) return tr[i].Min;
    int res = 1e18;
    if (tr[ls].r >= l) res = min(res, query(ls, l, r));
    if (tr[rs].l <= r) res = min(res, query(rs, l, r));
    return res;
}
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), W = read();
        for (int i = 1; i <= n; ++i) {
            prefw[i] = w[i] = read();
            prefw[i] += prefw[i - 1];
        }
        for (int i = 1; i <= n; ++i) {
            prefd[i] = d[i] = read();
            prefd[i] += prefd[i - 1];
        }
        build(1, 1, n);
        int res = 0, ans = -1e18, ww = 0;
        for (int i = 1; i <= n; ++i) {
            ww += w[i], res += d[i];
            if (ww >= W) {
                int pos = upper_bound(prefw.begin() + 1, prefw.begin() + i + 1, ww - W) - prefw.begin();
                if (!--pos) continue;
                ans = max({ans, res - query(1, 1, pos), res});
            }
        }
        write(ans);
    }
    return 0;
}

双指针 c o d e code code

signed main() {
 
    int T = 1;
//    T = read();
    while (T--) {
		vector<int> w(N), d(N), prefd(N), prefw(N);
        int n = read(), W = read();
        for (int i = 1; i <= n; ++i) {
            prefw[i] = w[i] = read();
            prefw[i] += prefw[i - 1];
        }
        for (int i = 1; i <= n; ++i) {
            prefd[i] = d[i] = read();
            prefd[i] += prefd[i - 1];
        }
        int res = 0, ans = -1e18, ww = 0, l = 0, Min = 1e18;
        for (int i = 1; i <= n; ++i) {
            ww += w[i], res += d[i];
            while (ww - W >= prefw[l]) Min = min(Min, prefd[l++]);
            ans = max({ans, res - Min});
        }
        write(ans);
    }
    return 0;
}

喜欢序列

  • s e t set set + 树状数组 o r or or 线段树
  • 预处理断点, s e t set set 存断点下标。
  • 考虑加上 w w w l , r l,r l,r 处的关联情况。
    • l l l 与前一个断点相邻, r r r 不为断点。
    • l l l 与前一个断点相邻, r r r 为断点。
    • l l l 与前一个断点不相邻, r r r 不为断点。
    • l l l 与前一个断点不相邻, r r r 为断点。
  • 在断点处的情况考虑更新后两个区间是否能合并即可。
  • 不在断点处更新后则从端点处断开即可。
  • 注意:断点下标可能为 0 ?? o r ?? n 0\;or\;n 0orn 此时不用断开。

树状数组 c o d e code code

vector<int> a(N), tr(N);
signed main() {
    auto add = [] (int x, int n, int v) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
    };
    auto query = [&] (int x, int n) {
        int ans = 0;
        for (int i = x; i; i -= lowbit(i)) ans += tr[i];
        return ans;
    };
    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i) {
            a[i] = read();
            add(i, n, a[i] - a[i - 1]);
        }
        set<int> endpos;
        for (int i = 1; i <= n; ++i) {
            if (a[i] ^ (a[i - 1] + 1)) endpos.insert(i - 1);
        }
        endpos.insert(0), endpos.insert(n);
        int s = 0, pre = 0;
        for (auto it: endpos) {
            s += (it - pre) * (it - pre);
            pre = it;
        }
        auto powt = [&] (int x) {
            return x * x;
        };
        while (m--) {
            int l = read(), r = read(), w = read();
            if (!w) {
                writeln(s);
                continue;
            }
            add(l, n, w), add(r + 1, n, -w);
            auto pos1 = endpos.lower_bound(l), pos2 = endpos.lower_bound(r);
            if (l == *prev(pos1) + 1 && r ^ *pos2) {
                if (*prev(pos1)) {
                    int v1 = query(l - 1, n), v2 = query(l, n);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*pos1 - *prev(pos1)), t2 = powt(*prev(pos1) - *prev(prev(pos1)));
                        int t3 = powt(*pos1 - *prev(prev(pos1)));
                        s = s - t1 - t2 + t3;
                        endpos.erase(l - 1);
                    }
                }
                int t1 = powt(*pos2 - *prev(pos2));
                int t2 = powt(*pos2 - r), t3 = powt(r - *prev(pos2));
                s = s - t1 + t2 + t3;
                endpos.insert(r);
            }
            else if (l == *prev(pos1) + 1 && r == *pos2) {
                if (*prev(pos1)) {
                    int v1 = query(l - 1, n), v2 = query(l, n);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*pos1 - *prev(pos1)), t2 = powt(*prev(pos1) - *prev(prev(pos1)));
                        int t3 = powt(*pos1 - *prev(prev(pos1)));
                        s = s - t1 - t2 + t3;
                        endpos.erase(l - 1);
                    }
                }
                if (r ^ n) {
                    int v1 = query(r, n), v2 = query(r + 1, n);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*next(pos2) - r), t2 = powt(r - *prev(pos2));
                        int t3 = powt(*next(pos2) - *prev(pos2));
                        s = s - t1 - t2 + t3;
                        endpos.erase(r);
                    }
                }
            }
            else if (l ^ (*prev(pos1) + 1) && r == *pos2) {
                if (r ^ n) {
                    int v1 = query(r, n), v2 = query(r + 1, n);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*next(pos2) - r), t2 = powt(r - *prev(pos2));
                        int t3 = powt(*next(pos2) - *prev(pos2));
                        s = s - t1 - t2 + t3;
                        endpos.erase(r);
                    }
                }
                int t1 = powt(*pos1 - *prev(pos1));
                int t2 = powt(*pos1 - l + 1), t3 = powt(l - 1 - *prev(pos1));
                s = s - t1 + t2 + t3;
                endpos.insert(l - 1);
            }
            else if (l ^ (*prev(pos1) + 1) && r ^ *pos2) {
                int t1 = powt(*pos1 - *prev(pos1));
                int t2 = powt(*pos1 - l + 1), t3 = powt(l - 1 - *prev(pos1));
                s = s - t1 + t2 + t3;
                endpos.insert(l - 1);
                t1 = powt(*pos2 - *prev(pos2));
                t2 = powt(*pos2 - r), t3 = powt(r - *prev(pos2));
                s = s - t1 + t2 + t3;
                endpos.insert(r);
            }
            writeln(s);
        }
    }
    return 0;
}

线段树 c o d e code code

vector<int> a(N);
struct p {
    int l, r, v, tag;
}tr[N << 2];
void build(int i, int l, int r) {
    tr[i] = {l, r, 0, 0};
    if (l == r) {
        tr[i].v = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
}
void pushdown(int i) {
    if (tr[i].tag) {
        tr[ls].tag += tr[i].tag, tr[rs].tag += tr[i].tag;
        tr[ls].v += (tr[ls].r - tr[ls].l + 1) * tr[i].tag;
        tr[rs].v += (tr[rs].r - tr[rs].l + 1) * tr[i].tag;
        tr[i].tag = 0;
    }
}
void modify(int i, int l, int r, int k) {
    if (tr[i].l >= l && tr[i].r <= r) {
        tr[i].tag += k;
        tr[i].v += k;
        return ;
    }
    pushdown(i);
    if (tr[ls].r >= l) modify(ls, l, r, k);
    if (tr[rs].l <= r) modify(rs, l, r, k);
}
int query(int i, int pos) {
    if (tr[i].l == tr[i].r) return tr[i].v;
    pushdown(i);
    if (pos <= tr[ls].r) return query(ls, pos);
    else return query(rs, pos);
}
signed main() {
 
    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        build(1, 1, n);
        set<int> endpos;
        for (int i = 1; i <= n; ++i) {
            if (a[i] ^ (a[i - 1] + 1)) endpos.insert(i - 1);
        }
        endpos.insert(0), endpos.insert(n);
        int s = 0, pre = 0;
        for (auto it: endpos) {
            s += (it - pre) * (it - pre);
            pre = it;
        }
        auto powt = [&] (int x) {
            return x * x;
        };
        for (int i = 1; i <= m; ++i) {
            int l = read(), r = read(), w = read();
            if (!w) {
                writeln(s);
                continue;
            }
            modify(1, l, r, w);
            auto pos1 = endpos.lower_bound(l), pos2 = endpos.lower_bound(r);
            if (l == *prev(pos1) + 1 && r ^ *pos2) {
                if (*prev(pos1)) {
                    int v1 = query(1, l - 1), v2 = query(1, l);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*pos1 - *prev(pos1)), t2 = powt(*prev(pos1) - *prev(prev(pos1)));
                        int t3 = powt(*pos1 - *prev(prev(pos1)));
                        s = s - t1 - t2 + t3;
                        endpos.erase(l - 1);
                    }
                }
                int t1 = powt(*pos2 - *prev(pos2));
                int t2 = powt(*pos2 - r), t3 = powt(r - *prev(pos2));
                s = s - t1 + t2 + t3;
                endpos.insert(r);
            }
            else if (l == *prev(pos1) + 1 && r == *pos2) {
                if (*prev(pos1)) {
                    int v1 = query(1, l - 1), v2 = query(1, l);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*pos1 - *prev(pos1)), t2 = powt(*prev(pos1) - *prev(prev(pos1)));
                        int t3 = powt(*pos1 - *prev(prev(pos1)));
                        s = s - t1 - t2 + t3;
                        endpos.erase(l - 1);
                    }
                }
                if (r ^ n) {
                    int v1 = query(1, r), v2 = query(1, r + 1);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*next(pos2) - r), t2 = powt(r - *prev(pos2));
                        int t3 = powt(*next(pos2) - *prev(pos2));
                        s = s - t1 - t2 + t3;
                        endpos.erase(r);
                    }
                }
            }
            else if (l ^ (*prev(pos1) + 1) && r == *pos2) {
                if (r ^ n) {
                    int v1 = query(1, r), v2 = query(1, r + 1);
                    if (v1 + 1 == v2) {
                        int t1 = powt(*next(pos2) - r), t2 = powt(r - *prev(pos2));
                        int t3 = powt(*next(pos2) - *prev(pos2));
                        s = s - t1 - t2 + t3;
                        endpos.erase(r);
                    }
                }
                int t1 = powt(*pos1 - *prev(pos1));
                int t2 = powt(*pos1 - l + 1), t3 = powt(l - 1 - *prev(pos1));
                s = s - t1 + t2 + t3;
                endpos.insert(l - 1);
            }
            else if (l ^ (*prev(pos1) + 1) && r ^ *pos2) {
                int t1 = powt(*pos1 - *prev(pos1));
                int t2 = powt(*pos1 - l + 1), t3 = powt(l - 1 - *prev(pos1));
                s = s - t1 + t2 + t3;
                endpos.insert(l - 1);
                t1 = powt(*pos2 - *prev(pos2));
                t2 = powt(*pos2 - r), t3 = powt(r - *prev(pos2));
                s = s - t1 + t2 + t3;
                endpos.insert(r);
            }
            writeln(s);
        }
    }
    return 0;
}
文章来源:https://blog.csdn.net/wyzz_yz/article/details/135728711
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。