题目链接：http://codeforces.com/contest/738

A题：SB题。

B题：SB题。

C题：二分。

D题：贪心。

E题：乱搞。

F题：设f[i][j][k]代表甲先手，左边消去了i个，右边消去了i+j个，上一次消去k个时答案。g[i][j][k]乙先手。可以证明j<=sqrt(2n),k<=sqrt(2n)。o(n^2)。

代码：

A：

#include
     
      #include
      
       #include
       
        #define maxn 105using namespace std;int n;char s[maxn];bool check(int x){if(x>n-2)return 0;return s[x]=='o'&&s[x+1]=='g'&&s[x+2]=='o';}int main(){  scanf("%d",&n);scanf("%s",s+1);  for(int i=1;i<=n;){    if(check(i)){      if(check(i+2))i+=2;      else putchar('*'),putchar('*'),putchar('*'),i+=3;    }else putchar(s[i]),i++;  }  puts("");  return 0;}
       
      
     

B题：

#include
     
      #include
      
       #include
       
        #define maxn 1005using namespace std;int n,ans,m,a[maxn][maxn],sum[maxn][maxn];int read(){  int x=0,f=1;char ch;  for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;  for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';  return x*f;}int main(){  n=read();m=read();  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];  for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)if(!a[i][j]){	if(sum[i-1][j]-sum[i-1][j-1])ans++;	if(sum[i][j-1]-sum[i-1][j-1])ans++;	if(sum[n][j]-sum[n][j-1]-sum[i][j]+sum[i][j-1])ans++;	if(sum[i][m]-sum[i][j]-sum[i-1][m]+sum[i-1][j])ans++;    }  printf("%d\n",ans);  return 0;}
       
      
     

C题：

#include
     
      #include
      
       #include
       
        #define maxn 200005using namespace std;int n,k,s,t,tot,a[maxn],c[maxn],v[maxn];int read(){  int x=0,f=1;char ch;  for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;  for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';  return x*f;}bool check(int x){  int sum=0;  for(int i=1;i<=tot;i++){    if(x
        
         t)return 0;else return 1;}int main(){  n=read();k=read();s=read();t=read();  for(int i=1;i<=n;i++)c[i]=read(),v[i]=read();  for(int i=1;i<=k;i++)a[++tot]=read();a[++tot]=s;  sort(a+1,a+tot+1);  int l=0,r=1e9,mid;  while(l<=r){    mid=(l+r)>>1;    if(check(mid))r=mid-1;    else l=mid+1;  }  int ans=2e9;  for(int i=1;i<=n;i++)if(v[i]>r&&c[i]
        
       
      
     

D题：

#include
     
      #include
      
       #include
       
        #define maxn 200005using namespace std;int n,a,b,k,tot,ans[maxn];char s[maxn];int main(){  scanf("%d%d%d%d\n",&n,&a,&b,&k);scanf("%s",s+1);  int pre=0;  for(int i=1;i<=n;i++){    if(s[i]=='1'){      for(int j=pre+b;j
       
      
     

E题：

#include
     
      #include
      
       #include
       
        #define maxn 200005using namespace std;int n,s,a[maxn],ans;int read(){  int x=0,f=1;char ch;  for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;  for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';  return x*f;}int main(){  n=read();s=read();  for(int i=1;i<=n;i++){    a[i]=read();    if(i==s&&a[i])a[i]=0,ans++;    if(i!=s&&!a[i])a[i]=1e9;  }  sort(a+1,a+n+1);  for(int i=2,j=n;i<=j;i++){    int t=max(a[i]-a[i-1]-1,0);    if(j-i+1<=t)ans+=j-i+1,j=i-1;    else j-=t,ans+=t;  }  printf("%d\n",ans);  return 0;}
       
      
     

F题：

#include
     
      #include
      
       #include
       
        #define maxn 4005using namespace std;int n,f[2][maxn][180][90],a[maxn],sum[maxn];const int inf=1e9;int read(){  int x=0,f=1;char ch;  for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;  for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';  return x*f;}int dfs(int z,int l,int r,int k){  if(f[z][l][r][k]!=-1)return f[z][l][r][k];  if(z==0)f[z][l][r][k]=max(2*l+r-90+k>n?0:dfs(1,l+k,r-k,k)+sum[l+k]-sum[l],2*l+r-90+k+1>n?-inf:dfs(1,l+k+1,r-k-1,k+1)+sum[l+k+1]-sum[l]);  else f[z][l][r][k]=min(2*l+r-90+k>n?0:dfs(0,l,r+k,k)-sum[n-l-r+90]+sum[n-l-r+90-k],2*l+r-90+k+1>n?inf:dfs(0,l,r+k+1,k+1)-sum[n-l-r+90]+sum[n-l-r+90-k-1]);  return f[z][l][r][k];}int main(){  n=read();for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];  memset(f,-1,sizeof(f));  printf("%d\n",dfs(0,0,90,1));  return 0;}