本文共 3225 字，大约阅读时间需要 10 分钟。

这次还好

T1

看了一眼数据，$O(n)$的时间复杂度显然可过
所以——
大胆暴力
拿到了$100pts$

$ACCode$

#include<algorithm>#include<iostream>#include<cstdio>#include<cmath>using namespace std;long long n,ans=922337203685477,js;long long x[100010],y[100010];int main(){   	freopen("marathon.in","r",stdin);	freopen("marathon.out","w",stdout);	scanf("%lld",&n);	for(int i=1; i<=n; i++)	 {   	 	scanf("%lld %lld",&x[i],&y[i]);	 	if(i>=2)	 	  js=js+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);   //统计	 }	for(int i=2; i<=n-1; i++)	 {   	 	if(js-abs(x[i]-x[i-1])-abs(y[i]-y[i-1])-abs(x[i]-x[i+1])-	 	abs(y[i]-y[i+1])+abs(x[i-1]-x[i+1])+abs(y[i-1]-y[i+1])<ans) //类似搭桥        ans=js-abs(x[i]-x[i-1])-abs(y[i]-y[i-1])-abs(x[i]-x[i+1])-        abs(y[i]-y[i+1])+abs(x[i-1]-x[i+1])+abs(y[i-1]-y[i+1]);	 }	printf("%lld",ans);	return 0;}

T2

发现了正数与负数的巧妙联系，
再看一眼数据，$O(n)$的时间复杂度显然可过
所以——
大胆暴力
拿到$100pts$

$ACCode$

#include<algorithm>#include<iostream>#include<cstdio>#include<cmath>using namespace std;long long n,ans=999999999;struct node{   	long long a,b;}boss[1000010];int cmp(const node&aa,const node&bb){   	return aa.a<bb.a;}int main(){   	freopen("sum.in","r",stdin);	freopen("sum.out","w",stdout);	scanf("%lld",&n);	for(int i=1; i<=n; i++)	 {   	 	scanf("%lld",&boss[i].a);	 	boss[i].b=boss[i].a;	 	if(boss[i].a<0)      //全部变正数	 	  boss[i].a*=-1;	 }	sort(boss+1,boss+1+n,cmp);    //结构体排序	for(int i=2; i<=n; i++)	 if(abs(boss[i].b+boss[i-1].b)<ans)	   ans=abs(boss[i].b+boss[i-1].b);	printf("%lld",ans);	return 0;}

T3

比赛时输出样例
拿了10分。。。
正解：前缀和+贪心

$ACCode$

#include<algorithm>#include<iostream>#include<cstdio>#include<cmath>using namespace std;int ans,c[1000010],n,js;char x;struct node{   	int a,b;}e[1000005];bool cmp(const node&l,const node&r){   	return l.a<r.a;}int main(){       freopen("fairphoto.in","r",stdin);    freopen("fairphoto.out","w",stdout);    scanf("%d",&n);    for(int i=1; i<=n; i++)     {           cin>>e[i].a>>x;        if(x=='G')          e[i].b=1;          //G放1，H放-1.        else          e[i].b=-1;     }    sort(e+1,e+n+1,cmp);        //快排，保证最优性。    for(int i=1; i<=n; i++)     {           js+=e[i].b;        if(js==0)          ans=max(ans,e[i].a-e[1].a);      //贪心        if(c[js+n]==0)          c[js+n]=i;        else		  ans=max(ans,e[i].a-e[c[js+n]+1].a);     //前一段-后一段     }	printf("%d",ans);    return 0;}

T4

这题我本来可以拿93.3分的！！！
结果神经质多打了个$for$
导致只有$40pts$
正解也是模拟

$ACCode$

#include<algorithm>#include<cstring>#include<iostream>#include<cstdio>#include<cmath>using namespace std;int ls,lzs,i,js;string s,zs;int main(){   	freopen("censor.in","r",stdin);	freopen("censor.out","w",stdout);	cin>>s>>zs;	ls=s.size();	lzs=zs.size(); 	while(i<=ls-1) 	 {    		if(s[i]==zs[lzs-1]&&i>=lzs-1) 	 	 {   	 			js=i-lzs+1; 			for(int j=0;j<=lzs-1;j++)   //用for节省一些时间 			 if(zs[j]==s[js])			   js++; 			 else			  {   				 js=-1;				 break;			  } 			if(js!=-1)			 {   			 	s.erase(i-lzs+1,lzs);				i-=lzs;			 }  		 }		i++;	 }	cout<<s;	return 0;}

T5

骗分失败，$0pts$
正解：DP

还没做
$ACCode$

总分：

$100+100+10+40=250pts$

总结:

1. 做完题后如果还有时间要回来看看做过的题目能不能优化。

转载地址：http://jjle.baihongyu.com/