(旧存档) 2019年徐州ICPC网络赛总结
A. Who is better?
题意： 裸的扩展中国剩余定理 + 斐波那契博弈。
斐波那契博弈: 有一堆个数为n的石子，游戏双方轮流取石子，满足：
- 先手不能在第一次把所有的石子取完；
- 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。
约定取走最后一个石子的人为赢家，先手胜当且仅当n不是Fibonacci数。换句话说，必败态构成Fibonacci数列。
范围： $ 1\le k \le 10 ,1 \le n \le 10^{15}$
解法： 扩展中国剩余定理、斐波那契博弈。注意范围会爆long long，应开__int128。
代码：
#include <cstdio>
#include <set>
using namespace std;
typedef __int128 ll;
const int N = 100;
ll a[N], b[N], f[N];
template<class T1, class T2>
inline T2 mod(T1 a, T2 b) {
return (a % b + b) % b;
}
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll gcd = ex_gcd(b, a % b, y, x);
y -= (a / b) * x;
return gcd;
}
inline bool ex_gcd(ll a, ll b, ll c, ll &x, ll &y, ll &gcd) {
gcd = ex_gcd(a, b, x, y);
if (gcd == 0 || c % gcd) return false;
x = mod(c / gcd * x, b / gcd);
y = c - a * x;
return true;
}
inline bool merge(ll a1, ll b1, ll &a2, ll &b2) {
ll x, y, gcd, d = a1 - a2;
if (!ex_gcd(b1, b2, d, x, y, gcd)) return false;
b2 = b2 * (b1 / gcd);
a2 = mod(a1 - x * b1, b2);
return true;
}
inline bool solve(ll *a, ll *b, int n, ll &ans) {
for (int i = 1; i < n; ++i) {
if (!merge(a[i - 1], b[i - 1], a[i], b[i])) return false;
}
ans = a[n - 1];
return true;
}
int main() {
int n;
set<ll> s;
f[0] = f[1] = 1, s.emplace(1);
for (int i = 2; i < N; ++i) {
f[i] = f[i - 1] + f[i - 2];
s.emplace(f[i]);
}
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
long long x, y;
scanf("%lld%lld", &x, &y);
b[i] = x, a[i] = y;
}
ll ans = 0;
if (solve(a, b, n, ans))
puts(s.count(ans) ? "Lbnb!": "Zgxnb!");
else
puts("Tankernb!");
return 0;
}
B. so easy
题意： 在数组上有连续的$n$个点，标号为$1$到$n$，有两种操作:
- 将点 $x$ 设为不可用
- 询问在点 $x$ 之后的第一个可用的点
范围： $1\le q \le 10 ^{6} ,1 \le x \le n \le 10^{9}$
解法一： 暴力即可 (1161ms)
代码一：
#include <unordered_set>
#include <cstdio>
using namespace std;
int main() {
int n, q;
scanf("%d%d", &n, &q);
unordered_set<int> s;
while (q--) {
int op, x;
scanf("%d%d", &op, &x);
if (op == 1) {
s.emplace(x);
} else {
while (s.find(x) != s.end()) {
++x;
}
printf("%d\n", x);
}
}
return 0;
}
解法二： 使用unordered_map并查集 (825ms)
代码二：
#include <cstdio>
#include <unordered_map>
using namespace std;
unordered_map<int, int> fa;
int find(int x) {
return fa.find(x) == fa.end() ? x : fa[x] = find(fa[x]);
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
while (q--) {
int op, x;
scanf("%d%d", &op, &x);
if (op == 1) {
fa[x] = x + 1;
} else {
printf("%d\n", find(x));
}
}
return 0;
}
C.Buy Watermelon
题意： 把一个数 $x$ 分为两份，并且这两个数都是2的倍数
范围： $1\le x \le 100$
解法： 注意 $x=2$ 应特判即可
代码：
#include <cstdio>
using namespace std;
int main() {
int n;
scanf("%d", &n);
if (n % 2 || n == 2) {
puts("NO");
} else {
puts("YES");
}
return 0;
}
D.Carneginon
题意： 题意很长，按照要求模拟即可
范围： $1 \le |T| \le 10^{5}, 1\le|S|\le10^{5},1\le q \le1000$
解法： 一般来说，这种题应该用KMP算法来匹配子串，没想到这里用了函数strstr就过了，大水题。
代码：
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
char s[N], t[N];
int main() {
gets(s);
int q, n = strlen(s);
scanf("%d", &q);
getchar();
while (q--) {
gets(t);
int m = strlen(t);
if(n > m){
if(strstr(s, t)) puts("my child!");
else puts("oh, child!");
}else if(n < m){
if(strstr(t, s)) puts("my teacher!");
else puts("senior!");
}else{
if(strcmp(s, t)) puts("friend!");
else puts("jntm!");
}
}
return 0;
}
E. XKC’s basketball team
题意： 给你一串数列 $A_{n}$ 和一个数字 $m$，对于每个 $A_{i}$，找到最右边的满足 $A_{j}\ge A_{i} + m$ 且 $j \ge i$ 的数 , 如果找到这个数，输出 $j - i - 1$，否则输出$-1$。
范围： $1 \le n \le 5*10^{5}, 1\le m\le10^{9},1\le A_{i} \le 10^{9}$
解法一： 注意到数据的范围, 时间复杂度要求大概为 $O(nlogn)$ ，可以使用线段树这种数据结构，由于要找到最右边符合条件的数，优先往右子树找即可。
代码一：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
int a[N], b[N << 2];
void build(int l, int r, int rt = 1) {
if (l == r) {
b[rt] = a[l];
return;
}
int m = (l + r) / 2;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
b[rt] = max(b[rt << 1], b[rt << 1 | 1]);
}
int query(int val, int l, int r, int rt = 1) {
if (l == r) {
return l;
}
int m = (l + r) / 2;
if (b[rt << 1 | 1] >= val) return query(val, m + 1, r, rt << 1 | 1);
else return query(val, l, m, rt << 1);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(1, n);
for (int i = 1; i <= n; ++i) {
int pos = query(a[i] + m, 1, n);
printf("%d", max(pos - i - 1, -1));
putchar(i == n ? '\n' : ' ');
}
return 0;
}
解法二： 考虑到任意一个数 $A_{i}$，如果 $A_{i} \le A_{j}$ 且 $i \le j$ , 那么去掉 $A_{i}$ 对其他位置的答案没有影响。考虑去掉所有这样的 $A_{i}$，将操作后的数组 $A_{i}$ 记作数组 $B_{i}$ ，同时记录 $B_{i}$ 中元素在 $A_{n}$ 中的位置。由于 $B_{i}$ 是有序的，于是可以对每个 $A_{i}$， 在 $B_{n}$ 里二分 $A_{i} + m$ ，就可以 $O(nlogn)$ 得到答案。
代码二：
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
int a[N], b[N], id[N];
int main() {
int n, m, tot = 1;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
b[0] = a[n - 1], id[0] = n - 1;
for (int i = n - 2; i >= 0; --i) {
if (a[i] > b[tot - 1]) {
b[tot] = a[i];
id[tot] = i;
tot++;
}
}
for (int i = 0; i < n; ++i) {
int pos = lower_bound(b, b + tot, a[i] + m) - b;
if (pos == tot) {
printf("%d", -1);
} else {
printf("%d", max(id[pos] - i - 1, -1));
}
putchar(i == n - 1 ? '\n' : ' ');
}
return 0;
}
G.Colorful String
题意： 给你一个字符串 $s$ ，询问 $s$ 中所有的回文串中不同字母个数的和。
范围： $1 \le |s| \le 3*10^{5}$
解法： 用回文自动机求出所有的回文串，使用主席树求出回文串中不同字母个数的和。
代码：
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 3e5 + 5, M = 26;
typedef long long ll;
struct prtree {
int sum[N << 5], lson[N << 5], rson[N << 5], tot_node = 0;
int root[N], last[N], top[M + 'a'], n = 0;
int insert(int last, int x, int l, int r) {
int rt = ++tot_node;
sum[rt] = sum[last] + 1, lson[rt] = lson[last], rson[rt] = rson[last];
if (l < r) {
int mid = (l + r) / 2;
if (x <= mid) lson[rt] = insert(lson[rt], x, l, mid);
else rson[rt] = insert(rson[rt], x, mid + 1, r);
}
return rt;
}
int query(int i, int j, int qr, int l, int r) {
if (r <= qr) return sum[j] - sum[i];
int mid = (l + r) / 2, t = 0;
if (qr <= mid) t += query(lson[i], lson[j], qr, l, mid);
else t += sum[lson[j]] - sum[lson[i]] + query(rson[i], rson[j], qr, mid + 1, r);
return t;
}
int query(int l, int r) {
int ans = query(root[l - 1], root[r], l - 1, 0, n);
return ans;
}
void build(char *s, int len) {
n = len;
for (int i = 1; i <= n; ++i) {
int x = s[i];
last[i] = top[x];
top[x] = i;
}
for (int i = 1; i <= n; ++i) {
root[i] = insert(root[i - 1], last[i], 0, n);
}
}
} t;
struct PAM {
char s[N];
int cnt[N];
int len, last, tot;
struct node {
int len, pos, nxt[M], fail;
int left() { return pos - len + 1; }
int right() { return pos; }
} nd[N];
int get_fail(int x) {
while (s[len - nd[x].len - 1] != s[len]) x = nd[x].fail;
return x;
}
int new_node(int len = 0, int fail = 0) {
nd[tot].len = len, nd[tot].fail = fail, nd[tot].pos = 0;
return tot++;
}
PAM() : len(0), last(0), tot(0) {
new_node(0, 1);
new_node(-1, 0);
s[0] = '$';
}
void insert(char ch) {
ch -= 'a';
s[++len] = ch;
int now = get_fail(last);
if (!nd[now].nxt[ch]) {
int x = new_node(
nd[now].len + 2,
nd[get_fail(nd[now].fail)].nxt[ch]
);
nd[now].nxt[ch] = x;
if (nd[x].len > 1) nd[x].pos = len;
}
last = nd[now].nxt[ch];
++cnt[last];
}
ll solve() {
ll res = len;
for (int i = tot - 1; i; --i) {
cnt[nd[i].fail] += cnt[i];
}
for (int i = 2; i < tot; ++i) {
if (nd[i].pos) {
res += (ll) cnt[i] * t.query(nd[i].left(), nd[i].right());
}
}
return res;
}
};
PAM a;
char s[N];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
t.build(s, n);
for (int i = 1; s[i]; ++i) {
a.insert(s[i]);
}
printf("%lld\n", a.solve());
return 0;
}
I. Query
题意： 给你一个长度为 $n$ 的排列，询问个数有 $m$ 个，每组询问问你在区间 $[l,r]$ 中有多少组整除对。
范围： $1 \le n \le 10^{5},1\le m \le 10^{5}$
解法： 一个典型的二维偏序问题，解法类似 P1972 [SDOI2009]HH的项链。
我们希望得到这类题的普遍解法，于是我们设: $C(x,y,l,r) = {(u, v)|u \in[x, y] \wedge v \in [l, r] \wedge q(u,v)\wedge u\le v}$，其中 $q(u,v)$ 为二元命题。
- 那么: $Ans_{l,r}=|C(1,r,1,r)|-|C(1,l-1,1,r)|$
- 我们记：$S(x,y)=|C(1,x,1,y)|$
- 那么有：$Ans_{l,r}=S(r,r)-S(l-1,r)$，这是一个类似前缀和的结构
- 假设我们记录了所有的询问，我们可以这样求每一个 $Ans_{l,r}$
- 记录所有的询问 $(l,r)$
- 从小到大枚举右端点 $r$ :
- 在 $S(x,r-1)$ 的基础上，更新所有的 $S(x,r)$ （应使用一维数组实现）
- 处理所有右端点为 $r$ 的询问，询问的答案为 $Ans_{l,r}=S(r,r)-S(l-1,r)$
- 输出所有询问的答案
其实不仅对于这类二维偏序问题，对其他二维偏序问题，都可以用类似的方法解决：具体可以看这里：CDQ分治总结
那么对于本题而言， $q(u,v)=u|v$ ，为了 $O(logn)$ 更新 $S(x,y)$ ,需要预处理：
- 记录每个元素出现的位置
- 记录右端点为 $1\le r \le n$ 的所有整除对
在更新 $S$ 数组时，将右端点为 $r$ 的所有整除对的位置对应的位置加 1，然后询问前缀和 $S(r)-S(l-1)$ 即可，使用树状数组维护。
代码：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct query {
int l, id;
query(int l, int id) : l(l), id(id) {}
};
int a[N], pos[N], ans[N], b[N], n;
vector<int> left[N];
vector<query> q[N];
inline int lowbit(int x) { return x & (-x); }
inline void add(int x, int val) {
while (x <= n) {
b[x] += val;
x += lowbit(x);
}
}
inline int sum(int x) {
int val = 0;
while (x > 0) {
val += b[x];
x -= lowbit(x);
}
return val;
}
int main() {
int m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
pos[a[i]] = i;
}
for (int i = 1; i <= n; ++i) {
int val = a[i];
for (int j = val + val; j <= n; j += val) {
auto p = minmax(i, pos[j]);
left[p.second].emplace_back(p.first);
}
}
for (int i = 1; i <= m; ++i) {
int l, r;
scanf("%d%d", &l, &r);
q[r].emplace_back(l, i);
}
for (int i = 1; i <= n; ++i) {
for (int pos : left[i]) add(pos, 1);
for (auto x: q[i]) ans[x.id] = sum(i) - sum(x.l - 1);
}
for (int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}
K. Center
题意： 给你一组点集 $S$ , 问你在该点集中加入多少个点，可以使整个点集 $S$ 呈中心对称。
范围： $ 1 \le |S| \le 1000, (X_{i}, Y_{i})(-10^{6}\le X_{i},Y_{i}\le 10^{6})$
解法： 要使加入的点最少，那么点集的中心点要么是点集 $S$ 中的点， 要么是点集中任意两点 $P, Q$ 的中点 $M$，枚举所有的点 $P$ 和中点 $M$, 选择枚举次数 $cnt$ 最多的点, 最后答案为 $n - cnt$。
代码一： 使用std::map(924ms)
#include <cstdio>
#include <map>
using namespace std;
typedef pair<int, int> point;
const int N = 1e3 + 5;
int x[N], y[N];
int main() {
int n, ans = 1;
scanf("%d", &n);
map<point, int> a;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x[i], &y[i]);
a.emplace(point(x[i] << 1, y[i] << 1), 1);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
point t(x[i] + x[j], y[i] + y[j]);
a[t] += 2;
ans = max(ans, a[t]);
}
}
printf("%d\n", n - ans);
return 0;
}
代码二： 使用std::unordered_map (593ms)
#include <cstdio>
#include <unordered_map>
using namespace std;
typedef pair<int, int> point;
const int N = 1e3 + 5;
int x[N], y[N];
namespace std {
template<>
struct hash<point> {
long long factor = INT32_MAX;
size_t operator()(const point &p) const {
return factor * p.first + p.second;
}
};
}
int main() {
int n, ans = 1;
scanf("%d", &n);
unordered_map<point, int> a;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x[i], &y[i]);
a.emplace(point(x[i] << 1, y[i] << 1), 1);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
point t(x[i] + x[j], y[i] + y[j]);
a[t] += 2;
ans = max(ans, a[t]);
}
}
printf("%d\n", n - ans);
return 0;
}
M. Longest subsequence
题意： 给你两串字符串 $S$ , $T$, 求 $S$ 中字典序大于 $T$ 的最长的子序列
范围： $1 \le |S|,|T| \le 10^{6}$
解法： 一定要弄清楚子序列和子串的区别，子序列可以不连续而子串一定连续。由于字典序的性质，如果 $S_{i} > T_{j}$， 那么答案就是 $|S| - i + j $ 。对于每一个 $T_{j}$ ， 枚举符合条件的最小的 $i$ 即可。由于题目要求严格大于 $T$ 的最长的子序列，只需要在 $T$ 的末尾加上一个 'a' - 1 的标记即可.
代码：
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
char s[N], t[N];
int nxt[N][26];
int main() {
int m, n;
scanf("%d%d", &n, &m);
scanf("%s", s);
scanf("%s", t);
t[m] = 'a' - 1, t[m + 1] = 0, ++m;
for (int j = 0; j < 26; ++j) {
nxt[n][j] = n;
}
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < 26; ++j) {
nxt[i][j] = nxt[i + 1][j];
}
nxt[i][s[i] - 'a'] = i;
}
int pos = 0, ans = 0;
for (int i = 0; i < m && pos < n; ++i) {
for (int j = max(0, t[i] - 'a' + 1); j < 26; ++j) {
if (nxt[pos][j] != n)
ans = max(ans, n - nxt[pos][j] + i);
}
pos = nxt[pos][t[i] - 'a'] + 1;
}
printf("%d\n", ans ? ans : -1);
return 0;
}