TCO2015 level3 题解

r_64 posted @ 2016年4月20日 20:37 in 未分类 , 429 阅读

只做了几个傻逼题 已经停更了 放出来算了

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$乘起来就好。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter