SRM 543 DIV2

比赛后才做的

250

简单题

View Code

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
using namespace std;

class EllysTSP {
    public:
    int getMax(string places);
    

};
int EllysTSP::getMax(string places) {
    int i,j,k,len;
    len=places.size();
    for(i=j=k=0;i<len;i++)
        if(places[i]=='V')
            k++;
        else
            j++;
    if(abs(j-k)<=1)
        return j+k;
    if(!j||!k)
        return 1;
    return min(j,k)*2+1;
}

500

给定n,m求n和m之间所有数异或之后的值X，

n,m较大,模拟肯定超时

由异或的性质可知，X可有1~n的异或值异或1~m的异或值可得.

1,10,11,100,101,110,111,1000

先看个数,1,0交替出现,周期为2,再看十位1,1, 0,0周期为4，以此类推，就可以求出1~n的异或值

在网上看到居然还可以直接找规律，只有4种情况。。。。

View Code

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
using namespace std;

class EllysXors {
    public:
    long long getXor(long long L, long long R);
    long long Cal(long long n);

};
long long EllysXors::Cal(long long n){
    long long i,j,k=0;
    if(n%4==1||n%4==2)
        k=1;
    for(i=2;i<=n;i<<=1)
    {
        j=(n-i+1)%(i<<1);
        if(j<=i&&j&1)
            k=k|i;
    }
    return k;
}
long long EllysXors::getXor(long long L, long long R) {
    long long i,j;
    i= Cal(L-1);
    j= Cal(R);
    return i^j;
}

1000

过河问题。

给定三条河,在三条河的游泳速度(任意方向)，三条河的宽,岸长(只能竖直移动),步行速度，求过三条河从左下角到达右上角最少所需时间

一开始以为是数学题，觉得不会做，直接看别人的，三分搜索，最后还靠卡循环次数60才过的，题目的精度要求太变态了

View Code

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
using namespace std;

class EllysThreeRivers {
    public:
    double Solve(int i, double length, double walk, vector <int> width, vector <int> swim)
    {
            if(i==3)
                return length/walk;
            double t1,t2,low=0,high=length,mid1,mid2;
            for(int k=0;k<60;k++)
            {
                mid1=(low+low+high)/3;
                mid2=(low+high+high)/3;
                t1=Solve(i+1, length-mid1, walk, width, swim)
                +hypot(mid1,width[i]*1.0)/swim[i];
                t2=Solve(i+1, length-mid2, walk, width, swim)
                +hypot(mid2,width[i]*1.0)/swim[i];
                if(t1<t2)
                    high=mid2;
                else
                    low=mid1;
            }
            return min(t1,t2);
    };
    double getMin(int length, int walk, vector <int> width, vector <int> swim)
    {
        return Solve(0, length*1.0, 1.0*walk, width , swim) ;
    };
    

};