srm 543

250

---

求$A, B(A,B\le 4\times 10^{12})$之间所有数的$XOR$

Solution

转换成$1\sim B$异或和异或$1\sim A$异或和，容易发现当$n\ge 2时，1~\sim 2^n-1异或和为0$，$0,1,2,3$特判即可

Code

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
LL gao(LL x) {
    LL t = 0;
    for (int i = 40; i >= 0; --i) {
        LL p = 1ll << i;
        if (x == 3 || !x) return t;
        if (x == 2) return t + 3;
        if (x == 1) return t + 1;
        if (p <= x) {
            if ((x - p + 1) & 1)    t += p;
            x ^= p;
        }
    }
    return t;
}
struct EllysXors {
    long long getXor(long long L, long long R) {
        return gao(R) ^ gao(L - 1);
    }
};

500

---

Description

在一个横坐标轴上有若干个垂直的线段.每个线段之间的距离为$width[i]$,现在让你从最左线段的左下角运动到最右线段的右上角
线段之间的运行速度为speed[i],在线段上垂直运动的速度为$walk$线段之间只能从整数坐标点运动到整数坐标点, 每个线段的高度都是一个定值$length$
请问最快多久可以到达目的地
$length\le 100000$

Solution

很容易想到dp,$dp[i][j]$表示过了前$i$个线段，当前在$j$的答案，暴力转移复杂度爆炸，容易发现，在每个线段的答案沿高度是单调的，转移时维护上一次转移的位置即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const double inf = 1e20;
double dp[2][100005];
struct EllysRivers {
    double getMin(int length, int walk, vector <int> width, vector <int> speed) {
        int n = width.size();
        for (int i = 0; i <= length; ++i)   dp[0][i] = (double)i / walk;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length; ++j)   dp[i & 1][j] = inf;
            int last = 0;
            for (int j = 0; j <= length; ++j)
                for (int k = last; k <= j; ++k) {
                    double t =  dp[(i - 1) & 1][k] + hypot(width[i - 1], j - k) / speed[i - 1];
                    if (t > dp[i & 1][j])   break;
                    dp[i & 1][j] = t;
                    last = k;
                }
        }
        return dp[n & 1][length];
    }
};