首页 > 代码库 > 2014北京邀请赛(部分题解)
2014北京邀请赛(部分题解)
马上要去比赛了。
今天做了一下2014北京邀请赛,出了两道题目,感觉很水啊、、、
首先H题:
H. Happy Reversal
Input
Output
For each case, first output the case number as "Case #x: ", and x is the case number. Then you should output an integer, indicating the maximum result that Elfness can get.
题意:给出n个二进制串,可以把其中的一些0和1反转(即0变1,1变0),找出转化后n个串中的最大值和最小值的差值。
分析:思路就是把所有的串和反转的存在一个数组中,然后排序,找最大值和最小值的差,(如果是同一个串反转的就找第二大的和最小的或第二小和最大的中的最大值)。注意假如只有一个串的话结果为0
代码:
#include <iostream> #include <string> #include <algorithm> using namespace std; class number { public: long long p; string s; void Set(long long p,string s) { this->p = p; this->s = s; } friend bool operator < (number a,number b) { return a.s < b.s; } }; int main() { long long T,c=0; cin>>T; number num[20020]; while(T--) { c++; long long n,k; cin>>n>>k; string s; for(long long i = 0; i < 2*n; ++ i) { cin>>s; num[i].Set(i,s); for(long long j = 0; j < k; ++ j) if(s[j]=='0') s[j]='1'; else s[j]='0'; ++i; num[i].Set(i-1,s); } sort(num,num+2*n); // for(long long i = 0; i < 2*n; ++ i) // cout<<num[i].s<<endl; cout<<"Case #"<<c<<": "; if(n == 1) { cout<<"0"<<endl; } else if(num[0].p!=num[2*n-1].p) { long long a=0,b=0; for(long long i = k-1,j=1; i >= 0; -- i,j<<=1) { if(num[0].s[i] == '1') a+=j; } for(long long i = k-1,j=1; i >= 0; -- i,j<<=1) { if(num[2*n-1].s[i] == '1') b+=j; } cout<<b-a<<endl; } else { string s1,s2; long long a=0,b=0,ans=0; s1 = num[0].s; s2 = num[2*n-2].s; for(long long i = k-1,j=1; i >= 0; -- i,j<<=1) { if(s1[i] == '1') a+=j; } for(long long i = k-1,j=1; i >= 0; -- i,j<<=1) { if(s2[i] == '1') b+=j; } ans = b-a; b=0;a=0; s1 = num[1].s; s2 = num[2*n-1].s; for(long long i = k-1,j=1; i >= 0; -- i,j<<=1) { if(s1[i] == '1') a+=j; } for(long long i = k-1,j=1; i >= 0; -- i,j<<=1) { if(s2[i] == '1') b+=j; } cout<<max(ans,b-a)<<endl; } } return 0; }
B题:
B. Beautiful Garden
Input
- The first line contains an integers number n (1 ≤ n ≤ 40), representing the number of trees lxhgww planted;
- The second line contains n integers numbers, the ith number represents xi. (-1000000000 ≤ xi ≤ 1000000000)
Output
For each case, first output the case number as "Case #x: ", and x is the case number. Then output a single number, representing the minimum number of trees lxhgww needs to move.
题意:给出一些数,表示数轴上的位置,让你移动最少的点让所有相邻点的差值均相等!求移动次数
分析:思路就是暴力,因为点只有40个,所以我们可以枚举相邻点的差值,因为我最少也能够保证两个点是不动的,那么我枚举这两个点作为所有的差值,然后找一个落在枚举的方案的最大点的方案。
此题目坑点很多!首先有可能两个点落在同一位置,其次枚举的话数据范围会超int。算是一个坑题。
代码:
#include <iostream> #include <string> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; long long a[200]; int main() { long long T; scanf("%lld",&T); for(long long cas=1;cas<=T;cas++) { long long n,ans=0; scanf("%lld",&n); long long len=n; for(long long i=0;i<n;i++) ///输入 { scanf("%lld",&a[i]); } sort(a,a+n); long long count=0,tmp=1; for(long long i=1;i<n;i++) //找数组中只有两个数且重点的最小值 { if(a[i]==a[i-1]) { tmp++; } else break; } long long xx = 0,tt=0; int p = 0; for(int i = 0; i < n; ++ i) //找所有里面重点最多的 { if(i == n-1) { ++tt; if(xx < tt) xx = tt; } else if(a[i]==a[p]) tt++; else { p = i; if(xx < tt) xx = tt; tt=1; }//printf("*%lld\n",tt); } // printf("x%lld\n",tmp); count = min(tmp,len-tmp); for(long long i=1;i<n;i++) ///删除重复元素 { if(a[i]==a[i-1]) { for(long long j=i;j<n-1;j++) a[j]=a[j+1]; n--;i--; } } // for(long long i=0;i<n;i++) // printf("%lld ",a[i]); for(long long i=0;i<n-1;i++) ///枚举结果 { for(long long j=i+1;j<n;j++) { long long lis=a[j]-a[i]; // if(lis==0) // continue; for(long long k=0;k<n;k++) { long long mm=0; long long ri=a[k]+(len-1)*lis; // printf("x%lld ",ri); for(long long f=k;f<n && a[f]<=ri;f++) { // if(f==i || f==j) // continue; long long tmp=a[f]-a[i]; if(tmp<0) tmp=-tmp; if(tmp%lis==0) mm++; } // printf("%lld\n",mm); if(mm>ans) ans=mm; } } // printf("xx\n\n"); } printf("Case #%lld: ",cas); if(n==1 || len==2) { printf("0\n");continue; } else if(n==2 && len>2) { printf("%lld\n",count);continue; } printf("%lld\n",min(len-ans,len-xx)); } return 0; }