「csp校内训练 2019-11-04」解题报告
T1、腿部挂件
\(Description\)：
Jim 是一个热爱打游戏的小伙子，可惜他的游戏水平不太行，以至于经常在游戏里被别人欺负。而且 Jim 不仅游戏玩的菜，他还很爱喷人，但是由于自己的垃圾操作，他又喷不过别人。为了改善这种局面，Jim 决定成为一个腿部挂件 (俗称抱大腿)。
已知现在有 \(N\) 个选手可供 Jim 选择，每位选手的能力值为 \(a_i\)，\(N\) 位选手不一定每位选手都有时间陪 Jim 玩游戏而且 Jim 的状态也时好时坏；
所以 Jim 有 \(Q\) 个询问，每个询问是 \(3\) 个数 \(X、L、R\)，求第 \(L\) 个人到第 \(R\) 个人这 \(R-L+1\) 个人中与 Jim 配合后的能力值最大是多少，Jim 与第 \(i\) 位选手配合后的能力值为 \(a_i\) 与 \(X\) 进行异或运算 (Xor)。
\(1 \leq N \leq 200000, 1 \leq Q \leq 200000\)
\(0 \leq a_i \leq 10^9\)
\(0 \leq X \leq 10^9,0 \leq L \leq R < N\)
注意：序列从 \(0\) 开始。
\(Solution\)：
可持久化 \(trie\) 树。
本题不强制在线，可以离线处理，在 \(trie\) 中记录每个节点最后出现的位置即可。
时间复杂度 \(O(n \log_2 a_i)\)。
\(Source\)：
离线：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 2e5 + 5;
struct info {
int l, r, x, id;
inline bool operator < (const info &y) const {
return this->r < y.r;
}
} b[N];
int a[N], res[N];
struct trie {
int c[N * 31][2], last[N * 31], tot, rt;
void insert(const int k, const int tim) {
int p = rt;
for (int i = 30; i >= 0; --i) {
int t = (k >> i) & 1;
if (!c[p][t])
c[p][t] = ++tot;
last[c[p][t]] = tim;
p = c[p][t];
}
}
int query_max(const int k, const int tim) {
int p = rt, ret = 0;
for (int i = 30; i >= 0; --i) {
int t = (k >> i) & 1;
if (last[c[p][t ^ 1]] >= tim) {
ret |= (1 << i);
p = c[p][t ^ 1];
} else {
p = c[p][t];
}
}
return ret;
}
} T;
int n, q;
int main() {
//freopen("in", "r", stdin);
freopen("hugclose.in", "r", stdin);
freopen("hugclose.out", "w", stdout);
n = in(), q = in();
for (int i = 1; i <= n; ++i)
a[i] = in();
for (int i = 1; i <= q; ++i)
b[i].x = in(), b[i].l = in() + 1, b[i].r = in() + 1, b[i].id = i;
std::sort(b + 1, b + 1 + q);
for (int i = 1, pos = 1; i <= q; ++i) {
for (; pos <= b[i].r; T.insert(a[pos], pos), ++pos);
res[b[i].id] = T.query_max(b[i].x, b[i].l);
}
for (int i = 1; i <= q; ++i)
printf("%d\n", res[i]);
return 0;
}在线：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 2e5 + 5;
struct persistable_trie {
int c[N * 31][2], rt[N];
int tot;
int insert(int pre, int k) {
int p, ret;
p = ret = ++tot;
for (int i = 30; i >= 0; --i) {
int t = (k >> i) & 1;
c[p][t ^ 1] = c[pre][t ^ 1];
c[p][t] = ++tot;
p = c[p][t], pre = c[pre][t];
}
return ret;
}
int query_max(int pre, int p, int k) {
int ret = 0;
for (int i = 30; i >= 0; --i) {
int t = (k >> i) & 1;
if (c[p][t ^ 1] ^ c[pre][t ^ 1]) {
ret |= (1 << i);
p = c[p][t ^ 1], pre = c[pre][t ^ 1];
} else {
p = c[p][t], pre = c[pre][t];
}
}
return ret;
}
} T;
int n, q;
int main() {
//freopen("in", "r", stdin);
freopen("hugclose.in", "r", stdin);
freopen("hugclose.out", "w", stdout);
n = in(), q = in();
for (int i = 1; i <= n; ++i)
T.rt[i] = T.insert(T.rt[i - 1], in());
while (q--) {
int x = in(), l = in(), r = in();
printf("%d\n", T.query_max(T.rt[l], T.rt[r + 1], x));
}
return 0;
}T2、走夜路
\(Description\)：
Jim 是一个胆小的男生，可是每天他都要学习到很晚才能回家，而且他回家的路上没有路灯。
Jim 非常怕黑，万幸的是他还有一个手电筒可以用，我们设手电筒的电量上限为 \(T\)。
在 Jim 回家的路上有 \(N+1\) 个充电站， \(0\) 是起点 \(N\) 是终点，Jim 每走一个单位距离消耗 \(1\) 个单位的电量。
给出每个充电站到下一个充电站的距离 \(D\)，以及冲单位电量的花费 \(P\) ，求整个旅途的最少花费。
如果 Jim 无法保证全程手电筒都亮着输出 \(-1\)。
\(N \leq 500000\)
\(2 \leq N \leq 500000 , 1 \leq T \leq 10^9\)
\(1 \leq d_i, p_i \leq 1000000\)
\(Solution\)：
当且仅当两个充电站之间的距离超过 \(T\)，输出 \(-1\)。
贪心地想，如果当前在 \(i\)，那么肯定要走到之后第一个不大于 \(p_i\) 的地方再充电；
若没有这样的充电站，那么就在 \(i\) 充足够的电量 (注意要使到终点的剩余电量为 \(0\))。
\(Source\)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 5e5 + 5;
int n, T, p[N], fr[N];
long long d[N];
void prep() {
static int sta[N], tp;
sta[0] = n + 1;
for (int i = n; i; --i) {
for (; tp && p[sta[tp]] > p[i]; --tp);
fr[i] = sta[tp];
sta[++tp] = i;
}
}
long long work() {
long long ret = 0, rest = 0;
for (int i = 1; i <= n; ) {
if (d[fr[i]] - d[i] > T) {
ret += std::max(0ll, std::min(1ll * T, d[n + 1] - d[i]) - rest) * p[i];
chk_max(rest, std::min(1ll * T, d[n + 1] - d[i]));
if (d[i + 1] - d[i] > T)
return -1;
rest -= d[i + 1] - d[i];
++i;
} else {
ret += std::max(0ll, d[fr[i]] - d[i] - rest) * p[i];
chk_max(rest, d[fr[i]] - d[i]);
rest -= d[fr[i]] - d[i];
i = fr[i];
}
}
return ret;
}
int main() {
//freopen("in", "r", stdin);
freopen("wayhome.in", "r", stdin);
freopen("wayhome.out", "w", stdout);
n = in(), T = in();
for (int i = 1; i <= n; ++i)
d[i + 1] = d[i] + in(), p[i] = in();
prep();
printf("%lld\n", work());
return 0;
}T3、宝石专家
\(Description\)：
Jim是一位宝石收藏品行家,
在他的收藏室里保存着许多珍贵的宝石，磷叶石、钻石、摩根石、透绿柱石…………
已知 Jim 有 \(n\) 个宝石，现在他将这 \(n\) 个宝石从 \(1\) 到 \(n\) 排开编号从 \(1\) 到 \(n\) 。
Jim 发现他所有的宝石中竟然有不少是完全相同的的，我们规定每个宝石都有一个特征值 \(a_i\) ，当两个宝石特征值相等时及认为两个宝石相同。
Jim 发现两个相同的宝石离得越接近越明显。
Jim 现在有 \(m\) 个问题，他想问你在编号 \(l\) 到 \(r\) 这一区间里的所有宝石中，两个相同宝石的最近距离是多少(两个宝石的距离是它们编号的绝对值之差)。
保证 \(l < r\)，对于 \(a_x\) 和 \(a_y\) 若 \(a_x=a_y\) 它们的距离为 \(|x-y|\) 。
\(1 \leq n,m \leq 2 \times 10^5\)
\(-10^9 \leq a_i \leq 10^9\)
\(1 \leq l_j \leq r_j \leq n\)
\(Solution\)：
先将询问离线处理，按右端点升序排序。
对于某种特征的宝石在序列中的位置 \(p_1, p_2, p_3 \dots p_k\)；
显然答案只能在 \(p_{i + 1} - p_i \ (i < k)\) 中出现。
那么考虑两个相同特征的宝石 \(x, y\)，设 \(x\) 是 \(y\) 之前第一个与其相同的；
当且仅当 \(r_j \geq y\) 且 \(l_j \leq x\) 时，\(y - x\) 会影响询问 \(j\)。
右端点已经处理好，保证可以找出所有在 \(r_j\) 之前的宝石。
左端点用线段树维护就行，写法比较多，我把每一个 \(y - x\) 在线段树中 \(x\) 位置单点更新，查询区间查即可。
\(Source\)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 2e5 + 5;
struct info {
int l, r, id;
inline bool operator < (const info &y) const {
return this->r < y.r;
}
} b[N];
int a[N], res[N], last[N];
int n, m, nn;
struct segment_tree {
int min[N << 2], M;
void init() {
memset(min, -1, sizeof(min));
for (M = 1; M - 2 < n; M <<= 1);
}
void modify(int p, int k) {
for (p += M; p; p >>= 1)
if (!~min[p])
min[p] = k;
else
chk_min(min[p], k);
}
int query(int l, int r) {
int ret = -1;
for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if ((~l & 1) && ~min[l ^ 1]) {
if (!~ret)
ret = min[l ^ 1];
else
chk_min(ret, min[l ^ 1]);
}
if ((r & 1) && ~min[r ^ 1]) {
if (!~ret)
ret = min[r ^ 1];
else
chk_min(ret, min[r ^ 1]);
}
}
return ret;
}
} T;
void prep() {
static int tmp[N];
memcpy(tmp, a, sizeof(a));
std::sort(tmp + 1, tmp + 1 + n);
nn = std::unique(tmp + 1, tmp + 1 + n) - tmp - 1;
for (int i = 1; i <= n; ++i)
a[i] = std::lower_bound(tmp + 1, tmp + 1 + nn, a[i]) - tmp;
T.init();
std::sort(b + 1, b + 1 + m);
}
int main() {
//freopen("in", "r", stdin);
freopen("jewel.in", "r", stdin);
freopen("jewel.out", "w", stdout);
n = in(), m = in();
for (int i = 1; i <= n; ++i)
a[i] = in();
for (int i = 1; i <= m; ++i)
b[i].l = in(), b[i].r = in(), b[i].id = i;
prep();
for (int i = 1, pos = 1; i <= m; ++i) {
for (; pos <= b[i].r; ++pos) {
if (last[a[pos]])
T.modify(last[a[pos]], pos - last[a[pos]]);
last[a[pos]] = pos;
}
res[b[i].id] = T.query(b[i].l, b[i].r);
}
for (int i = 1; i <= m; ++i)
printf("%d\n", res[i]);
return 0;
}