AC. 梦想

[ZJOI 2013] 蚂蚁寻路

题意简述 给定一个n \times m的带权网格。 要求在网格中选出一个封闭图形。具体可以用一条路线描述。 开始位置在某一格点上,方向朝向北。接着右转两次,左转两次,右转两次,左转两次…… 最后再右转一次。规定这条路线上,不能连续旋转两次,不能经过重复的点,最后需要回到起始……
17/03/02 | 暂无评论 | 543阅读 阅读详情

[ZJOI 2013] 丽洁体

题意简述 给定一个串s。 现在你需要删去尽量少的字符,让其可以和模板串a*b*c匹配。 其中a,b,c是三个串,*可以匹配0个或多个字符。 1 \le |s|, |a|, |b|, |c| \le 50000,保证每个字符出现不超过500次。 算法讨论 难得的清真题。 考虑一个暴力。设f(i,j)为考虑到s的第i个字符,……
17/03/01 | 暂无评论 | 682阅读 阅读详情

[ZJOI 2013] 抛硬币

题意简述 有一枚硬币,抛出正面的概率是\frac{a} {b},反面的概率就是1 - \frac{a} {b}。 现在给定一个硬币序列S(正面/反面)。现在开始连续抛硬币,当某一枚硬币抛完后,若S作为一段连续子序列出现在了抛出的硬币序列中,则停止。 求到停止的期望步数。输出一个最简分数。 1 \……
17/03/01 | 暂无评论 | 1,075阅读 阅读详情

[ZJOI 2013] 话旧

题意简述 有一个长度为n+1的序列A_0, A_1, ..., A_n,满足下列条件。 1. A_0 = A_n = 0。 2. 对于0 \le i \le n - 1,|A_i - A_{i+1}| = 1。 3. 对于所有极小值点k,有A_k = 0。 我们还规定了A的m个位置的值。 求满足条件的序列个数 和 序列最大值的最大值。第一问的答案对19940……
17/03/01 | 暂无评论 | 762阅读 阅读详情

[ZJOI 2014] 消棋子

题意简述 有一个r \times c的棋盘和n种颜色的棋子,每种颜色各两枚。 棋盘中一个格子可能为空,也可能有恰好一枚棋子。 你可以执行一种消棋子的操作:选定一个空格子和两个平行于坐标轴的方向,如果这个格子在这两个方向上第一个遇到的棋子是同种颜色的棋子,则这两个棋子可以同……
17/03/01 | 暂无评论 | 672阅读 阅读详情

[ZJOI 2014] 星系调查

题意简述 给定n点m边的简单无向连通图。每个点对应一个二维平面上的坐标。 有q个询问,每次给定u,v,求u,v所有简单路径中,路径权值的最小值。 路径权值定义为,在所有直线中,到路径上所有点对应的坐标的欧几里得距离的平方和的最小值。 1 \le n, q \le 10 ^ 5, m \le n,权值\……
17/03/01 | 暂无评论 | 739阅读 阅读详情

Codeforces 炖题计划

做一波Codeforces的题目涨涨姿势。 744B Hongcow's Game 有一个n \times n的矩阵,A_{i,i} = 0。 现在你有不超过20次的询问机会,询问一个[1, n]的下标集合S,对所有i,返回M_i = \min_{j \in S} {A_{i, j}}。 现在你需要求出对于所有i,求出Q_i = \min_{j \neq i} {A_{i, j}}……
17/02/13 | 暂无评论 | 857阅读 阅读详情

TopCoder SRM 练习记

膜拜一波集训队作业QAQ 练习一下TC SRM提高智商~ 虽然知道早有大爷们写好了完整清楚的题解,但是感觉还是尽量自己独立做,记录一下题解效果更好。在博客上写这么多题解不太好管理,就传到GitHub上好啦,长期更新~ 传送门 链接 欢迎大家指正错误。
17/02/12 | 暂无评论 | 1,464阅读 阅读详情

THUWC 2017 游记

记录一下THUWC吧,毕竟还是挺有意义的。 说起来2月8日我们就回杭州了,于是完整地错过了WC的颁奖典礼,有点惨惨啊QAQ 2月9日下午接到了某PKU的神秘电话,可惜我在杭州啊(没有退路了?) 晚上报到。作为一个学军的学生,我也被自己学校的豪华震惊到了,这和西溪校区的画风完全不……
17/02/12 | 暂无评论 | 1,806阅读 阅读详情

WC 2017 游记

今年冬令营在绍兴市第一中学举行。WC 2017,有怎样的精彩呢? 这一波我就不详述每一天的经历了。不妨就几方面总结一下这次的冬令营吧! 住宿。这是我第一次住学校的宿舍哎,好新奇。绍兴一中生活方面准备的还是不错的呐,至少感觉住的还是挺舒心的。晚上有空调好评,每人都有书……
17/02/08 | 暂无评论 | 1,616阅读 阅读详情