Content
- ZJU-ICPC Summer 2020 Contest 4 by Group A
-
- Problem C. guofuqian50
-
- Problem E. Problem of Card Bonus
-
- Problem F. Magical String
- ZJU-ICPC Summer 2020 Contest 5 by Group B
-
- Problem D. Cities
-
- Problem F. Contour
- [absent]ZJU-ICPC Summer 2020 Contest 6 by Group C
ZJU-ICPC Summer 2020 Contest 4 by Group A
Problem C. guofuqian50
[10s/512MB] 给定一个 (n(le 5 imes 10^4)) 个点，(m(le 10^5)) 条边的无向图，带边权 ((le 10^9))。上面标有 (k(le n)) 个特殊点，记特殊点集为 (S)。每个点有一个权值 (w_i(le 20))。定义一个点 (u) 在能见度为 (r) 的时间内的“危险度”为 (sum_{vin S}[ ext{dist}(u, v)le r])（( ext{dist}(u, v)) 表示 (u, v) 两点之间的最短距离），若其危险度大于 (ge w_u) 则称点 (u) 为“危险的”。现在有 (t(le 10^5)) 天，第 (i) 天的你能见度为 (r_i(le 10^{18}))，求每个点在这 (t) 天中，成为“危险的”的天数。
本质上就是求距离每个点前 (w_i) 近的点与之的最短距离的集合。只要得到了这个，那么我们看看第 (w_i) 近的点的最短距离是否超过 (r_i) 即可。
之所以可以这么考虑，是因为 (w_i) 的范围非常小，使之成为了本题的突破口。
这可以魔改一下 Dijkstra 算法实现，但还是很多细节的，比如如果直接将所有特殊点放进去跑，会出现“串味”的现象，导致反复横跳。
要避免这个，我们还应保存一个 源点编号，然后将原来保存答案的数组换成 map 或 unordered_map，记录不同源点的答案。
但记录全部仍然无法满足要求，于是我们回顾 (w_ile 20) 这个条件，根据 Dijkstra 贪心的思想，先到的一定更优，于是我们限定 map 的大小最大为 (max { w_i})，超出了直接跳过。
这样的时间复杂度为 (O(w(n+m)log m))。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Article : ZJU Summer Training 2020
*/
#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
const int M = 5e5 + 5;
const int T = 5e5 + 5;
const int W = 20;
int n, m, t, k;
LL w[N];
LL lim[N];
LL day[N];
bool tag[N];
struct edge { int to; LL len; };
vector<edge> G[N];
struct {
struct heapNode {
int src, pos; LL dis;
inline bool operator < (const heapNode& x) const {
return dis > x.dis;
}
};
priority_queue<heapNode> pq;
map<int, LL> dist[N];
void Dijkstra() {
for (int i = 1; i <= n; i++)
if (tag[i]) pq.push({i, i, 0});
while (!pq.empty()) {
heapNode x = pq.top(); pq.pop();
if (dist[x.pos].count(x.src)) continue;
if (dist[x.pos].size() > W) continue;
dist[x.pos][x.src] = x.dis;
for (auto y : G[x.pos]) {
if (dist[y.to].count(x.src)) continue;
pq.push({x.src, y.to, y.len + x.dis});
}
}
}
void get() {
for (int i = 1; i <= n; i++) {
vector<pair<LL, int> > rec;
for (auto j : dist[i]) rec.push_back({j.second, j.first});
sort(rec.begin(), rec.end());
lim[i] = w[i] > rec.size()
? LL(1e18)
: rec[w[i] - 1].first;
}
}
} sssp;
signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; LL w;
scanf("%d%d%lld", &u, &v, &w);
G[u].push_back({v, w});
G[v].push_back({u, w});
}
scanf("%d", &k);
for (int i = 1; i <= k; i++) {
int a; scanf("%d", &a);
tag[a] = true;
}
for (int i = 1; i <= n; i++)
scanf("%lld", w + i);
sssp.Dijkstra();
sssp.get();
scanf("%d", &t);
for (int i = 1; i <= t; i++)
scanf("%lld", day + i);
sort(day + 1, day + 1 + t);
for (int i = 1; i <= n; i++) {
int ans = lower_bound(day + 1, day + 1 + t, lim[i]) - day - 1;
printf("%d ", ans);
}
printf("
");
return 0;
}
Problem E. Problem of Card Bonus
给定三个长为 (n(le 10^3)) 的数组 (a_{1cdots n}(le 10^4), b_{1cdots n}(le 10^4), c_{1cdots n}(le 2 imes 10^6))。给定 (p(le 10^4))，求一组 (x_{1cdots n}(in {0, 1}))，满足 (sumlimits_{1le ile n} a_i x_i le p le sumlimits_{1le ile n} b_i x_i) 时，(sumlimits_{1le ile n} c_i x_i) 的最小值。
动态规划。设 (f(i, j)) 为前 (i) 个 (x)，满足 (sum a_i x_i le p le sum b_i x_i) 时 (sum c_i x_i) 的最小值。
那么对于当前状态，有两种转移：
- (x_i = 0 o f(i - 1, j)) 不选。
- (x_i = 1 o) 所有于 (j) 的差值在范围 ([a_i, b_i]) 的 (k)， (f(i - 1, k)) 的最小值。由于当前被选择，需要加上 (c_i)。
状态转移方程：
但直接做显然是 (O(n imes p^2)) 的。由于我们发现，方程中的第二项本质上是一个滑动最值问题，考虑用单调队列优化这个过程。
如果卡空间还可以把第一维滚掉，但是这里不需要。时间复杂度 (O(n imes p))。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Article : ZJU Summer Training 2020
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
const int N = 1e3 + 5;
const int P = 1e4 + 5;
typedef long long LL;
int n, p;
int a[N], b[N], c[N];
LL f[N][P];
void solve() {
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) scanf("%d", b + i);
for (int i = 1; i <= n; i++) scanf("%d", c + i);
memset(f, 0x3f, sizeof f);
f[0][0] = 0ll;
for (int i = 1; i <= n; i++) {
deque<int> dq;
for (int j = 0; j <= p; j++) {
if (j < a[i]) { f[i][j] = f[i - 1][j]; continue; }
while (!dq.empty() && f[i - 1][j - a[i]] <= f[i - 1][dq.back()]) dq.pop_back();
dq.push_back(j - a[i]);
while (!dq.empty() && dq.front() < j - b[i]) dq.pop_front();
f[i][j] = min(f[i - 1][j], f[i - 1][dq.front()] + c[i]);
}
}
printf("%lld
", f[n][p] >= 1e14 ? -1ll : f[n][p]);
}
signed main() {
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}
Problem F. Magical String
给定一个一个文本串 (A(|A| le 500))，以及一个大小为 (m) 的模式串集 (B = {B_1, B_2, cdots, B_m}(mle 10^5, |B_i| le |A|, sum|B_i| le 10^6))。试选出一个 (B) 的子集 (S)，满足 (S) 中的字符串存在一种排列方式（可以任意排列），使排列后的新字符串 (C) 无限向两端复制的结果等价于 (A) 向两端无限复制的结果。求 (min |S|)。
非常显然，若 (S) 可以匹配到 (A) 的一个循环节，那么整个都可以匹配。而 (A) 的一个循环节无限复制的结果和 (A) 本身复制的结果是相同的。于是我们之间匹配 (A) 的 最小循环节 即可。记这个最小循环节长度为 (L)。
我们处理出 (B) 中的模式串在 (A) 中的出现情况。对于 (A) 的某一个位置 (i)，若 (A[i, j]) 是 (B) 中的一个串，那么我们称 第 (i) 个位置可以转移到第 (j+ 1) 个位置。但可能会超出最小循环节，于是令 (j) 对 (L) 取模。
考虑如何对于所有的 (i in [1, L])，处理出所有从 (i) 开始的转移。由于转移中的 (B) 一定是 (A[i, |A|]) 的 一个前缀，当一个位置断掉了，之后一定不会匹配。可以用 Trie 树辅助实现这一过程。
现在我们已经得到了所有转移，那么我们不妨 将位置视为点，将转移视为边，构成了一个有向图。 其中每使用一次转移，就相当于使用 (B) 中 的一个元素。这个元素并不会重用，因为处理出了 (A) 的最小循环节。
那么我们要求的答案就是 最小环的大小。这个直接 Floyd 可以过，复杂度 (O(n^3))。
思路主要来自 kqh （orz）
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Article : ZJU Summer Training 2020
*/
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1005;
const int L = 1e6 + 5;
const int M = 1e5 + 5;
const int S = 26;
int n, m;
char s[N];
char t[N];
int g[N][N];
int f[N][N];
struct trie {
int ch[L][S];
int total;
bool end[L];
trie() {
total = 1;
}
void insert(char* s) {
int x = 1;
for (int i = 0; s[i]; i++) {
int c = s[i] - 'a';
if (!ch[x][c]) ch[x][c] = ++total;
x = ch[x][c];
}
end[x] = 1;
}
inline int* operator [] (int p) {
return ch[p];
}
} tr;
bool same(char* a, char* b, int l){
for (; l; --l, ++a, ++b) if (*a != *b) return false;
return true;
}
signed main() {
scanf("%s", s + 1);
n = strlen(s + 1);
int cl = n;
for (int l = n; l; --l) {
if (n % l != 0) continue;
bool f = 1;
for (register int start = l + 1; start <= n && f; start += l)
if (!same(s + 1, s + start, l)) f = false;
if (f) cl = l;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%s", t);
tr.insert(t);
}
copy(s + 1, s + 1 + n, s + 1 + n);
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= cl; i++) {
int x = 1;
for (int j = i; j <= n + i; j++) {
x = tr[x][s[j] - 'a'];
if (!x) break;
if (tr.end[x]) {
int k = j % cl + 1;
if (k == i) { puts("1"); return 0;}
g[i][k] = 1;
}
}
}
for (register int i = 1; i <= cl; i++)
g[i][i] = 0;
memcpy(f, g, sizeof g);
long long ans = 0x3f3f3f3f;
for(int k = 1; k <= cl; k++)
for(int i = 1; i <= cl; i++)
for(int j = 1; j <= cl; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
for(int i = 1; i <= cl; i++)
for(int j = 1; j <= cl; j++)
if (i != j)
ans = min(ans, 1ll * f[i][j] + f[j][i]);
printf("%lld
", ans > n * 2 ? -1 : ans);
return 0;
}
ZJU-ICPC Summer 2020 Contest 5 by Group B
Problem D. Cities
给定一个 (n(le 50)) 个点，(m(le 110)) 条边的无向图，起始点位于顶点 (1)，在一天的时间内有三种选择：往相邻点走，停留在原地，或结束。给定 (t(le 10^8))，求在 (t) 天内有几种不同的行动方案数 (pmod{2020})。
考虑到 (n) 非常小，那么可能提示我们用邻接矩阵存图。当一个邻接矩阵 (A_{i, j}) 可以表示结点 (i, j) 的联通状态，但这里我们理解为 从结点 (i) 到结点 (j) 的行动方案数。因此我们令所有 (in[1, n]) 的 (i)，(A_{i, i} leftarrow 1)。
若我们设一次（一天）转移后得到矩阵 (B)，不难得出：
这个一看就是 矩阵乘法，于是我们记一次转移的结果为 (A^2)，那么 (t) 次即为 (A^t)。然而不幸的是，矩阵 (A^t) 中的元素之和并不是我们的答案，因为可以任意的退出。很显然只要把所有 ([0, t]) 的矩阵幂算出来，于是答案其实是：(C = R imes sumlimits_{pin[0, t]} A^p)，其中 (R_{1, 1} = 1)，其余元素为零。
但这东西仍然无法直接求。我们又设 (S = egin{bmatrix} A & 0 \ I & Iend{bmatrix})，那么算出 (S^{t+1}) 即可，(C = (S^{t+1})_{1, 2})。关于矩阵套矩阵：POJ 3233 - Matrix Power Series
时间复杂度 (O(n^3 log t))
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Article : ZJU Summer Training 2020
*/
#include <iostream>
#include <vector>
using namespace std;
const int N = 55;
const int mod = 2020;
typedef vector<int> vec;
typedef vector<vec> mat;
int n, m, t;
inline mat operator * (mat a, mat b) {
mat x(a.size(), vec(b[0].size(), 0));
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b[0].size(); j++)
for (int k = 0; k < b.size(); k++)
(x[i][j] += a[i][k] * b[k][j] % mod) %= mod;
return x;
}
inline mat matI(int n) {
mat x(n, vec(n, 0));
for (int i = 0; i < n; i++)
x[i][i] = 1;
return x;
}
mat fastpow(mat b,int k) {
if (!k) return matI(b.size());
mat t = fastpow(b, k >> 1);
if (k & 1) return t * t * b;
else return t * t;
}
signed main() {
cin >> n >> m;
mat A = matI(n << 1);
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
A[u - 1][v - 1] = 1;
A[v - 1][u - 1] = 1;
}
for (int i = 0; i < n; i++)
A[n + i][i] = 1;
mat I(n, vec(n));
I[0][0] = 1;
cin >> t;
A = fastpow(A, t + 1);
mat S(n, vec(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
S[i][j] = A[i + n][j];
S = I * S;
/* (+n, +0) */
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
(ans += S[i][j]) %= mod;
cout << ans << endl;
return 0;
}
Problem F. Contour
平面上有 (n(in [4, 10^4])) 个点，现在要用这 (n) 个点构造一个图形，满足：
- 这个图形是闭合的；
- 每条边的端点必须是给定的点，且每个给定的点必须被用到；
- 每个点连接的两条边必须互相垂直；
- 每条边必须平行于坐标轴；
- 任意两条边除了顶点外不能相交；
- 这个图形的周长最小。
如果有解，输出最小周长，否则输出(0)。
构造题。对于部分 (x) 坐标相同的点的点集 (S)，若要使有解，必须满足 (|S|mod 2 = 0)。对于 (y) 坐标同理。根据这个思想，我们可以得出一个规律——对于在同一竖直线或水平线上的点，应该是第一个和第二个，第三个和第四个……第 (2k-1) 个和第 (2k(kin mathbb{Z})) 个连边。
因此不难得出以下构造算法：先将所有点分别按 (x, y) 为第一关键字，第二关键字排序，依据上述结论连上所有竖直的线段。题目要求连通，于是考虑使用并查集；题目又要求线段不相交，于是存下所有竖直的线段。再将所有点分别按 (y, x) 为第一关键字，第二关键字排序，依据上述结论连上所有水平的线段。并更新并查集，判断相交情况。
最后若全图连同则有解，输出答案。该解唯一，～～因为只能这样构造～～，不存在调整之后得到另一个解的情况。于是自然就是最优解了。
#include <algorithm>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 1e4 + 5;
const int inf = 0x3f3f3f3f;
int n;
struct Point {
int x, y, idx;
} p[N];
struct cmp_x {
inline bool operator () (const Point& x, const Point& y) {
return x.x != y.x ? x.x < y.x : x.y < y.y;
}
};
struct cmp_y {
inline bool operator () (const Point& x, const Point& y) {
return x.y != y.y ? x.y < y.y : x.x < y.x;
}
};
struct Segment {
int x, y1, y2;
} s[N];
int total = 0;
int dsu[N];
int find(int x) {
return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) dsu[fx] = fy;
}
void error() {
cout << 0 << endl;
exit(0);
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
p[i].idx = dsu[i] = i;
cin >> p[i].x >> p[i].y;
}
long long ans = 0ll;
sort(p + 1, p + 1 + n, cmp_x());
for (int l = 1, r; l <= n; l = r + 1) {
int x = p[l].x;
r = upper_bound(p + 1, p + 1 + n, Point{x, inf}, cmp_x()) - p - 1;
if ((r - l + 1) & 1) error();
for (int i = l; i < r; i += 2) {
s[++total] = Segment{x, p[i].y, p[i + 1].y};
merge(p[i].idx, p[i + 1].idx);
ans += p[i + 1].y - p[i].y;
}
}
sort(p + 1, p + 1 + n, cmp_y());
for (int l = 1, r; l <= n; l = r + 1) {
int y = p[l].y;
r = upper_bound(p + 1, p + 1 + n, Point{inf, y}, cmp_y()) - p - 1;
if ((r - l + 1) & 1) error();
for (int i = l; i < r; i += 2) {
for (int j = 1; j <= total; j++)
if (s[j].y1 < y && y < s[j].y2 && p[i].x < s[j].x && s[j].x < p[i + 1].x)
error();
merge(p[i].idx, p[i + 1].idx);
ans += p[i + 1].x - p[i].x;
}
}
for (int i = 1; i < n; i++)
if (find(i) != find(i + 1))
error();
cout << ans << endl;
return 0;
}