Codeforces部分题⽬题解（⼝胡）
883D
题⽬⼤意：给你⼀个长度为n的字符串，上⾯有⽜(“P”)，草(“*”)和空地(“.”)。现在你给每⼀头⽜规定⼀个⽅向，它会⼀直往前吃草，直到⾛到边界。每⼀份草只会被吃1次，要求输出最多吃多少草，以及在此基础下吃完最后⼀份草的最⼩时间。n<=1000000。
做法：很明显两头⽜就可以吃完所有草，于是暴⼒处理0,1头⽜的情况。然后由于具有单调性，考虑⼆分答案后贪⼼（时限3s不虚）。接下来证明两个⼩结论：
1.最前⾯的草，顶多会被它后⾯第⼆头⽜吃掉。
这个从上图就可以看出。①中红⾊和蓝⾊的边分别⽐②中红⾊和蓝⾊的边长。
2.⼆分完阀值mid后，如果最前⾯的草后⾯mid处⾄少有两头⽜，且第⼀头⽜与第⼆头⽜之间没有草，那么让第⼀头⽜吃该草，第⼆头⽜往后吃。
这个结论应该很显然……
但是如果两头⽜中间有草怎么办呢？是不是让第⼆头⽜往前吃，第⼀头⽜往后吃就最优了？答案是否定的。我⼀开始按照这个思路写了个贪⼼，结果被下⾯这组数据卡掉了：
19
（这组数据的最优⽅案应该是让第⼀，三头⽜往前吃，第⼆头⽜往后吃）
所以我们要⽤DP！记f[i]=j表⽰考虑完第i头⽜之后，最多能处理完1~j处的草。然后根据上述思路⽤f[i-2]或f[i-1]转移即可。
我⼀开始把时限看成了1s，结果想了很久都想不出O(n)的做法QAQ
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
橡皮的英语#include<algorithm>
using namespace std;
const int maxn=1000100;
int sum[maxn];
int f[maxn];
int id[maxn];
char s[maxn];
int a[maxn];
int n;
int cnt=0,num=0;
bool Judge(int x)
{
f[0]=0;
for (int i=1; i<=num; i++)
{
f[i]=0;
int y=id[i];
if (f[i-1]>=y-1) f[i]=max(f[i],y+x);
if (f[i-1]<y-1)
if (sum[y]-sum[ f[i-1] ])
if (sum[max(0,y-x-1)]-sum[ f[i-1] ]>0) return fal;
el
{
f[i]=max(f[i],y);
if ( i>=2 && sum[max(0,y-x-1)]-sum[ f[i-2] ]<=0 ) f[i]=max(f[i],id[i-1]+x);
}
el f[i]=max(f[i],y+x);
}
if ( f[num]>=n || sum[n]-sum[ f[num] ]<=0 ) return true; return fal;
}
int Binary()
{
int L=0,R=n;
while (L+1<R)
{
int mid=(L+R)>>1;
if ( Judge(mid) ) R=mid;
el L=mid;
}
return R;
}
int main()
{
freopen("2326.in","r",stdin);
freopen("2326.out","w",stdout);
scanf("%d",&n);
scanf("%s",s);
for (int i=1; i<=n; i++)
{
if (s[i-1]=='*') a[i]=0,cnt++;
韩红新歌if (s[i-1]=='P') a[i]=1,id[++num]=i;
if (s[i-1]=='.') a[i]=2;
}
if (num<=1)
if (num==0) printf("0 0\n");
el
{
int x=0,y=0;
for (int i=1; i<=n; i++)
if (a[i]==0) y++;
int Le=0,Ri=0;
for (int i=x; i>=1; i--)
if (a[i]==0) Le=x-i;
for (int i=x; i<=n; i++)
if (a[i]==0) Ri=i-x;
if (y>cnt-y) printf("%d %d\n",y,Le);
el
if (y<cnt-y) printf("%d %d\n",cnt-y,Ri);
el
if (Le<Ri) printf("%d %d\n",y,Le);
el printf("%d %d\n",cnt-y,Ri);
}
el
{
sum[0]=0;
for (int i=1; i<=n; i++)
{
sum[i]=sum[i-1];
if (a[i]==0) sum[i]++;
}
物华天宝的意思>亲爱的用英语怎么说
int ans=Binary();
printf("%d %d\n",cnt,ans);
}
return0;
}
875E
题⽬⼤意：有n个城市，给出它们在数轴上的坐标。现在有两个⼈在s1和s2处，他们要按顺序⾛完这n个城市，求他们两个⼈最⼤距离的最⼩值。n<=100000。
做法：分析之后发现，它就是要你把这n个城市分成若⼲段，使得每⼀段的所有城市到上⼀段的最后⼀个城市的距离⼩于等于ans。⼆分答案之后⽤treap维护即可，时间复杂度。
然⽽这样做会被卡常（虽然CF的机⼦跑得灰常快）。
更优的⽅法是从后往前考虑。如果第n-1个城市在[a[n]-mid,a[n]+mid]的范围内，就可以⽆视掉第n个城市；否则就要求第n-2个城市在[a[n]-mid,a[n]+mid]与[a[n-1]-mid,a[n-1]+mid]的交集内，不存在则⽆解。这样时间就是。
CODE（Treap）：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100100;
const int oo=2000001000;
const long long M1=998244353;
const long long M2=1000000007;
const long long M3=1333333331;
typedef long long LL;
LL ed;
{
int val,id,min_id,fix;
Tnode *lson,*rson;
} tree[maxn];
Tnode *Root;
int cur;
int Right[maxn];
int a[maxn];
int n,s1,s2;
int Rand()
{
ed=(ed*M1+M2)%M3;
return ed;
}
Tnode *New_node(int Val,int Id)
{
cur++;
tree[cur].val=Val;
tree[cur].min_id=tree[cur].id=Id;
tree[cur].fix=Rand();
tree[cur].lson=tree[cur].rson=NULL;
return tree+cur;
}
void Recount(Tnode *P)
{
P->min_id=P->id;
if (P->lson) P->min_id=min(P->min_id,P->lson->min_id); if (P->rson) P->min_id=min(P->min_id,P->rson->min_id); }
void Right_turn(Tnode *&P)
{
妈妈听我说Tnode *W=P->lson;
P->lson=W->rson;
W->rson=P;
P=W;
Recount(P->rson);
过去分词的用法
Recount(P);
}
void Left_turn(Tnode *&P)
{
Tnode *W=P->rson;
P->rson=W->lson;
W->lson=P;
P=W;
Recount(P->lson);
Recount(P);
}
void Inrt(Tnode *&P,int Val,int Id)
{
if (!P) P=New_node(Val,Id);
el
if ( Val<P->val || ( Val==P->val && Id<P->id ) )
{
Inrt(P->lson,Val,Id);
if ( P->lson->fix < P->fix ) Right_turn(P);
el Recount(P);
{
Inrt(P->rson,Val,Id);
if ( P->rson->fix < P->fix ) Left_turn(P);
el Recount(P);
}
}
int Find_succ(Tnode *P,int Val,int Ans)
{
if (!P) return Ans;
if (Val<P->val)
{
Ans=min(Ans,P->id);
if (P->rson) Ans=min(Ans,P->rson->min_id);
return Find_succ(P->lson,Val,Ans);
}
return Find_succ(P->rson,Val,Ans);
怎么编手链}
int Find_prev(Tnode *P,int Val,int Ans)
{
if (!P) return Ans;
if (P->val<Val)
{
Ans=min(Ans,P->id);
if (P->lson) Ans=min(Ans,P->lson->min_id);
word文档打不开return Find_prev(P->rson,Val,Ans);
}
return Find_prev(P->lson,Val,Ans);
}
bool Judge(int x)
{
Root=NULL;
cur=-1;
Inrt(Root,-oo,n+1);
Inrt(Root,oo,n+1);
for (int i=n; i>=1; i--)
{
int Succ=Find_succ(Root,a[i]+x,n+1);
int Prev=Find_prev(Root,a[i]-x,n+1);
Right[i]=min(Prev,Succ)-1;
Inrt(Root,a[i],i);
}
int now=0;
int Succ=Find_succ(Root,s1+x,n+1);
int Prev=Find_prev(Root,s1-x,n+1);
now=max(now, min(Prev,Succ)-1 );
Succ=Find_succ(Root,s2+x,n+1);
Prev=Find_prev(Root,s2-x,n+1);
now=max(now, min(Prev,Succ)-1 );
for (int i=1; i<=n; i++)
{
if (i>now) return fal;
now=max(now,Right[i]);
}
return true;
}
int Binary()
{
int L=0,R=1000000000;
while (L+1<R)
