牛客练习赛73 ABCD题解

补题原则

ABCD四题比赛时通过人数均超过40
其中ABC题较水，用来练习python语法
D用来锻炼自己的思维

A.招生

简单模拟题，考察排序，注意分数不能小于0
python的排序函数 $sorted$ ，如果只调用 $sorted(a)$ 并不会把 $a$ 的元素排序
需要执行 $a = sorted(a)$
另外第m大可以用 $a[-m]$ 得到

Code

n, m, p = map(int, input().split())
a = []
for i in range(n):
  x, y = map(int, input().split())
  a.append(x * 0.85 + y * 0.15)
a = sorted(a)
#print(a[-m])
ans = int((a[-m] - p * 0.15) / 0.85) + 1
if ans <= 0:
  ans = 0
print(ans)

B.遥远的记忆

我的方法是构造一个初始为 $1$ 到 $n$ 的数组，进行原来 $c_i$ 数组的变换规则后，最后找该数组有多少个不同元素

Code

n = int(input())
c = list(map(int, input().split()))
a = [0] * n
for i in range(n):
  a[i] = i
vis = [0] * n
for i in range(n - 1, -1, -1):
  if c[i] == 1 and i != n - 1:
    a[i] = a[i + 1]
for i in range(n):
  if c[i] == 0 and i != 0:
    a[i] = a[i - 1]
#print(a)
ans = 0
for i in range(n):
  if vis[a[i]] == 0:
    vis[a[i]] = 1
    ans += 1
print(ans)

C. 生涯回忆录

题目显然就是要让我们求 $mex$ ，不妨枚举能够作为 $mex$ 的值为 $i$
对于大于 $i$ 的值都可以放进来，即贡献为 $\prod\limits_{x > i} 2^{cnt_x}$
对于小于 $i$ 的值不能为空，否则会跟前面统计的有重复，即贡献为 $\prod\limits_{x < i} 2^{cnt_x} - 1$
处理一下前后缀积即可。因为 $mex$ 最大为 $n + 1$ (鸽巢原理)
超过 $n + 1$ 的数字看做是 $n + 2$ 即可

Code

mod = 20000311
n = int(input())
a = list(map(int, input().split()))
# x range in [0, n + 1]
vis = [0] * (n + 10)
s = [0] * (n + 10)
s[0] = 1
for i in range(1, n + 5):
  s[i] = s[i - 1] * 2 % mod

for i in range(n): #calculate how many time one number appears  
  if a[i] > n + 1:
    vis[n + 2] += 1
  else:
    vis[a[i]] += 1

fac1 = [1] * (n + 10)
fac2 = [1] * (n + 10)

for i in range(1, n + 5):
  fac1[i] = fac1[i - 1] * (s[vis[i]] - 1 + mod) % mod
for i in range(n + 4, -1, -1):
  fac2[i] = fac2[i + 1] * s[vis[i]] % mod
ans = 0
for i in range(1, n + 2): # enum x from [0, n + 1] 
  ans += i * fac1[i - 1] * fac2[i + 1] % mod
  ans %= mod
print(ans)

D. 离别

$tags:$ 离线查询+线段树
看了一篇题解
注意是连续的区间，那么每个数字的贡献只有跟上次出现的位置有关
我们可以记录当前位置的 $a_i$ 是第几次出现，以及每个 $a_i$ 出现的位置，那么对于当前的 $i$ , 如果目前已经出现过 $k$ 次，显然就会出现一个区间对他有贡献，关于贡献可以用线段树来维护。
如样例，画出下图：
图片说明

$pos = 3$ 的时候，此时 $2$ 出现的次数已经满足 $>=k$ , 维护一个满足条件的区间 $[1, 2]$
$pos = 4$ 的时候，此时 $1$ 出现的次数已经满足 $>=k$ , 维护一个满足条件的区间 $[1, 2]$ ( $r$ 要保证最大，因为维护的是区间数量最多的)
$pos = 5$ 的时候，此时 $2$ 出现的次数 $> k$ , 区间指针右移，变成 $[3, 3]$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N]; 
struct node {
  int l, r, id;
};
vector<node> Q[N];
vector<int> pos[N];
int sum[N];
ll ans[N];
struct Tree {
  int l, r;
  ll sum, lazy;
}t[N << 2];
void push_up(int rt) {
  t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum;
}
void push_down(int rt) {
  if(t[rt].lazy) {
    t[rt << 1].sum += (t[rt << 1].r - t[rt << 1].l + 1) * t[rt].lazy;
    t[rt << 1].lazy += t[rt].lazy;  
    t[rt << 1 | 1].sum += (t[rt << 1 | 1]. r - t[rt << 1 | 1].l + 1) * t[rt].lazy;
    t[rt << 1 | 1].lazy += t[rt].lazy;
    t[rt].lazy = 0;
  }
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    return ;
  }
  int mid = l + r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
}
void update(int rt, int ql, int qr, int x) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    t[rt].lazy += x;
    t[rt].sum += 1LL * (t[rt].r - t[rt].l + 1) * x;
    return ;
  }
  push_down(rt);
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    update(rt << 1, ql, qr, x);
  } else if(ql > mid) {
    update(rt << 1 | 1, ql, qr, x);
  } else {
    update(rt << 1, ql, mid, x);
    update(rt << 1 | 1, mid + 1, qr, x);
  }
  push_up(rt);
}
ll query(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return t[rt].sum;
  }
  push_down(rt);
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return query(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query(rt << 1 | 1, ql, qr);
  } else {
    return query(rt << 1, ql, mid) + query(rt << 1 | 1, mid + 1, qr);
  }
  push_up(rt);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, q, k; cin >> n >> q >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= q; i++) {
    int l, r; cin >> l >> r;
    Q[r].emplace_back(node{l, r, i});
  }
  for(int i = 1; i <= n; i++) {
    sum[i] = pos[a[i]].size();
    pos[a[i]].push_back(i);
  }
  build(1, 1, n);
  for(int i = 1, l = 0, r = 0; i <= n; i++) {
    if(sum[i] >= k - 1) {
      r = max(r, pos[a[i]][sum[i] - k + 1]);
    }
    if(sum[i] >= k) {
      l = max(l, pos[a[i]][sum[i] - k]);
    }
    if(l < r) {
      update(1, l + 1, r, 1);
    }
    for(auto &x : Q[i]) {
      ans[x.id] = query(1, x.l, x.r);
    }
  }
  for(int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}