【考前冲刺Day2】骗分之旅

T1 x

今天唯一一道没有用骗分方法的题目,然而还是由于一个小细节写挂了orz

显然的是,如果两个数不互质,显然他们必须在一个集合里,于是我们可以将不互质的数连边,最后看有多少个联通块,答案就是\(2^{s}-2\)其中s就是联通块的个数.如果用暴力的方法来实现的话,时间复杂度是\(O(n^2)\)的.

我们可以只枚举每个数的质因子,来降低这一复杂度.


T2 y

考试的时候用的是dfs枚举,骗了30分,可以不枚举状态转而判断状态的存在性,可以骗到90分,然而还是过不了.

正解是动态规划,

出题人说:f[i][j][mask] 表示从 i 出发,j 结束,是否存在一条表示为 mask 的路径。

然而这样会T,得分甚至不如dfs,于是出题人又说

meet in the middle,对于每种可能的路径,枚举中间的那个位置判断。时间复杂度为\(O(2^\frac{d}{2} \times n \times (n + m) + 2^d \times n)\)

用了bitset,先放个表格方便理解代码:

变量名 变量类型 变量作用
g0[i] bitset 表示i点与哪些节点连权值为0的边
g1[i] bitset 表示i点与哪些节点连权值为1的边
dp[i] bitset 表示i状态可以以哪些点为终点
f[i] bitset 表示i状态可以以哪些点为起点

4 thoughts to “【考前冲刺Day2】骗分之旅”

发表评论

电子邮件地址不会被公开。 必填项已用*标注