http://codeforces.com/contest/1314

A. Recommendations

 

题意：有n个数，要求所有数不能相同，并给出了每个数+1所需的值，问最小花费。

并查集，贪心

容易得到要求所有数的最终位置乘以花费的和最小，可以贪心，因为花费大的多移动一个大于花费少的多移动一个。

把花费从大到小排序，遍历时遇到相同的数说明要移动了，并且一定是移动后遇到的那个，移动到连续块的最大值处，而连续块可以并查集维护最大值，每次把移完的值x与x+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
map<ll, ll>par;
ll find(ll x) { if (!par.count(x))par[x] = x; return par[x] == x ? x : par[x] = find(par[x]); }
void uni(ll x, ll y) { par[find(x)] = find(y); }
int n;
typedef pair<ll, ll>pii;
pii a[N];
bool cmp(const pii& a, const pii& b) { return a.second == b.second ? a.first<b.first : a.second>b.second; }
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i].first), par[a[i].first] = a[i].first;
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i].second);
	sort(a + 1, a + n + 1, cmp);
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ll x = find(a[i].first);
		ans += (x - a[i].first)*a[i].second;
		uni(x, x + 1);
	}
	cout << ans << endl;
	return 0;
}

 

D. Tourism

 

题意：有向完全图，从1出发，要求走k步回到1，总边权值最小，且不能经过奇环。

二分图+随机

无向图上没有奇环就一定是二分图，但有向图也可能没有环，但是本题一定是几个环拼在一起，否则没法一笔走回去。

那么就是二分图了，照例是枚举两个点集。

随机给点涂色，规定只能走连接异色点的边，记 d[i][j]d[i][j] 为经过 jj 步到达点 ii 的最小值。再通过中介点 kk 更新。

多随机几次就好了，不会算就随机到复杂度上限，注意换种子。0.o

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 int N = 2e5 + 10;
int n, m;
int w[100][100], d[100][20], c[100];
int main() {
	srand(time(0));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)scanf("%d", &w[i][j]);
	}
	int T = 10000, ans = INF;
	while (T--) {
		memset(d, 0x3f, sizeof(d));
		d[1][0] = 0;
		for (int i = 1; i <= n; i++)c[i] = rand() % 2;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++) {
					if (c[j] ^ c[k])d[j][i] = min(d[j][i], d[k][i - 1] + w[k][j]);
				}
			}
		}
		ans = min(ans, d[1][m]);
	}
	cout << ans << endl;
	return 0;
}