- 博客(453)
- 收藏
- 关注
RSS订阅原创 【bzoj1566】【NOI2009】【管道取珠】【dp】
Description Input第一行包含两个整数n, m，分别表示上下两个管道中球的数目。 第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。 第三行为一个AB字符串，长度为m，表示下管道中的情形。Output仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。Sample Inp
2016-07-14 20:49:06
2027
原创 【bzoj4003】【JLOI2015】【城池攻占】【可并堆】
Description小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，其中 fi 中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否
2016-07-14 20:38:49
1404
原创 【bzoj1038】【ZJOI2008】【瞭望塔】【半平面交】
Description 致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。我们将H村抽象为一维的轮廓。如下图所示 我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dad
2016-07-14 20:31:55
810
原创 【bzoj3786】【星系探索】【dfs序+splay】
Description物理学家小C的研究正遇到某个瓶颈。他正在研究的是一个星系，这个星系中有n个星球，其中有一个主星球(方便起见我们默认其为1号星球)，其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。我们定义依赖关系如下：若星球a的依赖星球是b,则有星球a依赖星球b.此外，依赖关系具有传递性，即若星球a依赖星球b,星球b依赖星球c,则有星球a依赖星球c.对于这个神秘的
2016-07-12 07:59:45
821
原创 【bzoj2337】【HNOI2011】【XOR和路径】【高斯消元】
Description题解： 按位考虑,假设当前考虑到第x位. f[i]表示从i到n第x位是1的概率. 枚举i的后继节点j 如果i到j的边第x位是1,那f[i]+=1/d[i]*(1-f[j]); 如果i到j的边第x为是0,那f[i]+=1/d[i]*f[j];
2016-07-12 07:59:12
739
原创 【bzoj1115】【poi2009】【石子游戏Kam】【阶梯博弈】
Description有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。Input第一行u表示数据组数。对于每组数据，第一行N表示石子堆数，第二行N个数ai表示第i堆石子的个数(a1Outputu行，若先手必胜输出T
2016-07-08 15:03:04
622
原创 【bzoj3729】【GTY的游戏】【阶梯博弈+splay】
Description某一天gty在与他的妹子玩游戏。妹子提出一个游戏，给定一棵有根树，每个节点有一些石子，每次可以将不多于L的石子移动到父节点，询问将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。gty很快计算出了策略。但gty的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。gty不忍心打击妹子，所以他将这个问题交给了你。另外由于gty十分绅士
2016-07-08 14:56:42
584
原创 【bzoj4636】【蒟蒻的数列】【线段树】
Description蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列题目描述DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。Input第一行一个整数N，然后有N行，每行三个正整数a、b、k。NO
2016-07-08 14:49:23
1254
原创 【bzoj1297】【SCOI2009】【迷路】【矩阵乘法】
Descriptionwindy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。Input第一行包含两个整数，N T。 接下来有 N 行，每行一个长度为 N 的字符串。 第
2016-07-08 14:41:24
600
原创 【bzoj2500】【幸福的道路】【树形dp+单调队列】
Description小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他
2016-07-08 14:37:37
1166
原创 【bzoj4515】【SDOI2016】【游戏】【线段树+树链剖分】
DescriptionAlice 和 Bob 在玩一个游戏。游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+
2016-07-08 11:51:54
716
原创 【bzoj3316】【JC loves MKK】【单调队列+二分答案】
DescriptionInput第1行，包含三个整数。n，L，R。第2行n个数，代表a[1..n]。Output仅1行，表示询问答案。如果答案是整数，就输出整数；否则，输出既约分数“P/Q”来表示。Sample Input5 3 43 1 2 4 5Sample Output7/2HINT
2016-07-08 11:40:48
663
原创 【bzoj3938】【Robot】【线段树】
Description小q有n只机器人，一开始他把机器人放在了一条数轴上，第i只机器人在ai的位置上静止，而自己站在原点。在这之后小q会执行一些操作，他想要命令一个机器人向左或者向右移动x格。但是机器人似乎听不清小q的命令，事实上它们会以每秒x格的速度匀速移动。看着自己的机器人越走越远，小q很着急，他想知道当前离他（原点）最远的机器人有多远。具体的操作以及询问见输入格式。注意，
2016-07-08 11:29:33
1028
原创 【bzoj2521】【SHOI2010】【最小生成树】【最小割】
DescriptionSecsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 3中所示的都是图 2中的无向图的最小生成树：当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多
2016-07-08 11:24:56
819
原创 【bzoj4337】【BJOI2015】【树的同构】【hash】
Description树是一种很常见的数据结构。我们把N个点，N-1条边的连通无向图称为树。若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
2016-07-08 11:14:38
1579
原创 【bzoj4327】【JSOI2012】【玄武密码】【AC自动机】
Description在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。 很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。 经过分析，我们可以用东南西北
2016-07-08 11:06:46
2173
原创 【bzoj3648】【寝室管理】【环套树+点分治+树状数组】
Description T64有一个好朋友，叫T128。T128是寄宿生，并且最近被老师叫过去当宿管了。宿管可不是一件很好做的工作，碰巧T128有一个工作上的问题想请T64帮忙解决。 T128的寝室条件不是很好，所以没有很多钱来装修。礼间寝室仅由n-1条双向道路连接，而且任意两间寝室之间都可以互达。最近，T128被要求对一条路径上的所有寝室进行管理，这条路径不会重复经过某个点或
2016-07-08 10:56:13
855
原创 【bzoj3522】【poi2014】【hotel】【树形dp】
Description有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。有多少种方案能让吉丽满意？Input第一行一个数n。接下来n-1行，每行两个数x,y，表示x和y之间有一条边相连。
2016-07-08 09:59:45
462
原创 【bzoj3784】【树上的路径】【点分治+堆+st表】
Description给定一个N个结点的树，结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b）表示从结点a到结点b路边上经过边的权值。其中要求aInput第一行两个正整数N,M下面N-1行，每行三个正整数a,b,c(a,bOutput共M行，如题所述.Sample Input5 101
2016-07-08 09:52:36
1795
原创 【bzoj1316】【树上的询问】【点分治+map】
Description一棵n个点的带权有根树，有p个询问，每次询问树中是否存在一条长度为Len的路径，如果是，输出Yes否输出No.Input第一行两个整数n, p分别表示点的个数和询问的个数． 接下来n-1行每行三个数x, y, c，表示有一条树边x→y，长度为c． 接下来p行每行一个数Len，表示询问树中是否存在一条长度为Len的路径．Output输出有p行，Y
2016-07-08 09:30:31
1252
原创 【bzoj4011】【HNOI2015】【落忆枫音】【dp+容斥原理】
Description「恒逸，你相信灵魂的存在吗？」 郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫，枫茜突然问出这样一个问题。 「相信吧。不然我们是什么，一团肉吗？要不是有灵魂……我们也不可能再见到你姐姐吧。」 恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。 「那你仔细观察过枫叶吗？」 说罢，枫茜伸手，接住了一片飘落的枫叶。 「其实每一片枫叶都是
2016-07-08 09:27:32
821
原创 【bzoj2553】【beijing2008】【禁忌】【AC自动机+矩阵乘法】
Description Magic Land上的人们总是提起那个传说：他们的祖先John在那个东方岛屿帮助Koishi与其姐姐Satori最终战平。而后，Koishi恢复了读心的能力…… 如今，在John已经成为传说的时代，再次造访那座岛屿的人们却发现Koishi遇到了新麻烦。 这次她遇到了Flandre Scarlet——她拥有可以使用禁忌魔
2016-07-08 09:05:40
489
原创 【bzoj1444】【jsoi2009】【有趣的游戏】【AC自动机+矩阵乘法】
DescriptionInput注意 是0OutputSample InputSample OutputHINT 30%的数据保证, n ≤ 2. 50%的数据保证, n ≤ 5. 100%的数据保证, n , l, m≤ 10.题解： 对所有玩家的串建立AC自动机.
2016-07-08 08:54:58
481
原创 【bzoj3530】【sdoi2014】【数数】【AC自动机+数位dp】
Description我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。 给定N和S，计算不大于N的幸运数个数。Input 输入的第一行包含整数N。 接下来一行一个整数M，表示S中元素的数量。
2016-07-08 08:27:29
629
原创 【bzoj4200】【NOI2015】【小园丁与老司机】【dp+最小流】
Description小园丁 Mr. S 负责看管一片田野，田野可以看作一个二维平面。田野上有 nn 棵许愿树，编号 1,2,3,…,n1,2,3,…,n，每棵树可以看作平面上的一个点，其中第 ii 棵树 （1≤i≤n1≤i≤n） 位于坐标 (xi,yi)(xi,yi)。任意两棵树的坐标均不相同。老司机 Mr. P 从原点 (0,0)(0,0) 驾车出发，进行若干轮行动。每一轮，Mr.
2016-07-08 08:17:13
958
原创 【bzoj4213】【贪吃蛇】【有上下界的费用流】
Description 最近lwher迷上了贪吃蛇游戏，在玩了几天却从未占满全地图的情况下，他不得不承认自己是一个弱菜，只能改去开发一款更弱的贪吃蛇游戏。在开发的过程中，lwher脑洞大开，搞了一个多条蛇的模式。但由于这种模式太难操作，于是他只好改变游戏的玩法，稍微变化一下游戏目标。新的游戏是这样的：一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了
2016-07-04 22:16:21
1594
原创 【bzoj2502】【清理雪道】【最小流】
Description 滑雪场坐落在FJ省西北部的若干座山上。从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。由于每次飞行的耗费是
2016-07-04 21:55:50
396
原创 【bzoj3698】【XWW的难题】【有上下界的网络流】
DescriptionXWW是个影响力很大的人，他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易，需要通过XWW的考核。XWW给你出了这么一个难题：XWW给你一个N*N的正实数矩阵A，满足XWW性。称一个N*N的矩阵满足XWW性当且仅当：（1）A[N][N]=0；（2）矩阵中每行的最后一个元素等于该行前N-1个数的和；（3）矩阵中每列的最后一个元素等于
2016-07-03 11:31:23
605
原创 【bzoj2055】【80人环游世界】【有上下界的费用流】
Description 想必大家都看过成龙大哥的《80天环游世界》，里面的紧张刺激的打斗场面一定给你留下了深刻的印象。现在就有这么 一个80人的团伙，也想来一次环游世界。 他们打算兵分多路，游遍每一个国家。 因为他们主要分布在东方，所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为1...N。假若第i个人的游历路线为P1、P2.....
2016-07-03 11:20:25
694
原创 【bzoj2324】【ZJOI2011】【营救皮卡丘】【有上下界的费用流+Floyd】
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重
2016-07-01 11:49:04
507
原创 【bzoj3876】【AHOI2014】【支线剧情】【有上下界的费用流】
Description【故事背景】宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。【问题描述】JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前
2016-07-01 11:35:13
540
原创 【bzoj3774】【最优选择】【最小割】
Description小N手上有一个N*M的方格图，控制某一个点要付出Aij的代价，然后某个点如果被控制了，或者他周围的所有点(上下左右)都被控制了，那么他就算是被选择了的。一个点如果被选择了，那么可以得到Bij的回报，现在请你帮小N选一个最优的方案，使得回报-代价尽可能大。Input第一行两个正整数N,M表示方格图的长与宽。接下来N行每行M个整数Aij表示控制的代
2016-07-01 11:28:51
901
原创 【bzoj1835】【ZJOI2010】【基站选址】【dp+线段树】
Description有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。 输入数据 (base.in) 输入文件
2016-06-29 14:20:56
1299
原创 【bzoj3931】【CQOI2015】【网络吞吐量】【spfa+最大流】
Description 路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由
2016-06-29 11:48:57
405
原创 【bzoj2989】【数列】【cdq分治+树状数组】
Description给定一个长度为n的正整数数列a[i]。定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。2种操作（k都是正整数）：1.Modify x k：将第x个数的值修改为k。2.Query x k：询问有几个i满足graze(x,i)考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a
2016-06-29 11:46:57
970
原创 【bzoj4553】【TJOI2016&HEOI2016】【序列】【cdq分治+树状数组】
Description 佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。注意：每种变化最多只有一个值发生变化。在样例输入1中，
2016-06-29 11:39:54
838
原创 【bzoj】【1176】【mokia】【cdq分治】
Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数MInput第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小接下来每行为一下三种输入之一(不包含引号):"1 x y a""2 x1 y1 x2 y2""3"输入1:你需要把(x,y)(第x行第y列)的格子
2016-06-25 19:29:49
579
原创 【bzoj1492】【NOI2007】【货币兑换】【斜率优化+cdq分治】
Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下简称B券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的价值分别为 AK 和 BK（元/单位金券）。为
2016-06-25 16:41:03
806
原创 【bzoj3203】【保护出题人】【凸包+三分】
DescriptionInput第一行两个空格隔开的正整数n和d，分别表示关数和相邻僵尸间的距离。接下来n行每行两个空格隔开的正整数，第i + 1行为Ai和 Xi，分别表示相比上一关在僵尸队列排头增加血量为Ai 点的僵尸，排头僵尸从距离房子Xi米处开始接近。 Output一个数，n关植物攻击力的最小总和 ，保留到整数。Sample Input
2016-06-23 19:25:43
400
原创 【bzoj2388】【旅行规划】【分块+凸包】
DescriptionOIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变
2016-06-23 19:12:25
1036
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人