算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

吐槽:

   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 <doubleint> >, 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)  编辑 收藏 引用 所属分类: 比赛感言

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理