算法 - Page 23 - hzwer.com

「BZOJ2095」[POI2010] Bridges
DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承...
02015年4月4日4,982最大流,二分法,欧拉图

「East!_XVI」不祥之刃
Background卡特琳娜又要怒拿五杀了,怎么办啊?某无良设计师伊泽瑞尔笑了笑:“基兰,断网,重赛!”Description卡特琳娜要从1到N依次通过这N个李青[小学僧/盲僧],并最终击杀第N+1个李青[Dopa僧]。对于[小学僧],卡特琳娜可以击杀他得到一点法强和数量等同于该[小学僧]权值的金币;对于[盲僧],如果卡特琳娜当前法强大于等于该[盲僧]的权值,就会被该[盲僧]击杀。现在卡特琳娜要击杀[Dopa僧],就必须得到大于等于其权值的法强。问卡特琳...
02015年4月4日3,269STL,贪心
「East!_XVI」九尾妖狐
Background某无良设计师伊泽瑞尔:刀妹太弱了,我们来增强阿狸吧。Description阿狸现在有N个技能,伊泽瑞尔要决定它们是AD技能还是AP技能。因为出装不同,所以当一个技能是AP时,阿狸的爆发增加ap_i,当一个技能是AD时,阿狸的爆发增加ad_i。有些技能配合可以打出伤害加成,这样阿狸的技能就可以被表示为一张无向图。当有关联的两个技能都是AD时,阿狸的爆发增加AD_i,当两个技能都是AP时,阿狸的爆发增加AP_i,当两个技能不...
02015年4月4日4,424最小割
「ch18」fff的诅咒
$「ch18」fff的诅咒$
背景06年的浙江考生还是很不服，于是我再水了一题。描述设A,B是两个非空集合，如果存在一法则f，使得对A中的每个元素按法则f在B中有唯一确定的元素与之对应，则称f为从A到B的映射，记作f:A→B，映射在数学及相关的领域经常等同于函数。设s是由1到n的所有正整数组成集合，定义映射f:A→B。已知n，求满足的映射f有多少个？这个数可能很大，你只需要给出答案对质数p取模的值即可。输入格式三个空格隔开的正整数n,k,p。输出格...
22015年4月3日3,296递推与动规,排列组合
意外的FJOI2015
意外地发现没有退役先让我读两周文化课镇静一下。。。吾不言TT祝skydec，KuribohG，wulala，Timemachine，kzoacn，Bakser，PoPoqqq，usedtobe，iwtwiioi，shanest怒虐省选噢还有些签约爷。。。（签约了还去省选差评）（如果有谁我一时忘了请留言打脸）2015.4.2上周末经历一场奇怪的FJ省选考前和别人说：今天要是四题的话我就直接弃疗出考场了。结果暴力+乱搞+模板+worldfinal神坑题。。。这是啥风格。。。出题人良心发现...
302015年4月3日8,642竞赛历程
「BZOJ2083」[POI2010] Intelligence test
Description霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。Input第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=...
02015年4月3日2,999二分法
「BZOJ2084」[POI2010] Antisymmetry
Description对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。Input第一行一个正整数N(N<=500,000)。第二行一个长度为N的01字符串。Output一个正整数，表示反对称子串的个数。SampleInput811001011SampleOutput7hint7个反对称子串分别是：01(出现两...
22015年4月2日3,876二分法,哈希表
「BZOJ3522」[POI2014] Hotel
Description有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。有多少种方案能让吉丽满意？Input第一行一个数n。接下来n-1行，每行两个数x,y，表示x和y之间有一条边相连。Output让吉丽满意的方案数。SampleInput7125725235645SampleOutp...
02015年4月2日4,435树形动规
dancing link
其实感觉就是个搜索的优化我们只要知道一件事情就是双向链表中删除一个元素xl[r[x]]=l[x],r[l[x]]=r[x]这时候实际上x元素的左右指针没有被改变所以可以很容易地恢复回来然后看看代码应该就不难理解了贴一波代码hust1017fzu1686hdu2295hust1017精确覆盖应该没有更裸的了[crayon-6781969edae59647141315/]fzu1686裸重复覆盖实际上重复覆盖仅仅是在精确覆盖基础上略微改动一些主要是加入一个估价函数，即当前状态至少还需要的步数从左...
22015年4月1日4,517深度搜索,链表
「BC35」DZY Loves Topological Sorting
问题描述一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v)从u到v，都满足u在排列中出现在v之前。现在，DZY有一张有向无环图(DAG)。你要在最多删去k条边之后，求出字典序最大的拓扑序列。输入描述输入有多组数据。(TestCase≤5)第一行，三个正整数n,m,k(1≤n,m≤105,0≤k≤m).接下来m行，每行两个正整数u,v(u≠v,1≤u,v≤n),代表一条有向边(u→v).输出描述对于每组测试数据，输出一行字典序最大的拓...
02015年3月30日3,301贪心,STL,拓扑排序
「BC35」DZY Loves Balls
问题描述一个盒子里有n个黑球和m个白球。现在DZY每次随机从盒子里取走一个球，取了n+m次后，刚好取完。DZY用这种奇怪的方法生成了一个随机的01串S[1⋯(n+m)]。如果DZY第i次取出的球是黑色的，那么S[i]=1，如果是白色的，那么S[i]=0。DZY现在想知道，'01'在S串中出现的期望次数。输入描述输入有多组测试数据。(TestCase≤150)每行两个整数,n,m(1≤n,m≤12)输出描述对于每个测试数据，输出一行答案，格式为p/q(p,q...
12015年3月30日2,583深度搜索
「NOIP模拟赛」小奇的仓库
原题：「East!_XI」第一个问题2015年10月4日hzwer改写了题面「题目背景」小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵星系的货运飞船引擎还停留在上元时代！「问题描述」喵星系有n个星球，星球以及星球间的航线形成一棵树。从星球a到星球b要花费[dis(a,b)XorM]秒。（dis（a,b）表示ab间的航线长度，Xor为位运算中的异或）为了给仓库选址，小奇想知道，星球i（1<=i<=n）到其它所有星球花费的时...
62015年3月30日5,470树形动规