6.27 测试

6.27 测试

混氏新子 蒟蒻
  2023-07-02 15:29:22 2023-07-02 15:29:22 创建   2023-09-24 19:11:47 2023-09-24 19:11:47 更新    1.6k 字  8 分钟  

前情提要

题目链接

成绩表

成绩表

今天还行吧？

P.S. 今天所有题都是和随机化有关的，嘻嘻，人品爆炸。

题解

T1

#dp

不会，用了一个不严谨的乱想的算法，然后不如直接暴力 dfs ，所以以后一看就是错误的算法还想骗几分的还是老老实实暴力吧~

正解用 color-coding，就是给每个点染色，染色数大于 k ，然后用状压进行 dp ，你可以计算一下最长链不同颜色的概率多算几次提高概率就行了。真是妙啊~

小心超时。

code
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
#include <bits/stdc++.h>
#define eb emplace_back
#define N 5010
using namespace std;
mt19937 mt(random_device{}());
int t, n, m, k;
int u, v, tim;
int tt[N][N];
vector <int> gg[N];
int col[N];
int f[N][128];
int ans;
int main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
//		memset(tt, 0, sizeof(tt));
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; ++i) gg[i].clear();
		for (int i = 0; i < m; ++i) {
			scanf("%d%d%d", &u, &v, &tim);
			tt[u][v] = tim;
			tt[v][u] = tim;
			gg[u].eb(v);
			gg[v].eb(u);
		}
		ans = -1;
		for (int orz = 0; orz < 360; ++orz) {
			memset(f, -0x3f, sizeof(f));
			for (int i = 1; i <= n; ++i) col[i] = mt() % k, f[i][1 << col[i]] = 0;
			for (int i = 2; i <= k; ++i) {
				for (int j = 1; j <= n; ++j) {
					for (auto &l : gg[j]) {
						for (int o = 1; o < (1 << k); ++o) {
							if (o & (1 << col[j])) continue;
							f[j][o ^ (1 << col[j])] = max(f[j][o ^ (1 << col[j])], f[l][o] + tt[j][l]);
						}
					}
				}
			}
			for (int i = 1; i <= n; ++i) {
				ans = max(ans, f[i][(1 << k) - 1]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

T2

#模拟退火 #dp #树形dp

用模拟退火切了 80 分，nice，orz，orz，orz。
直接先随机个点的排列，然后枚举前几个点删掉的答案。多几次退火就行。

80分代码（人品不好可能会更低）

80 pts code
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
#include <bitsdc++.h>
#define eb emplace_back
using namespace std;
using ll = long long;
mt19937 mt(random_device{}());
int t, n, m;
ll a, b;
ll ans;
pair <int, int> ed[45];
vector <int> gra[45];
bool mp[45][45];
bool vis[45];
int bs[45];
ll js() {
	ll ans = a * m;
	for (int j = 0; j <= n; ++j) {
		memset(vis, 0, sizeof(vis));
		int totp = j;
		for (int i = 1; i <= j; ++i) {
			bool flag = 0;
			for (auto &k : gra[bs[i]]) {
				if (!vis[k]) flag = 1;
				vis[k] = 1;
			}
			if (!flag) --totp;
		}
		int tot = 0;
		for (int k = 0; k < m; ++k) if (vis[k]) ++tot;
		ans = min(ans, b * totp + a * (m - tot));
	}
	return ans;
}
void mnth() {
	double T = 100000, dt = 0.99;
	while (T > 1e-8) {
		int x = mt() % (n - 1) + 1, y = mt() % (n - x) + x + 1;
		swap(bs[x], bs[y]);
		ll tmp = js();
		if (tmp < ans) {
			ans = tmp;
		} else if (exp(- abs(ans - tmp) / T) * 6553600 < mt() % 6553600) {
			swap(bs[x], bs[y]);
		}
		T *= dt;
	}
}
int main() {
	freopen("random.in", "r", stdin);
	freopen("random.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%lld%lld", &n, &m, &a, &b);
		for (int i = 1; i <= n; ++i) gra[i].clear();
		memset(mp, 0, sizeof(mp));
		memset(bs, 0, sizeof(bs));
		ans = 1e18;
		for (int i = 0; i < m; ++i) {
			scanf ("%d%d", &ed[i].first, &ed[i].second);
			gra[ed[i].first].eb(i);
			gra[ed[i].second].eb(i);
		}
		for (int i = 1; i <= n; ++i) bs[i] = i;
		srand(time(NULL));
		random_shuffle(bs + 1, bs + n + 1);
		mnth();mnth();mnth();
		mnth();mnth();mnth();
		mnth();mnth();mnth();
		printf("%lld\n", ans);
	}
	return 0;
}

观察数据

  • 当时，直接暴力就行。

  • 当时，所以先建一个树，然后用树形 dp 就行。那么多余的边呢？可以有三种选择，指定删一个点，或者删边。但会超时，考虑简化到两种，如果指定的点不删就要加上删边的代价，时间复杂度就变成2为底的了。

P.S. 代码不长，但很容易在一些地方错，注意。

code
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
mt19937 mt(random_device{}());
int t, n, m;
int u, v;
ll a, b;
ll ans;
vector<int> gra[45], gb[45], tr[45], rt;
bool vb[45];
int del[45];
void dfs20(int u) {
	if (u > n) {
		int tp = 0;
		memset(vb, 0, sizeof(vb));
		for (int i = 1; i <= n; ++i) {
			if (!del[i]) continue;
			++tp;
			for (auto &j : gb[i]) {
				vb[j] = 1;
			}
		}
		int tot = 0;
		for (int j = 0; j < m; ++j) tot += vb[j];
		ans = min(ans, b * tp + a * (m - tot));
		return;
	}
	del[u] = 0;
	dfs20(u + 1);
	del[u] = 1;
	dfs20(u + 1);
}
vector <int> hb[2];
int ddd[45], ttt, siz[45];
void js(int u, int v) {
	vb[u] = 1;
	ddd[u] = ++ttt;
	siz[u] = 1;
	for (auto &i : gra[u]) {
		if (i == v) continue;
		if (vb[i]) {
			if (ddd[i] >= ddd[u]) {
				hb[0].eb(i);
				hb[1].eb(u);
			}
			continue;
		}
		tr[u].eb(i);
		js(i, u);
		siz[u] += siz[i];
	}
}
ll f[45][2];
void dp(int u) {
	f[u][0] = b;
	f[u][1] = a * del[u];
	for (auto &i : tr[u]) {
		dp(i);
		f[u][0] += min(f[i][0], f[i][1]);
		f[u][1] += min(f[i][0], f[i][1] + a);
	}
}
void dfsplus(int step) {
	if ((ull)step == hb[0].size()) {
		ll tot = 0;
		for (auto &i : rt) {
			dp(i);
			tot += min(f[i][0], f[i][1]);
		}
		ans = min(ans, tot);
		return;
	}
//	del[hb[1][step]] = 0;
	++del[hb[0][step]];
	dfsplus(step + 1);
	--del[hb[0][step]];
//	del[hb[0][step]] = 0;
	if (hb[1][step] != hb[0][step]) {
		++del[hb[1][step]];
		dfsplus(step + 1);
		--del[hb[1][step]];
	}
}
int main() {
	freopen("random.in", "r", stdin);
	freopen("random.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		ans = 1e18;
		ttt = 0;
		scanf("%d%d%lld%lld", &n, &m, &a, &b);
		for (int i = 1; i <= n; ++i) gra[i].clear(), gb[i].clear(), tr[i].clear();
		hb[0].clear();
		hb[1].clear();
		for (int i = 0; i < m; ++i) {
			scanf("%d%d", &u, &v);
			gra[u].eb(v);
			if (u != v) gra[v].eb(u);
			gb[u].eb(i);
			if (u != v)gb[v].eb(i);
		}
		if (n <= 20) {
			dfs20(1);
			printf("%lld\n", ans);
		} else {
			memset(vb, 0, sizeof(vb));
			memset(del, 0, sizeof(del));
			rt.clear();
			for (int i = 1; i <= n; ++i) {
				if (!vb[i]) js(i, 0), rt.eb(i);
			}
			dfsplus(0);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

T3

#哈密顿回路

难耶，瞎编了一个规律，得了28。

首先有一个做法，但是是从一个论文里来的，恶心。

还有一个就是比较复杂的做法，但好想，就是找一个长度能全部出现过，这样显然小于这个长度的都全部出现过，长度大于它的也显然没有重复。然后就可以来找环，或者说再想想或许能想到第一个比较简单的做法。

code
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
#include <bits/stdc++.h>
using namespace std;
int n;
basic_string<bool> s;
map <basic_string<bool>, bool> mp;
int main() {
	freopen("substring.in", "r", stdin);
	freopen("substring.out", "w", stdout);
	scanf("%d", &n);
	if (n == 1) {
		puts("0");
		return 0;
	}
	int k = 0, nn = n;
	while (nn) {
		++k, nn >>= 1;
	}
	--k;
	for (int i = 0; i < k; ++i) {
		putchar('0');
		s.push_back(0);
	}
	mp[s] = 1;
	for (int i = k; i < (1 << k); ++i) {
		s.push_back(1);
		if (mp[s.substr(max(0, i - k + 1), i + 1)]) {
			s[i] = 0;
		} else {
			mp[s.substr(max(0, i - k + 1), i + 1)] = 1;
		}
		putchar(s[i] + '0');
	}
	for (int i = (1 << k); i < n; ++i) {
		putchar('0');
	}
	return 0;
}

后记

行，很行，感觉大受震撼，大家都是神犇。

  • 标题: 6.27 测试
  • 作者: 混氏新子
  • 创建于 : 2023-07-02 15:29:22
  • 更新于 : 2023-09-24 19:11:47
  • 链接: https://blog.huasushis.cn/2023/6.27 测试/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 7.3 测试 7.3 测试 6.28 测试 6.28 测试
推荐阅读
6.29 测试 6.29 测试 7.3 测试 7.3 测试
评论
此页目录
6.27 测试
  1. 前情提要
  2. 题解
    1. T1
    2. T2
    3. T3
  3. 后记