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

2018年3月24日

XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Peterhof

摘要： A. City Wall 找规律。 B. Domino Colorings 若已经知道了a56爆大奖在线娱乐格子的颜色，那么可以DP判断是否能由某种骨牌铺成，设$dp[S]$a56爆大奖在线娱乐轮廓线上$n$个点匹配状态为$S$是否可行即可。现在不知道a56爆大奖在线娱乐格子的颜色，那么需要DP这些颜色，设$f[i][j][c][v]$a56爆大奖在线娱乐考虑阅读全文

posted @ 2018-03-24 01:06 Claris 阅读(1593) 评论(0) 推荐(0) 编辑

2018年3月22日

XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Siberia

摘要： 1. GUI 按题意判断即可。 2. Searching on the Cube 首先爬山找到一个极小点，然后不断前进找到另一个极小点，分析哪一个是答案即可。 3. Mirrors 留坑。 4. Roads to cinematography $1$和$n$的最优连法一定是$1$往下，$n$往左，中阅读全文

posted @ 2018-03-22 20:01 Claris 阅读(1179) 评论(0) 推荐(1) 编辑

2018年3月21日

BZOJ5177 : [Jsoi2013]贪心的导游

摘要：首先预处理出对于a56爆大奖在线娱乐模数，所有被模数按结果从大到小排序的结果，那么对于一个询问，如果可以在$O(1)$时间内判断某个数字是否出现，则可以$O(1000)$回答。考虑对序列进行分治，对于区间$[l,r]$，取$mid=\lfloor\frac{l+r}{2}\rfloor$。处理出$mid$到$[ 阅读全文

posted @ 2018-03-21 03:06 Claris 阅读(484) 评论(0) 推荐(0) 编辑

BZOJ1482 : [Balkan2017]Cats

摘要：若猫和狗中至少有一个出现了$0$次，那么答案显然是$0$，否则若狮子出现了$0$次，那么显然无解。那么现在至少有一个动物保持原地不同，其它动物恰好移动一次。如果全部猫都不动而全部狗都动，那么可以贪心求出答案，最多移动一个狮子。同理可以处理全部猫动而全部狗都不动的情况。现在考虑同时存在猫和狗不阅读全文

posted @ 2018-03-21 01:11 Claris 阅读(311) 评论(0) 推荐(0) 编辑

2018年3月17日

BZOJ5207 : [Jsoi2017]隧道

摘要：若$\min(n,m)<\min(n+1,m-1)$，则考虑计算左边与右边不连通的概率，然后用$1$减去它得到答案。若$\min(n,m)\geq \min(n+1,m-1)$，则考虑计算对偶图中上边与下边不连通的概率。同时当$n<m$时还可以旋转$90$°来交换$n$和$m$，使得$m\leq 阅读全文

posted @ 2018-03-17 04:02 Claris 阅读(498) 评论(0) 推荐(0) 编辑

2018年3月12日

XVIII Open Cup named after E.V. Pankratiev. Ukrainian Grand Prix

摘要： A. Accommodation Plan 对于已知的$K$个点，离它们距离都不超过$L$的点在树上是一个连通块，考虑在每种方案对应的离$1$最近的点统计。即对于a56爆大奖在线娱乐点$x$，统计离它距离不超过$L$的点数$call[x]$，再减去离它和它父亲距离都不超过$L$的点数$cext[x]$，然后用组合阅读全文

posted @ 2018-03-12 01:37 Claris 阅读(956) 评论(0) 推荐(0) 编辑

2018年3月11日

BZOJ3457 : Ring

摘要：根据Polya定理： \[ans=\frac{\sum_{d|n}\varphi(d)cal(\frac{n}{d})}{n}\] 其中$cal(n)$a56爆大奖在线娱乐长度为$n$的无限循环后包含$S$的串的数量。对于$cal(n)$的计算，考虑用总方案数$2^n$减去单次循环内不包含$S$的方案数。枚举进阅读全文

posted @ 2018-03-11 03:05 Claris 阅读(454) 评论(1) 推荐(0) 编辑

2018年3月10日

ZOJ Monthly, March 2018

摘要： A. Easy Number Game 贪心将第$i$小的和第$2m-i+1$小的配对即可。 B. Lucky Man $\sum_{i=1}^n\lfloor\frac{n}{n-i+1}\rfloor=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum_{i=1 阅读全文

posted @ 2018-03-10 18:40 Claris 阅读(1715) 评论(6) 推荐(4) 编辑

BZOJ2647 : [Neerc2011]Journey

摘要： $|x|+|y|=\max(x+y,x-y,-x+y,-x-y)$，设$f[i][j]$a56爆大奖在线娱乐在$(0,0)$，朝向方向$j$，执行第$i$条指令后的信息： $cir$：是否陷入循环 $d$：朝向 $x,y$：坐标 $v_0$：$\max(x+y)$ $v_1$：$\max(x-y)$ $v_2$：$ 阅读全文

posted @ 2018-03-10 03:25 Claris 阅读(256) 评论(0) 推荐(0) 编辑

Asia-Tsukuba 2017

摘要： A. Secret of Chocolate Poles DP，$f[i][j]$a56爆大奖在线娱乐高度为$i$，顶层颜色为$j$的方案数。时间复杂度$O(l)$。 B. Parallel Lines 将$O(n^2)$对点对按斜率分组，设$f[S][i]$a56爆大奖在线娱乐$S$集合的点已经配对，当前分组选了$i$条直线的阅读全文

posted @ 2018-03-10 01:46 Claris 阅读(1096) 评论(0) 推荐(0) 编辑

2018年3月9日

BZOJ3877 : [Ahoi2014&Jsoi2014]保龄球

摘要：考虑从前往后放所有轮。如果上一轮是全中：那么这一轮如果是补中，一定放第一次最小的，这样可以让第一次大的放在其它补中之后。如果这一轮是失误，那么一定放总分最大的。如果上一轮是补中：这一轮一定放第一次最大的。 a56爆大奖在线娱乐每�a56爆大奖在线娱乐捶挪怪欣锏谝淮巫钚〉模捶挪怪欣锏谝淮巫畲蟮摹� 最优解中一定是全中补中阅读全文

posted @ 2018-03-09 02:15 Claris 阅读(448) 评论(0) 推荐(0) 编辑

2018年3月7日

Petrozavodsk Winter-2018. Carnegie Mellon U Contest

摘要： A. Mines a56爆大奖在线娱乐点能爆炸到的是个区间，线段树优化建图，并求出SCC进行缩点。剔除所有不含任何$n$个点的SCC之后，最小代价为a56爆大奖在线娱乐入度为$0$的SCC中最小点权之和，用set维护即可。时间复杂度$O(n\log n)$。 B. Balls 用set维护所有球和墙的坐标，操作1显然。对于操阅读全文

posted @ 2018-03-07 23:07 Claris 阅读(1356) 评论(0) 推荐(0) 编辑

BZOJ4218 : 不知道高到哪里去了

摘要：设$degi[x]$和$dego[x]$分别a56爆大奖在线娱乐a56爆大奖在线娱乐点的入度和出度，将线性规划的限制写出来：目标函数： $\max.\ \sum_{x=1}^n(dego[x]P[x]-degi[x]Q[x])$ 限制： $P[x]-Q[y]\leq T(x,y)-L(x,y)$ $Q[y]-P[x]\leq L 阅读全文

posted @ 2018-03-07 01:58 Claris 阅读(606) 评论(0) 推荐(0) 编辑

2018年3月6日

Petrozavodsk Winter-2018. Jagiellonian U Contest

摘要： A. XOR 求出所有数的异或和$sum$，将所有数and上$sum$，然后求线性基，则选取$sum$的所有$1$对应的基最优。时间复杂度$O(n\log x)$。 B. Tribute 按题意模拟即可。 C. Boardroom Meeting CDQ分治+扫描线树状数组，时间复杂度$O(n\l 阅读全文

posted @ 2018-03-06 22:00 Claris 阅读(1076) 评论(0) 推荐(0) 编辑

2018年3月4日

BZOJ4267 : 小强的颜色

摘要：首先剔除$1$号心情不能到达的无用心情，然后采用分割法进行DFA的最小化。每次遍历所有集合，将集合中和集合中第一个心情行为或者转移所在集合不同的心情放入新集合中。最后按字典序依次给a56爆大奖在线娱乐集合编号即可。因为最多$O(N)$次分离，每次遍历时间复杂度为$O(NP)$。故总时间复杂度为$O(N^2P 阅读全文

posted @ 2018-03-04 22:14 Claris 阅读(302) 评论(0) 推荐(0) 编辑

2018年3月3日

BZOJ2512 : Groc

摘要：最优解一定是将起点、终点以及所有必经点连接成一棵树，对于每条树边恰好走两次，而从起点到终点的一条路径只走一次。考虑连通性DP，设$f[i][j][k][x]$a56爆大奖在线娱乐考虑完前$i$个走道，第$i$个走道底部和上部是否存在于树中，底部和上部是否和起点连通，走一次的路径端点是底部还是上部时的最小代价。时阅读全文

posted @ 2018-03-03 22:28 Claris 阅读(263) 评论(0) 推荐(0) 编辑

2018年2月23日

BZOJ3644 : 陶陶的旅行计划

摘要：假设是序列问题，且$S<T$，可以贪心求解，通过维护下述信息进行区间合并。对于区间$[l,r]$，维护的信息有： $v$：跳到了$\geq r$的位置后，可以花费$1$往右最多扩展多少。 $f[i]$：从$\leq l+i$开始跳到$\geq r$的位置的最少步数。 $g[i]$：从$\leq l 阅读全文

posted @ 2018-02-23 17:12 Claris 阅读(297) 评论(0) 推荐(0) 编辑

2018年2月22日

BZOJ1439 : YY的问题

摘要：考虑容斥，枚举哪些不存在的边选中了，剩下的不管，则可以用组合数计算方案数。时间复杂度$O(m2^m+nm)$。阅读全文

posted @ 2018-02-22 23:12 Claris 阅读(244) 评论(0) 推荐(0) 编辑

2018年2月21日

BZOJ2872 : 优莱卡

摘要： $A$类数据：直接输出$B[l]$，$O(n+m)$。$B$类数据：ST表求区间最小值，$O(n\log n+m)$。$C$类数据：可持久线段树求区间$k$小值，$O((n+m)\log n)$。剩下的数据先用可持久线段树求出$a,b$的实际值，转化为矩形内$B$值的询问。$D$类数据：即求矩形$B 阅读全文

posted @ 2018-02-21 01:48 Claris 阅读(248) 评论(0) 推荐(0) 编辑

2018年2月18日

BZOJ3273 : liars

摘要：枚举a56爆大奖在线娱乐人，计算他必定是诚实者的情况下至少有几个人说谎，若超过$t$则他肯定是说谎者。对于至少有几个人说谎，区间信息可以合并： a56爆大奖在线娱乐区间维护最左最右两个人$l,r$以及$f[i][j]$a56爆大奖在线娱乐$l$和$r$诚实说谎状态分别为$i,j$时他们之间至少几个人说谎。利用前缀和、后缀和可以在$O(1)$时阅读全文

posted @ 2018-02-18 02:22 Claris 阅读(270) 评论(0) 推荐(0) 编辑

Claris' Blog

公告