[LOJ#522]「LibreOJ β Round #3」绯色 IOI(危机)
试题描述
IOI 的比赛开始了。Jsp 和 Rlc 坐在一个角落,这时他们听到了一个异样的声音 ……
接着他们发现自己收到了一封电子邮件:
吃惊的 Jsp 和 Rlc 开始了调(报)查(警)。之后,这些话被证实了。并且两人还发现了另一个性质:
经过进一步研究,Rlc 发现最为安全的方法是这样:首先选出若干个关键炸弹安装监测器,然后慢慢拆除。
因为炸弹的某些特性,安装监测器的炸弹必须组成一个有序序列 a1,a2,...,an,且满足:
- ai 互不相同,且为 [1,N] 中的整数。
- ai 能直接或间接引爆 ai+1。
Rlc 设计了一个衡量监测器安装方案的安全程度的方法:
首先可以测出每个炸弹的特征值 vi。
那么监测器安装方案的安全程度为:∑i=1~n−1F(va_i,va_(i+1)),其中 F(x,y)=(x⊕y+xy) mod 998244353(⊕ 表示二进制按位异或,本题中按位异或的优先级高于乘法和加法)。
现在她想知道,对于 [1,N] 中的每个整数 i,如果她安装监测器的最后一个炸弹是 i(即 an=i),安全程度最大是多少。
请特别注意,题面中大写的 N 表示炸弹总数,小写 n 表示上下文中的序列长度,请勿混淆。
输入
第二行 N 个整数 X1,X2,...,XN,表示炸弹的坐标。
第三行 N 个整数 R1,R2,...,RN,表示炸弹的爆炸半径。
第四行 N 个整数 v1,v2,...,vN,表示炸弹的特征值。
输出
输入示例
6 -3 -2 0 2 3 4 0 1 4 1 0 1 4 1 3 4 2 0
输出示例
19 5 0 19 33 3
数据规模及约定
对于所有数据,1≤N≤3×105,0≤vi<998244353,0≤Ri≤1018,∣Xi∣≤1018。
题解
这道题题意如此长,其实是想方设法创造条件让暴力 AC。。。
首先根据性质 1,它是个 DAG,自然会想到 dp。
然后根据性质 1&3,因为两个炸弹不能互相炸到对方,假设炸弹 A 的范围包含了 B,那么 B 的半径(记做 B_r)一定小于 A_r 的一半,以此类推,会发现对于任意两个炸弹 u, v,如果 u 直接炸到了 v,那么从 v 向 u 连边,那么这个图的最长路径长度不会超过 log max{ Ri }。
发现直接连边数太多了,过不了(大概有 45 分),那么我们直连哪些直接炸到的并且离得最近的边(这个可以从左到右、从右到左扫一遍分别维护 Xi + Ri 和 Xi - Ri 递减和递增的单调栈),这样边数就是 O(n) 的了(证明比较简单,详见 LOJ 官方题解)。
dp 转移的时候暴力沿着路径 dfs 一下,沿途中遇到所有的 dp 值都用来更新一下就好了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define LL long long LL read() { LL x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f; } #define maxn 300010 #define maxm 600010 #define LL long long #define hzt1 998244353 int n, m, head[maxn], nxt[maxm], to[maxm], perm[maxn]; LL X[maxn], R[maxn], v[maxn]; void AddEdge(int a, int b) { to[++m] = b; nxt[m] = head[a]; head[a] = m; return ; } int S[maxn], top; LL f[maxn]; void dfs(int st, int u); LL search(int u); void dfs(int st, int u) { // printf("u: %d ", u); f[st] = max(f[st], search(u) + ((v[st] ^ v[u]) + v[st] * v[u]) % hzt1); for(int e = head[u]; e; e = nxt[e]) dfs(st, to[e]); return ; } LL search(int u) { if(f[u] >= 0) return f[u]; f[u] = 0; for(int e = head[u]; e; e = nxt[e]) dfs(u, to[e]); return f[u]; } bool cmp(int a, int b) { return X[a] < X[b]; } int main() { n = read(); for(int i = 1; i <= n; i++) X[i] = read(), perm[i] = i; for(int i = 1; i <= n; i++) R[i] = read(); for(int i = 1; i <= n; i++) v[i] = read(); sort(perm + 1, perm + n + 1, cmp); // for(int i = 1; i <= n; i++) printf("%lld %lld [%d] ", X[perm[i]], R[perm[i]], perm[i]); for(int i = 1; i <= n; i++) { while(top && X[S[top]] + R[S[top]] < X[perm[i]]) top--; if(top) AddEdge(perm[i], S[top]); // , printf("type1: %d -> %d ", perm[i], S[top]); while(top && X[S[top]] + R[S[top]] <= X[perm[i]] + R[perm[i]]) top--; S[++top] = perm[i]; } top = 0; for(int i = n; i; i--) { while(top && X[S[top]] - R[S[top]] > X[perm[i]]) top--; if(top) AddEdge(perm[i], S[top]); // , printf("type2: %d -> %d ", perm[i], S[top]); while(top && X[S[top]] - R[S[top]] >= X[perm[i]] - R[perm[i]]) top--; S[++top] = perm[i]; } memset(f, -1, sizeof(f)); for(int i = 1; i <= n; i++) printf("%lld ", search(i)); return 0; }
我还是第一次写代码让两个函数互相调用。。。