算法 - Page 21 - hzwer.com

「East!_XX」手机号码
Description众所周知，天朝泱泱五千年的文化积淀下，人们在数字上尤为挑剔。很多人认为，不吉利的数字会导致流年困顿。「阿弥陀佛，作为社会主义接班人，我们应该相信科学，远离迷信!」在天朝，不同的人读手机号码有不同的方式（见右图）。人们选择手机号码时，为了照顾“不吉利数字恐惧症”患者，总会希望任何人报自己的电话号码时都不会连续说出来不吉利数字。例如，很多天朝子民认为5914是一串很不吉利的号码，因此尾号为5914的...
02015年4月18日2,682递推与动规

「BZOJ3991」[SDOI2015] 寻宝游戏
Description 小B最近正在玩一个寻宝游戏，这个游戏的地图中有N个村庄和N-1条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个...
82015年4月17日9,265虚树,dfs序,STL,最近公共祖先
「BZOJ2957」楼房重建
Description　　小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房...
22015年4月17日7,765线段树
「BZOJ1913」[Apio2010] signaling 信号覆盖
DescriptionInput输入第一行包含一个正整数n,表示房子的总数。接下来有n行，分别表示每一个房子的位置。对于i=1,2,..,n,第i个房子的坐标用一对整数xi和yi来表示，中间用空格隔开。Output输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出结果与精确值的绝对误差不超过0.01。SampleInput402440020SampleOutput3.500HINT3.5,3.50,3.500,…中的任何一个输出均为正确。此外，3.49,3.51,3.499999，…等也...
02015年4月17日5,272几何,排列组合
「BZOJ2770」YY的Treap
Description志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你...
02015年4月16日4,109STL,二分法,线段树
「BZOJ3638 / 3272」Cf172 k – Maximum Subsequence Sum
Description给一列数，要求支持操作：1.修改某个数的值2.读入l,r,k，询问在[l,r]内选不相交的不超过k个子段，最大的和是多少。InputThefirstlinecontainsintegern(1 ≤ n ≤ 105),showinghowmanynumbersthesequencehas.Thenextlinecontainsnintegersa1, a2, ..., an(|ai| ≤ 500).Thethirdlinecontainsintegerm(1 ≤ m ≤ 105)—thenumberofqueries.Thenextmlinescontainthequeriesintheformat,giveninthestate...
22015年4月16日5,053费用流,线段树
TCO 2015 Round 1A DIV1
250：枚举l-r的数，爆搜，统计数位，用map存一下TT实际上对于每个数小范围暴力即可TT[crayon-6781699a7494b491022417/]500：暴力走min(n^2,K)次，预处理出哪些不能同时取。。。再暴搜+快速幂算方案TAT结果有个点T了。。。正解假如k步之前在一起了，那么k步的时候一定在一起了所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）所以暴力求状态后乘起来就行了。。...
02015年4月15日34,092STL,深度搜索,二分图匹配
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-6781699a74e87619970967/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,419贪心,spfa,点分治,floyd
UOJ Round #1
http://vfleaking.blog.uoj.ac/blog/33「UR#1」缩进优化[crayon-6781699a75833501168169/]「UR#1」外星人这题似乎没那么麻烦f[i][j]表示前i大的，得出的结果为j的方案数第i大的可以在当前视之生效，也可以放在剩下n-i个任意一个的后面使之不生效[crayon-6781699a7583d842549860/]「UR#1」跳蚤国王下江南什么。。仙人掌毁灭世界。？这个大坑估计不会填了...
32015年4月14日4,097递推与动规,调和级数
「BZOJ2303」[Apio2011] 方格染色
DescriptionSam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2× 2的方形区域都包含奇数个（1个或3个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色）。可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍...
12015年4月14日7,527并查集
「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Examyy个奇怪的构造TT[crayon-6781699a7647b173889710/]「cf534B」CoveredPathd很小，最大速度就很小，dp即可[crayon-6781699a76484799945434/]「cf534C」Polycarpus'Dice对于每个骰子，得出其它骰子的和sum则它的最小值为A-sum，最大值为A-n+1[crayon-6781699a76489198046821/]「cf534D」Handshakes尽量大的能处理则处理[crayon-6781699a7648e188999706/]「cf534E」BerlandLocalPositioningSystem非...
02015年4月13日3,593递推与动规,贪心,深度搜索,构造,状压动规
UOJ Easy Round #1
http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-6781699a769ef356944578/]「UER#1」跳蚤OS[crayon-6781699a769f8287649121/]「UER#1」DZYLovesGraph[crayon-6781699a769fe870208859/] ...
02015年4月13日6,840并查集,AC自动机