8.02集训

Posted on Edited on In

上午

考试 # 下午

第一题

一句话题意：给出两个\(1\) \(to\) \(n\)的序列，定义\(T(a,b)\)为\(a\)与\(b\)在序列中的距离

其计算公式为：\(下标_{b所在的位置} - 下标_{a所在的位置}\)

找出两个序列中，\(max({T_1(a,b),+T_2(a,b))}\)

看一组例子：

1
2
A:3 2 1 4 5
B:2 5 1 3 4

考虑\(2\)与\(4\)这两个数字对答案的贡献，

显然：\(ans_{当前} = (下标_{4所在的A系列位置}-下标_{2所在的A序列位置}) +(下标_{4所在的B系列位置}-下标_{2所在的B序列位置})\)

合并之后得到：\(ans_{当前} = (下标_{4所在的A系列位置} + 下标_{4所在的B系列位置})-(下标_{2所在的A序列位置} + 下标_{2所在的B序列位置})\)

A序列中的\(2\)与\(4\)是递增分布的，考虑，如果B序列中出现\(4.......2\)的情况怎么办？

或者A序列中\(4.......2\)，而B序列中\(2......4\)怎么办？

也就是说B序列与A序列的“顺序不同”（需要感性理解）

这时候我们考虑把下标从右往左标上一圈，原来不是从左往右吗？现在所谓的“逆序”，我们从右往左，实现也很简单，\(n-下标_{当前}+1\)就是你逆序之后的下标

给出自己的代码（借鉴了Tethysdalao的代码）

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

inline long long read() {
   long long s = 0, f = 1; char ch;
   while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
   for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
   return s * f;
}

const int N = 1e6+66;

int n, res, ans_s_max, ans_s_min = N<<1, ans_n_max, ans_n_min = N<<1;
int a[N], b[N], f[N];

inline void shuruyijijiejueheshuchu() {
   n = read();
   for (int i = 1; i <= n; ++ i) a[i] = read();
   for (int i = 1; i <= n; ++ i) {
      b[i] = read();
      f[b[i]] = i;
   }
   for (int i = 1; i <= n; ++ i) {
      ans_s_max = max(ans_s_max, i + f[a[i]]);
      ans_s_min = min(ans_s_min, i + f[a[i]]);
      ans_n_max = max(ans_n_max, i + n-f[a[i]]+1);
      ans_n_min = min(ans_n_min, i + n-f[a[i]]+1);
      res = max(res, ans_s_max - ans_s_min);
      res = max(res, ans_n_max - ans_n_min);
   }
   cout << res;
}

inline int thestars() {
   shuruyijijiejueheshuchu();
   fclose (stdin), fclose (stdout);
   return 0;
}

int youngore = thestars();

signed main() {;}
/*
5
2 1 5 3 4
4 2 5 1 3
*/

我懒得去写具体的代码分析了，日后补吧

第二题

一句话题意：求\(\begin{aligned}\sum_{i=0}^xC_{x}^i*C_{y}^{z+i}\%998244353\end{aligned}\)

其中数据：\(T<=10000,0<=x,y,z<=1000000\)

可曾听闻范德蒙德卷积？

然后就没了

\(\begin{aligned}\sum_{i=0}^k{C_n^iC_{m}^{k-i}}=C_{n+m}^{k}\end{aligned}\)

具体详见Ame__

给出代码：

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;

const int N = 1e7+66, mod = 998244353;

inline int read() {
   int s = 0, f = 1; char ch;
   while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
   for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
   return s * f;
}

int x, y, z, t;
int js[N];

inline int ksm(int a, int b) {
   if (!b) return 1;
   if (b&1) return a*ksm(a,b-1);
   int tmp = ksm(a, b/2)%mod;
   return tmp*tmp%mod;
}
//这个快速幂我没有测
inline int C(int n, int m) {
   if (n < m) return 0;
   return js[n]*ksm(js[m]*js[n-m]%mod, mod-2)%mod;
}

inline int Lucas(int n, int m) {
   if (!m) return 1;
   return C(n%mod, m%mod)*Lucas(n/mod, m/mod)%mod;
}

inline void shuruhejiejueheshuchu() {
   t = read();
   js[0] = 1, js[1] = 1;
   for (int i = 2; i <= N; ++ i) js[i] = js[i - 1]*i%mod;
   while (t -- > 0) {
      // cin >> x >> y >> z;
      x = read(), y = read(), z = read();
      int sum =  Lucas(x+y, x+z)%mod;
      cout << sum << '\n';
   }
}

inline int thestars() {
   shuruhejiejueheshuchu();
   return 0;
}

int youngore = thestars();

signed main() {;}

这题tmd卡快读，艹，我用\(cin\)全T飞了

第三题

一句话题意：给你个序列，每次要异或一个数，还要查询一个判定器，其中\(n \leq 1e6\)

显然暴力\(n^2\)，正解是：\(01Tire\)，艹，我就是tm讲的Trie树，我自己没看出来，老往主席树什么玩意的想去了

关键是前几天学长好几道异或的题，都跟01Trie树没关系啊，我知道是01Trie树之后，当场mmp

后来gzh奆佬直言：学过01Trie树的一眼就能看出来（于是口吐不清的开始了他迷迷糊糊的讲解）

具体思路：在01Trie树上搞一搞就可以了

给出代码：

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 6e6+66;

int n, t, x, y, cnt;
int ch[N][6], tag[N];

inline void shuruyijijiejueheshuchu() {
   cin >> n >> t;
   for (int i = 1; i <= n; ++ i) {
      int now = 0;
      cin >> x;
      for (int j = 16; j >= 0; -- j) {
         if (!ch[now][x>>j&1]) ch[now][x>>j&1] = ++ cnt;
         now = ch[now][x>>j&1];
         ++ tag[now];
      }
   }
   while (t --> 0) {
      int res = 0, now = 0;
      cin >> x >> y;
      for (int j = 16; j >= 0; -- j) {
         if (y>>j&1) res += tag[ch[now][x>>j&1]];
         now = ch[now][(y>>j&1)^(x>>j&1)];
         if (!now) break;
      }
      if (now) res += tag[now];
      cout << res << '\n';
   }
}

inline int thestars() {
   shuruyijijiejueheshuchu();
   return 0;
}

int youngore = thestars();

signed main() {;}
/*
5 5
7 6 7 3 4
2 6
1 8
8 7
3 2
6 2
*/