noip模拟45

08-21-2021 约 1409 字预计阅读 3 分钟

T1打表

看似神仙，实则简单的题

答案就是所有 $|a[i] - a[ans]|$ 的和除 $2^k$

题解证明：令 $P(i)$ 表示还剩 $i$ 个二进制位没有被操作时，期望值是剩下的数与正确输出差的平均值。当 $i= 1$ 时， $P(1)$ 是正确的，因为每个CPU有50%的机会操作这一位。对于 $i>1$ ，根据 $P(i1)$ ，促打表CPU和反打表CPU一定会选择同一位，但填相反的数，因为剩下的数与正确输出差的和是一定的。因此 $P(i)$ 也是正确的，因为选择同一位相当于将剩下的数分为了两个不相交集合。

T2 蛇

它玩蛇呢？！根本无法想出如何转移

不会，咕了！

T3 购物

千万不要用一个假暴力和一个正解对拍

否则会收获大大的零蛋一个

这道题打暴力时如果把每个区间都输出出来会发现后很多重复的地方，就想怎么去掉重复的区间来优化。通过瞎想发现一个值的右边界（最大的k）为它的前缀和。因此，一大堆区间就变成了n个区间（可是还是有重复），每个区间的范围都是从 $ceil(a[i] / 2)$ （千万别忘了ceil，我就是因为拍错了就把这里删掉而爆蛋的。至于正确性，so EZ）到从第一个数到它的前缀和。

 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


#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 100010;
struct INTERV {
  long long l, r;
  friend bool operator< (INTERV a, INTERV b) {
    return (a.l != b.l) ? a.l < b.l : a.r < b.r;
  }
};
INTERV avail[maxn * 2];
int cnt;
long long a[maxn], qz[maxn];
int n;
int main() {
  int ans = 0;
  cin >> n;
  For(i, 1, n) cin >> a[i];
  sort(a + 1, a + 1 + n);
  For(i, 1, n) qz[i] = qz[i - 1] + a[i];
  For(i, 1, n) avail[++cnt] = (INTERV){ceil(a[i] / 2.0), qz[i]};
  sort(avail + 1, avail + 1 + cnt);
  long long l = max(1ll, avail[1].l), r = avail[1].r;
  For(i, 2, cnt) {
    if (avail[i].l > r) {
      ans += r - l + 1;
      l = avail[i].l, r = avail[i].r;
    }
    r = avail[i].r;
  }
  cout << ans + r - l + 1<< endl;
  return 0;
}

T4 ants

需要用到回滚莫队，知识盲区

不会，咕了！

upd: 现在（不）会了

实际上不是，用到了并查集。大致思想就是在同一个块内的就直接暴力sort出答案，不在一个块内的就是回滚莫队

P.S. 这道题和permu一样一样的

  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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 140010;

template<typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int n, m, blkLen;
int p[maxn], blk[maxn], dep[maxn];
bool vis[maxn];

struct QUERY {
  int l, r, id;
  friend bool operator< (QUERY a, QUERY b) {
    return a.r < b.r;
  }
};
struct STK {
  int id ,dep;
} stk[maxn * 2];
vector<QUERY> que[maxn];

int solveSameBlock(int l, int r) {
  if (l == r) return 1;
  int tmp[maxn] = {0};
  For(i, l, r) {
    tmp[++tmp[0]] = p[i];
  }
  sort(tmp + 1, tmp + 1 + tmp[0]);
  int nowLen = 1, maxLen = 1;
  int now = tmp[1];
  For(i, 2, tmp[0]) {
    if (tmp[i] == now + 1) {
      nowLen++;
      now = tmp[i];
    } else {
      maxLen = max(maxLen, nowLen);
      nowLen = 1;
      now = tmp[i];
    }
  }
  maxLen = max(maxLen, nowLen);
  return maxLen;
}

int top, maxx; // (dep)

class DJU {
public:
  int fa[maxn];
  void init(int n) {
    For(i, 1, n) {
      fa[i] = i;
    }
  }
  int findFa(int a) {
    return (fa[a] != a) ? fa[a] = findFa(fa[a]) : a;
  }
  void merge(int a, int b) {
    int faa = findFa(a), fab = findFa(b);
    if (faa == fab) return;
    if (dep[faa] < dep[fab]) swap(faa, fab);
    maxx = max(maxx, dep[faa] + dep[fab]);
    fa[fab] = faa;
    stk[++top] = (STK){faa, dep[faa]};
    stk[++top] = (STK){fab, dep[fab]};
    dep[faa] += dep[fab];
  }
} dj;

void mge(int a) {
  vis[a] = 1;
  if (vis[a - 1]) dj.merge(a - 1, a);
  if (vis[a + 1]) dj.merge(a, a + 1);
}


int ans[maxn];

void solveDiffBlock(int now, vector<QUERY> &v) {
  maxx = 1, top = 0;
  int pos = min(maxn, now * blkLen) + 1;
  int lstPos, lstMaxx, l = pos, r = pos - 1;
  For(i, 0, n) {
    dj.fa[i] = i;
    dep[i] = 1;
    vis[i] = 0;
  }
  for (auto i : v) {
    while (r < i.r) mge(p[++r]);
    lstMaxx = maxx;
    lstPos = top;
    while (l > i.l) mge(p[--l]);
    ans[i.id] = maxx;
    maxx = lstMaxx;
    while (top > lstPos) {
      dj.fa[stk[top].id] = stk[top].id;
      dep[stk[top].id] = stk[top].dep;
      top--;
    }
    while (l < pos) vis[p[l++]] = 0;
  }
}

int main() {
  n = read<int>();
  m = read<int>();
  dj.init(n);
  blkLen = n / sqrt(m);
  For(i, 1, n) {
    p[i] = read<int>();
    blk[i] = (i - 1) / blkLen + 1;
  }
  For(i, 1, m) {
    int l, r;
    l = read<int>();
    r = read<int>();
    if (blk[l] == blk[r]) {
      ans[i] = solveSameBlock(l, r);
    } else {
      que[blk[l]].push_back((QUERY){l, r, i});
    }
  }
  For(i, 1, blk[n]) {
    sort(que[i].begin(), que[i].end());
    solveDiffBlock(i, que[i]);
  }
  For(i, 1, m) {
    cout << ans[i] << endl;
  }
  return 0;
}

目录

noip模拟45

T1打表

T2 蛇

T3 购物

T4 ants