TCO2015 level3 题解
只做了几个傻逼题 已经停更了 放出来算了
1A.Revmatching
题目描述：给一张$n\times n$的二分图，每条边有权值，删除权值和尽量小的边使得其不存在完备匹配。
难度：★
难度这一栏都是瞎扯的
时间复杂度：$O(2^nn\log n)$这一栏也是瞎扯的
根据Hall定理，只需要使得某个左集合的子集$L'$的邻集$R'$小于它的大小即可。枚举$L'$，算出需要给多少钱才能把某个点从$R'$中辞退，贪心地搞就行了。
1B.TheTreeAndMan
题目描述：自己去tc上看吧，略鬼畜，大概就是求一棵树中人的个数，人的定义是
1
|
|
2
/|\
/ | \
3 5 4
/ \
/ \
6 7
难度：★
时间复杂度：$O(N)$
大概就是。。首先枚举点$4$，设它有$C$个儿子，子树大小为$S_1,S_2,\dots,S_C$，那么选$(4,5,6)$的方案数为$\binom{\sum S}{2}-\sum\binom{S}{2}$。记选出的点$4$为$x$，方案数为$w_x$。
然后枚举点$1$，设它有$D$个儿子，子树大小$T_1,\dots,T_D$，那么选$(2,3,4,5,6)$方案数为为
$$\sum_{i=1}^D\sum_{x_4\in subtree(x_1,i)}w_{x_4}(\binom{\sum_{j\ne i}T_j}{2}-\sum_{j\ne i}\binom{T_j}{2})$$
枚举$x_1$，算出$\sum T$和$\sum T^2$，枚举$x_4$，可以得到剩下的$\sum T$和$\sum T^2$就好。
事实上如果你记一个$w$的子树和，那么这题可以做到$O(N)$。
然后是点$0$的数量，就是点$1$的严格祖先数。
1C.DevuAndBeautifulSubstrings
题目描述：一个01串是美丽的，当且仅当它任意两个相邻字符不想等。求长度为$N$，恰有$cnt$个美丽子串的01串的个数。子串不同当且仅当它们的位置不同，比如说0001有$5$个美丽子串。
难度：☆
时间复杂度：$O(N^4)$，其中$cnt=O(N^2)$。
差分后就是说，求长度为$N-1$的$01$串的个数的两倍。这个$01$串的性质：设有$K$段连续是$1$的段，长度分别为$a_1,a_2,\dots,a_K$，那么$\sum_{i=1}^Ka_i(a_i+1)/2=cnt-N$。
$f_{i,j}$表示长度为$i$，$\sum a(a+1)/2=j$的串的个数。那么考虑每次往串后面加入$i_0$个$1$和$1$个$0$。就是
$$f_{i,j}\to f_{i+i_0+1,j+i_0(i_0+1)/2}$$
当然$f_{N-1,cnt-N}$统计的是以$0$结尾的串的个数。。枚举最后一段$1$有多长就好。
$$\sum_{i=0}^{N-1}f_{N-1-i,cnt-N-i(i+1)/2}$$
2A.TrianglePainting
题目描述：有$N$个三角形，每个三角形有一定概率被选中，求它们的Minkowski和的面积的期望。
难度：★★
时间复杂度：$O(N^2)$，想做到$O(N\log N)$说不定也可以
假设每条边的贡献是它底下那块梯形的有向面积，让我们来考虑每一条边的贡献，发现就是要求它的期望高度$Eh$，而这个$Eh$只与极角$\le $它的边有关。对于极角$\le $它的边$(\Delta x,\Delta y)$，如果与它是同一个三角形里的，就给$Eh$增加$\Delta y$，否则就增加$prob\times \Delta y$。
注意，所有的三角形要么都是顺时针，要么都是逆时针。否则会wa。
3B.CommutativeMapping
题目描述：$S=\{0,1,\dots,N-1\}$，$f,g$都是$S\to S$的函数，且$\forall 0\le i<N,f_{g_i}=g_{f_i}$，给出$f$，求$g$的个数。
难度：★☆
时间复杂度：$O(N^2)$
假设确定了$g_i$那么可以确定$g_{f_i}$。因为$g_{f_i}=f_{g_i}$。
这样我们可以给每个$i$向$f_i$连边。这样连成了一些环套树。假设只有树的情况，用$f_{i,j}$表示$g_i=j$时，$i$的子树中点的$g$值的方案数。那么
$$f_{i,j}=\prod_{k\text{ is a child of }i}(\sum_{g_q=j}f_{k,q})$$
这样可以求出去掉所有环之后的答案。
考虑接上环，对于一个环$c_1,c_2,\dots,c_l$枚举环上所有数的$g$值(因为确定了一个就可以确定所有的，所以只有$O(N)$种$g$值)，乘起来加上就是环的方案数。具体说：
$$ANS=\sum_{\text{function }g}\prod_{i=1}^lf_{c_i,g_{c_i}}$$
把所有环的$ANS$乘起来就好。
评论 (0)