成绩

比赛经过

先看了 \(\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

咕咕咕

考后反思

首先一个是知识点的缺漏（但是提高组会考可持久化？）。然后就是高精度取模这种东西，算是一个小技巧吧。

结尾

咋会出现这么多没学过的知识点捏？