【纪中】Day1

【队伍统计】
题意:在n个人中,有m条矛盾关系(u, v),表示编号为u的人想要排在编号为v的人前面。询问矛盾关系不超过k条的排列。
这题早上没有做,也没听讲,但看了眼题目感觉是深搜或者状压dp。
这里采用状压dp。用S表示当前已经排好队的状态,则f[s][k]表示当前状态违背的矛盾关系。对于一个要新加入的i,需要满足i不在排列中。设i与当前排列产生的矛盾关系为q,
那么f[s][k]则可以转移到f[s|(1 << (i - 1)) ][k + q]。暴力转移时间复杂度是O(2^n * n ^ 2 * k)。
由于矛盾关系没有重复,则可以把与i有矛盾关系的用二进制来表示。矛盾关系数便可以表示为&操作后的1个数。
T1【序列问题】
题意:给出一个序列,求每个区间的最大最小值的乘积和。
以前做过一道看上去相似的题目,先暴力预处理,再线段树修改。今天也是怎么想,但显然不对。。。
正解对序列进行分治,考虑过mid的区间[l,r]对答案的贡献。枚举右端点r,那么当右端点的指针往右移时,max增加,min减少,左端点l满足max 𝑙 = min(𝑟),则可以左移。于是,相同的max、min的贡献就可以O(1)求出。序列分治可以用递归处理。
T2【带权排序】
题意:序列A的每一个数在一个区间中随机生成,每个位置有权值si,求排序后A的期望。
期望。。。不会化!不会求!没听懂!
T3【概率博弈 】
题意:给出一颗以1为根的树,树上权值随机生成,求从根节点到叶节点的期望。
设当前要求ans > x。因为只会是向大于x或小于x的方向走,设权值 >x的为1,否则为0.相当于有m - x + 1个1,x- 1个0,则问题转化为求f[1]的概率。可用树形背包来解决。

第一天给我的感觉是题目好难,唯一看的出解的还不需要做。下午的讲题有点难懂,第一题分治方法好理解,但最关键的前缀和处理则一句跳过。第二题期望本来就不会,还要化简。第三题转化听懂了,但树形背包是什么???

Day8

【日历游戏】
题意:对一个日期有两种操作:1.跳到日历上的下一天。2.跳到日历上的下个月的同一天(如果不存在,则不能这么做)。询问先手是否必胜。
博弈论+记忆化搜索,对于先手必胜的日期,它的下一天或下个月同一天先手必败。对于先手必败的日期,其后一天或下个月先手必胜。
【二叉查找树】
题意:求将n个数加入二叉树,并使其高度恰好为h的方案数。
考虑树形dp。设f[x][h]表示有x个节点的子树,并以x为父节点,高度为h的方案数,设g[x][h]表示有x个节点的子树,并以x为父节点,高度小于等于h的方案数。
那么f[x][h] = (f[x - 1][h - 1]*f[n - x][h - 1] - g[x - 1][h - 2] * g[n - x][h - 2]) * C(x - 1, n - 1);
由于f[x - 1]的相乘会计算重复的,所以要减去重复计算的,最后的排列组合是计算将剩下的数放入x的子树中的方案数。
【我们爱数数】
题意:规定第i人坐在i - 1、i、i + 1的位置上是开心的,询问使>=k的人开心的方案数。
DFS + DP + 容斥。令f[i][j][s]表示1-i位子有j个人已经坐下且这j个人一定开心,s表示i和i+1是否坐下。首先暴力枚举初始状态,即1、2位置是否坐人,坐的人是谁。
那么f[i][j][s >> 1 ] += f[i - 1][j][s];
f[i][j][(s | (1 << d)) >> 1] += f[i - 1][j - 1][s](d=0,1,2,分别表示第i-1,i,i+1个人坐第i个位置)。
最后判断一下初态和终态是否矛盾。
设ans[n][j]表示j个人一定开心的方案(存在重复)。ans[n][j] = f[n][j][s] * (n - j)!。
因为ans中剩下的n - j不一定是不开心的,所以在统计中会出现重复的状态。
最后用容斥来求方案数。

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

【POJ2411】Mondriaan's Dream

题意:

给出n*m的方阵,求用1*2的小矩形铺满有几种情况。

题解:

这题可以用状压dp来解决,但现在我用的是轮廓线dp(状压dp的一种,但在这题中比状压dp更优)。

我们可以从左到右、从上到下把方阵分成n*m个阶段。由于小矩形是1 * 2的, 所以对于每个阶段的决策有影响的只有当前这一行和上一行的一些部分。而上面“#”的部分是已经确定的,对当前点没有影响

如:1 2 3 4 5

1      # # # # #

2      # # 1 1 1

3      0 0 ?

·······

把对于决策有影响的阶段称为轮廓线(如上图的11100)

于是,可以用2^(m -1)来枚举轮廓线的状态。(m < n)

1表示被覆盖,0表示没被覆盖。

设(i, j)为当前阶段,k为当前轮廓线的状态

则可以得到转移方程:
不放: 下一个状态 now =  (k << 1) & ( (1 << m)  -  1)
dp[cur][now] += dp[cur ^ 1][k];

条件k&(1 << (m - 1))[即 [i-1][j]一定要被覆盖]
向上放: 下一个状态 now = ( (k << 1) | 1) & ( (1 << m)  - 1)
dp[cur][now] += dp[cur ^ 1][k];

条件!(k&(1 << (m - 1)))[即 [i-1][j]一定没被覆盖]
向左放: 下一个状态 now = ((k << 1)|3)&((1 << m) - 1)
dp[cur][now] += dp[cur ^ 1][k];

条件k&(1 << (m - 1)) && !(k&1)[即 [i-1][j]一定要被覆盖,[i][j-1]一定不能被覆盖]

时间复杂度O(n*m*2^m),由于一个点的状态只由它前一个点的状态转移来,可以开滚动数组来存储答案,最后答案dp[cur][2^m-1]

代码如下:

继续阅读【POJ2411】Mondriaan's Dream

矩阵填数

题意:

给出一些有限制的矩阵,求出满足要求的方案数。

可以发现,如果将每个矩形的四条边延长,可以将大矩形划分成不多于400个的小矩形。

对于每个有限制的矩形,只有两种情况:达到要求和未达到要求。最多有2^10种状态。

由于状态少,可以用状压DP来解决。

设f[tot][k]为第i个小矩形达到状态k的方案数,state[i][j]为小矩形tot满足要求每个有限制的矩形的状态

就有

  1. f[tot + 1][k|sta[i][j]] += (long long)f[tot][k] * (power(V[i][j], num[i][j]) -power(V[i][j] - 1, num[i][j]))
  2. f[tot + 1][k] += (long long)f[tot][k] * (power(V[i][j] - 1, num[i][j])

最后f[tot][(1<<n) - 1](tot是小矩形数,(1<<n) - 1是状态数)为答案

继续阅读矩阵填数

[BZOJ 2734] [HNOI 2012] 集合选数

状压 DP

考虑如何构造出题目要求的集合。构造这样一个矩阵:


     i         3i        (3^2)i     ...
    2i       2*3i      2*(3^2)i     ...
(2^2)i   (2^2)*3i   (2^2)(3^2)i     ...
   ...        ...           ...     ...

注意矩阵中不能存在大于 n 的数,故矩阵各行列数不一定相等

则在该矩阵中题目给的选数规则等价于选取矩阵中横、纵向不相邻的数。

因为实际上矩阵长宽较小,故可以考虑用状压 DP 解决方案数统计问题。

令 f[i][j] 表示该矩阵第 1~i 行,第 i 行选取情况为 j 时的方案数,其中 0 < j < 2^(矩阵第 i 行列数

易知若 j & (j>>1) != 0,即 j 中存在连续两位为 1 时, f[i][j] = 0

f[i][j] = f[i][j] + f[i-1][k],即 f[i][j] 由 f[i-1][k] 转移得到当且仅当 j & k == 0,即 j 与 k 不重叠。

那么这个矩阵中的方案数即为所有 f[r][j] 的和(r 为矩阵行数)。

但是发现这个矩阵中并不包含所有 1~n 的数。因此要以每个当前没有出现过的数为第一个数构造矩阵。由乘法原理可知,总答案为所有矩阵方案数的积。

代码如下:

继续阅读[BZOJ 2734] [HNOI 2012] 集合选数

BZOJ【2734】集合选数

题意

求出1~n中,x出现,2x、3x不出现的子集个数。

首先,我们可以先写出一个矩阵

1    2       4       8      16       32

3    6       12    24    48       96

9    18     36    72    144    288

使每个数都等于左边的数*2,上面的数*3

这样,满足要求子集就相当于在矩阵中取数,并且和这个数相邻的数不能被取出的数的集合。

于是可以用状压DP实现。

先用一串二进制数来表示每行的状态,0表示当前位没有取,1表示取了。

例如:00110,表示取第三、第四位的数,第一、二、五位不取。

要保证不取相邻的数,可以用位运算来实现,假设当前状态k,只要k&(k>>1) = 0即可。因为只要相邻的数没被同时取,那么k左移一位&k答案肯定为0

如:


1
2
3
4
0 0 1 0 1     0 1 1 0 0
  0 0 1 0 1     0 1 1 0 0
___________   ___________
0 0 0 0 0 0   0 0 1 0 0 0

同理,要使上下两行的状态可行,只要 k&j=0即可。

便得出转移方程

f[i][k] = sum(f[i - 1][y])  ( k&(k>>1) != 0 ,y&(y>>1) != 0, k&y !=0)

由于每次求解只能算当前矩阵出现的的数,于是要把每个还没出现过的数当作矩阵开头都算一次,再将其相乘。 继续阅读BZOJ【2734】集合选数