Codeforces Round# 309 (Div. 2) 总结

http://codeforces.com/contest/554

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

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

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

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

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

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]}

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

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 data-recalc-dims=f[i-1]" />,那么我们就先构造出长度为n-2的第k-f[i-1]个序列,再在最前面添加一个2一个1即可。

vector大法好

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

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

 

发表评论

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

*