https://ac.nowcoder.com/acm/contest/5670

I - Hard Math Problem

 

题意：一个无限大的二维网格，每格可以填 1，2，3，要求每个 1 四周至少有一个 2 和一个 3。问 1 的密度最大多少。

构造

如上图，在 (i+j)%3==0(i+j)\%3==0 处放 2 或 3，其它地方放 1 ，并满足 1 和 2，3 相邻。

1
2
3
4
5
6
#include<bits/stdc++.h>
using namespace std;
int main() {
	puts("0.666667");
	return 0;
}

D - Drop Voicing

 

题意：给定一个 1 到 n 的排列，2 种操作：所有数环形向左平移一位；前 n-1 个数环形向右平移一位。连续的第 2 种操作算作一次大操作，问最少用几次大操作使得排列变为有序。

贪心+最长上升子序列

先进行一次连续 k 个第 2 种操作，再进行连续 k 个第 1 种操作，则原先的最后一个数向前平移了 k 位。其中 k 可以是任意数。

并且在这之前进行几次第一种操作，则可以把任意数放到最后一个位置上。

所以一次大操作可以把任意数放到任意位置上去。

当然，在第 2 种操作后，可以进行不等于 k 个第 1 种操作，但是这样也就相当于在一次移动之后再单独进行几次第 1 种操作。这多出的几次第1 种操作可以放到最前面去，因为既然每次可以交换插入到位置，先平移还是后平移就没有关系了。

所以问题变为选尽可能少的数放到任意位置上，使得有序。

那么肯定是选最长上升子序列之外的数了。而由于之前所说的，把多出来的第 1 种操作都放到最前面去，所以刚开始时需要平移，枚举平移的距离，再每次求最长上升子序列。

LIS可以贪心得到，从前到后遍历，如果新数大于目前最大的数，则LIS长度增加，否则把新数替换到前面合适的位置，每次lowerbound找到要替换的位置，所以该位置上的数就减小了，对于找到LIS更有利。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 998244353;
int n;
int a[N];
int b[N];
int ans;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &a[i]);
	for (int i = 0; i < n; i++) {
		fill(b, b + n + 1, INF);
		for (int j = 0; j < n; j++) {
			int p = lower_bound(b, b + n, a[(i + j) % n]) - b;
			b[p] = a[(i + j) % n];
		}
		for (int j = n - 1; j >= 0; j--) {
			if (b[j] < INF) {
				ans = max(ans, j + 1);
				break;
			}
		}
	}
	printf("%d\n", n - ans);
	return 0;
}

 

B - Graph

 

题意：给定一棵树，有边权，要求删边或加边，保证图联通且每个环上的所有边的异或和为 0。

Trie+最小生成树

容易发现新加的边的边权只与边的两端点有关，与加边或删边的顺序无关。且加的边权等于两端点各自到树根的路径异或长度的异或和。

则可以变为一张完全图，每条边的边权等于两端点到根的异或路径长度的异或和。

若给每点赋点权等于它到根的路径异或长度，则问题变为求一个完全图的最小生成树，图上每条边的边权等于两端点的点权异或和。

就变成了这道原题 CF888G. Xor-MST

求最小生成树有一个 Boruvka 算法，大致思路就是对每个联通块连出它连出的边中的最小值，再连上这条最小边，进入下一轮，重新计算联通块，直到所有点联通。

这个算法常用于边权为计算值的完全图。

本题并不是直接模拟这个算法，而是计算每次的最小边的边权。把所有会成为最小边的边都找出来，求出贡献，再求和。

对于异或的问题，还是要考虑Trie。

考虑 cf 那题的样例，共 5 点，分别为 1，2，3，4，5。插入道 Trie 中，要连接这些点，使得所有点都成为一个联通块。对于点 2 和点 3，连接这两个点的代价为最底层的 0 与 1 的异或值，对于 2，5 而言，连接的代价为从根开始的所有 0 1 的异或值之和，所以显然要优先从下往上连接，贪心是正确的，因为对于点集 {1，2，3}，{4，5}，必定存在一条边连接，而这条边的代价只能是从 Trie 的根开始计算的。

考虑 Trie 上的每点的贡献，连接两点的代价由于等于两点点权的异或和，所以在 Trie 上就是两点到 LCA 的代价和，图上绿点为可能成为 LCA 的点，由于 Trie 是一棵二叉树，所以把每个点管理的叶节点分为两部分，这两部分之间必须要有连边，代价就是所有可能连边的最小情况。

以 Trie 的根为例，它的右儿子管理叶节点 4，5，假设 4，5 已经联通，所以现在要选 4 或 5 与根的左儿子中某点连接，假设选 4，则最高层的代价不可避免，再往下，必定是要尽量沿着与 4 相同的路径走，这样异或和最小。这样求出 4，再类似求出 5 的代价，取最小值，就连接了 Trie 根节点左右儿子。

对于 Trie 上每一点，如果有分叉，则需要合并左右儿子，否则一直往下走。

如果有两点的点权相同，则可以先把这两点联通，代价为 0，之后只要把它们当成一点算即可，以上方法同样可以适用。

注意 Trie 上的叶节点的 dep 为 -1。

本题也类似，只要先处理出每点的点权，就可以直接套。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 998244353;
int n;
int a[N];
struct E
{
	int v, w;
};
vector<E>G[N];
void dfs(int u, int _fa, int le) {
	a[u] = le;
	for (E& e : G[u]) {
		if (e.v == _fa)continue;
		dfs(e.v, u, e.w^le);
	}
}
struct Trie
{
	int ch[N * 40][2];
	int tot = 0;

	void ins(int& now, int x, int dep) {
		if (!now)now = ++tot;
		if (dep < 0)return;
		int bit = ((a[x] >> dep) & 1);
		ins(ch[now][bit], x, dep - 1);
	}

	ll qry(int now, int val, int dep) {			//val与存在Trie中的数的最小差值
		if (dep < 0)return 0;
		int bit = ((val >> dep) & 1);
		if (ch[now][bit])return qry(ch[now][bit], val, dep - 1);
		else return qry(ch[now][bit ^ 1], val, dep - 1) + (1ll << dep);
	}
}Tri;
vector<int>vc;
ll solve(vector<int>&vc, int rt, int dep) {
	if (!rt)return 0;
	vector<int>vv[2];
	for (int u : vc)vv[(u >> dep) & 1].push_back(u);
	if (vv[0].empty())return solve(vv[1], Tri.ch[rt][1], dep - 1);
	if (vv[1].empty())return solve(vv[0], Tri.ch[rt][0], dep - 1);
	ll tmp = inf;
	for (int u : vv[1]) {
		tmp = min(tmp, Tri.qry(Tri.ch[rt][0], u, dep - 1) + (1ll << dep));
	}
	return tmp + solve(vv[0], Tri.ch[rt][0], dep - 1) + solve(vv[1], Tri.ch[rt][1], dep - 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		u++; v++;
		G[u].push_back(E{ v,w });
		G[v].push_back(E{ u,w });
	}
	dfs(1, 0, 0);
	int root = 0;
	for (int i = 1; i <= n; i++)vc.push_back(a[i]), Tri.ins(root, i, 30);
	printf("%lld\n", solve(vc, 1, 30));
	return 0;
}

 

A - Portal

 

题意：真《传送门》，给定一张无向图，多个任务按顺序完成：每次先到一点拿到一个block，再到目标点。可以在任意点开一个传送门，如果有两个传送门则可以传送，多于两个则必须先选一个关掉。问完成所有任务最少走的距离。

dp

每次任务要按顺序走过两个点，所以干脆把它们拆开，看成2个任务，每个任务只要从上一次的目标点走到这次的目标点。

最暴力的 dp[i][j][u][v]dp[i][j][u][v] 表示第 i 个任务，现在在 j 点，u，v 有两个传送门。

但是发现并不需要记录两个传送门，因为使用时必定要先删掉一个，再在现在所在点开一个，所以只要记录剩下的一个传送门即可。变成 dp[i][j][u]dp[i][j][u]。

再发现其实并不需要记录现在在哪里，因为直接从上一个目标到下一个，中间最多使用一次传送门，只要枚举传送的中间点，其它距离完全可以预处理出来，使用时直接加上去。所以最终变成 dp[i][u]dp[i][u]。

转移方程：

f[i][j]f[i][j] 为 dp，d[i][j]d[i][j] 为 i，j 距离，u=p[i−1]u=p[i-1] 为上一个目标点，v=p[i]v=p[i] 为当前目标点。

  • f[i][j]=f[i−1][j]+d[u][v]f[i][j]=f[i-1][j]+d[u][v] 直接从上一个目标走到下一个，不用传送门。
  • f[i][j]=f[i−1][j]+d[j][v]f[i][j]=f[i-1][j]+d[j][v] 传送到 j，从 j 走到 v。
  • f[i][k]=f[i−1][j]+d[j][k]+d[k][v]f[i][k]=f[i-1][j]+d[j][k]+d[k][v] 从上一个目标开门传送到 j，再从 j 走到 k，开门，再从 k 走到当前目标。
  • f[i][k]=f[i−1][j]+d[u][k]+d[k][v]f[i][k]=f[i-1][j]+d[u][k]+d[k][v] 从上一个目标走到 k，开门，再从 k 走到当前目标。
  • f[i][k]=f[i−1][j]+d[u][k]+d[j][v]f[i][k]=f[i-1][j]+d[u][k]+d[j][v] 从上一个目标走到 k，开门，再传送到 j，再从 j 走到当前目标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 998244353;
int n, m, q;
ll d[310][310], f[610][310];
int p[610];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; i++)d[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        d[u][v] = d[v][u] = min(w, d[u][v]);
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[0][1] = 0ll;
    p[0] = 1;
    for (int i = 1; i <= 2 * q; i++) {
        scanf("%d", &p[i]);
        int u = p[i - 1], v = p[i];
        for (int j = 1; j <= n; j++) {
            f[i][j] = min(f[i][j], f[i - 1][j] + min(d[u][v], d[j][v]));
            for (int k = 1; k <= n; k++) {
                if (k != j) {
                    ll a = d[j][k] + d[k][v];
                    ll b = d[u][k] + d[k][v];
                    ll c = d[u][k] + d[j][v];
                    f[i][k] = min(f[i][k], f[i - 1][j] + min(a, min(b, c)));
                }
            }
        }
    }
    ll ans = inf;
    for (int i = 1; i <= n; i++)ans = min(ans, f[2 * q][i]);
    printf("%lld\n", ans);
    return 0;
}