题目链接:咕 闲扯:这题暴力分似乎挺多,但是一些奇奇怪怪的细节没注意RE了,还是太菜了 分析:首先我们考虑最naiive的状压DP ,$f[u][v][state]$表示u开头,v结尾是否存在一条表示为state的路径,这个好转移不讲了,但是由于d的范围时间复杂度过大,于是考虑折半搜索 我们把一条最终路径的路径分成两部分$p=(d+1)/2$(其实就是上取整),$q=d-p$,显然$p>=q
题目链接:咕 闲扯:这题考场上把子任务都敲满了,5个namespace,400行11k 结果爆0了哈哈,因为写了个假快读只能读入一位数,所以手测数据都过了,交上去全TLE了 把边分成三类:0. 需要染色的 1. 不需要染色的 2. 染不染色无所谓 考场上首先发现一个性质,就是一定存在一种最优解没有染任何一条本来不需要的染色边。 为啥?其实也挺显然的,因为你染色跨过这条边还得染这条边一次,不如直接只
CF992ENastyaAndKing-Shamans题解—神奇线段树题目链接https://cn.vjudge.net/problem/CodeForces-992E 分析首先我们从$p=1$开始找比大于等于$[1,p]$这个前缀的元素下标$x$,同时判断$a[x]$是否合法,若不合法$p=x$继续找.但是有个性质就是$sum(1,x)>= 2 * sum(1,p) $.非常显然因为$a[
CF1016ERest In Shades题解—二分+几何题目链接https://cn.vjudge.net/problem/CodeForces-1016E 分析我们将固定的点视作光源,实际上就是求点与轨迹端点连线之间在$x$轴上不被遮盖的长度,然后运用相似转化即可 维护每个线段之前有多少长度没被遮盖的前缀和,二分得到端点所在或最近的线段就好了 注意二分别写挂以及特判,还要处理两端多出来的部分
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=3747 分析不敢相信这居然是线段树题…还是太菜了 我们钦定第$i$天的电影一定去看(也就是说区间右端点为$i$).那么对于第$i$天放映的电影记录其上一次放该电影的日期为第$lst[i]$天,那么显然这天放映的电影一个做出贡献的区间为$[lst[i]+1,i]$，当然第$i$天放映的那部电影
题目链接https://www.luogu.org/problemnew/show/CF894C Chinese Round.英文题面略微暴力,特意发了一发翻译变得更加暴力 分析一道思维构造题,很容易发现集合中最小的元素$x$一定要满足$x|a[i]$，$a[i]$是集合中其他的元素 为啥? 因为$gcd(a_1,a_2…a_m)$显然是那个最小的元素,那么显然上述性质成立 于是判无解就很好判了
题目链接https://www.luogu.org/problemnew/show/P3959 分析首先最后得到的一定是一颗生成树,从树高为h的节点x向深处扩展y的代价为(h+1) * dis(x,y) 我们以树高作为阶段,枚举已经扩展哪些节点的二进制状态x,又向深处扩展哪些节点的二进制状态y，设$f[dep][sta]$为已经挖到第dep层,当前已经挖了的宝藏用二进制表示下的状态为sta时的最小
题目链接https://cn.vjudge.net/problem/POJ-2411#author=goodlife2017 分析处理方法和玉米田类似,每行作为阶段,通过枚举相邻两行状态更新. 在这里怎么处理1 * 2的矩形呢?我们用1表示一个竖着的矩形的上部分,0表示其他情况,那么对于第$i$列状态x和第$i-1$列状态$y$,需满足以下条件才能转移: x&y ==0 显然 x|y相邻的
题目链接https://www.luogu.org/problemnew/show/P2622 分析这题有点不一样,每个开关可以重复使用那么用每个开关作为阶段似乎不太好,那么我们按照题意设$f[sta]$为达到$sta$这个状态最少操作次数,我们枚举到达下一个状态用了哪个开关,假设用了某个开关后的状态为$x$,显然$f[x]=min(f[x],f[sta]+1)$ 于是我们倒着枚举状态作为阶段就好
题目链接https://www.luogu.org/problemnew/show/P1896 分析做过玉米田的应该不难设计出状态转移与预处理 $f[sta][i][j]$表示第$i$行状态为$sta$,总共已经放了$j$个的方案数 $f[sta][i][j] = \sum f[p][i-1][j-num[sta]]$ $num[sta]$是$sta$二进制表示下$1$的个数,当然要保证$p,st