2014 Beijing Invitational

本文主要是介绍2014 Beijing Invitational，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B.Beautiful Garden

题意：n(<=40)个点，求最小移动数使得任意相邻两个点间距离相等

思路：O(n^4) 

枚举两个不动点 复杂度：n^2  再枚举这两个点间可能的点数，复杂度：n 再枚举第一个点在n中的位置 复杂度:n

然后判断有多少个点可以不动，可以用标记数组，但是偷懒用了个set，时间上差不多，因为有剪枝

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
LL a[50];
set<LL>s;
int main(){int T,cas=0; scanf("%d",&T);while(T--){int n; scanf("%d",&n); s.clear();for(int i=0;i<n;i++) scanf("%lld",&a[i]),s.insert(a[i]);sort(a,a+n); int ans=n-1;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){LL d=a[j]-a[i];for(int k=0;k<=n-2;k++){if(!(d%(k+1)==0)) continue;LL dd=d/(k+1);if(dd==0){int now=0;for(int l=0;l<n;l++)if(a[l]==a[i]) now++;ans=min(ans,n-now);continue;}for(int l=0;l<n;l++){int now=0;for(int x=0;x<n;x++){LL y=a[i]+(x-l)*dd;if(!s.count(y)) now++;}ans=min(ans,now);}}}}printf("Case #%d: %d\n",++cas,ans);}return 0;
}

F.Football on Table

题意：给出球的初始位置和运动方向，以及在某些列上会出现若干间距固定的人，问球最后不碰到人不碰到边界的概率

思路：模拟，考虑球能经过每列中每个人的间隙的可能性，保证整列的最终高度不会超过w

#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
double sx,sy,dx,dy,x,y,height,w,l;
vector<double>d,v;
int main(){int T,n,m,cas=0; scanf("%d",&T);while(T--){scanf("%lf%lf",&l,&w);scanf("%lf%lf%lf%lf",&sx,&sy,&dx,&dy);scanf("%d",&m); double ans=1;for(int i=0;i<m;i++){scanf("%lf%d",&x,&n);v.clear(),d.clear(),height=0;for(int j=0;j<n;j++) scanf("%lf",&y),v.push_back(y),height+=y;for(int j=1;j<n;j++) scanf("%lf",&y),d.push_back(y),height+=y;double now=(x-sx)/dx*dy+sy;if(now<0 || now>w){ ans*=0; continue; }double total_move=w-height;if(total_move<0){ ans*=0;  continue; }double can=0,tmp=0,cnt=0;can+=max(0.0,now-height);for(int j=0;j+1<n;j++){cnt+=v[j];if(now<cnt) continue;double largest=now+height-cnt;if(largest>w) can+=max(0.0,d[j]+w-largest);else{if(now<=cnt+d[j]) can+=now-cnt;else can+=d[j];}cnt+=d[j];}can+=max(0.0,w-(now+height));ans*=can/total_move;}printf("Case #%d: %.5lf\n",++cas,ans);}return 0;
}

H.Happy Reversal

题意：n(<=1w)个长度为k(<=60)的01二进制串，每个串可以进行取反操作也可以不取反，问最后最大值和最小值差的最大值

思路：首位为1的串全部置反，首位为0的不管，然后根据字符串排序，答案只会是第一个置反和第二个的差

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
#define maxn 10010
string str[maxn];
LL bit[62];
int n,k;
void init(){bit[0]=1;for(int i=1;i<62;i++) bit[i]=bit[i-1]*2;
}
LL num(string s){LL ans=0;for(int i=0;i<k;i++) ans+=bit[k-1-i]*(s[i]-'0');return ans;
}
LL snum(string s){LL ans=0;for(int i=0;i<k;i++) ans+=bit[k-1-i]*(1-(s[i]-'0'));return ans;
}
int main(){int T; cin>>T; int cas=0; init();while(T--){cin>>n>>k;for(int i=0;i<n;i++){cin>>str[i];if(str[i][0]=='1'){for(int j=0;j<str[i].size();j++)if(str[i][j]=='1') str[i][j]='0';else str[i][j]='1';}}sort(str,str+n);LL ans=snum(str[0])-num(str[1]);if(n==1) ans=0;printf("Case #%d: %lld\n",++cas,ans);}return 0;
}

E. Elegant String

click here

J. Justice String

click here

这篇关于2014 Beijing Invitational的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---