前言
目前打过的最逆天的一场，前半场CF评测机度假去了，全场In queue，两小时左右评测机终于回来了，Standings遍地开花，听取WA声一片。
昨天就有好几道题是因为没及时看题所以没做，赛后还和队友商量说应该先把所有题大致看一遍，结果今天不长记性，还没看H和J，就去写思路不一定对+实现起来难得要死的D，最后还没做出来。要是把这时间拿去做H，多半能搞出来。明天一定长记性。一定。
G. Gnoll Hypothesis
题意
不细说了，大家应该都做了而且都会做，但好像都用组合数算的，我来点不太一样的思路。
解法
n个怪物有k个要被选中，现在考虑x号怪物，在所有方案中它被选中的概率其实就是k/n，它的答案就加上s[x] * k/n。接下来还剩n-1个怪物，要选k-1个，也就是要有(n-1)-(k-1) = (n-k)个不被选中，那x的前一个怪物不被选中的概率其实就是(n-k)/(n-1)，答案就加上s[x-1] * k/n * (n-k)/(n-1)。依此类推。也就是说初始概率p为n/k，往前推到x-i个位置，p就乘上(n-k-i+1)/(n-i)，然后x位置的答案加上s[x-i] * p即可。
虽然本质和组合数的方法一样，但想起来好像要容易很多……反正对本数学蒟蒻来说是这样的。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ld long double
using namespace std;
const int N = 1005;
int n, k, fz, fm;
ld a[N], p, ans[N];
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i + n] = a[i];
}
for(int i = n + 1; i <= n * 2; i++){
p = (ld)k / (ld)n;
fz = n - k;
fm = n - 1;
ans[i - n] = p * a[i];
for(int j = 1; j <= n - k; j++){
p = p * (ld)fz / (ld)fm;
ans[i - n] += p * a[i - j];
fz--;
fm--;
}
}
for(int i = 1; i <= n; i++){
if(i > 1) printf(" ");
printf("%.12Lf", ans[i]);
}
return 0;
}
H. Height Profile
题意
平面上有n+1个点，它们的横坐标依次是从0到n的整数，从左到右依次给出每个点的纵坐标，然后把这些点从左到右顺次相连，形成一条折线。k次询问，每次给出一个斜率g（下面的代码里写成q了），问这条折线上是否存在两个点，它们的连线的斜率不小于g。如果有，求出这两个点的横坐标的最大差值；如果没有，输出-1。
解法
边画边想，容易想到 如果存在这样的两个点，那么它们至少有一个横坐标是整数[1]。首先考虑暴力解法：枚举每个横坐标为整数的点，分别找到 它左侧横坐标最小的、它右侧横坐标最大的 两个可行的横坐标为整数的点，如果这两个点不是第0个、第n个点，可以简单地用数学方法求得向左、向右最多能延伸到什么位置。然后更新答案即可。
[1] 假设两个端点横坐标都不是整数，也就是说它们都位于折线的某一段的中间。如果这两段的斜率相等，那找到的线段就可以 两个端点固定在折线上 任意平移。那我们把线段平移到可行的最左端或最右端位置，这种情况就相当于两个点横坐标都是整数。如果两段斜率不相等，那我们可以向上或向下移动这条线段，使得它长度变长且斜率不变，就不是最优解了。
可是上述做法时间复杂度能达到O(k·n2)，会TLE。设上述过程中枚举到某个横坐标为r的点时，找到的左侧最远的可行点是l，就有(h[r]-h[l])/(r-l) ≥ g，也就是h[r]-rg ≥ h[l]-lg。可以把所有整数横坐标的点按h[i]-ig从小到大排序。从前往后遍历，枚举到横坐标为i的点时，已经遍历过的点中横坐标最小的点，就是左侧要找的点。直接更新答案即可。找右侧可行点同理。时间复杂度只有O(k·nlogn)，可以通过。
唉，读完题思路就差不多了，可惜只剩半小时的时候才看这题，难受qwq
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#define ll long long
#define ld long double
using namespace std;
const int N = 1e5 + 5;
const ll INF = 1e18;
int n, k;
ld h[N], q;
struct node{
int id;
ld mk;
node(int id1 = 0, ld mk1 = 0){
id = id1;
mk = mk1;
}
bool operator < (const node &n1) const{
if(mk == n1.mk) return id < n1.id;
return mk < n1.mk;
}
}d[N];
int main(){
cin.tie(0);
cin >> n >> k;
for(int i = 0; i <= n; i++){
cin >> h[i];
}
while(k--){
cin >> q;
q *= 10;
ld ans = 0;
for(int i = 0; i <= n; i++){
d[i] = node(i, h[i] - (ld)i * q);
}
sort(d, d + 1 + n);
int minpos = d[0].id;
for(int i = 1; i <= n; i++){
if(d[i].id < minpos){
minpos = d[i].id;
continue;
}
ld cur = (ld)(d[i].id - minpos);
if(minpos > 0){
cur += (h[d[i].id] - q * cur - h[minpos]) / (q - h[minpos] + h[minpos - 1]);
}
ans = max(ans, cur);
}
int maxpos = d[n].id;
for(int i = n - 1; i >= 0; i--){
if(d[i].id > maxpos){
maxpos = d[i].id;
continue;
}
ld cur = (ld)(maxpos - d[i].id);
if(maxpos < n){
cur += (h[maxpos] - q * cur - h[d[i].id]) / (q - h[maxpos + 1] + h[maxpos]);
}
ans = max(ans, cur);
}
if(ans == 0){
printf("-1\n");
}
else{
printf("%.12Lf\n", ans);
}
}
return 0;
}