Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「JSOI2007」建筑抢修 - 贪心

    部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多的建筑。

    于  BZOJ, JSOI, 贪心 继续阅读

  2. 「JSOI2007」麻将 - 枚举 + 贪心

    在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数 不被限制在一到九的范围内,而是在 1 1 n n 的范围内。同时,也没有每一种牌四张的限制。一组和了的牌由 3m+2 3m + 2 张牌组成,其中两张组成对子,其余 3m 3m 张组成三张一组的 m m 组,每组须为顺子或刻子。现给出一组 3m+1 3m + 1 张的牌,要求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。

    于  BZOJ, JSOI, 枚举, 贪心 继续阅读

  3. 「JSOI2008」最小生成树计数 - 搜索

    求一个图的不同的最小生成树的数量,保证相同权值的边数量 10 \leq 10

    于  BZOJ, JSOI, 搜索, 最小生成树 继续阅读

  4. 「JSOI2008」星球大战 - 离线 + 并查集

    给一个图,每次删除一个点,求连通块数量。

    于  BZOJ, JSOI, 并查集, 离线 继续阅读

  5. 「JSOI2008」火星人 - Splay + Hash

    给定一个字符串,每次修改一个字符、插入一个字符、查询某两个后缀的最长公共前缀。

    于  BZOJ, Hash, JSOI, Splay, 字符串 继续阅读

  6. 「JSOI2007」字符加密 - 后缀数组

    把一个字符串 S S 排成一圈,从每个字符开始读一圈,把每次读到的字符串排序,按顺序将每个串的最后一个字符排成一个新字符串,求新字符串。

    于  BZOJ, JSOI, 后缀数组, 字符串 继续阅读

  7. 「JSOI2009」有趣的游戏 - AC 自动机 + 概率与期望

    现有 n n 个单词,均由前 m m 个大写字母组成。每一时刻随机产生一个字母,产生第 i i 个字母的概率为 piqi(0piqi) {p_i \over q_i} (0 \leq p_i \leq q_i) T T 时刻后会产生一个长度为 T T 的串。

    如果某个时刻,有一个单词在这个串中出现了,则过程结束。求产生的串中出现每个单词的概率。

    于  AC 自动机, BZOJ, JSOI, 字符串, 数学, 概率与期望, 高斯消元 继续阅读

  8. 「JSOI2007」文本生成器 - AC 自动机

    「文本生成器」可以随机生成一些文章 ―― 总是生成一篇长度固定且完全随机的文章 —— 也就是说,生成的文章中每个字节都是完全随机的。

    如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章 a a 包含单词 b b ,当且仅当单词 b b 是文章 a a 的子串)。

    求生成的所有文本中可读文本的数量。

    于  AC 自动机, BZOJ, DP, JSOI, 字符串 继续阅读

  9. 「JSOI2008」魔兽地图 - 背包 DP

    游戏中,一些装备有价格,可以无限购买;另一些装备需要其它装备合成,这些装备有合成次数限制。每个装备都有膜法值,求 M M 个金币最多能得到多少膜法值的装备。

    于  BZOJ, DP, JSOI, 背包 DP 继续阅读

  10. 「JSOI2009」游戏 - 博弈 + 二分图匹配

    N×M N \times M 的迷宫中有一个棋子,AA 首先任意选择棋子放置的位置。然后,YY 和 AA 轮流将棋子移动到相邻的格子里。

    游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏。

    求 AA 初始将棋子放在哪些格子会有必胜策略。

    于  BZOJ, Dinic, JSOI, 二分图匹配, 博弈, 网络流 继续阅读