T20200902

Posted on Edited on In Word count in article: 1.5k Reading time ≈ 5 mins.
大东辰的测试

T1 石头剪刀布(rps)

那么，我们就枚举最后赢得人是谁

然后归并保证字典序最小

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10;
const int Mod = 1e9 + 7;

int n, _a[3];
const char s[] = "RPS";

string Get(int n, int x)
{
	if (!n) {
		string ans;
		ans.push_back(s[x]);
		return ans;
	}
	string a = Get(n - 1, x), b = Get(n - 1, (x + 1) % 3);
	return a < b ? a + b : b + a;
}

bool Check(int x)
{
	int a[3] = {}, a0[3] = {};
	a[x] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= 2; ++j) a0[j] = a[j];
		for (int j = 0; j <= 2; ++j) a[(j + 1) % 3] += a0[j];
	}
	for (int i = 0; i <= 2; ++i) if (a[i] != _a[i]) return 0;
	cout << Get(n, x) << endl;
	return 1;
}

int main()
{
	scanf ("%d %d %d", _a + 0, _a + 1, _a + 2);
	while ((1 << n) != _a[0] + _a[1] + _a[2]) ++n;
	for (int i = 0; i <= 2; ++i)
		if (Check(i)) exit(0);
	puts("IMPOSSIBLE");
}

T2 投票(vote)

将 \(p_i\) 从小到大排好序，则存在一个最优方案，其中选择的同学是一段前缀和一段后缀

证明：

​ 假设有一个选择的同学，他前后都存在未选的同学，考虑固定其他选中的同学时这个同学的概率的贡献，是一个一次函数，所以换成前后一定不劣。

Q.E.D

现在的问题是，对 \(\forall i\)，求出选择前\(i\)个和后\(k-i\)个时平票的概率

一个想法是支持插入删除的 \(dp\)，但有精度问题

\(pre_{i,j},\;suf_{i,j}\)表示选择前/后\(i\)个同学，有 个投”好”的概率

时间复杂度\(O(n)\)

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 2000 + 10;
const int Mod = 1e9 + 7;

int n, m, k;
double p[Maxn], ans;
double Pre[Maxn][Maxn], Suf[Maxn][Maxn];

int main()
{
	scanf ("%d %d", &n, &k);
	for (int i = 1; i <= n; ++i) scanf ("%lf", p + i);
	sort (p + 1, p + n + 1);

	Pre[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = n; j >= 1; --j) Pre[i][j] = p[i] * Pre[i - 1][j - 1] + (1 - p[i]) * Pre[i - 1][j];
		Pre[i][0] = (1 - p[i]) * Pre[i - 1][0];
	}

	Suf[n + 1][0] = 1;
	for (int i = n; i >= 1; --i) {
		for (int j = n; j >= 1; --j) Suf[i][j] = p[i] * Suf[i + 1][j - 1] + (1 - p[i]) * Suf[i + 1][j];
		Suf[i][0] = (1 - p[i]) * Suf[i + 1][0];
	}

	m = k >> 1;
	for (int i = 1; i <= k; ++i) {
		int j = n + i + 1 - k;
		double temp(0);
		for (int t = 0; t <= k; ++t) temp += Pre[i][t] * Suf[j][m - t];
		ans = max(ans, temp);
	}
	printf ("%.9f", ans);
}

T3 工厂(factory)

还没有改

首先把问题转化为二分图模型，左边 \(n\) 个点表示工人，右边 \(n\) 个点表示机器，左右两个点有边当且仅当对应工人会操作对应机器。无论哪种情况下所有机器都能有人操作，就等价于，任意一个极大匹配都是完美匹配

考虑问题的一个弱化版本：判断是否任意一个极大匹配都是完美匹配

观察发现，任意一个极大匹配都是完美匹配\((a)\) ，如果任意一个联通块都是左右点数相等的完全二分图\((b)\)。

证明：

从\(b\)推出\(a\)是显然的，下面只用证明从\(a\)推出\(b\)。

反证法。

假设存在一张二分图，存在一个联通块不是左右点数相等的完全二分图，同时满足任意一个极大匹配都是完美匹配。如果这个联通块左右点数不相等，那么它就不存在完美匹配，显然矛盾。否则这个联通块不是完全二分图，设左边的\(a\)点和右边的\(b\)点之间没有边，随便找一条从\(a\)到\(b\)的简单路径，记作\(p\)。选择\(p\)上的奇数边，再随便选一些边构造一个极大匹配，那么这个极大匹配必定是完美匹配。把奇数边改成偶数边，其他的边不变，那么除了\(a,b\)以外的点都在匹配上，所以得到了一个非完美匹配的极大匹配，矛盾。

Q.E.D.

回到原问题，对每个联通块求出它在左右的点数，记作\((x_i, y_i)\) ，现在的问题相当于，将 \((x_i,y_i)\) 分成若干个集合，\(\forall s\) 满足\(\sum_{i\in s}x_i=\sum_{i\in s}y_i\)，最小化 \(\sum_s(\sum_{i\in s}x_i)^2\)。

状压 \(dp\)。 \(dp_{s,i}\)表示集合 中已经划出的满足要求的集合的 \(\sum x=i\) 的最小代价。

转移就枚举 \(x\)，从\(dp_s\) 转移到 \(dp_{s\cup\{x\}}\)。

对所有相同的 \((x_i,y_i)\) 只用关心个数，当 \(n=30\) 时，本质不同的集合个数的最大值是 \(173032\) ，可以通过本题。

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
#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T &x,const T &y)
{
	if(x>y)x=y;
}
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=30+2,U=2e5;
int n;
char s[N][N];
int dp[U][N];
pii q[N*2];int m,cnt[N*2],w[N*2];
bool vis[N*2];

pii operator +(const pii &a,const pii &b)
{
	return pii(a.first+b.first,a.second+b.second);
}
pii operator *(const pii &a,int x)
{
	return pii(a.first*x,a.second*x);
}
void operator +=(pii &a,const pii &b)
{
	a=a+b;
}
int sqr(int x)
{
	return x*x;
}

int main()
{
		scanf("%d",&n);
		rep(i,1,n)scanf("%s",s[i]+1);
		m=0;
		rep(i,1,n*2)vis[i]=0;
		rep(i,1,n*2)
		if(!vis[i])
		{
			deque<int>nq;
			auto push=[&](int x) { if(!vis[x]){nq.push_back(x);vis[x]=1;} }; 
			push(i);
			pii now=pii(0,0);
			while(!nq.empty())
			{
				int x=nq.front();nq.pop_front();
				if(x<=n)
				{
					++now.first;
					rep(y,1,n)
					if(s[x][y]=='1')push(y+n);
				}
				else
				{
					++now.second;
					rep(y,1,n)
					if(s[y][x-n]=='1')push(y);
				}
			}
			q[++m]=now;
		}
		sort(q+1,q+m+1);
		int m0=m;m=1;
		cnt[1]=1;
		rep(i,2,m0)
		{
			if(q[i]==q[m])++cnt[m];
			else
			{
				q[++m]=q[i];
				cnt[m]=1;
			}
		} 
		w[1]=1;
		rep(i,2,m+1)w[i]=w[i-1]*(cnt[i-1]+1);
		rep(s,0,w[m+1]-1)
		rep(i,0,n)dp[s][i]=N*N;
		dp[0][0]=0;
		cerr<<w[m+1]<<endl;
		rep(s,0,w[m+1]-1)
		{
			pii sum=pii(0,0);
			rep(i,1,m)sum+=q[i]*(s%w[i+1]/w[i]);
			if(sum.first==sum.second)
			{
				rep(i,0,sum.first-1)chmin(dp[s][sum.first],dp[s][i]+sqr(sum.first-i));
			}
			rep(i,1,m)
			if(s%w[i+1]/w[i]<cnt[i])
			rep(j,0,n)chmin(dp[s+w[i]][j],dp[s][j]);
		}
		int sum=0;
		rep(i,1,n)
		rep(j,1,n)sum+=s[i][j]=='1';
		printf("%d\n",dp[w[m+1]-1][n]-sum);
}