hzwer.com - Page 22

「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,552几何,排列组合

「BZOJ2770」YY的Treap
Description志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你...
02015年4月16日4,326STL,二分法,线段树
「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,311费用流,线段树
TCO 2015 Round 1A DIV1
250：枚举l-r的数，爆搜，统计数位，用map存一下TT实际上对于每个数小范围暴力即可TT[crayon-68eb0626f21bc829303705/]500：暴力走min(n^2,K)次，预处理出哪些不能同时取。。。再暴搜+快速幂算方案TAT结果有个点T了。。。正解假如k步之前在一起了，那么k步的时候一定在一起了所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）所以暴力求状态后乘起来就行了。。...
02015年4月15日34,813STL,深度搜索,二分图匹配
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-68eb0626f2782875962243/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,773spfa,贪心,floyd,点分治
UOJ Round #1
http://vfleaking.blog.uoj.ac/blog/33「UR#1」缩进优化[crayon-68eb0626f32f0411783374/]「UR#1」外星人这题似乎没那么麻烦f[i][j]表示前i大的，得出的结果为j的方案数第i大的可以在当前视之生效，也可以放在剩下n-i个任意一个的后面使之不生效[crayon-68eb0626f3300431106358/]「UR#1」跳蚤国王下江南什么。。仙人掌毁灭世界。？这个大坑估计不会填了...
32015年4月14日4,298递推与动规,调和级数
「BZOJ2303」[Apio2011] 方格染色
DescriptionSam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2× 2的方形区域都包含奇数个（1个或3个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色）。可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍...
12015年4月14日7,864并查集
「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Examyy个奇怪的构造TT[crayon-68eb0626f40e7884602975/]「cf534B」CoveredPathd很小，最大速度就很小，dp即可[crayon-68eb0626f40f0469742149/]「cf534C」Polycarpus'Dice对于每个骰子，得出其它骰子的和sum则它的最小值为A-sum，最大值为A-n+1[crayon-68eb0626f40f6249241881/]「cf534D」Handshakes尽量大的能处理则处理[crayon-68eb0626f40fa729554702/]「cf534E」BerlandLocalPositioningSystem非...
02015年4月13日3,881递推与动规,贪心,深度搜索,构造,状压动规
UOJ Easy Round #1
http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-68eb062700558485338528/]「UER#1」跳蚤OS[crayon-68eb062700561061139315/]「UER#1」DZYLovesGraph[crayon-68eb062700568341918529/] ...
02015年4月13日7,380并查集,AC自动机
「codechef」April Challenge 2015
BROKPHON模拟[crayon-68eb062700b34227322463/]CHEFLCM所有约数和[crayon-68eb062700b3d195511710/]PIANO1暴力TT[crayon-68eb062700b42887849461/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-68eb062700b46412211198/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日5,367模拟,递推与动规,ST表,并查集,排列组合,乘法逆元
[sdoi2008] Sandy的卡片
时限0.5sSandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。S...
72015年4月10日5,899KMP,后缀数组
「BZOJ3238」[Ahoi2013] 差异
DescriptionInput一行，一个字符串SOutput一行，一个整数，表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧，bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了，这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值，这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...
62015年4月9日6,470后缀数组,单调栈