11-21模拟赛

11 / 21 / 2020 | 最后修改于 11 / 21 / 2020

Contest OI

宝藏

题目描述

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nn 个深埋在地下的宝藏，第 ii 个宝藏价值为 wiw_i，挖掘它需要时间 tit_i。

赞助商给小明的时间是有限的，他只有 TT 的时间用来挖掘宝藏。也就是说他挖掘的宝藏消耗的总时间不得超过 TT。现在小明一共进行了 QQ 次开采活动，第 ii 次开采正好开采 xix_i 个宝藏（保证 xix_i 为奇数），他想要您计算开采的宝藏的价值的中位数最大是多少。（这些开采活动是独立的，即不会实际对宝藏造成影响）

题解

发现当选取的宝藏越多时，答案单调减，所以先将宝藏按 ww 排序，从最大值开始扫，同时维护从 n∼i+1n \sim i+1 和 i−1∼1i-1 \sim 1 的前 kk 小的 tt 的和，题解用的主席树，但是由于要查询的区间只有两种且有规律，用两棵线段树就好了

考试时由于没考虑清加入、删除和查询的先后顺序，挂成78了（还调了4个小时） /kk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Tags:
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 3e5 + 5, M = 1e6 + 5;
int n, q, maxt, ans[N];
ll t;

struct Obj {
  int w, t;
  inline bool operator<(const Obj &rhs) const { return w < rhs.w; }
} a[N];

struct SegmentTree {
  struct Node {
    int cnt;
    ll sum;
  } tr[M << 2];

  inline void pushup(int x) {
    tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
    tr[x].cnt = tr[x << 1].cnt + tr[x << 1 | 1].cnt;
  }

  ll query(int x, int l, int r, int p) {
    if (p == 0) return 0;
    if (l == r) { return (ll)p * l; }
    int mid = (l + r) >> 1;
    if (p <= tr[x << 1].cnt) return query(x << 1, l, mid, p);
    return tr[x << 1].sum + query(x << 1 | 1, mid + 1, r, p - tr[x << 1].cnt);
  }

  void modify(int x, int l, int r, int p, int v) {
    if (l == r) { return tr[x].cnt += v, tr[x].sum += p * v, void(); }
    int mid = (l + r) >> 1;
    if (p <= mid) modify(x << 1, l, mid, p, v);
    else
      modify(x << 1 | 1, mid + 1, r, p, v);
    pushup(x);
  }
} pre, suf;

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("treasure.in", "r", stdin);
  freopen("treasure.out", "w", stdout);
#endif
#endif

  read(n), read(t), read(q);
  for (int i = 1; i <= n; ++i)
    read(a[i].w), maxt = std::max(maxt, read(a[i].t));
  std::sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) pre.modify(1, 0, maxt, a[i].t, 1);
  memset(ans, -1, sizeof(ans));
  for (int i = n, j = 1; i && j <= n; --i) {
    pre.modify(1, 0, maxt, a[i].t, -1);
    while (((j >> 1) <= i - 1) && ((j >> 1) <= n - i) &&
           (suf.query(1, 0, maxt, j >> 1) + pre.query(1, 0, maxt, j >> 1) +
                a[i].t <=
            t)) {
      ans[j] = a[i].w, j += 2;
    }
    suf.modify(1, 0, maxt, a[i].t, 1);
  }
  for (int i = 1, x; i <= q; ++i) { printf("%d\n", ans[read(x)]); }
  return 0;
}

寻找道路

题目描述

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cctype>
#include <cstdio>
#include <vector>

typedef unsigned long long ull;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 1e6 + 5, mod = 1e9 + 7;
int n, dis[N], m;
ull dis2[N];
std::vector<int> G[2][N];
int q[N], tmp[N];
bool vis[N];

inline void add(int u, int v, int w) { G[w][u].push_back(v); }

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("path.in", "r", stdin);
  freopen("path.out", "w", stdout);
#endif
#endif

  read(n), read(m);
  for (int i = 1, u, v, w; i <= m; ++i) {
    read(u), read(v), read(w);
    add(u, v, w);
  }
  int l = 1, r = 1;
  q[1] = 1, vis[1] = true;
  while (l <= r) {
    int u = q[l++];
    for (int v : G[0][u])
      if (!vis[v]) vis[v] = true, q[++r] = v;
  }
  l = 1, r = 0;
  for (int i = 1; i <= n; ++i)
    if (vis[i]) q[++r] = i;
  while (l <= r) {
    int tot = 0;
    for (int i = l; i <= r && dis[q[i]] == dis[q[l]]; ++i) tmp[++tot] = q[i];
    l += tot;
    for (int i = 0; i < 2; ++i)
      for (int j = 1; j <= tot; ++j) {
        int u = tmp[j];
        for (int v : G[i][u])
          if (!vis[v]) {
            vis[v] = true;
            dis[v] = (((ull)dis[u] << 1) | i) % mod;
            q[++r] = v;
          }
      }
  }
  for (int i = 2; i <= n; ++i) printf("%d ", vis[i] ? dis[i] : -1);
  return 0;
}