Codeforces Round# 309 (Div. 2) 总结

http://codeforces.com/contest/554

嗯。。其实这场我是做的div1。无奈太弱,滚回了div2。赛后补完了这场Div2的题。。

A:给出一个串\(s,(|s|\le 20)\),可以在该串任意地方插入一个字符,问能组成多少种字符串

枚举地方再枚举字符。。set大法好

#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<iostream>
using namespace std;
string s;
set<string> st;
int main() {
	cin >> s;
	int ans = 0;
	for (int i = 0; i <= s.length(); ++i)
		for (char c = 'a'; c <= 'z'; ++c) {
			string ts = s;
			ts.insert(i, 1, c);
			if (st.find(ts) == st.end()) {
				++ans;
				st.insert(ts);
			}
		}
	cout << ans << endl;
}

B:给出一个\(n\times n(n\le 100)\)的01矩阵,可以进行任意次操作,将某一列的值全部反转。问最多可以有多少行全是1

对于每一行,把这一行0的位置全部取出来组成一个集合。发现对于任意两行,只有在集合完全相等的情况下能满足这两行全是1。问题转化成了求最多有多少行完全相同。\(O(n^3)\)暴力即可

#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN = 100 + 5;
char mat[MAXN][MAXN];
int main() {
	int n;
	int ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%s", mat[i]);
	for (int i = 0; i < n; ++i) {
		int t = 0;
		for (int j = 0; j < n; ++j)
			if (strcmp(mat[i], mat[j]) == 0)
				++t;
		ans = std::max(ans, t);
	}
	printf("%d\n", ans);
}

C:有\(k\)种颜色,每种颜色有\(c[i]\)个物品。对于任意颜色\(i(2\le i\le k)\),第\(i\)种颜色的最后一个物品一定要在第\(i-1\)中颜色的最后一个物品之后取出。每种颜色物品没有区别。问有多少种取法。(\(\sum c[i]\le 1000\))

令\(dp[i]\)代表取出所有前\(i\)种颜色物品的方案数。考虑因为第\(i\)种物品的最后一个一定是放在最后的,所以这个确定了,剩下的就在前面随便放。再定义\(sum[i]\)代表前\(i\)种物品一共有多少个,\(num(n,m)\)代表在\(n\)个物品里面插入\(m\)个物品的方案数,那么\(dp[i]=dp[i-1]*num(sum[i-1],c[i])\)

现在的问题是如何求\(num(n,m)\)

\(n\)个物品产生了\(n+1\)个空位,定义\(x_i\)为第\(i\)个空位里放的物品数,则有\(x_0+x_1+x_2+\cdots+x_i=m\),给左边每一项加上1,有\((x_0+1)+(x_1+1)+(x_2+1)+\cdots+(x_n+1)=n+m+1\)。用插板法可得,答案为\(C_{n+m}^n\)

那么\(dp[i]=dp[i-1]*C_{sum[i-1]+c[i]-1}^{sum[i-1]}=dp[i-1]*C_{sum[i]-1}^{sum[i-1]}\)

递推就行了。。我脑残写了记忆化搜索。。

#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN = 1000 + 5;
const int MOD = 1000000007;
typedef long long LL;
int C[MAXN][MAXN];
LL dp[MAXN];
void init() {
	memset(dp, -1, sizeof dp);
	C[0][0] = 1;
	for (int i = 0; i < MAXN; ++i)
		for (int j = 0; j <= i; ++j) {
			if (j == 0) C[i][j] = 1;
			else (C[i][j] = C[i - 1][j] + C[i - 1][j - 1]) %= MOD;
		}
}
int c[MAXN];
int sum[MAXN];
int k;
LL src(int i) {
	if (i == 0) return 1;
	LL& ans = dp[i];
	if (ans >= 0) return ans;
	ans = src(i - 1) * C[sum[i] - 1][sum[i - 1]] % MOD;
	return ans;
}
int main() {
	init();
	scanf("%d", &k);
	for (int i = 0; i < k; ++i) scanf("%d", c + i);
	sum[0] = c[0];
	for (int i = 1; i < k; ++i) sum[i] = sum[i - 1] + c[i];
	printf("%d\n", (int) src(k - 1));
}

D:一个置换满足A性质当且仅当把这个置换拆成循环,然后每个循环把最大的那个数放在最前面,然后以第一个数为关键字sort所有循环,拆掉括号后与原来一样。问长度为\(n\)的第\(k\)个满足A性质的置换是什么(字典序)。

首先我们挖掘一下题目中的条件。。对于长度\(n\),包含\(n\)的循环一定是放在最后一个的。如果这个循环长度是1,显然是满足条件的。如果长度是2,仅当和循环的另一个元素是\(n-1\)的时候满足条件。如果长度是3或者更多,怎么安排都不满足条件。所以处在最后的那个循环长度一定是1或者2。那么去掉最后的1个或2个元素,剩下元素的依然满足条件。

定义\(f[i]\)为长度为\(i\)的串满足要求的个数,则有\(f[i]=f[i-1]+f[i-2]\),很容易看出是个fibonacci数列,\(f[i]=fib[i+1]\)。

那么怎么构造呢。。

假如我们要构造长度为\(n\)的第\(k\)个序列,如果\(k\le f[i-1]\),那么我们就先构造出来长度为\(n-1\)的第\(k\)个序列,给这个序列所有元素全部加上1,再在最前面添加一个1即可。如果\(k>f[i-1]\),那么我们就先构造出长度为\(n-2\)的第\(k-f[i-1]\)个序列,再在最前面添加一个\(2\)一个\(1\)即可。

vector大法好

#include<cstdio>
#include<vector>
#include<algorithm>
using std::vector;
typedef vector<int>::iterator vit;
typedef long long LL;
LL fib[105];
void init() {
	fib[1] = fib[2] = 1;
	for (int i = 3; i <= 100; ++i)
		fib[i] = fib[i - 1] + fib[i - 2];
}
vector<int> work(int n, LL k) {
	vector<int> ans;
	if (n == 1) ans.push_back(1);
	else if (n == 2) {
		if (k == 1) ans.push_back(1), ans.push_back(2);
		else ans.push_back(2), ans.push_back(1);
	}
	else {
		if(k <= fib[n]) {
			ans = work(n - 1, k);
			for (vit it = ans.begin(); it != ans.end(); ++it)
				(*it) ++;
			ans.insert(ans.begin(), 1);
		}
		else {
			ans = work(n - 2, k - fib[n]);
			for (vit it = ans.begin(); it != ans.end(); ++it)
				(*it) += 2;
			ans.insert(ans.begin(), 1);
			ans.insert(ans.begin(), 2);
		}
	}
	return ans;
}
int main() {
	init();
	int n;
	LL k;
	scanf("%d%I64d", &n, &k);
	vector<int> ans = work(n, k);
	for (vit it = ans.begin(); it != ans.end(); ++it)
		printf("%d%c", *it, it == ans.end() - 1 ? '\n' : ' ');
}

E:有\(n(n\le 100,000)\)个人,任意两个人要么\(Love\),要么互相\(Hate\)。对于任意三个人,要么相互Love,要么\(A\ Love\ B,C\ Hate\ A,C\ Hate\ B\)一些关系已经给出,让你确定剩下的关系,问有多少种方案。无解输出0。

每个点拆成2个。。用经典的并查集操作维护。即,若\(A\ Love\ B\),合并\(A,B\)和\(A’,B’\)。若\(A\ Hate\ B\),合并\(A’,B\)和\(A,B’\)。发现冲突直接输出\(0\)。否则在合并完后缩点,就能得到一些孤立的没有边相连的\(n’\)个点。如果将这些点用\(n’-1\)条边连成一条链(即\(Hate\)关系或\(Love\)关系),则所有关系都会随之确定下来,并且不会有冲突。而这\(n’-1\)条边所代表的关系是随便选的,所以答案就是\(2^{n’-1}\)

#include <cstdio>
#include <algorithm>
const int MOD = 1000000007;
const int MAXN = 100000 + 5;
int n, m;
int pa[MAXN << 1];
void init() {
	for (int i = 1; i <= 2 * n; ++i)
		pa[i] = i;
}
int find(int x) {
	return pa[x] == x ? x : pa[x] = find(pa[x]);
}
void unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y) return;
	pa[x] = y;
}
int main() {
	scanf("%d%d", &n, &m);
	init();
	while (m--) {
		int u, v, k;
		scanf("%d%d%d", &u, &v, &k);
		if (k == 1) {
			if (find(u + n) == find(v)) {
				puts("0");
				return 0;
			}
			unite(u, v);
			unite(u + n, v + n);
		}
		else {
			if (find(u) == find(v)) {
				puts("0");
				return 0;
			}
			unite(u + n, v);
			unite(v + n, u);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= 2 * n; ++i) if (pa[i] == i)
		cnt++;
	cnt = cnt / 2 - 1;
	int ans = 1;
	for (int i = 0; i < cnt; ++i)
		ans = ans * 2 % MOD;
	printf("%d\n", ans);
}

 

发表评论

电子邮件地址不会被公开。