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

C. 矩阵消除游戏

 

题意：nm的矩阵，每次选一行或一列得到它的元素和，并把这行或列置为0，问操作k次的最大值。

状压枚举

直接枚举行的选择情况，再每次nm处理出列，取最大的。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int a[20][20], n, m, k;
int t;
int sum2[N], vc[N], ans, sum1[N];
int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)scanf("%d", &a[i][j]), sum1[i]+=a[i][j],sum2[j] += a[i][j];
	}
	for (int s = 0; s < (1 << n); s++) {
		int cnt = 0, res = 0;
		for (int i = 0; i < n; i++) {
			if (s&(1 << i)) {
				cnt++;
				res += sum1[i];
			}
		}
		if (cnt > k)continue;
		t = 0;
		for (int j = 0; j < m; j++) {
			int tmp = sum2[j];
			for (int i = 0; i < n; i++)if (s&(1 << i)) {
				tmp -= a[i][j];
			}
			vc[t++] = tmp;
		}
		sort(vc, vc + t, greater<int>());
		for (int i = 0; i < k - cnt; i++) {
			res += vc[i];
		}
		ans = max(ans, res);
	}
	cout << ans << endl;
	return 0;
}

 

D. 迷宫

 

题意：nm的迷宫，以 右>下>左>上 的优先级从左上角走到右下角，遇到障碍就按照优先级能转向就转向。问在原图的基础上最少还要加多少个障碍。

dp

每一格只有从上或从左走过来才有意义。假设从右走过来：从右走过来说明右边的右边一格一定是障碍，并且右边不是障碍，那么在走到这一格后就会不停地左右走，死循环了。而如果是从下走过来，那说明下面那格的左，右，下都有障碍，那么之前是怎么走到下面那格的？显然是从这一格走过去的，那也变成个死循环了。而由于如果这一格的右和下有格子，那这一格一定不是终点，在中间点就陷入了死循环，这样无法走到终点的情况是不能统计的。

设 dp[i][j]dp[i][j] 表示走到 (i,j)(i,j) 需要再加的最少障碍数。

那么只有两个转移方向了，从左转移过来就直接用就好了，因为右优先级最高。

从上转移过来就要判断，如果右上一格是障碍，那么默认向下走，否则要手动加一个障碍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
char mz[1010][1010];
int dp[1010][1010];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%s", mz[i] + 1);
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)dp[i][j] = INF;
    for (int j = 1; j <= m; j++)if (mz[1][j] == '0')dp[1][j] = (mz[1][j] == '0' ? dp[1][j - 1] : INF);
    for (int i = 2; i <= n; i++)if (mz[i][1] == '0')dp[i][1] = (mz[i - 1][2] == '0' ? dp[i - 1][1] + 1 : dp[i - 1][1]);
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            if (mz[i][j] == '0')
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + (mz[i - 1][j + 1] == '0' ? 1 : 0));
        }
    }
    printf("%d\n", dp[n][m] >= INF ? -1 : dp[n][m]);
    return 0;
}

 

E. 最大GCD

 

题意：给出长度为 nn 的序列，你需要进行 qq 次查询，每次查询形如以下格式：l,r,xl,r,x：你需要选择两个整数 s,ts,t 满足 l<=s<=t<=rl<=s<=t<=r，使得gcd(a[s],a[s+1]...a[t−1],a[t],x)gcd(a[s],a[s+1]...a[t-1],a[t],x) 最大化。输出最大值。

对于每次询问，枚举x的因数，只要直到给定区间是否有数含有这个因数。

可以预处理出每个因数被哪些数包含，复杂度是 nnn\sqrt n 的！！

每次询问，枚举x的因数，再二分查包含该因数的位置是否在给定区间中。

O(nnlog⁡n)O(n\sqrt n \log n)

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int>vc[N];
int n, q;
int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		for (int j = 1; j*j <= x; j++) {
			if (j*j == x)vc[j].push_back(i);
			else {
				if (x%j == 0)vc[j].push_back(i), vc[x / j].push_back(i);
			}
		}
	}
	while (q--) {
		int l, r, x;
		scanf("%d%d%d", &l, &r, &x);
		int ans = 0;
		for (int i = 1; i*i <= x; i++) {
			if (x%i != 0)continue;
			auto pos = lower_bound(vc[i].begin(), vc[i].end(), l);
			if (pos != vc[i].end() && (*pos) <= r)ans = max(ans, i);
			pos = lower_bound(vc[x / i].begin(), vc[x / i].end(), l);
			if (pos != vc[x / i].end() && (*pos) <= r)ans = max(ans, x / i);
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

F. XOR TREE

 

题意：定义点 uu 到点 vv 的路径的长度为点 uu 到点 vv 的最短路径上的所有结点的权值的异或和。

单独一个点不算做路径。

现在要求你维护 qq 个操作：

  • 1,u,x1,u,x 将点 uu 的权值修改为 xx
  • 2,u,v2,u,v 求点 uu 到点 vv 之间的所有子路径的长度的异或和

 

树状数组+树链刨分

每次询问只有 log⁡n\log n 的时间，显然需要树刨。并且不等真的求所有子路径而是求出所有点对答案的贡献。

试着分类讨论一下，假设路径上点从 uu 到 vv 为 1,2,⋯k1,2,\cdots k，可以发现，当路径长度为奇数时只有偶数点被经过的次数为奇数次，也就只有奇数点对答案有贡献。

当长度为偶数时，所有点都有贡献。

再考虑如何区分奇数和偶数点。显然奇数点于偶数点的深度是相间的，那么根据深度的奇偶维护两个树状数组，再加上一个维护所有点的树状数组即可。

在树刨过程中，跳重链时把链上所有点根据深度奇偶用相应的树状数组前缀和得到这一段点的异或和。

不得不说，这题内存卡的真的死，用前向星还会卡内存。

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
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+ 10;
const int INF = 0x3f3f3f3f;
int n, q;
int val[N];
vector<int>G[N];
int dfn[N], fa[N], siz[N], son[N], topf[N], dep[N], clk;
void dfs1(int u, int _fa) {
	siz[u] = 1; fa[u] = _fa;
	for (int v:G[u]) {
		if (v == _fa)continue;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v])son[u] = v;
	}
}
void dfs2(int u, int topfa) {
	topf[u] = topfa;
	dfn[u] = ++clk;
	if (!son[u])return;
	dfs2(son[u], topfa);
	for (int v:G[u]) {
		if (!topf[v])dfs2(v, v);
	}
}
int lowbit(int x) { return x & -x; }
int sum[3][N];
void add(int id, int p, int x) {
	for (int i = p; i <= n; i += lowbit(i))
		sum[id][i] ^= x;
}
int query(int id, int r) {
	int ans = 0;
	for (int i = r; i > 0; i -= lowbit(i))
		ans ^= sum[id][i];
	return ans;
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)scanf("%d", &val[i]);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for (int i = 1; i < n; i++) {
		add(dep[i] % 2, dfn[i], val[i]);
		add(2, dfn[i], val[i]);
	}
	while (q--) {
		int op, u, v;
		scanf("%d%d%d", &op, &u, &v);
		if (op == 1) {
			add(dep[u] & 1, dfn[u], val[u] ^ v);
			add(2, dfn[u], val[u] ^ v);
			val[u] = v;
		}
		else {
			int ans = 0, sta;
			if (dep[u] % 2 != dep[v] % 2)sta = 2;
			else if (dep[u] & 1)sta = 0;
			else sta = 1;
			while (topf[u] ^ topf[v]) {
				if (dep[topf[u]] > dep[topf[v]])swap(u, v);
				ans ^= query(sta, dfn[v]) ^ query(sta, dfn[topf[v]] - 1);
				v = fa[topf[v]];
			}
			if (dep[u] > dep[v])swap(u, v);
			ans ^= query(sta, dfn[v]) ^ query(sta, dfn[u] - 1);
			printf("%d\n", ans);
		}
	}
	return 0;
}