2017_CCPC_HARBIN
新博客的第一篇文章，打算吸取一下之前CSDN写完博客找不到题的教训：对于套题的补题应该设置一些比较明显的目录以待今后查阅，每个题目的题目以及知识点都予以简单的描述。
这好像是一场比较难(但是队友很顶)的训练赛，然而我又一次死在了计算几何上，并且成为爆交狂魔…qaq
不过总而言之打套题还是感觉不仅对于算法力还是对于码力都有很大的提升，自此我找到了真正的快乐 /xyx
A 回文串 & 线段树
场上队友过了这道题(orz)，赛后自己补一下
研读题目规定的回文串的具体形式，发现这是两个回文串的嵌套，因而题目便转化为了找有序对(i, j)满足
-
$i <j$
-
$i + r[i] >= j$
-
$j - r[j] <= i$
其中$r[i]$是以i为中心的回文串的半径；$r$数组可以用Manacher算法$O(n)$的处理出来，接下来就是统计互相覆盖的点对。
想了很久并没有想到好办法…学习了一番线段树的解法..
我们先预处理出数组vec[i]表示以i为起点的回文串的中心位置，然后顺序遍历字符串，每次将数组vec[i]的中心位置加入线段树，接着查询[i + 1, i + r[i]点的个数。因为查询的是[i + 1, i + r[i]]，所以可以保证上述三个条件中的12条件；另一方面，因为该中心点已经出现在线段树中了，所以其起点的位置一定小于等于当前位置i，这也就保证条件3的成立。综上所述就可以$O(nlogn)$扫一遍得到所有的结果。
1const int maxn = 5e5 + 10;
2
3/*
4 Manacher算法
5 读入一个字符串temp及其长度n;
6 该算法构造出s并赋予截断标志, 自动初始化、获得数组p[i];
7 对于某个位置i∈[0, 2 * n], 以i为中心的回文串的参数如下:
8 int start = (i / 2) - (p[i] / 2) + (i & 1); //回文串在原串中的起点
9 int d = p[i] - 1; //回文串在原串中的总长度
10 int middle = (i - 1) / 2; //回文串在原串的中点
11 */
12int n;
13char temp[maxn], s[maxn << 1];
14int p[maxn << 1];
15void manacher(){
16 for(int i = 0; i < n; i++){
17 s[i << 1] = '#'; s[i << 1 | 1] = temp[i];
18 }
19 s[n << 1] = '#'; s[n << 1 | 1] = 0;
20
21 int id = 0, right = 0;
22 for(int i = 0; i <= n << 1; i++) p[i] = 1;
23 for(int i = 1; i <= n << 1; i++){
24 if(i <= right) p[i] = min(right - i + 1, p[2 * id - i]);
25 while(i + p[i] <= 2 * n && i - p[i] >= 0 && s[i + p[i]] == s[i - p[i]])
26 p[i]++;
27 if(right < i + p[i] - 1){
28 id = i; right = i + p[i] - 1;
29 }
30 }
31}
32
33#define ls (p << 1)
34#define rs ((p << 1) | 1)
35#define mid ((l + r) >> 1)
36
37vector<int> vec[maxn];
38
39ll st[maxn << 2], tag[maxn << 2];
40//区间查询，单点置值。
41inline void up(int p){st[p] = st[ls] + st[rs];}
42void update(int p, int l, int r, int k){
43 if(l == r && l == k){
44 st[p] += 1;
45 tag[p] += 1;
46 return ;
47 }
48 if(k <= mid) update(ls, l, mid, k);
49 else update(rs, mid + 1, r, k);
50 up(p);
51}
52
53ll query(int p, int l, int r, int L, int R){
54 if(L > R) return 0;
55 if(L <= l && r <= R) return st[p];
56 ll ans =0 ;
57 if(L <= mid) ans += query(ls, l, mid, L, R);
58 if(R > mid) ans += query(rs, mid + 1, r, L, R);
59 return ans;
60}
61
62int main(){
63// Fastin;
64 int t; scanf("%d", &t); while(t--){
65 clr(st, 0); clr(tag, 0);
66 scanf("%s", temp); n = (int)strlen(temp);
67 manacher();
68 for(int i = 0; i < n; i++) vec[i].clear();
69 for(int i = 1; i < 2 * n; i += 2){
70 int start = (i / 2) - (p[i] / 2) + (i & 1), middle = (i - 1) / 2;
71 vec[start].push_back(middle);
72 }
73 ll ans = 0;
74 for(int i = 0; i < n; i++){
75 //2 * i + 1 是在s串中的下标。
76 int r = (p[2 * i + 1] - 1) / 2;
77 for(int x: vec[i]) update(1, 0, n - 1, x);
78 ans += query(1, 0, n - 1, i + 1, i + r);
79 }
80 printf("%lld\n", ans);
81 }
82 return 0;
83}B 区间第k大 -> 二分
上一次见到区间第k大相关问题时是在2018CCPC网络赛，当时好像是个真实的在线查询与修改的主席树，而这一次是一个披着第k大外衣的二分算法。
对于某个待检验的值x，我们统计该序列中所有满足其第k大的数大于等于x的区间的个数。如果有个数$cnt>=m$，那么这个值$x$就有可能成为最终的第m大数，更新二分下界；不然，这个数肯定不会成为第m大数，更新二分上界。
有的答案用了离散化&二分答案，我学习了这种思想后觉得没有必要进行离散化的二分答案，可以直接对排过序、去过重的序列的下标进行二分，检查当前下标所对应的值以及序列中其他值的大小关系即可。
因为学习的算法中从1开始编号，所以我在L13计算的时候也用了(n - vec[i] + 1)计算….因而DEBUG了半天才过….
1const int maxn = 1e5 + 10;
2
3int n, l;
4ll m;
5int a[maxn], b[maxn];
6vector<int> vec;
7//检查多少个区间的第k大数 >= x
8bool check(int x){
9 vec.clear(); vec.push_back(-1);
10 for(int i = 0; i < n; i++) if(a[i] >= x) vec.push_back(i);
11 ll res = 0;
12 for(int i = 1, top = (int)vec.size(); i < top; i++){
13 if(i >= l) res += (vec[i - l + 1] - vec[i - l]) * 1ll * (n - vec[i]);
14 }
15 return res >= m;
16}
17
18int main(){
19// Fastin;
20 int t; scanf("%d", &t); while(t--){
21 scanf("%d %d %lld", &n, &l, &m); for(int i = 0; i < n; i++){
22 scanf("%d", a + i);
23 b[i] = a[i];
24 }
25 sort(b, b + n);
26 int top = (int)(unique(b, b + n) - b);
27 int left = 0, right = top - 1, middle;
28 while(left < right){
29 middle = (left + right + 1) >> 1;
30 if(check(b[middle])) left = middle;
31 else right = middle - 1;
32 }
33 printf("%d\n", b[left]);
34 }
35 return 0;
36}因为与2020校赛网络赛I题类似，而当时那道题看题解好像好难的样子就没有补，所以借此机会也补完了I题学习了第一个可持久化结构
J 组合数学 & 数学期望
学习于博客 : hdu6239 Interview 期望+拉格朗日插值法|生成函数 推公式
算是一个比较纯粹的数学题，但是发现这道题目的时候已经有点晚，没有来得及推完所有结果。
最初我自己想的时候没有考虑清楚，认为当前观测到的事实所带来一些约束条件出现的几率都是等可能的，但是这不符合题目的要求；题目只保证了在最开始经理选择K值时每个位置几率相等，所以当观测发生后，尽管K可能出现的范围确定，但是他们的几率不是等可能的，不能简单的进行等概率计算。
一种可行的办法是转化为古典概型，通过情况的总数、每一种情况下的观测值进行计算随机变量的数学期望。
当已知Bob在第一天面试时，应该有不等式$1 <= b <= k < a <= n$，总数就是这个不等式所有可能的三元组$(b, k, a)$的个数。我们可以将不等式转化为另一种形式:
令: $$x= b- 1, y = k - b, z = a - k - 1, w = n - a$$
则有: $$ x + y + z + w = n - 2, x, y, z, w>=0$$
求不定方程的整数解个数。
那么结果显然，总数有$(^{n+1}_{\space\space3})$
接下来考虑第二天面试次序的值。考虑这样的枚举方法：枚举Bob和Alice的间距$d$，两人一共有$n-d$种可能的布置位置，而对于每一种位置，K可以取的范围为[Bob, Alice)，Alice第二天的面试次序对应分别为1,2,...,d。因而对于每一个$d$，都会有贡献$\frac{d *(d + 1)}{2}$。故在所有情况中，Alice的位置可以用以下和式表达：
$\sum_{d = 1}^{n-1}$ $(n-d)*$ $ \frac {d (d + 1)}{2}$ $()$
化简一番得到$(^{n+2}_{\space\space4})$
由于这个和式可以很容易地构造阶梯项做差消去中间量，所以没有花功夫再去学习拉格朗日插值 生成函数等算法。不过最主要的原因还是要学的东西太多了…而组合数学和具体数学已经无数次被提起日程并被拖延至今了。
下面考虑Bob在第二天面试时。
总数可以类似地考虑两个不等式的值:
$0 <= k <a <b <= n$
$0<=k<b<a<=n$
这两个不等式形式对称，结合Bob第一天的讨论方法易知结果为$2*(^{n+1}_{\space\space3})$.
而面试的次序分为两类情况讨论:
- $0 <= k < a < b <= n$. 在这种情况中，我们可以类似地枚举距离$d = b - k$，对于每一个距离Alice的次序会取到
[1,..,d-1]，$d$从2取到n，将$(*)$式稍作变换就与这种情况相同。 - $0 <= k < b < a <= n$. 此时，我们枚举Alice在第二天的次序，即$d = a - k$。对于每一个次序，Bob可以取的范围在
[k + 1, a- 1]，即有$d-1$种可行位置，那么结果就是$\sum_{d=2}^{n}$ $d(d-1)$，这恰是上一种情况、也就是$(*)$式的两倍。
因而综上所示，Bob在第二天时位次的总和是$()$ 式的三倍，即$3(^{n+2}_{\space\space4})$.
至此，我们有了总数和每种情况下的次序之和，做除法就可以得到期望。结果分别为$\frac{n+2}{4}$与$\frac{3n+6}{8}$。
M 计算几何
论如何爆交40发
给出n个点，试找出一个圆过$ceil\frac n2$个点，保证这样的圆一定存在。
很明显的一个随机化，容易推出任意找三个点不在该圆上的概率接近$\frac78$，因而我们只需要随机100次就可以几乎确定下来这个圆。那为什么WA了40发呢..以为是精度，结果是情况少考虑了。qaq在我的算法中，如果随机得到的3个点共线，就continue进行下一次。然而我没有特判4点共线的情况，导致了这种情况下找不到一个合适的圆。
贴一个已知平面三点求圆心及其半径的板子。
证明方法为做差解二元一次方程的行列式结果。
1void cal(double x1, double y1, double x2, double y2, double x3, double y3){
2 double a, b, c, d, e, f;
3 a = 2 * (x2 - x1);
4 b = 2 * (y2 - y1);
5 c = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
6 d = 2 * (x3 - x2);
7 e = 2 * (y3 - y2);
8 f = x3 * x3 + y3 * y3 - x2 * x2 - y2 * y2;
9
10 double x, y, r;
11 x = (b * f - e * c)/(b * d - e * a);
12 y = (d * c - a * f)/(b * d - e * a);
13 r = sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
14}