A 动物世界
给出序列
输出这个最大值。
场上写了一个数据分治,成功卡过去了
考虑按
最坏复杂度也是
const int MAXN = 2e5 + 10;
const int MAXVAL = 1e6 + 10;
int n, arr[MAXN], mxval[MAXVAL], ans;
bool cnt[MAXVAL];
int main() {
IO::read(n);
rep(i, 1, n) IO::read(arr[i]), cnt[arr[i]] |= true;
sort(arr + 1, arr + n + 1); int m = unique(arr + 1, arr + n + 1) - arr - 1;
rep(i, 1, MAXVAL - 1) mxval[i] = cnt[i] ? i : mxval[i - 1];
rep(i, 1, m) {
for (int j = arr[i]; j <= MAXVAL - 1; j += arr[i]) {
if (mxval[min(j + arr[i] - 1, MAXVAL - 1)] >= arr[i]) ans = max(ans, mxval[min(j + arr[i] - 1, MAXVAL - 1)] % arr[i]);
}
}
printf("%d\n", ans);
return 0;
}
B 走进科学
有
发现任意一次坐标均不会改变任意车与任意车的相对位置。
因此如果我们忽略标号,会发现各车坐标关于时间是若干条斜率为
二分值。
发现将斜率为
假设二分的值是
即
由于值域很大,只能 lower_bound
一下求出
时间复杂度
还有更优的做法。
如果我们仍然忽略序号,碰撞本质就是交换序号。仅仅考虑一个标记:有标记的那个车就是这个时刻
考察一辆向左的车的碰撞过程:与左边第一辆向右的车交换;与右边第一辆向左的车交换;与左边第二辆向右的车交换;与右边第二辆向左的车交换
因此,从某种角度来看,标记访问过的车的下标,是连续的。(具体而言,如果我们单独考虑向左的车构成的下标,和向右的车构成的下标集合,那么标记访问的会是在向右的车中
这启发我们,如果我们知道一共交换了多少次,就能求出最后一次交换是哪两辆车的碰撞,进而检查能否在
所以二分交换了多少次即可。
typedef long double db;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 10;
int n, q, val[MAXN], pos[2][MAXN], D[2][MAXN], cnt[2];
pii arr[MAXN];
char str[MAXN];
bool chk(int x, int flg, int k, int t) {
if (!k) return true;
int lp, rp;
if (flg && (k & 1)) {
if (pos[0][x] - k / 2 < 1 || pos[1][x] + k / 2 > cnt[1]) return false;
lp = pos[0][x] - k / 2;
rp = pos[1][x] + k / 2;
} else if (flg && !(k & 1)) {
if (pos[0][x] - k / 2 + 1 < 1 || pos[1][x] + k / 2 > cnt[1]) return false;
lp = pos[0][x] - k / 2 + 1;
rp = pos[1][x] + k / 2;
} else if (!flg && (k & 1)) {
if (pos[1][x] + k / 2 + 1 > cnt[1] || pos[0][x] - k / 2 < 1) return false;
rp = pos[1][x] + k / 2 + 1;
lp = pos[0][x] - k / 2;
} else {
if (pos[1][x] + k / 2 > cnt[1] || pos[0][x] - k / 2 < 1) return false;
rp = pos[1][x] + k / 2;
lp = pos[0][x] - k / 2;
}
int tt = (D[1][rp] - D[0][lp]);
return tt <= t * 2;
}
int main() {
IO::read(n), IO::read(q);
rep(i, 1, n) {
IO::read(arr[i].first), arr[i].second = i, val[i] = arr[i].first;
}
sort(arr + 1, arr + n + 1);
scanf("%s", str + 1);
rep(i, 1, n) {
D[str[arr[i].second] == 'L'][++cnt[str[arr[i].second] == 'L']] = arr[i].first;
pos[0][arr[i].second] = cnt[0], pos[1][arr[i].second] = cnt[1];
}
rep(i, 1, q) {
int x, t;
IO::read(x), IO::read(t);
int l = 0, r = n, res;
while (l <= r) {
int mid = (l + r) / 2;
if (chk(x, str[x] == 'L', mid, t)) res = mid, l = mid + 1;
else r = mid - 1;
}
int ans;
int tmp = str[x] == 'L';
if (str[x] == 'L' && (res & 1)) {
ans = D[0][pos[0][x] - res / 2] + t;
} else if (str[x] == 'L' && !(res & 1)) {
ans = D[1][pos[1][x] + res / 2] - t;
} else if (str[x] == 'R' && (res & 1)) {
ans = D[1][pos[1][x] + res / 2 + 1] - t;
} else {
ans = D[0][pos[0][x] - res / 2] + t;
}
printf("%d\n", abs(ans));
}
return 0;
}
总结
A 写了个假的(事实上也不是很假)算法过了还是挺幸运的。不过标算也挺显然的(
B 和正解就差一步,已经考虑到了一个车忽略序号只考虑标记那个地步,并且手玩了一下((