吐槽:
1. 这场比赛完全是败给网络了....
2. 结果和代码明天再说
3. 三天没写题解了... 说明这三天我什么都没做... 好好放松了一下~~
upt : 涨10pt... rank500+ sucks... 500pt写好了
250pt
求A,B(1<=A,B<=4,000,000,000,000)之间所有数的XOR
分析:
还是考虑求0到A和0到B之间的所有数的XOR...
结论的话可以自己推一推, 不难发现f(2^n-1)一定是0.
根据这个重要结论我们可以直接推出结果了... 其实打表找下规律也是可以的额...
但是因为网络卡,我白白浪费了15min不能提交.... 125pt....
1 long long cal(long long x){
2 if(x%4==0) return x;
3 if(x%4==1) return 1;
4 if(x%4==2) return x+1;
5 if(x%4==3) return 0;
6 }
7 class EllysXors{
8 public :long long getXor(long long L, long long R){
9 return cal(R)^cal(L-1);
10 }
11 };
12
500pt
在一个横坐标轴上有若干个垂直的线段.每个线段之间的距离为width[i],现在让你从最左线段的左下角运动到最右线段的右上角.
线段之间的运行速度为speed[i],在线段上垂直运动的速度为walk.线段之间只能从整数坐标点运动到整数坐标点, 每个线段的高度都是一个定值length.
请问最快多久可以到达目的地
分析:
和"黑书"上钓鱼那道题是同一个模型...
在每个线段之间,至少是要水平运动距离width[i]了. 但是竖直方向上应该运动多少呢?
如果竖直方向上的一个单位选择在线段之间运动,那么每向上运动一格,时间就是三角形斜边差除以speed[i]. 否则就是1/walk.
这样的话,我们每次选取最小那个就好了... 应该非常好写... 但是我被网卡到最后... 呜呜呜...
1 #include<iostream>
2 #include<vector>
3 #include<queue>
4 #include<cmath>
5 using namespace std;
6 double L[55];
7 class EllysRivers{
8 public :
9 double getMin(int len,int w,vector <int> width, vector <int> speed){
10 vector <double> W,S;
11 int n = width.size();
12 for(int i=0; i<n ; i++){
13 W.push_back(width[i]);
14 S.push_back(speed[i]);
15 }
16 priority_queue < pair <double , int> ,vector <pair <double, int> >, greater <pair<double,int> > > Q;
17 Q.push( make_pair(1.0/w,n) );
18 double ans = 0;
19 for(int i=0; i<n ;i++){
20 L[i] = 0;
21 Q.push(make_pair((sqrt(W[i]*W[i] + 1) - W[i]) / S[i] , i ));
22 ans += W[i]/S[i];
23 }
24 for(int j=0; j< len;j++){
25 double u = Q.top().first;
26 int id = Q.top().second;
27 ans += u;
28 if(id == n) {
29 continue;
30 }
31 Q.pop();
32 L[id] += 1.0;
33 double t = ( sqrt((L[id]+1)*(L[id]+1) + W[id]*W[id]) - sqrt(L[id]*L[id]+W[id]*W[id]) )/S[id];
34 Q.push(make_pair(t,id));
35 }
36 return ans;
37 }
38 };
39
posted on 2012-05-20 01:59
西月弦 阅读(373)
评论(0) 编辑 收藏 引用 所属分类:
比赛感言