2019ICPC南昌邀请赛题解
The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest
B. Polynomial
Description
定义 f_i=\sum_{i=0}^{n}a_ix^{i}，然后给定f_{0} ~ f_{n}，现在给出 m 次询问，每次询问给定 L 和 R，问你 \sum_{i=L}^{R}f_{i} 是多少
Tutorial
拉格朗日插值裸题，正好复习一下
拉格朗日插值是用来对任意曲线进行多项式拟合的，假设现在给定某一曲线中的任意 n + 1 个点 (x_i,y_i)，那么我就可以使用拉格朗日插值求出该曲线的最高幂次为 n 近似多项式函数，其公式如下：
f(k)=\sum_{i=1}^{n}y_i\prod_{j \neq i}\frac{k-x_j}{x_i-x_j}
那么我们可以使用上式在 O(n^2) 的时间内求出该曲线内的任意一点的近似值
在本题中，显然 f_i 是一个最高幂次为 n 多项式函数，那么我们可以使用给定的 n + 1 个点来求出任意一点的值
但是 O(n^2) 的时间显然不能满足我们的需求，考虑优化
可以发现题目中的 x 是连续的，即 x = 1, 2, 3, ...，那么上式可以写成：
f(k)=\sum_{i=1}^{n}y_i\prod_{j \neq i}\frac{k-j}{i-j}
发现乘积部分的分母其实可以写成阶乘形式，而分子也可以化简
f(k)=\sum_{i=1}^{n}y_i\frac{pre_{i-1} \times suf_{i+1}}{fac_i \times (\pm fac_{n-i})}
其中
fac_i=i!
pre_i=\prod_{j=0}^{i}k-j
suf_i=\prod_{j=i}^{n}k-j
当 n - i 为奇数时 fac_{n-i} 需要取符号
这样我们预处理 fac 或其逆元，pre，suf 即可在 O(n) 时间内求出任意 x 的函数值
但是这样还是不够的，因为如果暴力求解 L ~ R 上的每个 f 时间肯定不够，还需要继续优化
百度告诉我最高幂次为 n 前 i 项和的函数是一个最高幂次为 n + 1 的多项式，那么我们可以利用插值分别求出 L - 1 和 R 处的前缀和做差即可
但是注意 n 个点只能确定最高幂次为 n - 1 的多项式，所以我们要先将 f_{n+1} 插出来再进行前缀和的插值求解
时间复杂度 O(T \cdot n)
AC Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2001;
const ll mod = 9999991;
ll pre[maxn], suf[maxn];
ll f[maxn], fac[maxn], inv[maxn];
ll qpow(ll n, ll m) {
ll res = 1;
while(m) {
if(m & 1) res = res * n % mod;
n = n * n % mod;
m >>= 1;
}
return res;
}
void init() {
fac[0] = 1;
for(int i = 1; i < maxn; ++i) fac[i] = fac[i - 1] * i % mod;
inv[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
for(int i = maxn - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll cal(int x, int s, int t) {
int n = t - s;
x = ((x % mod) + mod) % mod;
pre[0] = ((x - s) + mod) % mod;
suf[n] = ((x - t) % mod + mod) % mod;
for(int i = 1; i <= n; ++i) pre[i] = (pre[i - 1] * (x - (i + s)) % mod + mod) % mod;
for(int i = n - 1; i >= 0; --i) suf[i] = (suf[i + 1] * (x - (i + s)) % mod + mod) % mod;
ll res = 0;
for(int i = 0; i <= n; ++i) {
ll tmp = f[i + s];
if(i != 0) tmp = tmp * pre[i - 1] % mod;
if(i != n) tmp = tmp * suf[i + 1] % mod;
tmp = tmp * inv[i] % mod * inv[n - i] % mod;
if((n - i) & 1) res = (res - tmp + mod) % mod;
else res = (res + tmp) % mod;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
int T; cin >> T;
while(T--) {
int n, m; cin >> n >> m;
for(int i = 0; i <= n; ++i) cin >> f[i];
f[n + 1] = cal(n + 1, 0, n);
for(int i = 1; i <= n + 1; ++i) f[i] = (f[i] + f[i - 1]) % mod;
while(m--) {
int l, r; cin >> l >> r;
cout << ((cal(r, 0, n + 1) - cal(l - 1, 0, n + 1)) % mod + mod) % mod << '\n';
}
}
return 0;
}F. Sequence
Description
定义 f(l,r)=a_{l}\oplus a_{l+1} \oplus a_{l+2} \oplus ... \oplus a_{r}
F(l,r) = f(l,l) \oplus f(l,l+1) \oplus ... \oplus f(l,r) \oplus f(l + 1, l + 1) \oplus f(l + 1, l + 2) \oplus ... \oplus f(l+1, r) \oplus ... \oplus f(r,r)
有两个操作
- 0 x y 令a_x=y
- 1 l r 查询 F(l,r)
Tutorial
单点修改 + 区间查询，应该用线段树或者树状数组都行，考虑维护什么，这里需要用到一个异或的性质
a \oplus a = 0
观察上式发现当区间长度为偶数时答案为 0，否则答案为 L ~ R 区间内下标与 L 奇偶相同的异或和
那么用线段树维护区间内奇偶异或和即可
时间复杂度 O(T \cdot nlog_{2}^{n})
AC Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (root << 1)
#define rs (root << 1 | 1)
const int maxn = 1e6 + 10;
struct Tree {
int l, r;
ll w[2];
} tree[maxn];
void pushup(int root) {
tree[root].w[0] = (tree[ls].w[0] ^ tree[rs].w[0]);
tree[root].w[1] = (tree[ls].w[1] ^ tree[rs].w[1]);
}
void build(int root, int l, int r) {
tree[root] = { l, r, 0, 0 };
if(l == r) {
cin >> tree[root].w[l & 1];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(root);
}
void update(int root, int pos, int w) {
if(tree[root].l == pos && tree[root].r == pos) {
tree[root].w[pos & 1] = w;
return;
}
int mid = (tree[root].l + tree[root].r) >> 1;
if(pos <= mid) update(ls, pos, w);
else update(rs, pos, w);
pushup(root);
}
ll query(int root, int l, int r, int k) {
if(l <= tree[root].l && tree[root].r <= r) return tree[root].w[k];
int mid = (tree[root].l + tree[root].r) >> 1;
if(r <= mid) return query(ls, l, r, k);
else if(l > mid) return query(rs, l, r, k);
else return (query(ls, l, mid, k) ^ query(rs, mid + 1, r, k));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
for(int cas = 1; cas <= T; ++cas) {
int n, m;
cin >> n >> m;
build(1, 1, n);
cout << "Case #" << cas << ": \n";
while(m--) {
int op, x, y;
cin >> op >> x >> y;
if(!op) update(1, x, y);
else {
if((y - x) & 1) cout << 0 << '\n';
else cout << query(1, x, y, x & 1) << '\n';
}
}
}
return 0;
}G. Winner
Description
有 n 个人进行比赛，一共比三轮，每轮每个人有一个能力值，能力值大的人可以淘汰能力小的人，m 次询问，每次问你第 x 个人在自己安排比赛次序的情况下是否有可能胜出
Tutorial
每轮都对所有人按能力值排序，将能力大的人向能力小的人连一条边，然后用 Tarjan 算法进行缩点，入度为 0 的强联通分量中的人可以获胜
注意入度为 0 的强联通分量一定包含三种模式中能力值最大的三个人，因为在缩点前他们的入度为 0
时间复杂度 O(n + m)
AC Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
pair<int, int> p[4][maxn];
struct Edge {
int to, next;
} edge[maxn];
int head[maxn], tot;
int Low[maxn], DFN[maxn], Stack[maxn];
int Index, top;
int scc;
bool Instack[maxn];
int a, b, c;
vector<int> vv, vvv[maxn];
bool succ[maxn];
void addedge(int u, int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void Tarjan(int u) {
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for(int i = head[u]; i != -1; i = edge[i].next) {
v = edge[i].to;
if(!DFN[v]) {
Tarjan(v);
if(Low[u] > Low[v]) Low[u] = Low[v];
}
else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v];
}
if(Low[u] == DFN[u]) {
scc++;
do {
v = Stack[--top];
if(v == a || v == b || v == c) vv.push_back(scc);
Instack[v] = false;
vvv[scc].push_back(v);
} while(v != u);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= 3; ++i) {
for(int j = 1; j <= n; ++j) {
int x;
cin >> x;
p[i][j] = { x, j };
}
sort(p[i] + 1, p[i] + n + 1);
if(!a) a = p[i][n].second;
else if(!b) b = p[i][n].second;
else c = p[i][n].second;
}
memset(head, -1, sizeof(head));
for(int i = 1; i <= 3; ++i) {
for(int j = n; j >= 2; --j) {
addedge(p[i][j].second, p[i][j - 1].second);
}
}
for(int i = 1; i <= n; ++i) {
if(!DFN[i]) Tarjan(i);
}
for(int i = 0; i < vv.size(); ++i) {
for(int j = 0; j < vvv[vv[i]].size(); ++j) {
succ[vvv[vv[i]][j]] = true;
}
}
while(m--) {
int x;
cin >> x;
cout << (succ[x] ? "YES" : "NO") << '\n';
}
return 0;
}J. Prefix
Description
定义字母 ch 的难度值为 d_{ch}，字符串 str 的难度 D(str) 为 \prod_{i=1}^{|str|}d_{str_i} \bmod m，给定 n 个字符串，问这些字符串的前缀构成集合 P，问你对于第 i 个 字符串 s，P 中有多少个前缀 p 满足：
- p 是 s 的前缀
- D(p) > D(s)
Tutorial
用 map 记录一下每个前缀在 P 中出现的次数，对于每一个 s 的前缀判断其难度是否大于 s 即可
时间复杂度 O(\sum|str| \cdot log_{2}^{\sum|str|})
AC Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int a[26];
ll b[maxn];
string s[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
ll m;
cin >> n >> m;
for(int i = 0; i < 26; ++i) {
cin >> a[i];
a[i] %= m;
}
map<string, int> mp;
for(int i = 1; i <= n; ++i) {
cin >> s[i];
int len = s[i].length();
string p = "";
b[i] = 1;
for(int j = 0; j < len; ++j) {
b[i] = b[i] * a[s[i][j] - 'a'] % m;
p += s[i][j];
++mp[p];
}
}
for(int i = 1; i <= n; ++i) {
int res = 0, len = s[i].length();
string p = "";
ll tmp = 1;
for(int j = 0; j < len; ++j) {
p += s[i][j];
tmp = tmp * a[s[i][j] - 'a'] % m;
if(tmp > b[i]) res += mp[p];
}
cout << res << ' ';
}
return 0;
}K. A Good Game
Description
给定长度为 n 的数列 a 和 m 个区间 [L,R]，让你将这些区间排序，使得 sum=\sum_{i=1}^{m}i \sum_{j=L_{i}}^{R_{i}}a_{j} 最大
Tutorial
求出前缀和后用差分算出区间和，排序后求和即可
时间复杂度 O(n)
AC Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll sum[maxn];
ll a[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T--) {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
ll x;
cin >> x;
sum[i] = sum[i - 1] + x;
}
for(int i = 1; i <= m; ++i) {
int l, r;
cin >> l >> r;
a[i] = sum[r] - sum[l - 1];
}
sort(a + 1, a + m + 1);
ll res = 0;
for(int i = 1; i <= m; ++i) {
res += a[i] * i;
}
cout << res << '\n';
}
return 0;
}