补题报告之S班暑训第四场
成绩
比赛经过
先看了 \(\text{A}\) 题，想到随机取模，但是，我竟然不知道高精度怎么取模？？于是就和正解失之交臂了。至于为啥会有 \(83\) 分，我只能说数据太水了，\(\text{FFT}\) 写高精就超时了一个点 \(\dots\)。
看了 \(\text{B}\) 题，想了 \(10\) 分钟左右写出来方程，\(5\) 分钟左右证明单调性，\(5\) 分钟左右写代码（顺便证了一下样例里的那个非根式解）。
\(\text{C}\) 题，看到强制在线，就放弃莫队的了。然后前缀异或和的性质分析出来后，写了一个 \(\text{DP}\)（因为我不会可持久化 \(\text{01trie}\dots\)），然后继续换题。
\(\text{D}\) 题，可以转化为二分图上的动态问题，暴力没时间写了，直接二选一随机输出。奇妙的是，我过了一个点 \(\dots\)。
顺序：\(\text{A}\)，\(\text{B}\)，\(\text{A}\)，\(\text{C}\)，\(\text{A}\)，\(\text{D}\)。
赛后补题+分析
\(\text{A}\) calculate
简要/形式化题意
高精度数 \(a\)，\(b\)，\(c\)，判定 \(a \times b\) 是否等于 \(c\)。
题解
随机一个模数，对三个数分别取模当做哈希的数值，判断哈希后是否满足上面那个式子就好了，错误的概率很小，当然也可以多取几个随机模数。
AC code
为啥超时嘞？
\(\text{B}\) cylinder
简要/形式化题意
底面积为 \(1\)，高为 \(1\) 的圆柱形盒子装有体积为 \(V\) 的水，将底面积为 \(1\)，高为 \(1\) 的圆锥倒着插入到盒子里，求水此时的高度。
题解
利用小学知识可以列出方程。\(h-\dfrac{h^3}{3}=V\)。左边这个东西求个导就知道他在 \([0,1]\) 上是单调递增的，二分就好了。
AC code
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int T;
double V;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--) {
cin>>V;
double l=0.0,r=1.0;
while(r-l>=eps) {
double mid=(l+r)/2;
if(mid-mid*mid*mid/3<=V) l=mid;
else r=mid;
}
cout<<fixed<<setprecision(6)<<l<<endl;
}
return 0;
}
\(\text{C}\) xor
简要/形式化题意
区间最大异或子串问题，强制在线。
题解
首先我们可以用可持久化 \(\text{01trie}\) 做到 \(O(n^2 \log V)\)。
当然我们也可以预处理，直接 \(\text{DP}\) 就好了，做到了 \(O(n^3)\)，单词 \(O(1)\)。
没错，我们只要用分块平衡两者的复杂度就好了，复杂度 \(O(n\sqrt{n}\log V)\)，可以过。
AC code
咕咕咕
\(\text{D}\) massage
简要/形式化题意
平面上动态加删点，判断是否存在一个各边平行与网格的多边形。
题解
将加点和删点看做，加了一条行到列的边，和删去，问题转变为一个判环的问题。动态的话，考虑离线做线段树分治（陌生的领域）。
AC code
咕咕咕
考后反思
首先一个是知识点的缺漏（但是提高组会考可持久化？）。然后就是高精度取模这种东西，算是一个小技巧吧。
结尾
咋会出现这么多没学过的知识点捏？