【比赛总结】Codeforces472 Div1

前言：

第一次打Div1的比赛，本来准备睡到11：30再打，结果睡过头了。还忘了注册，赣。
慌里慌张的，题都没看明白就开始交，企图挽回失误，结果受到天罚了：B题Wa了两次，调了一个小时就因为看错题意。也直接导致了最后C题也没能调出来。果然掉回蓝名去了，爽翻（话说CF评测机停电是什么操作。。。）

不过简单题还是比较好做的（ABC），后面的还没来得及看。。现在时间紧就弃了。

---

A：

CF常规A题是骗人进来的水题：
给出一个$n*m(n,m\leq 50)$的棋盘，初始状态全部为白色，现在要求使得一些点为黑色，操作方式是：选择一些行与一些列，将这些行与列同时覆盖的点改为黑色。要求每行每列最多被选择一次。求是否能够得到目标状态。

由于N，M比较小，直接将每一行存储为一个二进制数（黑为1，白为0）
设这些数分别为$A_1,A_2,……A_n$
如果存在一对数$i,j$，使得$A_i$&$A_j ≠0且A_i≠A_j$则不可能得到目标状态
暴力枚举一发就过了

---

B:

给出一个递增序列E，找出一个三元组$(i,j,k)满足i<j<k$
求$\frac {E_k-E_j} {E_k-E_i}$的最大值，并且还有一个限制：$E_k-E_i\leq X$

$\\$
$\\$
很显然，在最优的情况下，j=i+1是必然的。因为当i确定时，$E_j$必须尽可能小，则$E_{i+1}$就是大于$E_i$的数中最小的。

现在反过来看，对于任意一组$i,j$，当$E_k$尽可能大时最优，这个也很好证明，可以将式子化成如下形式：

$$\frac {E_k-E_j} {E_k-E_i}=1+\frac {E_i-E_j} {E_k-E_i}$$ 由于i,j都已确定且 $E_i<E_j$，所以 $E_i-E_j<0$，则当 $E_k$尽可能大时，值也最大。
具体做法就是从左往右枚举i，再滑窗确定k即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
int a[MAXN],n,q;
bool flag;
double ans;
int main(){SF("%d%d",&n,&q);for(int i=0;i<n;i++)SF("%d",&a[i]);int k=1;for(int i=0;i<n;i++){while(a[k]-a[i]<=q&&k<n)k++;int k1=k-1;if(k1-i>1){int j=i+1;double ans1=double(a[k1]-a[j])/double(a[k1]-a[i]);ans=max(ans1,ans);flag=1;}}if(flag==0)PF("-1");elsePF("%.11lf",ans); 
}

---

C:

在一条河边记录N天水位线，每天都在当前的水平面处划一条线（如果重合则不划）
告知每天的水位线上方的线的数量(设为$M_i$)，求每天的水位线下方线的数量(设为$D_i$)之和的最小值。即$\sum_{i=1}^{i\leq n}D_i$
$N\leq 100000$

$\\$
$\\$
$\\$
设$k满足M_k=max(M_i)$
在第k天以后的每一天，都可以不增加新的线而使得水位线下方线的数量和尽可能小。证明很简单，设总的线的数量为n，那么$D_i=n-M_i-[当前的水位线是否与之前某一天重合]$，n的最小值显然是$M_k+1$，并且使得条件一直满足，则$D_j=M_k-M_j$。

现在第$k$以及之后已经解决了，我们考虑能否将这个算法持续做下去：再找到剩余的$k'=max(M_i)'$，很显然，这时就有一个限制条件了：即在第k天前，必须有$M_k$条水位线（考场上就是在处理这个的时候调了很久，最终GG）
其实也是个很简单的东西：考虑刚才那个式子，很显然在尽量靠后的天划线是最优的，因为它能影响的时间最短。

所以这道题的复杂度为O(n)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
int n;
long long ans;
int a[MAXN],maxid[MAXN];
void solve(int x,int sum){if(x<0)return ;int id=maxid[x];int add=sum-a[id]-1;int len=x-id+1;//PF("[%d [%d] %d %d]\n",id,a[id],add,len);for(int i=x;i>id;i--){ans+=(a[id]-a[i]+add);if(add>0)add--;}ans+=add;solve(id-1,add+a[id]);
}
int main(){SF("%d",&n);for(int i=0;i<n;i++)SF("%d",&a[i]);for(int i=1;i<n;i++){if(a[i]>a[maxid[i-1]])maxid[i]=i;elsemaxid[i]=maxid[i-1];}int id=maxid[n-1];for(int i=id;i<n;i++)ans+=(a[id]-a[i]);solve(id-1,a[id]);PF("%I64d",ans);
}