2016.3.16测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------
这次的数据超水...
T1剪枝搜索有60分
T2贪心乱搞有70分，还有人贪心乱搞A了（唉...我的姿势水平还是不够高啊...)
题面大概可以在SuperOj上找到...
--------------------------------------------------------------
T1:
定义一种边叫初始边，当且仅当他的幻影包含了他经过的两点
然后前向路径定义为他的幻影和他的路径一样，除了没有包含路径的最后一个点之外
后向路径定义为他的幻影和他的路径一样，除了没有包含路径的第一个点之外
然后极小的梦幻路径求出来
一个梦幻路径前面接一个前向路径或者后面加一个后向路径还是一个梦幻路径
然后这样DP就好
--------------------------------------------------------------
T2:
位数相同的选一个老大，都连到老大身上
老大之间暴力枚举连边情况
位数不同的，最大流
考虑每个块内的父亲数量，每个人都需要有一个且只有一个父亲
对于一个(i,j)的边（i,j是位数），把它连向第i块和第j块，容量为1
流向哪边，就表示给这个块内的点增加一个父亲（另一块的老大）
然后每块向汇点连边，容量是这一块需要的父亲数
不能满流输出-1
然后，连接的块一样的点可以合并一下，这样就只有(lg(n)+1)^2个点了
--------------------------------------------------------------
T3:
50分是一个很naive的DP:
g[i][j][k]表示第i种袜子，前j个人，刚好卖出去k个的概率
转移也很naive:
g[i][j][k] = g[i][j-1][k]*(1-a[j][i]) + g[i][j-1][k-1]*(a[j][i])
初始值也很naive: g[i][0][0] = 1
显然是m*n^2的
然后有一个很naive的数组f,f[i][j]表示只带j个第i种袜子，期望卖出去多少个
然后他有一个很naive的转移: f[i][j] = Σ(k=0,n)min{j,k}*g[i][n][k]
显然也是m*n^2的
然后还有一个很naive的数组h,h[i][j]表示前i个袜子，已经选了j个了，期望卖出去几个
各个袜子的期望是独立的（这个自己yy一下就知道了，每种情况每个人只可能买一种袜子，因此这个袜子卖出去的期望（概率）只和这
个人买这种袜子的概率有关），因此做个naive的m*n^2的背包就行了
时间复杂度就是很naive的O(m*n^2）
接下来说标算：
其实就是上面那个的优化
首先注意到f[i][j]-f[i][j-1](为了方便记为d[i][j-1]，推一下公式发现d[i][j]=1-Σ(k=0,j)g[i][j][k])是随着j变大而递减的
因此考虑把f[i]排成一排，每个初始第二维(j)都是0
每次选一个d[i][j]最大的位置，往后推一位，更新下d[i]
如此这样做n次就好，最后每个位置的j就是这个袜子应该带几个
顺便，实现的时候g要记忆化一下
时间复杂度O(n*m)
--------------------------------------------------------------
评论 (0)
