~ Esoteria Algorithm in Reverse Observatory

Cover Image

NOIP2018 骗分指南

Prologue

据悉,CCF 本人予以承认。它的泄题行为在选手中造成一定的恐慌和混乱,干扰了正常的竞赛秩序,有损竞赛的声誉,也给组织方带来不必要的负担和干扰。

Cover Image

树的中心

CAUTION
本文含有大段写得很丑的 Golang,可能会引起不适(

题目描述
蓮子和梅莉玩游戏。梅莉掏出一棵无根树,要蓮子在规定时间内确定一个点,使得这个点到其他点的最长路径最小,蓮子是一个只会 AK IPhO 的巨佬,所以她请教你帮她,事成之后就和梅莉结婚。

LGOJ P1174 | 打砖块

Portal

假设所以砖块都为 NN,无论打的顺序如何对后面的砖块都没有影响,这就是一个普通的多重背包。

hzwer7629 | 小奇挖矿 2

Portal

对于 60% 的数据,可以直接写出状态转移方程:
fi=max{fi4,fi7}+aif_i=\max {f_{i-4},f_{i-7}} +a_i

然后当成普通的一维 DP 做可以拿下 60pts。

对于 100% 的数据,由于 m109m\leq 10^9 如果直接用数组记录每个点的收益显然会 MLE。

NOIP2017D2T2 | 宝藏

Portal

观察题目,12 个顶点,1000 条边,显然有很多重边(显然是状压 DP)。所以在输入时不断取最短边,最后边数不超过 122 条。由于题目求的是一个花费最小的生成树,并不关心从以哪个点为根,显然对于一棵生成树,取不同的点为根只会有深度的差别,在输出时找出所有深度中花费最小的即可,而不必枚举根节点。因为有 12 个顶点,显然状态有一维应为状态压缩的被探索过的顶点。

NOI2001D2T1 | 炮兵阵地

Portal

炮兵的攻击范围是上下左右 2 格,那么显然应以行为阶段,以该行的放置情况和上行的情况作为状态。直接出状态转移方程:
fi,j,k=max{fi1,k,t+cj}f_{i,j,k}=\max{f_{i-1,k,t}+c_j}

SCOI2005D2T3 | 互不侵犯

Portal

按照状压 DP 套路,第一维为行,第二维为使用的国王数,状态压缩描述第 ii 行的状态。预处理出合法状态和该状态下有几个王。当第 ii 行的状态和该状态左右移再与 i1i-1 行的状态为假才转移。直接写出状态转移方程:
Fi,j,ck+cj+=Fi1,k,ckF_{i,j,c_k+c_j}+=F_{i-1,k,c_k}

POJ3254 | 玉米田

Portal Soruce

@赫鲁晓夫应该是最入门的状压 DP 题。按照状压 DP 套路,行为阶段,状态压缩去描述行的每一格种不种玉米。预处地形时,将不可用的位置或 1。按位与判断上下行间,该状态在该行的地形是否合法,不断从上一行转移。

JSK31434 | 广场车神

Portal

本 blog 最水的文章之二。题面藥丸。我就什么话也不说。