$f[i][j]$:以i为根的子树,且i在原图中的映射为j时的方案数 $f[i][j]=\prod{u\in i.child}\Sigma ^n {k=1} f[u][k]*map[i][u]$ 但这样求出的dp值包括了不合法的重复选点状态。重复选了一个的,两个的……选了(1,2)的,(1,3)的 ...
NOIP2010初赛部分解析
第 14 题$Description$在整数的补码表示法中,以下说法正确的是( )。 A. 只有负整数的编码最高位为1 B. 在编码的位数确定后,所能表示的最小整数和最大整数的绝对值相同 C. 整数0只有一个唯一的编码 D. 两个用补码表示的数相加时,如果在最高位产生进位,则表示运算溢出 ...
「构造博弈」[POJ1740]A New Stone Game
$Solution-MashiroSky$ 以下证明思路来自$MashiroSky$ 首先可以发现,只有一堆石子时先手必胜。 然后,若有两堆数目相同的石子,无论先手做什么,后手在另一堆完成同样的操作,就可以保证胜利。因此后手必胜。 这个结论可以推广到所有偶数堆且两两相等的情况。 而其他情况, ...
「容斥+dp」[CQOI2011]放棋子
$Description$在一个m行n列的棋盘里放一些彩色的棋子,使得每个格子最多放一个棋子,且不同 颜色的棋子不能在同一行或者同一列。有多少种方法? $Solution$ 由于不同色的棋子不能放在同一列,每种颜色的棋子的放置是相互独立的。 因此可以考虑dp处理。 设$f[i][j][k]$:前k ...
「学习笔记」基环树
$Recommend$基环树学习笔记-$cly$_$none$:写得非常清晰漂亮。 $Find\;the\;Loop$该代码可以找二元环。 $code\;by\;$$Gion$ vector<int> G[MAXN]; //基环树int fa[MAXN]; //dfs时 ...
一些好用的软件/网址推荐!
软件1.$vscode$自从拥有了它,我果断抛弃了$Dev$。 但它不带编译环境,有点麻烦。 c++编译环境-$tangming$ 它的高亮是真的很漂亮,主题也非常多,可以在扩展商店下载。 冰与火之歌$Winter\;is\;coming$ 哈利波特$Hogwarts$都贼靓! 原著党蠢蠢欲动 下面 ...
hexo一路坑
$Prologue$2019.8.18,我的博客正式搭建完成(基础功能和我喜欢的美化基本上都有了。) 中间出过的锅也不少,但结局也还算圆满。 将一路踩过的坑,记述于此。 $Recommend$$hexo$史上最全搭建教程-$zjufangzh$ $hexo$博客搭建指北-$ouuan$ $1.nod ...
「题解」 [HAOI2015]树上染色
$Description$$Solution$分开计算每条边的贡献。 边对点产生贡献,当且仅当边的两端都有点。 于是对于$(u,fa)$,$u$的子树选中了$x$个点,我们可以分开计算白点和黑点的贡献$sum:$ $sum_{(u,fa)}=x(k-x)+(size[u]-x)(n-size[u]- ...
「学习笔记」模拟退火
引用:浅谈$SA-M$_$sea$ $SA$学习笔记-$99NL$ 退火流程:$1.$由上一次接受的解$pre$出发,随机得到一个可能解$x$。 $2.$若当前解优于最优解$ans$,覆盖最优解。 $3.$否则$x$将会以$exp(delta/T)$的概率成为下一次的$pre$。 $4.T*\Del ...