第一次全程参加的CF比赛（虽然过了D题之后就开始干别的去了），人生第一次codeforces上分……（或许之前的比赛如果都参加全程也不会那么惨吧），终于回到了specialist的行列，感动~。虽然最后也只过了A、B、D3题，但能上分还是非常的激动不已呀。
先发出来A、B、D的参考解法，C比赛时读了题感觉自己可以做出来，但时间只剩20分钟了，索性弃疗……。
11.23 补充上了C的参考代码
A题：
用一些str函数应该也可以做，但考虑到字符串长度只有不到100以及题目整体不是很复杂，不如直接求解。
从头开始扫描，寻找为“ogo”的子串（注意扫到倒数第三个数就结束），如果扫到了那么就输出”***“并继续看“go"能重复多少个，这个过程都只用while循环控制一下就可以了。最后再从最后的位置到n用for循环(如果此时已经到头了那么for循环也不会也不需要进行了）
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
char a[];
int n,i=;
bool check()
{
if(a[i]=='o'&&a[i+]=='g'&&a[i+]=='o')
return true;
return false;
}
int main()
{ scanf("%d",&n);
scanf("%s",a);
while(i<=n-)
{
if(check())
{
i+=;
while(a[i]=='g'&&a[i+]=='o')
i+=;
printf("***");
}
else
{
printf("%c",a[i]);
i++;
}
}
for(int j=i;j<n;j++)
printf("%c",a[j]);
return ;
}
B题：
只需要看从每个1能没有阻挡的直走到多少个0，将这些加起来即为所求的答案。所以扫一遍整个图，从每个1出发，向四周走，遇到1或走到边界停下，不然个数就+1。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
int n,m,an,ii,jj;
int lo[][],dir[][]={{,},{,},{-,},{,-}};
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
an=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
scanf("%d",&lo[i][j]);
}
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
if(lo[i][j]==)
{
for(k=;k<;k++)
{
ii=i;
jj=j;
while((ii>&&ii<=n&&jj>&&jj<=m&&lo[ii][jj]==)||(ii==i&&jj==j))
{
ii+=dir[k][];
jj+=dir[k][];
if(ii>&&ii<=n&&jj>&&jj<=m&&lo[ii][jj]==)
{an+=;
}
else break;
}
}
}
}
}
printf("%d\n",an);
return ;
}
C题
二分查找，先按汽车油箱容量递增排序，二分查找符合条件的油箱最小容量。再排序，找最低的价格。初始设定答案为一个很大的数，如果最后答案不变输出-1，不然输出新的最小价格。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
long long int k,n,x=,dis[];
long long int s,t,time1,an,l,r,mid;
bool cmp(long long x,long long y)
{
return x<y;
}
struct oh
{
long long cap,val;
}che[];
bool cmp2(oh x,oh y)
{
if(x.cap!=y.cap)
return x.cap<y.cap;
else
return x.val<y.val;
}
bool cmp3(oh x,oh y)
{
return x.val>y.val;
}
int main()
{
scanf("%I64d%I64d%I64d%I64d",&n,&k,&s,&t);
long long int i,j;
dis[]=;
an=;
for(i=;i<=n;i++)
{
scanf("%I64d%I64d",&che[i].val,&che[i].cap);
}
for(i=;i<=k;i++)
{
scanf("%I64d",&dis[i]);
}
sort(dis+,dis+k+,cmp);
sort(che+,che+n+,cmp2);
dis[k+]=s;
time1=;
l=;r=n;
while(l<=r)
{
mid=(l+r)/;
for(j=;j<=k+;j++)
{
if(dis[j]-dis[j-]>che[mid].cap)
break;
else
{
if(x<che[mid].cap-*(dis[j]-dis[j-]))
time1+=(dis[j]-dis[j-]-x);
else
time1+=(*(dis[j]-dis[j-])-che[mid].cap);
}
}
if(j==k+&&time1<=t)
{
r=mid-;
}
else
{
l=mid+;
}
time1=;
}
if(r<n)
{sort(che+r+,che+n+,cmp3);
printf("%I64d\n",che[n].val);}
else
printf("-1\n");
return ;
}
D题
我的做法貌似有点麻烦。对整个字符串现在前面加上1，末尾加上1，之后扫描一遍，对于连续的0长度小于船长的部分直接填上1。并用he代表余下为0的个数，最少的操作数即为通过最少的操作达到he<船长*船个数的状态。（注意到射击1个1右面数第”船长“个0如果没有打中船，那么从这个1到那个位置之间所有的都一定不会是船的一部分）这样之后从左往右扫，遇到a[i]=1，a[i+1]=0就意味着从第i个数开始一定有不小于船长个连续的0，这样对其操作一定不会产生”浪费“，一定会是最优的操作。如果是1而下个数不是0，那么就是碰上连续1的情况，i++即可，如果是0的话，he--，继续扫描，注意要用一个计数变量记录连续这样的0有多少个，如果达到船长就意味着有必要进行一次操作，以求达到最优的解法。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
char a[];
int n,ge,len,st,en,i,j,he=,k,cnt=,an[],s,geshu,chang;
int main()
{
scanf("%d%d%d%d",&n,&ge,&len,&k);
a[]='';
scanf("%s",a+);
a[n+]='';
st=;en=;
he=n-k;
for(i=;i<=n+;i++)
{
if(a[i]=='')
{
en=i;
if(en-st->&&en-st-<len)
{for(i=st+;i<en;i++)
a[i]='';
he-=(en-st-);
}
else
if((en-st-)%len!=)
{
for(j=en-;j>=en-(en-st-)%len;j--)
{a[j]='';
he--;
}
}
st=i;
}
}
chang=len*ge;
i=;
while(he>=chang)
{
if(a[i]==''&&a[i+]=='')
{
geshu=;
an[cnt]=i+len;
cnt++;
for(j=i+;j<=i+len;j++)
{
a[j]='';
}
he-=len;
i=i+len;
}
else{
if(a[i]=='')
{
geshu=;
while(a[i]!='')
i++;
i--;
}
else
{
if(geshu<len-)
{
a[i]='';
geshu++;
he--;
}
else
{
he--;
geshu=;
a[i]='';
an[cnt]=i;
cnt++;
}
}
}
}
printf("%d\n",cnt);
for(i=;i<cnt;i++)
printf("%d ",an[i]);
return ;
}
通过这次CF，发现或许自己没有自己之前想象的那么水，以后再参加比赛一定好好对待，全程参加，不再划水了。