题解：CF850D Tournament Construction

考察兰道定理的证明。

首先由题目知兰道定理是充要条件，则直接

\text{DP}

出符合定理要求的得分序列即可。观察

f(x) = {x \choose 2}

和

g(x) = 30x

的增长速度可知最大的

n

在

60

左右，该部分复杂度为

O(n^2mA)

，其中

A = \max\{a\}

。

然后构造一个竞赛图。先令

i \to j

存在当且仅当

i > j

，此时我们将得到得分序列

t

。设最终得分序列需要为

s

（已排序），则使用如下调整法构造：

找到最小的 $t_p$ ，使得 $t_p < s_p$ 。若有多个，找 $p$ 最大的那一个；
找到 $p$ 后面的最小 $q$ ，使得 $t_q > s_q$ 。
此时 $t_p$ 和 $t_q$ 差值至少是 $2$ ，则一定有点 $x$ 满足路径 $q \to x \to p$ 存在（否则差值最大是 $1$ ），反转这条路径，有 $t_p \larr t_p + 1, t_q \larr t_q - 1$ ；
结合兰道定理的必要性知最开始 $t$ 的前缀和数组达到下界，且整个过程中 $t$ 的前缀和数组的每个位置不大于 $s$ 的对应位置，因此总能找到 $p, q, x$ 。这便是兰道定理充分性的证明。

CPP

/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 65;
int m, a[N], n, s[N], t[N]; bool dp[35][N][N * 35], mp[N][N];
inline bool check(int n, int sum) {return (sum >= n * (n - 1) / 2);}
inline void flip(int x, int y) {mp[x][y] ^= 1, mp[y][x] ^= 1;}
inline void take(int ID, int remain, int val)
{
	if(!ID && !remain && !val) return ;
	if(val >= a[ID] && dp[ID][remain - 1][val - a[ID]])
		take(ID, remain - 1, val - a[ID]), s[++n] = a[ID];
	else if(val >= a[ID] && dp[ID - 1][remain - 1][val - a[ID]])
		take(ID - 1, remain - 1, val - a[ID]), s[++n] = a[ID];
	else assert(0);
}
inline bool judge()
{
	for(int i = 1; i <= n; ++i) if(s[i] != t[i]) return true;
	return false;
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> m;
	for(int i = 1; i <= m; ++i) cin >> a[i];
	sort(a + 1, a + m + 1);
	
	dp[0][0][0] = true;
	for(int i = 0; i <= m; ++i)
	{
		for(int j = 0; j <= 61; ++j)
		{
			for(int k = 0; k <= j * 30; ++k)
			{
				if(i && check(j + 1, k + a[i])) dp[i][j + 1][k + a[i]] |= dp[i][j][k];
				if(check(j + 1, k + a[i + 1])) dp[i + 1][j + 1][k + a[i + 1]] |= dp[i][j][k];
			}
		}
	}
	for(int i = 1; i <= 62; ++i)
	{
		bool flag = false;
		for(int j = 0; j <= i * 30; ++j)
			if(dp[m][i][j] && i * (i - 1) / 2 == j)
				{flag = true; take(m, i, j); break;}
		if(flag) break;
		if(i == 62) {cout << "=(" << '\n'; return 0;}
	}
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j < i; ++j)
			mp[i][j] = true, ++t[i];
	while(judge())
	{
		int p = 0, q = 0;
		for(int i = 1; i <= n; ++i) if(t[i] < s[i]) {p = i; break;}
		while(t[p] == t[p + 1]) ++p;
		for(int i = p + 1; i <= n; ++i) if(t[i] > s[i]) {q = i; break;}
		if(mp[q][p]) flip(p, q), --t[q], ++t[p];
		else
		{
			for(int i = 1; i <= n; ++i)
			{
				if(mp[q][i] && mp[i][p])
					{flip(q, i), flip(i, p); --t[q], ++t[p]; break;}
			}
				
		}
	}
	
	cout << n << '\n';
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
			cout << mp[i][j];
		cout << '\n';
	}
	return 0;
}
/*

*/

题解：CF850D Tournament Construction

文章操作

相关推荐

评论

题解：CF850D Tournament Construction