CloudySky

纵使世界万般残酷

总有温暖值得守护

2022寒假高一有基础模拟赛

总是比别人慢很多呢。

1.20 / 模拟赛 3

集训前的最后一场模拟赛。感觉考的比较偏。

T1 [常中20180905 T1] 今天你AK了吗？

题目描述

给定数 n,kn, k ，求长度为 nn 的全排列中第 kk 小的排列。(n≤1e5,k≤min⁡(102000,n!)n \le 1e5, k \le \min(10^{2000}, n!))

思路

正解至今没人写。

如果不是 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
// Code By CloudySky
#include <bits/stdc++.h>
#define int __int128
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

int v[Maxn];
#define ls p << 1
#define rs p << 1 | 1

void add (int p, int pos, int k, int l, int r) {
  if (l == r) {
    v[p] += k; return;
  } int mid = (l + r) >> 1;
  if (pos <= mid) add (ls, pos, k, l, mid);
  else add (rs, pos, k, mid + 1, r);
  v[p] = v[ls] + v[rs];
}

int find (int p, int val, int l, int r) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (v[ls] >= val) return find (ls, val, l, mid);
  else return find (rs, val - v[ls], mid + 1, r);
}

int x[Maxn], p[Maxn];

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  int n = read (), k = read ();
  for (int i = 1; i <= n; ++i) {
    add (1, i, 1, 1, n);
  }
  x[1] = k - 1;
  for (int i = 1; i <= n; ++i) {
    if (x[i] < i) break;
    x[i + 1] += x[i] / i;
    x[i] %= i;
  }
  for (int i = n; i >= 1; --i) {
    p[i] = find (1, x[i] + 1, 1, n);
    add (1, p[i], -1, 1, n);
  }
  for (int i = n; i >= 1; --i)
    print (p[i], ' ');
  return 0;
}

T2 [常中20180903 T2] 小奇的数列

题目描述

给定一个长度为 nn 的序列，并进行 mm 次询问。每次给定 33 个数 l,r,Pl, r, P，求：

min⁡l≤l′≤r′≤r{∑l′≤i≤r′ai}\min_{l \le l' \le r' \le r}\{\sum_{l' \le i \le r'} a_i\}

即模意义下的区间子串和最小值。（pp 远小于 nn）

思路

有点类似诈骗题？

当区间长度 >P> P 时答案必定为 00 。 设第 ii 位前缀和为 sis_i。根据抽屉原理，当 len>Plen > P 时， ∃x,y(x,y∈(l,r],x<y),sx=sy\exist x, y(x, y \in (l, r], x < y), s_x = s_y。这也就意味着当 l′=x,r′=yl' = x, r' = y 时，∑l′≤i≤r′ai=0\sum_{l' \le i \le r'} a_i = 0。

由于 PP 的范围很小，所以复杂度得到了较大优化。

接下来只需要维护一个 setset 来存前缀和，每扫到一个数，找到 setset 中比它小的最大数和比它大的最小数和答案取 min⁡\min 然后把这个数插进去就行。如果答案已经取到 00 直接退出就好了。

代码

 
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
// Code By CloudySky
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 5e5 + 10;
using namespace std;

int a[Maxn];
set <int> s;

inline int solve (const int L, const int R, const int p) {
  int ans = 1e18;
  if (R - L >= p) return 0;
  for (int i = L; i <= R; ++i) {
    int cur = ((a[i] - a[L - 1]) % p);
    auto t = s.upper_bound (cur);
    ans = min (ans, cur - *(--t));
    s.insert (cur);
  }
  return ans;
}

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  int n = read (), m = read ();
  for (int i = 1; i <= n; ++i)
    a[i] = a[i - 1] + read ();
  for (int i = 1; i <= m; ++i) {
    int L = read (), R = read (), p = read ();
    s.clear (); s.insert (0);
    print (solve (L, R, p));
  }
  return 0;
}

T3 [常中20180903 T4] 寻路

题目描述

给定一个 nn 个点的数，支持删除两个点的子树，动态求直径。

思路

线段树维护欧拉序。

对于每次询问，把除了那两颗子树的信息合并到一起即可。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 3e5 + 10, inf = 0x3f3f3f3f;
using namespace std;

struct edge {int v, nxt;} e[Maxn << 1];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}; hd[u] = cnt;}

int in[Maxn], out[Maxn], id[Maxn], o[Maxn], tot;

void dfs(int x, int f) {
  if (x != 1) o[in[x] = ++tot] = 1;
  id[x] = ++tot;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y != f) dfs(y, x);
  }
  if (x != 1) o[out[x] = ++tot] = -1;
}

int flag;

struct Stree {
  int l1, r1, l2, r2, d, a, b;
  #define l1(x) St[x].l1
  #define r1(x) St[x].r1
  #define l2(x) St[x].l2
  #define r2(x) St[x].r2
  #define d(x) St[x].d
  #define a(x) St[x].a
  #define b(x) St[x].b
} St[Maxn << 2], T;

#define ls p << 1
#define rs p << 1 | 1

void init(int p, int l) {
  d(p) = a(p) = b(p) = 0;
  l1(p) = r1(p) = l2(p) = r2(p) = -inf;
  if (o[l] == 1) b(p) = 1;
  else if (o[l] == -1) a(p) = 1;
  else l1(p) = r1(p) = l2(p) = r2(p) = 0;
}

Stree merge(Stree x, Stree y) {
  Stree res;
  res.a = max(x.a, x.a + y.a - x.b);
  res.b = max(y.b, y.b + x.b - y.a);
  res.l1 = max(x.l1, max(x.a - x.b + y.l1, x.a + x.b + y.l2));
  res.r1 = max(y.r1, max(y.b - y.a + x.r1, y.b + y.a + x.r2));
  res.l2 = max(x.l2, y.l2 + x.b - x.a);
  res.r2 = max(y.r2, x.r2 + y.a - y.b);
  res.d = max(max(x.d, y.d), max(x.r1 + y.l2, x.r2 + y.l1));
  return res;
}

void build(int p, int l, int r) {
  if (l == r) return init(p, l);
  int mid = (l + r) >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
  St[p] = merge(St[ls], St[rs]);
}

void ask(int p, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    if (!flag) T = St[p], flag = 1;
    else T = merge(T, St[p]);
    return;
  }
  int mid = (l + r) >> 1;
  ask(ls, l, mid, ql, qr), ask(rs, mid + 1, r, ql, qr);
}

int Ask(int x, int y) {
  if (x == 1) return 0; flag = 0;
  ask(1, 1, tot, 1, in[x] - 1);
  if (id[y] >= in[x] && id[y] <= out[x]) ask(1, 1, tot, out[x] + 1, tot);
  else ask(1, 1, tot, out[x] + 1, in[y] -1), ask(1, 1, tot, out[y] + 1, tot);
  return T.d;
}

signed main() {
  openfile();
  int n = read(), m = read();
  for (int i = 1, u, v; i < n; ++i)
    u = read(), v = read(), add(u, v), add(v, u);
  dfs(1, 0), build(1, 1, tot);
  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read();
    if (in[u] > in[v]) swap(u, v);
    print(Ask(u, v));
  }
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

1.27 / 模拟赛 4

T1 「APIO2015」巴邻旁之桥

题目描述

共有 mm 个点对 xi,yix_i, y_i，设立两个特殊点 a,ba, b，使得 ∑i=1mmin⁡(dxi,a+dyi,a,dxi,b,dyi,b)+1\sum_{i = 1}^m \min(d_{x_i, a} + d_{y_i, a}, d_{x_i, b}, d_{y_i, b}) + 1 最小。其中 dx,yd_{x, y} 表示 x,yx, y 的权值之差。

思路

可以先考虑只选一个特殊点的情况，首先可以发现，这 mm 个点对并没有两两之间的特殊关系，所以可以拆成 2m2m 个点。问题就变成了

min⁡a{∑i=12mdxi,a}\min_a\{\sum_{i = 1}^{2m} d_{x_i, a}\}

仔细看一下这个式子，不就是货舱选址（蓝书经典问题）吗？直接一个中位数搞定。

那么，如果要选两点呢？
注意这个时候就要考虑点对了，不能让 xi,yix_i, y_i 选了不同的关键点。直接把决策权交到左侧点上就行了。首先可以想到的是，选择这两个特殊点的点一定分别在序列的两边。也就是说不存在某个点对选了右特殊点而它右边某个点对选了左特殊点。 不懂的话稍微画一画图就懂了。

然后就可以考虑将点对按照 ll 排序后，分别求出 [1,1],[1,2],⋯ ,[1,n][1, 1], [1, 2], \cdots, [1, n] 和 [n,n],[n−1,n],⋯ ,[1,n][n, n], [n - 1, n], \cdots, [1, n] 的中位数。然后枚举断点合并答案即可。

动态中位数可以用对顶堆或主席树来求。

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

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
inline int read_c() {
  char c = getchar();
  while (c<'A'||c>'B')c=getchar();
  if (c>='A'&&c<='B')return c;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

struct node {
  int l, r;
  bool operator < (const node y) const {
    return l + r < y.l + y.r;
  }
} a[Maxn];
int tot, suml, sumr, ansl[Maxn], ansr[Maxn];

priority_queue <int> q1;
priority_queue <int, vector <int>, greater <int> > q2;

void init () {
  suml = sumr = 0;
  while (!q1.empty ()) q1.pop ();
  while (!q2.empty ()) q2.pop ();
}

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  int k = read (), n = read (), ans = 0;
  for (int i = 1; i <= n; ++i) {
    char c1, c2; int l, r;
    c1 = read_c (), l = read (), c2 = read_c (), r = read ();
    if (l > r) swap (l, r);
    if (c1 == c2) ans += r - l;
    else
      ans ++, a[++tot] = (node) {l, r};
  }
  sort (a + 1, a + tot + 1);
  init ();
  for (int i = 1; i <= tot; ++i) {
    suml += a[i].l + a[i].r, q1.push (a[i].l), q1.push (a[i].r);
    suml -= q1.top (), sumr += q1.top (), q2.push (q1.top ()), q1.pop ();
    if (q1.top () > q2.top ()) {
      int x = q1.top (), y = q2.top ();
      suml = suml - x + y, sumr = sumr + x - y;
      q1.pop (), q2.pop (), q1.push (y), q2.push (x);
    }
    ansl[i] = sumr - suml;
  }
  if (k == 1) {print (ansl[tot] + ans); return 0;}
  init ();
  for (int i = tot; i >= 1; --i) {
    suml += a[i].l + a[i].r, q1.push (a[i].l), q1.push (a[i].r);
    suml -= q1.top (), sumr += q1.top (), q2.push (q1.top ()), q1.pop ();
    if (q1.top () > q2.top ()) {
      int x = q1.top (), y = q2.top ();
      suml = suml - x + y, sumr = sumr + x - y;
      q1.pop (), q2.pop (), q1.push (y), q2.push (x);
    }
    ansr[i] = sumr - suml;
  }
  int sum = 1e18;
  for (int i = 0; i <= tot; ++i) sum = min (sum, ansl[i] + ansr[i + 1]);
  print (ans + sum);
  return 0;
}

T2 「NOI2011」阿狸的打字机

题目描述

给定一坨字符串，多组询问 xx 在 yy 中出现的次数。

思路

由于要进行多串匹配，所以考虑先建出来 ACAC 自动机。但 ACAC 自动机并不是真正目的，我们要的是 failfail 树。

考虑每到一个点就对 failfail 树子树打上标记。然后对于每个询问，只需要求按照 trietrie 树路径走到 yy，xx 的 failfail 子树权值和。可以用树状数组来统计。

然后你发现这么着复杂度不对。。

离线一下就好啦。回溯时依次再把标记删除就行。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

int ac[Maxn][26], tot, fail[Maxn], fa[Maxn], id[Maxn], cnt;
vector <int> val[Maxn];

void insert (char* s) {
  int n = strlen (s), p = 0;
  while (s[n - 1] != 'P') n--;
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'B')
      p = fa[p];
    else if (s[i] == 'P')
      val[p].push_back (++cnt), id[cnt] = p;
    else {
      if (!ac[p][s[i] - 'a']) 
        ac[p][s[i] - 'a'] = ++tot, 
        fa[tot] = p;
      p = ac[p][s[i] - 'a'];
    }
  }
}

queue <int> q;
vector <int> g[Maxn];

void build () {
  for (int i = 0; i < 26; ++i)
    if (ac[0][i]) q.push (ac[0][i]);
  while (!q.empty ()) {
    int p = q.front (); q.pop ();
    g[fail[p]].push_back (p);
    for (int i = 0; i < 26; ++i) {
      int np = ac[fail[p]][i];
      if (ac[p][i])
        fail[ac[p][i]] = np,
        q.push (ac[p][i]);
      else ac[p][i] = np;
    }
  }
}

int v[Maxn];
void add (int x, int k) {
  for (; x <= tot; x += (x & -x))
    v[x] += k;
}

int ask (int x, int ans = 0) {
  for (; x; x -= (x & -x))
    ans += v[x];
  return ans;
}

int dfn[Maxn], siz[Maxn], tim;

void dfs (int x) {
  dfn[x] = ++tim, siz[x] = 1;
  for (int y : g[x]) 
    dfs(y), siz[x] += siz[y];
}


int trie[Maxn][26], ans[Maxn];
struct node { int x, id; };
vector <node> query[Maxn];

void solve (int x) {
  add (dfn[x], 1);
  for (int i : val[x])
    for (node k : query[i]) {
      int y = id[k.x];
      ans[k.id] = ask (dfn[y] + siz[y] - 1) - ask (dfn[y] - 1);
    }
  for (int i = 0; i < 26; ++i)
    if (trie[x][i]) solve (trie[x][i]);
  add (dfn[x], -1);
}

char s[Maxn];

signed main() {
// #ifndef ONLINE_JUDGE
//   freopen("in.in", "r", stdin);
//   freopen("out.out", "w", stdout);
// #endif
  scanf ("%s", s);
  insert (s);
  memcpy (trie, ac, sizeof (ac));
  build ();
  int m = read ();
  for (int i = 1; i <= m; ++i) {
    int x = read (), y = read ();
    query[y].push_back ((node) {x, i});
  }
  ++tot;
  dfs (0), solve (0);
  for (int i = 1; i <= m; ++i)
      print (ans[i]);
  return 0;
}

T3 「CEOI2011」Traffic

题意描述不清差评！

题目描述

一个矩形区间内有 nn 个点用 mm 条边相连。有一些为单向，也有一些为双向。

求对于每个最左侧的点，能到达多少最右侧的点。

"保证边在交点以外的任何地方不相交。"这句话的实际含义是 每个左侧点所能到达的右侧点是一个区间\large \text{每个左侧点所能到达的右侧点是一个区间}。

思路

考虑统计连通性先进行一波 tarjantarjan 。不过不必对每个点进行。只对左侧点进行即可。

枚举每个被访问过的右侧点，将它的贡献统计到所在的连通块顶上。

然后对缩完点的图跑一边 DAGDAG 上 DPDP 统计出每个点所能到的上界和下届就完事了。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 1e6 + 10;
using namespace std;

struct node {
  int x, y, id;
  bool operator < (const node b) const {return y > b.y;}
} p[Maxn];

struct edge {int v, nxt;} e[Maxn << 1];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}, hd[u] = cnt;}
vector <int> g[Maxn];

int dfn[Maxn], low[Maxn], tim, col[Maxn], vis[Maxn];
int stc[Maxn], top;

int A, B;
vector <node> a, b;

void dfs(int x) {
  dfn[x] = low[x] = ++tim;
  stc[++top] = x, vis[x] = 1;
  if (p[x].x == A) b.push_back(p[x]);
  for (int y : g[x]) {
    if (!dfn[y]) dfs(y), 
      low[x] = min(low[x], low[y]);
    else if (vis[y]) 
      low[x] = min(low[x], dfn[y]);
  }
  if (dfn[x] == low[x]) {
    int y;
    while ((y = stc[top--]) != 0) {
      vis[y] = 0, col[y] = x;
      if (y == x) break;
    }
  }
}

int mx[Maxn], mn[Maxn];

void dfs2(int x) {
  if (vis[x]) return;
  vis[x] = 1;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v; dfs2(y);
    mx[x] = max(mx[x], mx[y]), mn[x] = min(mn[x], mn[y]);
  }
}

signed main() {
  openfile();
  int n = read(), m = read(); A = read(), B = read();
  for (int i = 1; i <= n; ++i) p[i] = {read(), read(), i};
  for (int i = 1; i <= n; ++i) if (p[i].x == 0) a.push_back(p[i]);
  for (int i = 1, u, v, t; i <= m; ++i) {
    u = read(), v = read(), t = read();
    g[u].push_back(v); if (t == 2) g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i)
    if (!p[i].x) if (!dfn[i]) dfs(i);
  for (int u = 1; u <= n; ++u)
    for (int v : g[u]) if (col[u] != col[v]) add(col[u], col[v]);
  sort(a.begin(), a.end()), sort(b.begin(), b.end());
  memset(mn, 0x3f, sizeof(mn));
  for (auto x : b) {
    int _col = col[x.id], 
      pos = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
    mx[_col] = max(mx[_col], pos), mn[_col] = min(mn[_col], pos);
  }
  memset(vis, 0, sizeof(vis));
  for (auto u : a) 
    dfs2(col[u.id]), 
    print(max(0, mx[col[u.id]] - mn[col[u.id]] + 1));
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

2.8 模拟赛 / 5

T1 【常中20180817T2】基本定律

在线表演 O(n)O(\sqrt n) 过 1e181e18。

题目描述

给定 a,b,ca, b, c，判断 ab\frac{a}{b} 在 cc 进制下能否被整除。

思路

一开始看到题不知所措，想了半天甚至还用了进制转换器。。

后来去了趟厕所就突然想到类比 1010 进制下 22 和 55 能被整除。那么是不是只要 a,ba, b 约分之后 bb 不含有 cc 的质因数以外的质因数就能被整除，结果还真就对了。

然后我就交了发分解质因数上去。。

好吧考后正解：其实你只需要把 cc 乘个巨大次方然后判断能不能整除 bb 就行了。

或者你可以反复 b=b/gcd(b,c)b = b / gcd(b, c) 直到 gcd(b,c)=1gcd(b, c) = 1 (NONO) 或者 b=1b = 1 (YESYES)。然后根据小学奥数知识每次令 c=gcd(b,c)c = gcd(b, c) 并不会影响正确性，还能跑的飞快。真就基本定律呗。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

int gcd (int a, int b) { return !b ? a : gcd (b, a % b); }
vector <int> g;

void calc (int x) {
  g.clear ();
  for (int i = 2; i * i <= x; ++i) {
    if (x % i ==0) {
      g.push_back (i);
      while (x % i == 0) x /= i;
    }
  } if (x > 1) g.push_back (x);
}

void work () {
  int a = read (), b = read (), c = read ();
  if (!a) { printf ("YES\n"); return; }
  int d = gcd (a, b); a /= d, b /= d;
  while (b != 1) {
    int d = gcd (b, c);
    if (d == 1) { printf ("NO\n"); return;}
    b /= d, c = d;
  }
  printf ("YES\n"); return;
}

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  signed t = read ();
  while (t--) work ();
  return 0;
}

T2 [常中20181205 T3]-Travel

题目描述

给定一个长度为 nn 的序列 xix_i 保证 ∀i<j,xi<xj\forall i < j, x_i < x_j ，起始位置 ss，和需要向左跳的次数 LL。你需要正好跳 n−1n - 1 次，不重不漏地经过序列上的每个点。从 ii 到 jj 的贡献为 ∣xi−xj∣|x_i - x_j| 。

思路

首先对于 L<sL < s 的情况下，我认为有两种最优方案。

  1. 向左单格跳 L−1L - 1 次，最后一跳跳到最左边，然后向右经过没访问过的点。
  2. 先跳到最右边，然后向左跳 L−1L - 1 次，最后一跳跳到最左边，然后向右。

然而事实证明只有 11 是优的，没有 22 什么事（又或者被接下来的操作包含了）。大概算对了一半就怪了，码量还不够总量 15\frac{1}{5} 。

偶对了，还有一种特殊情况，当 L=n−2L = n - 2 时解法唯一。

剩下的就是 s≤L<n−2s \le L < n - 2 的情况了，首先你需要往左跳 s−1s - 1 次。来防止一会还需要跳回来造成巨大覆盖。由于区间太短，需要向左跳的次数太多，你需要在某些线段上转圈来防止多遍历那些贡献大的线段。

但是你发现 [t,n][t, n] 的线段是不能转圈的。因为向左走的次数和向右走的次数是相同的，转圈无意义。

然后就得枚举 TT，动态维护答案最小值。

最后构造时要注意如果你连续选了 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
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e6 + 10;
using namespace std;

int a[Maxn], n;

int solve (int s, int l, vector <int>& Ans) {
  static int rk[Maxn], tag[Maxn];
  // 特判 2，L < s 直接贪心即可
  if (l < s) {
    for (int i = s - 1; i > s - l; --i)
      Ans.push_back (i);
    for (int i = 1; i <= s - l; ++i)
      Ans.push_back (i);
    for (int i = s + 1; i <= n; ++i)
      Ans.push_back (i);
    return a[s] - a[1] + a[n] - a[1];
  }
  // 特判 3，L == n - 2 解法唯一，直接反回
  if (l == n - 2) {
    for (int i = s - 1; i >= 1; --i)
      Ans.push_back (i);
    for (int i = n; i > s; --i)
      Ans.push_back (i);
    return 2 * (a[n] - a[1]) - (a[s + 1] - a[s]);
  }
  // 开始主要部分
  l -= s - 1;  // s 左边全向左走，剩下的 l 在 s 右边完成
  static vector <pair <int,int > > pos;  // 用来记录备选需要重复走的线段
  pos.clear (), pos.push_back ({0, 0});
  for (int i = s + 2; i < n; ++i)
    pos.push_back ({a[i] - a[i - 1], i});
  sort (pos.begin () + 1, pos.end ());
  for (unsigned i = 1; i < pos.size (); ++i)
    rk[pos[i].second] = i;
  int mn = 0, sum = 0;  // mn 记录最小的总额外长度，sum 记录绕圈总长度
  for (int i = 1; i <= l; ++i)
    sum += pos[i].first;
  mn = 2 * sum;
  int t = n, j = l;  // t 为最终的结束位置，j 为最后一个令答案改变的线段排名
  for (int i = n - 1, p = l; i >= n - l; --i) {
    if (rk[i] <= p) sum -= pos[rk[i]].first;
    else sum -= pos[p--].first;
    while (p && pos[p].second >= i) p--;
    if (sum * 2 + a[n] - a[i] < mn)
      mn = sum * 2 + a[n] - a[i], t = i, j = p;
  }
  // 开始构造方案
  memset (tag, 0, sizeof (tag));
  for (int i = s - 1; i >= 1; --i)
    Ans.push_back (i);
  for (int i = s + 2; i < t; ++i)
    if (rk[i] <= j) tag[i] = 1;
  for (int i = s + 1; i < t; ++i) {
    if (!tag[i + 1]) Ans.push_back (i);
    else {
      int k = i + 1;
      while (tag[k]) ++k;
      for (int j = k - 1; j >= i; --j)
        Ans.push_back (j);
      i = k - 1;
    }
  }
  for (int i = n; i >= t; --i)
    Ans.push_back (i);
  return a[s] - a[1] + a[n] - a[1] + mn;
}

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  static int t[Maxn];
  static vector <int> Ans1, Ans2;
  n = read ();
  int l = read (), s = read ();
  for (int i = 1; i <= n; ++i)
    a[i] = read (), t[i] = a[i];
  // 特判 1，L 范围不合法，无解
  if (l == 0 && s != 1) { print (-1); return 0;}
  if (l == n - 1 && s != n) {print (-1); return 0;}
  // 进行对称处理
  int ans1 = solve (s, l, Ans1);
  for (int i = 1; i <= n; ++i)
    a[i] = -t[n - i + 1];
  int ans2 = solve (n - s + 1, n - l - 1, Ans2);
  // 比较两次答案并输出结果
  if (ans1 < ans2) {
    print (ans1);
    for (int i : Ans1) print (i, ' ');
  }
  else {
    print (ans2);
    for (int i : Ans2) print (n - i + 1, ' ');
  }
  return 0;
}

2.10 / 模拟赛 6

T1 常中20181205T1-Simple

题目描述

对于给定正整数 n,mn,m，我们称正整数 cc 为好的，当且仅当存在非负整数 x,yx,y，使得 nx+my=cnx+my=c。 现在给出多组数据，对于每组数据，给定 n,m,qn,m,q，求 [1,q][1,q] 内有多少个正整数不是好的。

思路

考场上打了个巨大的表，横轴代表 xx 选择个数（nn），纵轴代表 yy 选择个数（mm）。然后发现只有前 gcd(x,y)gcd(x, y) 行是有用的。就直接开冲了。

然后就对了，所以到现在也不会证。打表大法好！

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
using namespace std;

int gcd (int a, int b) { return !b ? a : gcd (b, a % b); }
int lcm (int a, int b) { return a * b / gcd (a, b); }

inline int ask (int a, int b, int q) {
  if (a < b) swap (a, b);
  bool ck1 = !a || a > q, ck2 = !b || b > q;
  if (ck1 && ck2) return q;
  if (ck1) return q - q / b;
  if (ck2) return q - q / a;
  int ans = 0, up = b / gcd (a, b);
  for (int i = 0; i < up; ++i) {
    if (i * a > q) break;
    ans += (q - i * a) / b + 1;
  }
  return q - ans + 1;
}

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  int t = read ();
  while (t --) {
    int a = read (), b = read (), q = read ();
    print (ask (a, b, q));
  }
  return 0;
}

T2 常中20181205T2-Walk

题目描述

给定一个 nn 个节点的树，求长度为 ii 的路径中所有边权 gcdgcd 最大是多少。

思路

最大公约数不好像边权和那样贪心选择。于是考虑枚举 dd ，在边权为 dd 的倍数的子图上跑直径。最后跑一个后缀 max⁡\max。

输入时，按权值存边，方便后面快速建图。当然，删边时也不能暴力清空，得一个一个来。

时间复杂度调和级数 O(nlogn)O(nlogn)

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 4e5 + 10, Maxw = 1e6 + 10;
using namespace std;

vector <pair<int, int> > E[Maxw];
int stc[Maxn << 1], ans[Maxn];

inline int Max (int a, int b) { return a > b ? a : b;}

struct edge { int v, nxt; } e[Maxn << 1];
int hd[Maxn], cnt;
void add (int u, int v) {
  e[++cnt] = (edge) {v, hd[u]};
  hd[u] = cnt, stc[cnt] = u;
}

int d; bool vis[Maxn];

inline int dfs (int x, int f) {
  vis[x] = 1;
  int mx = 0, sm = 0, len;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f || vis[y]) continue;
    len =  dfs (y, x);
    if (len >= mx) sm = mx, mx = len;
    else if (len > sm) sm = len;
  }
  d = Max (d, mx + sm); return mx + 1;
}

signed main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
  int n = read (), mx = 0, u, v, w, siz;
  for (int i = 1; i < n; ++i) {
    u = read (), v = read (), w = read ();
    E[w].push_back ({u, v}), mx = Max (mx, w);
  }
  for (int w = 1; w <= mx; ++w) {
    for (int i = w; i <= mx; i += w) {
      siz = E[i].size ();
      for (int j = 0; j < siz; ++j) {
        u = E[i][j].first, v = E[i][j].second;
        add (u, v), add (v, u);
      }
    }
    for (int i = 1; i <= cnt; ++i) {
      int t = stc[i];
      if (!vis[t]) dfs (t, 0);
    }
    ans[d] = w;
    for (int i = 1; i <= cnt; ++i) {
      int t = stc[i];
      hd[t] = 0, vis[t] = 0;
    }
    d = cnt = 0;
  }
  for (int i = n; i; --i) ans[i] = Max (ans[i], ans[i + 1]);
  for (int i = 1; i <= n; ++i) print (ans[i]);
  return 0;
}

T3 树

题目描述

给定一棵 nn 个结点的有根树 TT，结点从 11 开始编号，根结点为 11 号结点，每个结点有一个正整数权值 viv_i。

设 xx 号结点的子树内（包含 xx 自身）的所有结点编号为 c1,c2,⋯ ,ckc_1,c_2,\cdots,c_k，定义 xx 的价值为：

val(x)=(vc1+d(c1,x))⊕(vc2+d(c2,x))⊕⋯⊕(vck+d(ck,x))val(x)=(v_{c_1}+d(c_1,x))⊕(v_{c_2}+d(c_2,x))⊕\cdots⊕(v_{c_k}+d(c_k,x))

其中 d(x,y)d(x,y) 表示树上 xx 号结点与 yy 号结点间唯一简单路径所包含的边数，d(x,x)=0d(x,x)=0。⊕⊕ 表示异或运算。

请你求出 ∑i=1nval(i)\sum^n_{i = 1}val(i) 的结果。

思路

看到和异或有关的长得像数据结构的题就要往 TrieTrie 上多想想，不要着急否。（虽然这个题也想不出来）

一个支持子树加 11 的 01Trie01Trie 合并。

不同的是，这个 TrieTrie 树是从低位向高位建的，并且需要维护两个额外信息。

  • val(p)val(p) TrieTrie 树当前节点子树异或和

  • vis(p)vis(p) TrieTrie 树当前节点子树大小的奇偶性。

    目的：右子树大小奇偶性决定当前位置异或和奇偶性。

这样合并起来会方便很多。异或和直接输出 val(rt)val(rt) 即可。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 6e5 + 10;
using namespace std;
 
struct edge {int v, nxt;} e[Maxn];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}, hd[u] = cnt;}

int a[Maxn], ans;

int val[Maxn * 27], vis[Maxn * 27], trie[Maxn * 27][2], tot;
int rt[Maxn];

#define ls(x) trie[x][0]
#define rs(x) trie[x][1]

void pushup(int p) {
  vis[p] = val[p] = 0;
  if (ls(p)) vis[p] ^= vis[ls(p)], val[p] ^= (val[ls(p)] << 1);
  if (rs(p)) vis[p] ^= vis[rs(p)], val[p] ^= (val[rs(p)] << 1 | vis[rs(p)]);
}

void insert(int& p, int val, int dep) {
  if (!p) p = ++tot;
  if (dep > 20) return vis[p] ^= 1, void();
  insert(trie[p][val & 1], val >> 1, dep + 1);
  pushup(p);
}

void add(int p) {swap(ls(p), rs(p)); if (ls(p)) add(ls(p)); pushup(p);}

int merge(int x, int y) {
  if (!x || !y) return x | y;
  val[x] ^= val[y], vis[x] ^= vis[y];
  ls(x) = merge(ls(x), ls(y));
  rs(x) = merge(rs(x), rs(y));
  return x;
}

void dfs(int x) {
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v; dfs(y); 
    rt[x] = merge(rt[x], rt[y]);
  } 
  add(rt[x]), insert(rt[x], a[x], 0); 
  ans += 1ll * val[rt[x]];
}

signed main() {
  // openfile();
  int n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 2, f; i <= n; ++i) f = read(), add(f, i);
  dfs(1);
  print(ans);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

2.12 / 模拟赛 7

T1 【常中20180915T1】牧场

题目描述 / 思路

没啥可说的，裸的扫描线周长。并且不用离散化。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 4e5 + 10;
using namespace std;

struct Stree {
  int l, r, val, len;
  #define l(x) St[x].l
  #define r(x) St[x].r
  #define v(x) St[x].val
  #define ln(x) St[x].len
} St[Maxn << 2];

#define ls p << 1
#define rs p << 1 | 1

void build(int p, int l, int r) {
  l(p) = l, r(p) = r, v(p) = ln(p) = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
}

void pushup(int p) {
  if (v(p)) ln(p) = r(p) - l(p) + 1; 
  else ln(p) = ln(ls) + ln(rs);
}

void add(int p, int l, int r, int k) {
  if (l(p) >= l && r(p) <= r) return v(p) += k, pushup(p);
  int mid = (l(p) + r(p)) >> 1;
  if (l <= mid) add(ls, l, r, k);
  if (r > mid ) add(rs, l, r, k);
  pushup(p);
}

struct line {
  int pos, l, r, v;
  bool operator < (const line y) const {
    return pos == y.pos ? v > y.v : pos < y.pos;
  }
} q[Maxn];

int Abs(int x) {return x > 0 ? x : -x;}

long long solve(int cnt, long long ans = 0) {
  sort(q + 1, q + cnt + 1);
  build(1, -100000, 100000);
  for (int i = 1, lst; i <= cnt; ++i) {
    lst = ln(1);
    add(1, q[i].l, q[i].r, q[i].v);
    ans += 1ll * Abs(ln(1) - lst);
  }
  return ans;
}

struct sqr {int l, dn, r, up;} a[Maxn];

signed main() {
  openfile();
  int n = read(), cnt = 0; long long ans = 0;
  for (int i = 1; i <= n; ++i)
    a[i] = {read(), read(), read(), read()};
  for (int i = 1; i <= n; ++i)
    q[++cnt] = {a[i].l, a[i].dn, a[i].up - 1, 1},
    q[++cnt] = {a[i].r, a[i].dn, a[i].up - 1, -1};
  ans = solve(cnt);
  cnt = 0;
  for (int i = 1; i <= n; ++i)
    q[++cnt] = {a[i].dn, a[i].l, a[i].r - 1, 1},
    q[++cnt] = {a[i].up, a[i].l, a[i].r - 1, -1};
  print(ans + solve(cnt));
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

【常中20180921】C

题目描述

给定一个正整数 nn，求 [1,n][1, n] 中 (a,b)(a, b) 满足 gcd(a,b)=a xor bgcd(a, b) = a\ xor\ b 。

思路

结论题

由于 gcd(a,b)=gcd(b,a−b)gcd(a, b) = gcd(b, a - b) 所以 gcd(a,b)≤a−bgcd(a, b) \le a - b，由于 a xor ba\ xor\ b 代表按位大减小，所以 a xor b≥a−ba\ xor\ b \ge a - b。因此可以枚举 gcdgcd 然后枚举 a−ba - b。

时间复杂度，调和级数 O(nlogn)O(nlogn)

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
// const int Maxn = 1e5 + 10;
using namespace std;

signed main() {
  openfile();
  int n = read(), ans = 0;
  for (int i = 2; i <= n; i += 2) {
    for (int j = 1; (i + 1) * j <= n; ++j)
      if (j == (((i + 1) * j) ^ (i * j))) ++ans;
  }
  print(ans);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T3 【常中20180812T2】track

题目描述

给定一个数 nn 和一段由 U 和 D 构成的字符串 ss。

请你求出长度为 nn 的包含 ss 的 U D 串的个数满足且任意前缀中 U 的个数不小于 D 且最终 U 和 D 的个数相等。

思路

KMP DP 好题。

正难则反，既然直接求包含不好求，那就求不包含，然后容斥。

首先对 ss 跑 KMPKMP 。

设 gi,jg_{i, j} 表示不考虑包不包含，已填长度为 ii 当前 U−DU - D 为 jj 的方案数。转移很好考虑。

gi,j=gi−1,j−1+gi−1,j+1.g_{i, j} = g_{i - 1, j - 1} + g_{i - 1, j + 1}.

然后设 fi,j,kf_{i, j, k} 表示已填 ii 位，当前差值为 jj，已经匹配到 ss 的第 kk 为的方案数。这个东西填表不好整，改成刷表。

fi+1,j+1,nxt(k,U)+=fi,j,k(下一位填 U)fi+1,j−1,nxt(k,D)+=fi,j,k(下一位填 D)f_{i + 1, j + 1, nxt(k, U)} += f_{i, j, k} (\text{下一位填 U}) \\ f_{i + 1, j - 1, nxt(k, D)} += f_{i, j, k} (\text{下一位填 D})

其中 nxt(k,U)nxt(k, U) 表示当前匹配到 ss 的 kk 位，下一位填 UU 会匹配到第几位。

说句闲话：膜拜 zzfzzf DP 之神，吊打 stdstd！

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 210, P = 1e9 + 7;
using namespace std;

int g[Maxn][Maxn], f[Maxn][Maxn][Maxn];

char s[Maxn];
int nxt[Maxn];
int kmp(int k, char c) {
  while (k && s[k + 1] != c) k = nxt[k];
  if (s[k + 1] == c) ++k; return k;
}

signed main() {
  openfile();
  int n = read(), m, ans = 0;
  g[0][0] = f[0][0][0] = 1;
  scanf("%s", s + 1), m = strlen(s + 1); 
  for (int i = 2, j = 0; i <= m; ++i) {
    while (j && s[i] != s[j + 1]) j = nxt[j];
    if (s[i] == s[j + 1]) ++j;
    nxt[i] = j;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= i; ++j)
      (g[i][j] += g[i - 1][j - 1] + g[i - 1][j + 1]) %= P;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      for (int k = 0; k < m; ++k) {
        (f[i + 1][j + 1][kmp(k, 'U')] += f[i][j][k]) %= P;
        (f[i + 1][j - 1][kmp(k, 'D')] += f[i][j][k]) %= P;
      }
    }
  }
  for (int k = 0; k < m; ++k) (ans += f[n][0][k]) %= P;
  print(((g[n][0] - ans) % P + P) % P);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

2.15 / 模拟赛 8

T1 「JOISC 2016 Day 2」女装大佬

题目描述

我无能为力

思路

大概算是一道结论题？

考虑后缀和。（这是我考场上想到的离正解最近的思路，后面就偏了。）

对于每个串，设男选手值为 11，女选手为 −1-1。去考虑后缀和。设它后面的串的总后缀和为 Δ\Delta，当前串最终后缀和为 pip_i，最大后缀和为 mximx_i，出现次数为 tit_i。答案即为：

ans=max⁡{Δ+(ti−1)×max⁡(0,pi)+mxi}ans = \max\{\Delta + (t_i - 1) \times \max(0, p_i) + mx_i\}

表示之前的串以及当前串后面的 ti−1t_i - 1 次遗留下来的，以及第 11 次的最大值，尽量去补，补不了的贡献到答案里。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline int print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s); return 0;
}
}  // namespace IO
using namespace IO;
const int Maxn = 2e5 + 10;
using namespace std;

int p[Maxn], mx[Maxn], t[Maxn];
char s[Maxn];

signed main() {
  int n = read(), m = read(), tot = 0, ans = 1, delta = 0;
  for (int i = 1, ni; i <= m; ++i) {
    scanf("%s", s + 1);
    t[i] = read(), ni = strlen(s + 1);
    for (int j = ni; j; --j) {
      p[i] += (s[j] == 'M' ? 1 : -1);
      mx[i] = max(mx[i], p[i]);
    }
    tot += p[i] * t[i];
  }
  if (tot > 0)
    return print(-1);
  for (int i = m; i; --i) {
    ans = max(ans, delta + (t[i] - 1) * max(0ll, p[i]) + mx[i]);
    delta += p[i] * t[i];
  }
  return print(ans - 1);
}

T2 【常中20180812T3】test

题目描述

给定一个树，支持单点修改权值，求链上权值和，换根，求子树和。

思路

打个广告：CF916E Jamie and Tree 如果你觉着 T2 简单，那么你可以做这道题；如果你觉着 T2 难，你也可以做这道题。

首先发现前两个操作和根是啥没啥关系。正常树剖就行。考虑子树和与当前根的关系发现只有 33 种情况：

  1. 当前点 xx 为 rtrt，直接返回全局权值和。
  2. 当前点 xx 不在 rtrt 到原根的路径上，答案为静态子树和，无影响。
  3. 当前点 xx 在 rtrt 到原根的路径上，答案为 全局权值和 - rtrt 所在子树和。

判断 rtrt 是不是在 xx 子树内可以用 lca(x,rt)=xlca(x, rt) = x。

rtrt 所在子树可以在跳 lcalca 时顺便统计上 rt = fa[z = top[rt]] 。最后判断 fa[z] == x ? z : son[x]。显然是正确的。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

int a[Maxn], d[Maxn];

struct Stree {
  int l, r, sum;
  #define l(x) St[x].l
  #define r(x) St[x].r
  #define v(x) St[x].sum
} St[Maxn << 2];

#define ls p << 1
#define rs p << 1 | 1

void build(int p, int l, int r) {
  l(p) = l, r(p) = r, v(p) = d[l];
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
  v(p) = v(ls) + v(rs);
}

void change(int p, int v, int k) {
  if (l(p) == r(p)) {v(p) = k; return;}
  int mid = (l(p) + r(p)) >> 1;
  if (v <= mid) change(ls, v, k);
  else change(rs, v, k);
  v(p) = v(ls) + v(rs);
}

int ask(int p, int l, int r) {
  if (l(p) >= l && r(p) <= r) return v(p);
  int mid = (l(p) + r(p)) >> 1, ans = 0;
  if (l <= mid) ans += ask(ls, l, r);
  if (r > mid) ans += ask(rs, l, r);
  return ans;
}

struct edge {int v, nxt;} e[Maxn << 1];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = (edge) {v, hd[u]}; hd[u] = cnt;}

int dep[Maxn], siz[Maxn], fa[Maxn], son[Maxn];
void dfs1(int x, int f) {
  dep[x] = dep[f] + 1, fa[x] = f, siz[x] = 1;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v; if (y == f) continue;
    dfs1(y, x), siz[x] += siz[y];
    if (siz[y] > siz[son[x]]) son[x] = y;
  }
}

int top[Maxn], dfn[Maxn], tim;
void dfs2(int x, int f) {
  top[x] = f, dfn[x] = ++tim, d[tim] = a[x];
  if (son[x]) dfs2(son[x], f);
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y != son[x] && y != fa[x]) dfs2(y, y);
  }
}

int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}

int qlink(int x, int y) {
  int ans = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    ans += ask(1, dfn[top[x]], dfn[x]);
    x = fa[top[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  ans += ask(1, dfn[x], dfn[y]);
  return ans;
}

int check(int x, int y) {
  int s = x;
  while(top[x] != top[y]) s = top[x], x = fa[top[x]];
  if (fa[s] == y) return s;
  else return son[y];
}

int root = 1, n, m;
int qtree(int x) {
  if (x == root) return ask(1, 1, n);
  if (lca(x, root) != x) return ask(1, dfn[x], dfn[x] + siz[x] - 1);
  int kk = check(root, x);
  return ask(1, 1, n) - ask(1, dfn[kk], dfn[kk] + siz[kk] - 1);
}

signed main() {
  n = read(), m = read();
  for (int i = 1, u, v; i < n; ++i)
    u = read(), v = read(), add(u, v), add(v, u);
  for (int i = 1; i <= n; ++i) a[i] = read();
  dfs1(1, 0), dfs2(1, 1), build(1, 1, n);
  for (int i = 1, op, x, v, y; i <= m; ++i) {
    op = read(), x = read();
    if (op == 1) root = x;
    if (op == 2) v = read(), change(1, dfn[x], v);
    if (op == 3) print(qtree(x));
    if (op == 4) y = read(), print(qlink(x, y));
  }
  return 0;
}

T3 【20180819省队班】取数字

题目描述

给定 nn 个整数 aia_i，你需要从中选取若干个数，使得它们的和是 mm 的倍数。问有多少种方案。有多个询问，每次询问一个的 mm 对应的答案。（mm 远小于 nn）

思路

背包/组合数好题

正常的 O(nmq)O(nmq) 应该都会吧。考虑把每个数 %m\% m 的余数放进桶里。组合数预处理优化一下就能做到 O(m2q)O(m^2q)。

代码

 
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
// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 2e5 + 10, P = 1e9 + 7;
using namespace std;

int n, a[Maxn], t[110], jc[Maxn], inv[Maxn], jc_inv[Maxn];

inline int C(int n, int m) {return jc[n] * jc_inv[m] % P * jc_inv[n - m] % P;}

inline int Pow(int x, int y, int ans = 1) {
  for (; y; y >>= 1, x = x * x % P) if (y & 1) ans = ans * x % P;
  return ans;
}

int f[110][110], h[110];

int dp(int m) {
  memset(t, 0, sizeof(t));
  for (int i = 1; i <= n; ++i)
    t[((a[i] % m) + m) % m] ++;
  memset(f, 0, sizeof(f));
  f[0][0] = Pow(2, t[0]);
  for (int i = 1; i < m; ++i) {
    memset(h, 0, sizeof(h));
    for (int j = 0; j <= t[i]; ++j)
      (h[j % m] += C(t[i], j)) %= P;
    for (int j = 0; j < m; ++j) {
      for (int k = 0; k <= min(m - 1, t[i]); ++k)
        f[i][(j + i * k) % m] = (f[i][(j + i * k) % m] + f[i - 1][j] * h[k] % P) % P;
    }
  }
  return f[m - 1][0];
}

signed main() {
  n = read(); int q = read();
  for (int i = 1; i <= n; ++i)
    a[i] = read();
  jc[0] = jc[1] = 1, jc_inv[0] = jc_inv[1] = 1, inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    jc[i] = jc[i - 1] * i % P;
    inv[i] = (P - P / i) * inv[P % i] % P;
    jc_inv[i] = jc_inv[i - 1] * inv[i] % P;
  }
  for (int i = 1, sb; i <= q; ++i)
    sb = read(), print(dp(sb));
  return 0;
}

总结

大胆猜测，不要着急否定自己的想法。

gcd 一般是枚举出来的。

最后，还是老话：积累才是硬道理。

本文作者：CloudySky
写作时间： 2022-03-10
最后更新时间： 2022-03-10
遵循协议： BY-NC-SA

Top