QYcode QYcode
C++

8.7总结

· 2026-8-7 18:11:37

8.7总结

今天的题目都很水啊，没有什么很难的题目，除了最后一道没时间打以外，没有什么问题了

T1:Air Conditioners

链接:Air Conditioners - 题目详情 - QY code

题目大意：

有一条长度为 n 的格子带，编号从 1 到 n。

其中有 k 台空调，第 i 台空调放在格子 a[i]，设定温度为 t[i]。

对于每个格子 i，它的温度等于：

min⁡1≤j≤k(tj+∣aj−i∣)\min_{1\le j\le k}\big(t_j+|a_j-i|\big)

也就是说：

每个格子的温度，等于所有空调的“空调温度 + 到该格子的距离”中的最小值。

代码思路：

这道题如果直接暴力枚举每个格子、再枚举每台空调，复杂度是 O(nk)，可能会慢。

而我用了更聪明的方法：两次线性扫描，复杂度 O(n)。

复杂度：

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll res[300010];
int a[300010];
ll t[300010]; 
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n, k;
        scanf ("%d%d", &n, &k);
        for (int i = 1; i <= k; i++) scanf ("%d", &a[i]);
        for (int i = 1; i <= k; i++) scanf ("%lld", &t[i]);
        for (int i = 1; i <= n; i++) res[i] = INF;
        for (int i = 1; i <= k; i++) res[a[i]] = t[i];
        for (int i = 2; i <= n; i++) res[i] = min (res[i], res[i - 1] +  1);
        for (int i = n - 1; i >= 1; i--) res[i] = min (res[i], res[i + 1] + 1);
        for (int i = 1; i <= n; i++) printf ("%lld ", res[i]);
        printf ("\n");
    } 
    return 0;
}

T2:In Love

链接：In Love - 题目详情 - QY code

题目大意：

有一个初始为空的线段多重集，需要处理 q 次操作：

  • + l r：往集合里加入一条线段 (l, r)
  • - l r：从集合里删掉一条线段 (l, r)（保证一定存在）

每次操作后，判断集合中是否存在一对不相交的线段。

两条线段 (l, r) 和 (a, b) 不相交，意思是它们没有公共点。

判断方法：r<ar<a或b<lb<l

也就是说，一条线段完全在另一条线段的左边或右边。

如果集合中存在一对不相交的线段，那么一定存在：

最大的左端点>最小的右端点

也就是：max(l)>min(r)max(l)>min(r)

原因很简单：

  • 如果有一条线段左端点很大，说明它整体偏右；
  • 如果有一条线段右端点很小，说明它整体偏左；
  • 当最大左端点严格大于最小右端点时，这两条线段一定不相交。

所以问题变成：

维护所有线段左端点的最大值，以及右端点的最小值。

代码思路：

maxl 大根堆，维护左端点最大值
minr 小根堆，维护右端点最小值
cntl 记录每个左端点当前出现次数
cntr 记录每个右端点当前出现次数
tot 当前集合中线段数量

删除线段时，代码没有直接从堆里删除，而是：

  • 线段数量减 1；
  • 对应左端点和右端点的出现次数减 1。

这属于一种懒删除：

堆里的值先不删，等以后取堆顶时，如果发现它已经失效，就丢掉。

如果 maxl 堆顶对应的左端点已经被删完了，就把它弹出，直到堆顶是有效的。

如果线段数量小于 2，不可能存在一对线段，所以输出 NO。

这里判断：

max(l)>min(r)max(l)>min(r)

  • 如果成立，说明存在一条线段左端点很大，另一条线段右端点很小，它们不相交，输出 YES。
  • 否则输出 NO。

注意：max(l)≤min(r)max(l)≤min(r)表示所有线段的左端点都不超过最小右端点，所以任意两条线段都有公共点，不存在不相交的一对。

复杂度

每次操作：

  • 堆最多插入一次；
  • 懒删除时每个元素最多被弹出一次；
  • map 操作是 O(log n)。

所以整体复杂度大约是：O(q logq)O(q\ log_q)

空间复杂度：

O(q)O(q)

代码：

#include <bits/stdc++.h>
using namespace std;
int main () {
    int q;
    scanf ("%d", &q);
    priority_queue <int> maxl;
    priority_queue <int, vector <int>, greater <int> > minr;
    map <int, int> cntl, cntr;
    int tot = 0; 
    while (q--) {
        char op[2];
        int l, r;
        scanf ("%s%d%d", op, &l, &r);
        if (op[0] == '+') {
            tot ++;
            maxl.push (l), minr.push (r);
            cntl[l] ++, cntr[r] ++;
        } 
        if (op[0] == '-') {
            tot --;
            cntl[l] --, cntr[r] --;
        }
        while (!maxl.empty ()) {
            int top = maxl.top ();
            if (cntl[top] > 0) break;
            maxl.pop ();
        }
        while (!minr.empty ()) {
            int top = minr.top ();
            if (cntr[top] > 0) break;
            minr.pop ();
        }
        if (tot < 2) puts ("NO");
        else {
            int maxL = maxl.top ();
            int minR = minr.top ();
            if (maxL <= minR) puts ("NO");
            else puts ("YES");
        }
    }
    return 0;
}

T3:Data Structures Fan

链接：Data Structures Fan - 题目详情 - QY code

题目大意：

给定一个长度为 n 的数组 a，以及一个长度为 n 的二进制字符串 s（只含 0 和 1）。

需要处理 q 次查询，有两种操作：

  • 1 l r：把 s[l] 到 s[r] 全部取反（0 变 1，1 变 0）。
  • 2 g：查询所有满足 s[i] == g 的 a[i] 的异或和。

思路：

这道题的关键在于：

区间取反时，不需要真的去修改字符串 s，只需要维护两个值：

  • xor0：当前所有 s[i] == '0' 的 a[i] 的异或和
  • xor1：当前所有 s[i] == '1' 的 a[i] 的异或和

当对区间 [l, r] 取反时，这个区间里原本属于 0 的数会变成 1，原本属于 1 的数会变成 0。

所以只需要把区间 [l, r] 内所有数的异或和 fan 同时异或到 xor0 和 xor1 上即可。

原理：

  • 对于 xor0：原来在 0 组里的数被移走了（异或一次抵消），原来在 1 组里的数被加进来了（异或一次加入）。
  • 对于 xor1：同理。

因此：

xor0 ^= fan;
xor1 ^= fan;

就能同时完成两个组的更新。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010], pre[100010];
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
        char s[100010];
        scanf ("%s", s + 1);
        pre[0] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ a[i];
        ll xor0 = 0, xor1 = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '0') xor0 ^= a[i];
            else xor1 ^= a[i];
        } 
        int q;
        scanf ("%d", &q);
        while (q--) {
            int tp;
            scanf ("%d", &tp);
            if (tp == 1) {
                int l, r;
                scanf ("%d%d", &l, &r);
                ll fan = pre[r] ^ pre[l - 1];
                xor0 ^= fan, xor1 ^= fan;
            }
            else {
                int g;
                scanf ("%d", &g);
                if (g == 0) printf ("%lld ", xor0);
                else printf ("%lld ", xor1);
            }
        }
        printf ("\n");
    }
    return 0;
}

T4:Divide and Summarize

链接：Divide and Summarize - 题目详情 - QY code

题目大意：

有一个长度为 n 的数组 a，你可以对它反复做切分操作：

  • 计算

mid=⌊max+min2​⌋mid=⌊\frac{max+min}{2}​⌋

  • 把当前数组分成两部分：
    • left：所有 <= mid 的元素
    • right：所有 > mid 的元素
  • 只能保留 left 或 right 中的一个，另一个永久丢弃。

你可以操作任意次，也可以不操作。

对于每个询问 s，判断是否能通过若干次切分，使最终数组的元素和恰好等于 s。

思路：

用 DFS 枚举所有可能通过切分得到的子数组，把它们的元素和全部预处理出来，存进一个集合里。

之后每次查询只需要判断：s是否在集合中

如果在，输出 Yes，否则输出 No。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_set <ll> st;
int get_max (vector <int> a) {
    int res = a[0];
    for (int x : a) {
        if (x > res) res = x;
    }
    return res;
}
int get_min (vector <int> a) {
    int res = a[0];
    for (int x : a) {
        if (x < res) res = x;
    }
    return res;
}
void dfs (vector <int> a) {
    ll sum = 0;
    for (int x : a) sum += x;
    st.insert (sum);
    int maxn = get_max (a);
    int minn = get_min (a);
    if (maxn == minn) return ;
    int mid = (maxn + minn) / 2;
    vector <int> l, r;
    for (int x : a) {
        if (x <= mid) l.push_back (x);
        else r.push_back (x);
    }
    if (!l.empty ()) dfs (l);
    if (!r.empty ()) dfs (r);
}
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n, q;
        scanf ("%d%d", &n, &q);
        vector <int> a (n + 1);
        vector <int> tmp;
        for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
        for (int i = 1; i <= n; i++) tmp.push_back (a[i]);
        st.clear ();
        dfs (tmp);
        while (q--) {
            ll s;
            scanf ("%lld", &s);
            if (st.count (s)) puts ("Yes");
            else puts ("No");
        }
    }
    return 0;
}

T5:Vessels

链接：Vessels - 题目详情 - QY code

水题，绝对的水题！

题目大意：

有 n 个容器从上到下排成一列，第 i 个容器的容量为 a[i]。水从上往下流：当某个容器满了之后，多余的水会流入下一个容器；第 n 个容器溢出则流到地板上。

需要处理两种操作：

  • 1 p x：向第 p 个容器倒入 x 升水（模拟溢流过程）。
  • 2 k：查询第 k 个容器当前有多少水。

思路：

如果朴素模拟，每次倒水都从 p 开始逐层往下找未满的容器，最坏情况下会退化成 O(n)，总复杂度可能达到 O(nm)，会超时。

关键观察：当一个容器满了之后，以后再有水流到它这里，一定会直接流到下一个容器。所以我们可以用并查集把已满的容器"跳过"，让 find(i) 直接返回从 i 开始第一个未满的容器。

具体做法：

  • fa[i] = i：表示第 i 个容器还没满，水可以停在这里。
  • 当第 i 个容器满了之后，执行 fa[i] = find(i + 1)，让它指向下一个容器。
  • 这样 find(p) 就能快速跳过所有已满的容器，直接找到第一个能接水的容器。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int fa[200010];
ll a[200010], water[200010];
int find (int x) {
    if (fa[x] == x) return x;
    return fa[x] = find (fa[x]);
}
int main () {
    int n;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
        water[i] = 0;
        fa[i] = i;
    }
    fa[n + 1] = n + 1;
    int m;
    scanf ("%d", &m);
    while (m--) {
        int op;
        scanf ("%d", &op);
        if (op == 1) {
            int p;
            ll x;
            scanf ("%d%lld", &p, &x);
            int cur = find (p);
            while (cur <= n && x > 0) {
                ll can = a[cur] - water[cur];
                if (can <= x) {
                    water[cur] = a[cur];
                    x -= can;
                    fa[cur] = find (cur + 1);
                    cur = find (cur);
                }
                else {
                    water[cur] += x;
                    x = 0;
                }
            }
        }
        else {
            int k;
            scanf ("%d", &k);
            printf ("%lld\n", water[k]);
        } 
    }
    return 0;
}

T6:Array Restoration

链接：Array Restoration - 题目详情 - QY code

题目大意：

有一个长度为 n 的数组，初始值任意。依次执行 q 次操作，第 i 次操作选择一个区间 [l, r]，把该区间内所有元素改成 i。所有操作执行完后，某些位置被改成了 0，表示“未知”。

现在给你一个最终数组（含 0），问能否通过上述操作得到它。如果可以，输出任意一种还原方案。

思路：

这道题的关键在于理解操作的性质：

  • 操作是覆盖式的：第 i 次操作会把区间全改成 i，后面的操作会覆盖前面的。
  • 操作顺序固定：第 q 次操作最后执行，所以最终数组中值为 q 的元素一定是连续的（来自最后一次操作的区间）。
  • 合法性条件：对于任意值 x，它在最终数组中出现的所有位置构成一个区间 [L[x], R[x]]。在这个区间内，不能出现比 x 更小的值——因为如果有更小的值 y < x，说明 y 是在 x 之后被写入的，但 y 的操作编号更小，不可能在 x 之后执行。

代码的整体思路：

  1. 填充 0：先把 0 用相邻的非零值填充（从左到右、从右到左各扫一遍）。
  2. 检查 q 是否存在：如果数组中没有 q，必须把一个 0 改成 q；如果没有 0 也没有 q，则无解。
  3. 合法性验证：对每个值 x，检查其出现区间 [L[x], R[x]] 内的最小值是否 >= x。用 ST 表实现 O(1) 区间最小值查询。

代码：

#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
const int INF=200005;
int n,q;
int a[200010],b[200010];
int L[200010],R[200010];
int st[LOG][200010];
int logn[200010];
int get_min (int l, int r) {
    int len = r - l + 1;
    int k = logn[len];
    return min (st[k][l], st[k][r - (1 << k) + 1]);
}
int main () {
    scanf ("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &a[i]);
        b[i] = a[i];
    }
    if(b[1] == 0) b[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (b[i] == 0) b[i] = b[i - 1];
    }
    for (int i = n - 1; i >= 1; i--) {
        if (b[i] == 0) b[i] = b[i + 1];
    }
    bool has_q = false;
    for (int i = 1; i <= n; i++) {
        if (b[i] == q) has_q = true;
    }
    if (!has_q) {
        bool flag = false;
        for (int i = 1; i <= n; i++) {
            if (a[i] == 0) {
                b[i] = q;
                flag = true;
                break;
            }
        }
        if (!flag) {
            printf("NO\n");
            return 0;
        }
    }
    for (int i = 1; i <= q; i++) L[i] = INF, R[i] = -1;
    for (int i = 1; i <= n; i++) {
        int val = b[i];
        L[val] = min (L[val], i);
        R[val] = max (R[val], i);
    }
    logn[1] = 0;
    for (int i = 2; i <= n; i++) logn[i] = logn[i / 2] + 1;
    for (int i = 1; i <= n; i++) st[0][i] = b[i];
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) st[j][i] = min (st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    }
    bool ok = true;
    for (int x = 1; x <= q; x++) {
        if (L[x] > R[x]) continue;
        int mn = get_min (L[x], R[x]);
        if (mn < x) {
            ok = false;
            break;
        }
    }
    if (!ok) printf ("NO\n");
	else {
        printf ("YES\n");
        for (int i = 1; i <= n; i
++) printf ("%d ",b[i]);
        printf ("\n");
    }
    return 0;
}
//我用的是ST表，但这道题实际上使用栈会更快
1 次查看 举报

0 条评论

目前还没有评论...

Be the first to comment!

返回讨论列表
zhuyqi
277
通过题目
12
发帖数