Codeforces Round #127 (Div. 二)

2012-07-18

Codeforces Round #127 (Div. 2)转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmodecontents

Codeforces Round #127 (Div. 2)

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

好可惜的一场，不过凭借一开始的手速，还是涨了rate。

A：LLPS

找出字典序最大的回文子串，显然子串所有字母相同，全为字典序最大的那个，遍历一遍就OK了。

如果中间有别的字母，比如X()()X,括号中是别的小于X的字母，那么这个子串的字典序肯定小于XX

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-10#define LL long long#define LD long double#define pi acos(-1.0)using namespace std;char str[100005];int main(){while(scanf("%s",str)!=EOF){int mmax=0,cnt=0;for(int i=0;i<strlen(str);i++){if(str[i]>mmax){mmax=str[i];cnt=1;}else if(str[i]==mmax)cnt++;}for(int i=0;i<cnt;i++)printf("%c",mmax);printf("\n");}return 0;}

B： Brand New Easy Problem

被题目意思卡死，英语差太痛苦了，最后才做，结果还是把逆序对的意思理解错了，没有过system test。太可惜了

有一个字典里包括若干单词，可以任意排列，另外有一些句子，求出两个的相似度，不理解为什么有人直接依次判断就行了，貌似不是最优解啊

因为范围不大，直接全排列，而且在比较的时候我用的是dfs。

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-10#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1<<20using namespace std;int n,m;string word[5],tmp[5];string str[20];int cnt;int a[5],x;int jiecheng(int k){return k==0?1:k*jiecheng(k-1);}int find(string s){for(int i=0;i<n;i++)if(s==tmp[i])return i;}void dfs(int pos,int idx){if(pos==n){int t=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++)if(a[i]>a[j])t++;}x=min(x,t);return ;}for(int j=idx;j<cnt;j++)if(str[j]==word[pos]){a[pos]=find(word[pos]);dfs(pos+1,j+1);}}int main(){while(cin>>n){for(int i=0;i<n;i++){cin>>word[i];tmp[i]=word[i];}int idx=-1,p=0;cin>>m;for(int i=1;i<=m;i++){cin>>cnt;for(int j=0;j<cnt;j++)cin>>str[j];x=inf;sort(word,word+n);int ccc=jiecheng(n);while(ccc--){next_permutation(word,word+n);dfs(0,0);if(n*(n-1)/2-x+1>p){idx=i;p=n*(n-1)/2-x+1;}}}if(idx==-1)cout<<"Brand new problem!\n";else{cout<<idx<<"\n[:";for(int i=1;i<=p;i++)cout<<"|";cout<<":]\n";}}return 0;}

C:Clear Symmetry

B题开始看不懂，便很快转战C题，顺序的是很快解决而且1A，完全是靠C题，才涨的rate

枚举1-13，得出解，猜测结论，答案肯定为奇数，而且对于一个奇数i,最多能放i*i/2+1个1，但是要特判n=3，好多人挂在这

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-10#define LL long long#define LD long double#define pi acos(-1.0)using namespace std;int n;int main(){while(scanf("%d",&n)!=EOF){if(n==3)printf("5\n");else{for(int i=1;;i+=2)if(n<=i*i/2+1){printf("%d\n",i);break;}}}return 0;}

D - Guess That Car!

把X,Y分开考虑，对于横向的，将中心放在某点上，每一列到中心的横向距离是固定的，便可以先将横向和纵向和进行预处理。

然后枚举中心点。在计算的时候，我分两两种情况，一种是在左（上）边，一种是在右（下）边，也可以YY出一个综合式子

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-10#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1LL<<60using namespace std;int c[1000][1000],n,m;LL col[1000],row[1000];LL sqr(int x){return (LL)x*x;}int main(){while(scanf("%d%d",&n,&m)!=EOF){memset(col,0,sizeof(col));memset(row,0,sizeof(row));for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&c[i][j]);row[i]+=c[i][j];col[j]+=c[i][j];}int x=0,y=0;LL maxx=inf,maxy=inf;for(int i=0;i<=n;i++){LL tmp=0;for(int j=0;j<i;j++)tmp+=row[j]*sqr((abs(i-j-1)*4+2));for(int j=i;j<n;j++)tmp+=row[j]*sqr((abs(j-i)*4+2));if(tmp<maxx){x=i;maxx=tmp;}}for(int i=0;i<=m;i++){LL tmp=0;for(int j=0;j<i;j++)tmp+=col[j]*sqr((abs(i-j-1)*4+2));for(int j=i;j<m;j++)tmp+=col[j]*sqr((abs(j-i)*4+2));if(tmp<maxy){y=i;maxy=tmp;}}printf("%I64d\n",maxx+maxy);printf("%d %d\n",x,y);}return 0;}

E - Fragile Bridges

DP可解。dpl[i][0]表示从i出发遍历0-i的最大值，dpl[i][1]表示从i出发遍历0-i并且回到i的最大值。

dpr[i][0]表示从i出发遍历i-n的最大值，dpr[i][1]表示从i出发遍历i-n并且回到i的最大值。

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-10#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1LL<<60using namespace std;int a[100000],n;LL dpl[100000][2],dpr[100000][2];int main(){while(scanf("%d",&n)!=EOF){for(int i=1;i<n;i++)scanf("%d",&a[i]);dpl[0][0]=dpl[0][1]=0;for(int i=1;i<n;i++){dpl[i][1]=a[i]<=1?0:dpl[i-1][1]+a[i]/2*2;if(a[i]&1)dpl[i][0]=dpl[i-1][0]+a[i];elsedpl[i][0]=max(dpl[i-1][0]+a[i]-1,dpl[i][1]);}dpr[n-1][0]=dpr[n-1][1]=0;for(int i=n-2;i>=0;i--){dpr[i][1]=a[i+1]<=1?0:dpr[i+1][1]+a[i+1]/2*2;if(a[i]&1)dpr[i][0]=dpr[i-1][0]+a[i+1];elsedpr[i][0]=max(dpr[i][1],dpr[i+1][0]+a[i+1]-1);}LL ans=0;for(int i=0;i<n;i++)ans=max(ans,max(dpl[i][0],max(dpr[i][0],max(dpl[i][1]+dpr[i][0],dpr[i][1]+dpl[i][0]))));printf("%I64d\n",ans);}return 0;}

热点排行

编程

Codeforces Round #127 (Div. 二)