Claris - 博客园_a56爆大奖在线娱乐

2019年5月12日

BZOJ5243 : [Lydsy2017省队十连测]绝版题

摘要：要找的就是这棵树的带权重心，以带权重心为根时每棵子树的权值和不超过总权值和的一半。因此按$\frac{v[i]}{\sum v[i]}$的概率随机选取一个点$x$，则重心有$\frac{1}{2}$的概率落在$1$到$x$的路径上，期望随机次数为$O(1)$。随机方式可以直接随机一个$1$到$\ 阅读全文

posted @ 2019-05-12 03:59 Claris 阅读(978) 评论(0) 推荐(0) 编辑

2019年2月21日

BZOJ1991 : Pku2422 The Wolves and the Sheep

摘要：将a56爆大奖在线娱乐不是障碍的格子标号，设三只狼的位置分别为$A,B,C$，羊的位置在$D$。合法状态中强行限制$A<B<C$，这样状态数只有$\frac{n^8}{6}\approx 1.6\times 10^7$。设$f[S],g[S]$a56爆大奖在线娱乐目前局面是$S$，狼/羊正在决策，最优情况下羊会不会被围住。若$ 阅读全文

posted @ 2019-02-21 02:08 Claris 阅读(657) 评论(0) 推荐(0) 编辑

2019年2月20日

BZOJ3592 : Architext

摘要：首先特判多边形面积$=0$的情况，此时内部没有点，答案只会在顶点处取到。对于面积$>0$的情况，离线询问，将所有多边形合在一起得到平面图，然后求出对偶图，那么每条多边形边的两侧分别对应对偶图中两个域。 a56爆大奖在线娱乐多边形把这些域分成内外两个连通块，也就是保留除了多边形边之外的所有边后对偶图的连通情况。把阅读全文

posted @ 2019-02-20 23:51 Claris 阅读(390) 评论(0) 推荐(0) 编辑

BZOJ2640 : 可见区域

摘要：设$base$a56爆大奖在线娱乐直接能看到的面积，$f[i]$a56爆大奖在线娱乐仅去掉线段$i$后新增的面积，$g[i][j]$a56爆大奖在线娱乐仅去掉线段$i$和$j$后新增的面积。删除一条线段的答案为$base+\max(f[i])$。删除两条线段的答案为$base+\max(g[i][j]+f[i]+f[j],f最大值+f次大值) 阅读全文

posted @ 2019-02-20 02:52 Claris 阅读(383) 评论(0) 推荐(0) 编辑

2019年2月18日

BZOJ5316 : [Jsoi2018]绝地反击

摘要：若$R=0$，那么显然答案为离原点最远的点到原点的距离。否则若所有点都在原点，那么显然答案为$R$。否则考虑二分答案$mid$，检查$mid$是否可行。那么a56爆大奖在线娱乐点根据对应圆交，可以覆盖圆上的一部分，a56爆大奖在线娱乐可行方案都可以通过平移使得刚好卡住某个交点。枚举a56爆大奖在线娱乐交点，算出圆上$n$个位置的坐标，然后阅读全文

posted @ 2019-02-18 03:30 Claris 阅读(677) 评论(0) 推荐(1) 编辑

2019年2月16日

BZOJ5412 : circle

摘要：若仅保留这$k$个点仍然有环，那么显然无解。否则设$A$a56爆大奖在线娱乐这$k$个点的集合，$B$a56爆大奖在线娱乐剩下的点的集合，因为是竞赛图，a56爆大奖在线娱乐集合内部的拓扑关系是一条链，方便起见将所有点按照在所在集合的链上的位置进行重标号。对于$B$中a56爆大奖在线娱乐点$i$，求出$l_i$a56爆大奖在线娱乐最小的$j$，满足$B_i\rightarro 阅读全文

posted @ 2019-02-16 00:33 Claris 阅读(398) 评论(0) 推荐(0) 编辑

2019年2月15日

BZOJ5304 : [Haoi2018]字串覆盖

摘要：离线处理所有询问。对于$r-l\leq 50$的情况：按照串长从$1$到$51$分别把所有子串按照第一位字符为第一关键字，上一次排序结果为第二关键字进行$O(n)$基数排序。同理也可以用上一次比较结果来判断这一次某两个子串是否相同。对于a56爆大奖在线娱乐询问，找到排序结果中对应的区间，在里面二分出起点$x 阅读全文

posted @ 2019-02-15 02:12 Claris 阅读(652) 评论(0) 推荐(0) 编辑

2019年2月12日

BZOJ2567 : 篱笆

摘要：设第$i$个区间的左端点为$a[i]$，区间长度为$len$，要覆盖的部分的长度为$all$，因为区间左端点递增，a56爆大奖在线娱乐最优方案中它们的位置仍然递增。对于链的情况，要满足三个条件： 1. 区间$i$可以接上区间$i-1$ 设$f[i]$a56爆大奖在线娱乐最优解中第$i$个区间左端点的位置，则$f[i]=\min( 阅读全文

posted @ 2019-02-12 02:12 Claris 阅读(267) 评论(0) 推荐(0) 编辑

2019年2月11日

BZOJ5326 : [Jsoi2017]博弈

摘要：将所有物品按照$b$的选择顺序排序，则先手在�a56爆大奖在线娱乐馇�$i$个物品中最多只能拿走$\lceil\frac{i}{2}\rceil$个物品。将a56爆大奖在线娱乐物品的价值设为$a+b$，那么答案为先手拿走的价值和减去所有物品的$b$之和，目标是最大化先手拿走的价值和。如果不考虑修改，则满足拟阵，可以贪心选取，修改时阅读全文

posted @ 2019-02-11 03:26 Claris 阅读(578) 评论(0) 推荐(1) 编辑

2019年2月3日

BZOJ1757 : Apple 偷苹果

摘要：设$f0[i][j][x][y][S]$a56爆大奖在线娱乐盗贼位于$(i,j)$，守卫位于$(x,y)$，每棵苹果树苹果数量为$S$，盗贼先手时盗贼还能偷多少苹果。设$f1[i][j][x][y][S]$a56爆大奖在线娱乐盗贼位于$(i,j)$，守卫位于$(x,y)$，每棵苹果树苹果数量为$S$，守卫先手时盗贼还能偷多少苹果阅读全文

posted @ 2019-02-03 01:08 Claris 阅读(443) 评论(0) 推荐(0) 编辑

2019年1月31日

BZOJ5465 : [APIO 2018] 选圆圈

摘要：假设最大的圆半径为$R$，以$2R$为大小将地图划分为一个个格子，那么a56爆大奖在线娱乐圆只需要检查圆心在附近$9$个格子内部的所有圆。在当前圆的半径不足$\frac{R}{2}$时重构网格，那么最多重构$O(\log R)$次，且a56爆大奖在线娱乐圆最多被检查常数次。时间复杂度$O(n\log n\log R)$，利用H 阅读全文

posted @ 2019-01-31 00:02 Claris 阅读(1155) 评论(2) 推荐(3) 编辑

2019年1月15日

BZOJ2649 : riddle

摘要：题意同3495，但是内存限制收紧了，不能采用3495的前后缀优化建图的方式。注意到“a56爆大奖在线娱乐集合恰好选择一个点”可以放宽成“a56爆大奖在线娱乐集合最多选择一个点”，对于最后求出的方案里，如果某个集合没选点，任选一个就好了。考虑2-SAT建图，有两类边： 1. 对于每条给定的边$(u,v)$：如果不选$u$就必须选阅读全文

posted @ 2019-01-15 22:26 Claris 阅读(380) 评论(0) 推荐(1) 编辑

2019年1月3日

BZOJ3497 : Pa2009 Circular Game

摘要：令先手为$A$，后手为$B$，将相邻同色棋子合并成块，首先特判一些情况：无视所有大小为$1$的块，考虑剩下块里相邻两块，它们往外扩张比往内缩更优：如果是形如[A_A]___B__A__BA____B___[AA_A]，两边同色，a56爆大奖在线娱乐中间这些块（包括位置）可以删除，不影响游戏结果。如果是形如[A 阅读全文

posted @ 2019-01-03 02:49 Claris 阅读(658) 评论(0) 推荐(2) 编辑

2018年11月20日

BZOJ1386 : [Baltic2000]Stickers

摘要：显然每一位的限制独立，对于每一位求出仅限制该位下的最大数，然后求最小值即可。假设当前要求数字$d$的答案：考虑填数字的过程，可以看作依次考虑一个序列中的a56爆大奖在线娱乐数，当前缀和$<0$时退出。设$dp[i][j][k]$a56爆大奖在线娱乐正在考虑最低的$i$位，高位部分有$j$个$d$，第$i$位能不能填$0$为$ 阅读全文

posted @ 2018-11-20 15:40 Claris 阅读(465) 评论(0) 推荐(0) 编辑

2018年11月17日

BZOJ1431 : MLand

摘要：考虑�a56爆大奖在线娱乐庖豢蒙墒鳎拇凼且桓鲆淮魏� 因此所有生成树的最小值随着时间变化呈现出的是一个上凸壳。三分查找最大值即可。时间复杂度$O(m\log m\log w)$。阅读全文

posted @ 2018-11-17 02:16 Claris 阅读(465) 评论(1) 推荐(0) 编辑

2018年11月13日

XIX Open Cup named after E.V. Pankratiev. GP of Poland(AMPPZ-2018)

摘要： A. Drone With a Camera 三分套三分。 B. Fibonaccis’ vouchers 考虑用最少的Fib数a56爆大奖在线娱乐一个数，只需要从大到小贪心选取a56爆大奖在线娱乐Fib数。将一个数写成Fib进制，可以得到一个$01$串，满足没有连续两个$1$。从高位到低位逐位确定答案的每一位是$0$还是$1 阅读全文

posted @ 2018-11-13 19:27 Claris 阅读(1024) 评论(0) 推荐(0) 编辑

2018年11月3日

ZOJ4043 : Virtual Singers

摘要：将所有$A$和$B$混在一起排序，那么a56爆大奖在线娱乐$B$要匹配一个$A$，从左往右依次考虑a56爆大奖在线娱乐数：如果是一个$B$：如果左边没有多余的$A$，那么将其放入堆$q_C$中，a56爆大奖在线娱乐这个$B$还未匹配。否则选择左边代价最小的$A$和这个$B$进行匹配，并把代价取反，加上这个$B$往右匹配的贡献后放入堆$q_B 阅读全文

posted @ 2018-11-03 17:20 Claris 阅读(1476) 评论(0) 推荐(2) 编辑

2018年8月26日

BZOJ5335 : [TJOI2018]智力竞赛

摘要：二分答案，转化成求最少的路径，覆盖住所有权值$\leq mid$的点。建立二分图，若$i$的后继为$j$，则连边$i\rightarrow j$，求出最大匹配，则点数减去最大匹配数即为最少需要的路径数量。特别地如果某个点$i$的权值$>mid$，则它可以不经过，连边$i\rightarrow i 阅读全文

posted @ 2018-08-26 04:06 Claris 阅读(712) 评论(0) 推荐(0) 编辑

2018年8月22日

BZOJ2681 : 玩游戏2

摘要：首先若存在多个连通块，那么答案显然是$+\infty$。否则以$m$为根，每棵子树的根节点都最多只能放一个金币，且这些子树之间互不干扰。对于一棵父亲为$m$的子树，最优方案下一定可以将子树剖分成若干条祖先到孙子的链，每条链中a56爆大奖在线娱乐点$x$往上贡献$\lfloor\frac{v[x]}{2}\rfl 阅读全文

posted @ 2018-08-22 03:43 Claris 阅读(456) 评论(0) 推荐(0) 编辑

2018年8月5日

2018 Multi-University Training Contest 3 - HDU Contest

摘要：题解： solution Code： A. Ascending Rating B. Cut The String C. Dynamic Graph Matching D. Euler Function E. Find The Submatrix F. Grab The Tree G. Interst 阅读全文

posted @ 2018-08-05 18:12 Claris 阅读(1006) 评论(0) 推荐(0) 编辑

Claris' Blog

公告