2023.1.28 模拟赛记录

2023冬

预期得分：

实际得分：

Summary

T1: 考场上数组开小了，挂成30分
T2: 考场AC
T3: 考场上的时候想到了大致的维护策略，却执着于将线段树二分与修改放在一起写，增加了很多代码细节，导致没写出来。

T1 human

涉及算法/想法：异或，构造
思维难度：$A$
代码难度：$D$

Description

上了大学之后，小W 和 小Z 一起报了一门三宝课，在实践课上遇到了一些问题。
一条染色体上有 $n$ 对基因，每种基因都可以用一个数 $a_i$ 来表示，作为标号。
现在，在其中一条染色单体上某基因发生了突变。
此时染色体上有 $(n-1)$ 对相同的基因和一对不同的基因。
他们通过某种方法获得了这条染色体上的全部基因。
现在他们想知道发生突变的基因的标号是什么。

Solution

想法非常神奇的一道题目。

我们考虑用一个长度为 $64$ 的容器解决问题。

我们将容器分成两部分，将 $a_i$ 二进制分解，将为 $1$ 的第 $i$ 位异或上 $a_i$，将为 $0$ 的第 $i + 32$ 位异或上 $a_i$

此时，除了要求的两个数外，其他的数的贡献一定会消除，并且，容器中必定会剩下 $3$ 个数，$a$，$b$，$a$^$b$

并且将所有数直接异或起来就可以得到 $a$^$b$，则可以得到 $a$, $b$

Code

//The Code Is By HJC
# include <cstdio>
# define max(a, b) (a>b?a:b)
# define min(a, b) (a<b?a:b)
// # define N 1001000
using namespace std;
int n;
// int a[N];
int f[70], ban;
int main() {
  // freopen("human.in", "r", stdin);
  // freopen("human.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1, a; i <= n + n; i++) {
    scanf("%d", &a);
    ban ^= a;
    for (int i = 0; i < 32; i++) {
      if ((a >> i) & 1) {
        f[i] ^= a;
      } else {
        f[i + 32] ^= a;
      }
    }
  }
  int ans1 = 0, ans2 = 0;
  for (int i = 0; i < 64; i++) {
    if (f[i] && f[i] != ban) {
      if (ans1 == 0) {
        ans1 = f[i];
      } else if (f[i] != ans1) {
        ans2 = f[i];
        break;
      }
    }
  }
  printf("%d %d\n", min(ans1, ans2), max(ans1, ans2));
}

T2 garden

涉及算法/想法：前缀和，鸽巢原理
思维难度：$C$
代码难度：$D$

Description

上了大学之后，小W 和 小Z 一起报了一门水课，在做作业时遇到了问题。
有一个长度为 $n$ 的数列 $a$ ，为一列树木的美观值。
现在有 $m$ 次询问，每次给出三个数 $l$ , $r$ 和 $P$
询问对于所有的 $l \leq l' \leq r' \leq r$
$(a[l'] + a[l' + 1] + ... + a[r']) \bmod P$ 的最小值。

$1 \leq n, m \leq 5 * 10^4, 1 \leq l \leq r \leq n, 1 \leq P \leq 100, 0 \leq a[i] \leq 10^9$

Solution

先转化成前缀和 $(Sum[r] - Sum[l - 1]) \bmod P$

则我们希望，$Sum[r] \equiv Sum[l - 1]\pmod P$

长度如果超过 $P$，则必定有 $Sum[r] \equiv Sum[l - 1]\pmod P$

那么最多只有长度为 $\leq 100$ 的区间是有用的，这部分暴力即可。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 5 * 1e4 + 5;
int n, Q, T;
int a[maxn], Answer;
struct node {
    int l, r, id;
};
signed main() {
    freopen("garden.in", "r", stdin);
    freopen("garden.out", "w", stdout);
    n = read(), Q = read();
    for(register int i = 1; i <= n; ++i) a[i] = read();
    while(Q--) {
        int il = read(), ir = read(), mod = read();
            if(ir - il + 1 > mod) { printf("0\n"); continue; }
            Answer = 1e9 + 7;
            for(register int l = il; l <= ir; ++l) {
                int Cnt = 0;
                for(register int r = l; r <= ir; ++r) {
                    Cnt = (Cnt + a[r]) % mod;
                    Answer = min(Answer, Cnt);
                }
            }
        printf("%lld\n", Answer);
    }
    return 0;
}

T3 psy

涉及算法/想法：线段树，线段树二分
思维难度：$B^{+}$
代码难度：$A^{-}$

Description

给定 $n$ 个三元组 $(a,b,c)$，要求分到 $3$ 个集合 $S_a$, $S_b$, $S_c$ 中，每个集合的价值是三元组中对应元素的最大值，要求三个集合价值之和最小。

Solution

考虑枚举 $a$，计算 $b,c$

容易得到一个 $O(n^2\log n)$ 的做法。

发现每次重新排序太冗余，考虑将 $a$ 的枚举倒过来，则每次只需要加入一个双元组 $(b,c)$。

考虑他对后半段答案的影响。

我们可以将答案表示为 $\min(b_i + cmax_i)$ 其中 $cmax_i$ 为 $c$ 的后缀最大值。

那么只有在 $[0,b_i)$ 的区间中，满足 $cmax_i < c$ 的子区间会被影响到，并且是一个区间推平的操作。

那么考虑维护一颗线段树，每次线段树上二分出子区间的左端点，将子区间做区间推平，顺便维护答案即可。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5, INF = 1e9 + 7;
int n, Answer;
struct node {
    int a, b, c;
}Point[maxn];
int ls[maxn], tot;
namespace Sigment_Tree {
    struct node_Tree {
        int Suf, minn;
        int lz;
    }Tree[maxn << 2];
    #define lc(i) i << 1
    #define rc(i) i << 1 | 1
    inline void Push_Up(int i) { 
        Tree[i].Suf = min(Tree[lc(i)].Suf, Tree[rc(i)].Suf);
        Tree[i].minn = min(Tree[lc(i)].minn, Tree[rc(i)].minn);
    }
    inline void Build(int i, int l, int r) {
        Tree[i].Suf = 0;
        if(l == r) { Tree[i].minn = ls[l]; return ; } 
        int mid = (l + r) >> 1;
        Build(lc(i), l, mid), Build(rc(i), mid + 1, r);
        Push_Up(i);
    }
    inline void Push_Down(int i, int l, int r) {
        int mid = (l + r) >> 1;
        if(Tree[i].lz) {
            Tree[lc(i)].Suf = Tree[rc(i)].Suf = Tree[i].lz;
            Tree[lc(i)].lz = Tree[rc(i)].lz = Tree[i].lz;
            Tree[lc(i)].minn = Tree[i].lz + ls[l];
            Tree[rc(i)].minn = Tree[i].lz + ls[mid + 1];
            Tree[i].lz = 0;
        }
    }
    inline void Update(int i, int l, int r, int ql, int qr, int num) {
        if(l >= ql && r <= qr) {
            Tree[i].minn = num + ls[l];
            Tree[i].lz = Tree[i].Suf = num;
            return ;
        }
        Push_Down(i, l, r);
        int mid = (l + r) >> 1;
        if(ql <= mid) Update(lc(i), l, mid, ql, qr, num);
        if(qr > mid) Update(rc(i), mid + 1, r, ql, qr, num);
        Push_Up(i);
    }
    inline int Find(int i, int l, int r, int num) {
        Push_Down(i, l, r);
        if(l == r) return l;
        int mid = (l + r) >> 1;
        if(Tree[lc(i)].Suf <= num) return Find(lc(i), l, mid, num);
        else return Find(rc(i), mid + 1, r, num);
    }
}
using namespace Sigment_Tree;
signed main() {
    freopen("psy.in", "r", stdin);
    freopen("psy.out", "w", stdout);
    n = read();
    for(register int i = 1; i <= n; ++i) {
        Point[i].a = read();
        ls[++tot] = Point[i].b = read();
        Point[i].c = read();
    }
    sort(ls + 1, ls + tot + 1); tot = unique(ls + 1, ls + tot + 1) - ls - 1;
    for(register int i = 1; i <= n; ++i) Point[i].b = lower_bound(ls + 1, ls + tot + 1, Point[i].b) - ls;
    sort(Point + 1, Point + n + 1, [&](node x, node y){ return x.a < y.a; });
    Answer = Point[n].a, Build(1, 0, tot);
    for(register int i = n - 1; i >= 0; --i) {
        int pos = Find(1, 0, tot, Point[i + 1].c);
        Update(1, 0, tot, pos, Point[i + 1].b - 1, Point[i + 1].c);
        Answer = min(Answer, Point[i].a + Tree[1].minn);
    }
    printf("%lld\n", Answer);
    return 0;
}