杂题
T1
(MATCH)给出一个左边n个点,右边m个点的二分图,从左边第i个点到右边第j个点存在一条边的概率为p(i,j),求这个二分图的期望最大匹配的大小
n<=5,m<=100
Solution :
DP套DP?
看起来简单系列
考虑Hall定理,设计状态表示有哪些左部的集合当前满足Hall定理,把这些集合压起来(?),合法的状态只有几百个.
转移的时候,枚举右边的第i个点和左边的连边状态,然后DP计算一下新状态,再转移即可.
方程:
dp(S,i)表示
T2
给出一个长度为N的序列,其中有一些数字已经模糊不清了,请你求出可能的最长上升子序列长度.
N<=10^5
Solution :
T3
(coin)一个n×m的矩阵棋盘,有一些格子被ban(?)掉了,其余的每个格子你可以指定放或不放硬币.
放完硬币后你可以做若干次操作,每次操作你可以指定一个方向(上下左右),使所有的硬币尝试向那个方向移动一格.如果一个硬币的目标格子被ban那么它不会移动.硬币可以被移出棋盘(然后就掉在外面回不来了).一个格子上可以有多枚硬币.
求有多少种放硬币的方案,满足存在一种操作序列使至少一枚硬币被移出棋盘,同时,至少有一枚硬币留在棋盘上.
n,m<=40
Solution :
从每个方向暴力搜索,O(4^(n×m))
考虑方案的全集,假设有tot个格子没有被ban,那么就是2^tot-1.
T4
(Complete the Graph)给出一个图,一些边等待你赋权(最小为1).请你找到一中赋权方式,使得s到t的最短路为L.
n<=1e3,m<=1e4,L<=1e9.
Solution :
T5
(OldBridges)给定一个n个点的无向图.有些边可以经过无限次,有些边两个方向一共最多经过两次.
Alice计划从a1到a2进行an次往返旅行,同时Bob也计划从b1到b2进行bn次往返旅行.请问是否存在一种方案,使得两人的计划同时被满足.
n<=50.
Solution :
T6
(P3731 HAOI2017新型城市化)给出一个有向图,请计算对于s到t的最小割而言,每条边是否可能在最小割内和每条边是否一定在最小割内.
n<=4000,m<=60000.
Solution :
T7
(向再见说再见)
T8
给出一个长度为n的数列,要求从中取出若干个数,使得平均数小于等于中位数.
n<=40,ai<=10^9