分类 - 图论

? 解题记录 ? ? 洛谷 ? ? 并查集 ?    2018-10-21 15:05:05    464    0    0
题目描述lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?
? 解题记录 ? ? 洛谷 ? ? 树链剖分 ? ? 差分 ?    2018-10-09 14:25:45    388    0    0
小C同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一棵包含  个结点和  条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从  到  的连续正整数。 现在有  个玩家,第  个玩家的起点为 ,终点为 。每天打卡任务开始时,所有玩家在第  秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最
? 解题记录 ? ? 洛谷 ? ? 最短路 ? ? 动态规划 ?    2018-10-09 08:25:53    426    0    0
策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图,且没有自环和重边。其中 1 号点是公园的入口, N 号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。 策策每天都会去逛公园,他总是从 1 号点进去,从 N 号点出来。 策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策还是一个特别热爱学习的好孩子,他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路
? 解题记录 ? ? 洛谷 ? ? 最短路 ? ? 状态压缩 ?    2018-10-06 17:42:59    628    0    0
题解 for C:逃亡 首先我们看看这道题的部分分: 对于30%" role="presentation" style="position: relative;">30%30%30\%的数据,我们写个爆搜搜过去就可以了。 对于60%" role="presentation" style="position: relative;">60%60%60\%的数据,注意到n,m" role="presentation" style="position: relative;">n,mn,mn,m为100" role="present
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? 贪心 ? ? 哈希 ? ? stl ?    2018-10-06 17:42:56    447    0    0
题解 for D:希望 D.pdf 我们来看看这道题的部分分: 首先明确本题的贪心策略:一旦有放置魔法符文的方案就放,这个贪心策略是显然正确的。 对于Subtask1" role="presentation" style="position: relative;">Subtask1Subtask1Subtask1:枚举树上O(N2)" role="presentation" style="position: relative;">O(N2)O(N2)O(N^2)条路径,每一条路径都O(N)" role="presentation" style="position: re
? 解题记录 ? ? LOJ ? ? 圆方树 ?    2018-10-04 13:14:51    738    0    0
地址:https://loj.ac/problem/2587 先来说说我和这道题的故事吧。作为APIO2018最良心得分题,放在T3的位置是真的阴……当打完了T1,T2的暴力后,才发现T3貌似很好拿分,想的是把T1,T2的二档暴力打完后来慢慢拿T3的分。于是就被坑进T1了。T3最后只打了有环和链的、n<=10的。树的档都没看到,血亏。知道了点双树(圆方树)后,这道题就很送分了。对于圆点统计从不同子树中选出两个点的方案,对于方点统计从不同子树选出三个点的方案,加起来就行了。细节比较多,详见注释#include<cstdio> #include<cstring> #i
? 解题记录 ? ? BZOJ ? ? 费用流 ? ? 网络流 ?    2018-10-01 10:03:10    504    0    0
很套路的一道题,做过无限之环来看这道题还是十分好想的因为我比较菜,考试的时候就没能想出来。按照套路,把格子黑白染色,然后考虑图的特点,到一个地方一定拐弯。并且,对于一条回路来说,正向和反向的贡献都是一样的。接下来,我们指定黑、白格子的流向,考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了,我们规定黑格子横进竖出,白格子横出竖进。这样我们把问题抽象成一张图,对于每一个格子可以选择从进向自己连边,自己向出连边,相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件,一个点只能经过一条流量,也就是出入度都是1,想到限制出入度便想到了最小路劲覆盖的模型。于是,初步的构图便完成了。
? 解题记录 ? ? BZOJ ? ? Kosaraju ? ? 状态压缩 ? ? 莫队 ?    2018-09-25 08:12:04    883    0    0
Description在Byteland 一共有n 座城市,编号依次为1 到n,这些城市之间通过m 条单向公路连接。对于两座不同的城市a 和 b,如果a 能通过这些单向道路直接或间接到达b,且b 也能如此到达a,那么它们就会被认为是一对友好城市。Byt eland 的交通系统十分特殊,第i 天只有编号在[li, ri] 的单向公路允许通行,请写一个程序,计算每天友好城 市的对数。 注意:(a, b) 与(b, a) 没有区别。   Input第一行包含三个正整数n, m, q,分别表示城市的个数、单向公路的条数以及询问的天数。 接下来m 行,每行两个正整数ui, vi,表示一条从城
? 解题记录 ? ? 洛谷 ? ? 贪心 ?    2018-09-18 09:44:16    338    0    0
题目描述 给定一棵树,选择l条路径覆盖最多的点的个数是多少。  输入输出样例输入样例#1: 复制17 3 1 2 3 2 2 4 5 2 5 6 5 8 7 8 9 8 5 10 10 13 13 14 10 12 12 11 15 17 15 16 15 10 输出样例#1: 复制13​​   很好的一道题,果然我的贪心技巧还不够。观察因为可以重叠,我们选叶子作为端点一定是最优的,因为如果不到叶子结点那么向叶子结点延伸一定可以覆盖更多点,因此在叶子很多的情况下我们选2*l个叶子。接下来一步就比较巧妙了,我们换一个角度,从结果来思考。最后覆盖
? 解题记录 ? ? Codeforces ? ? 构造 ?    2018-09-18 09:37:50    475    0    0
Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from 1" data-mce-tabindex="0">11 to n" data-mce-tabindex="0">nn. For every edge e" data-mce-tabindex="0">ee of this tree, Mono