Chro's Blog


同じ世界に、立っていたんだ。


  1. 「BZOJ 4730」「UOJ 266」「清华集训2016」Alice和Bob又在玩游戏

    DescriptionAlice和Bob在玩游戏。有n个节点,m条边(0<=m<=n-1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。Alice和Bob轮流操作,每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输。注:树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。比如:1-3-2 这样一条链,1号点是根节点,删除1号点之…

    BZOJ, 博弈论, 树型 DP 继续阅读

  2. 「BZOJ 4585」「UOJ 205」「APIO2016」Fireworks

    烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成一棵树,烟花是树叶,如图所示。火花从开关出发,沿导火索移动。每当火花抵达一个分叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的速度是一个固定常数。图中展示了六枚烟花 {E1,E2,…,E6} 的连线布局,以及每根导火索的长度。…

    BZOJ, UOJ, 可合并堆, 树型 DP 继续阅读

  3. 「BZOJ 3631」「JLOI2014」松鼠的新家

    Description松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。 可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他,每…

    BZOJ, 树型 DP 继续阅读

  4. 「BZOJ 3696」化合物

    Description首长NOI惨跪,于是去念文化课了。现在,他面对一道化学题。 这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼,我相信你们也没有兴趣听。 由于这个游戏涉及博弈论,因此化竞的同学就要求首长求一个类似SG函数的值。 他们手中有一种非常神奇的化合物,它的分子由N个原子组成(不要在意一个原子可能和及其多个原子成键这个细节)。这个分子构成一个树结构,1号…

    BZOJ, 树型 DP 继续阅读

  5. 「BZOJ 3162」独钓寒江雪

    Solution如果没有「本质不同」的限制,那么就是一个很简单的树型 DP:f(i, j) 表示以 i 为根的子树,是否选择根节点 (j=0 表示不选,j=1 表示选),此时的最大独立集。 加上这条限制后,我们需要修改一下状态转移: 对于不同构的子树,无论如何选择节点,它们总是「本质不同」的。 对于若干同构的子树,假设共有 n 个。并假设每个子树都有 m 种独立集的方案。由于子树不区分顺…

    BZOJ, 哈希, 树同构, 树型 DP 继续阅读

  6. 「BZOJ 1369」「Baltic2003」Gem

    Description给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。 Input先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连 Output最小的总权值 Sample Input12345678910107 51 21 78 94 19 75 610 …

    BZOJ, 树型 DP 继续阅读

  7. 「BZOJ 3522」「POI2014」Hotel

    Description有一个树形结构的宾馆,n个房间,n-1条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。 有多少种方案能让吉丽满意? Input第一行一个数n。 接下来n-1行,每行两个数x,y,表示x和y之间有一条边相连。 Output让吉丽满意的方案数…

    BZOJ, 树型 DP 继续阅读

  8. 「BZOJ 1912」「APIO2010」patrol 巡逻

    Description Input第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行,每行两个整数 a, b, 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。 Output输出一个整数,表示新建了K 条道路后能达到的最小巡逻距离。 Sample Input123456788 11 23 13 45 37 58 55 6 Sample Output111 HINT1…

    BZOJ, 树型 DP 继续阅读

  9. 「BZOJ 3573」「HNOI2014」米特运输

    Description米特是D星球上一种非常神秘的物质,蕴含着巨大的能量。在以米特为主要能源的D星上,这种米特能源的运输和储存一直是一个大问题。D星上有N个城市,我们将其顺序编号为1到N,1号城市为首都。这N个城市由N-1条单向高速通道连接起来,构成一棵以1号城市(首部)为根的树,高速通道的方向由树中的儿子指向父亲。树按深度分层:根结点深度为0,属于第1层;根结点的子节点深度为1,属于第2层;依此…

    BZOJ, 树型 DP 继续阅读

  10. 「BZOJ 4868—4873」「HEOI/HLOI/JLOI/LNOI/SHOI/SXOI2017」Solution & Code

    鉴于 BZOJ 精简题面的行为已经把题目关键条件改丢了的情况+我实在懒得复制六个题面……我传了本次省选的原版 PDF(由于某些原因,传的是 SHOI 而不是 LNOI 的文件 2333) D1T1 exam枚举所有科目的出分时间 T,则对于所有科目,某些科目的时间要减少;而另外一些科目的时间本来就不足 T。用more表示「超出、要被砍掉」的时间单位数;用less表示「不足、可以填补」的时间…

    BZOJ, 数学期望, 最大权闭合子图, 树型 DP, 矩阵乘法, 线段树, 贪心, 逆元 继续阅读

  11. 「BZOJ 3037」创世纪

    Descriptionapplepi手里有一本书《创世纪》,里面记录了这样一个故事…… 上帝手中有着N 种被称作“世界元素”的东西,现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素,所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它,这样上帝就可以保持对世界的控制。 由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大…

    BZOJ, 树型 DP 继续阅读

  12. 「BZOJ 3727」「PA2014」Final Zadanie

    Description吉丽YY了一道神题,题面是这样的: “一棵n个点的树,每条边长度为1,第i个结点居住着a[i]个人。假设在i结点举行会议,所有人都从原住址沿着最短路径来到i结点,行走的总路程为b[i]。输出所有b[i]。” 吉丽已经造好了数据,但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗? Input第一行一个整数n(2<=n<=300000)。 接下来n-1行,每行…

    BZOJ, 树型 DP 继续阅读

  13. 「LA 3412」Pesky Heroes

    Description, in Chinese有一个树状的洞穴图,共有 n 个节点, 每个节点的度数不超过3。有 m 个节点上有陷阱;1号节点被认为是入口(并且度数一定是1)。 现在要放入若干个小兵检查洞穴。每个小兵通过一个传送门被传送到某条边上,它们一开始都背对着1号节点(入口)行走。它们遇到死胡同就掉头,遇到岔路就总是选择左边。如果走到陷阱上就会死掉。 每个小兵的探索是互相独立的,且小兵最…

    UVa Live Archive, 树型 DP 继续阅读

  14. 「BZOJ 4557」「LNOI/JLOI2016」侦察守卫

    Description小R和B神正在玩一款游戏。这款游戏的地图由N个点和N-1条无向边组成,每条无向边连接两个点,且地图是连通的。换句话说,游戏的地图是一棵有N个节点的树。游戏中有一种道具叫做侦查守卫,当一名玩家在一个点上放置侦查守卫后,它可以监视这个点以及与这个点的距离在D以内的所有点。这里两个点之间的距离定义为它们在树上的距离,也就是两个点之间唯一的简单路径上所经过边的条数。在一个点上放置侦查…

    BZOJ, 树型 DP 继续阅读

  15. 「BZOJ 1791」「IOI2008」Island 岛屿

    Description你将要游览一个有N个岛屿的公园。从每一个岛i出发,只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛,但每座桥均可以双向行走。同时,每一对这样的岛屿,都有一艘专用的往来两岛之间的渡船。 相对于乘船而言,你更喜欢步行。你希望所经过的桥的总长度尽可能的长,但受到以下的限制。 可以自行挑选一个岛开始游览。 任何一个岛都不能游览一次以上。 无论任何…

    BZOJ, 单调队列, 拓扑排序, 树型 DP 继续阅读