毒瘤的建图方式…… 题目描述 FJ has installed a beautiful pond for his cows' aesthetic enjoyment and exercise. The rectangular pond has been partitioned into square ce...
图论
bzoj1001/洛谷 P4001 [BJOI2006]狼抓兔子 题解【网络流】【最小割】
弃isap从dinic之路…… 题目描述 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下...
NOIp模拟题 植树方案 题解【2-SAT】【并查集】
一个类似2-SAT的思想,但是简化了很多。只需要用到并查集实现。 题目描述 企鹅国打算种一批树。所谓树,就是由$ N$个结点与$ N-1$条边连接而成的连通无向图。企鹅国的国王对于这些树有下列要求:...
洛谷 P3502 [POI2010]CHO-Hamsters 题解【字符串】【hash】【倍增】
这是一道字符串建模+图论的问题。 题目描述 Byteasar breeds hamsters. Each hamster has a unique name, consisting of lower case letters of the English alphabet. The ha...
洛谷 P1653 猴子 题解【并查集】【最短路】
这个一年前开坑的题到现在终于解决了…… 题目描述 有N只猴子,第一只尾巴挂在树上,剩下的N-1只,要么被其他的猴子抓住,要么抓住了其他的猴子,要么两者均有。当然一只猴子最多抓两...
洛谷 P1841 [JSOI2007]重要的城市 题解【floyd】【bitset】
bitset玄学完美优化复杂度? 题目描述 参加jsoi冬令营的同学最近发现,由于南航校内修路截断了原来通向计算中心的路,导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断...
洛谷 P1979 NOIp2013提高组 华容道 题解【最短路】【构造】
毒瘤图论建模题 题目描述 小B最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, ...
洛谷 P2446 [SDOI2010]大陆争霸 题解【优先队列bfs】【最短路】【贪心】
本来思路对了但是转移写麻烦了把自己绕进去了。 题目背景 在一个遥远的世界里有两个国家:位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神:杰...
洛谷 P2747 [USACO5.4]周游加拿大Canada Tour 题解【费用流】
类似方格取数/吃豆豆一类的费用流。(我考试没想到。。。) 题目描述 你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始,然后...
洛谷 P2633/bzoj 2588/spoj 10628 Count on a tree 题解【可持久化】【主席树】【树上前缀和】【倍增】【LCA】
看上去是个类似树剖的东西,不过是用树上前缀和做的。(树上两点间路径操作不要只想着树剖啊,要想到树上差分/前缀和) 题目描述 给定一棵N个节点的树,每个点有一个权值,对于M个询问(u...