模拟测试20191017~18 lrd Day1& Day2

$Day1:$

$T1:位运算$

从低位到高位分类讨论就好了

记得判$inf$

 

$T2:集合论$

考场上差点就打线段树了

用一个数组维护,同时用一个变量代表当前总体$+$&&$-$的值

 

$T3:连连看$

如果只有一个白联通块那么答案十分简单

然而这题有许多块,需要考虑重复计算的情况

首先遍历所有白块,给所有他们边缘的u块染色

然后考虑每一种块,随便容斥一下就好了

用$Hashmap$后复杂度$O(8n^{2})$用$map$复杂度$O(8n^{2}log)$

 

$Day2:$

$T1:串串香$

 傻逼$hash$或者大神$kmp$

$T2:糊涂图$

 大神级概率$dp$

$T3:木叶下$

(感觉和动态$dp$神似,也可能是我自己$yy$)

转化一下题意:求一棵树去掉一条链之后,从这条链出发的最长路

倍增维护$dp[i][j]$表示从$i$到$i$的$2^{j}$辈祖先路径外的最长链

这样对于链顶以下的答案可以$O(log)$求出

链顶以上可以直接换根$dp$

原文地址:https://www.cnblogs.com/mikufun-hzoi-cpp/p/11699628.html