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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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];
}
};