「雅礼day5/jzoj5398」崇拜Adore - 状态压缩+动态规划 发表于 2017-10-12 更新于 2019-06-10 分类于 OI Valine： 题目大意 小w 偶然间见到了一个 DAG。这个 DAG 有 m 层，第一层只有一个源点，最后一层只有一个汇点，剩下的每一层都有 k 个节点。现在小 w 每次可以取反第 i(1 < i < n - 1) 层和第 i + 1 层之间的连边。也就是把原本从(i, k1) 连到 (i + 1, k2) 的边，变成从 (i, k2) 连到 (i + 1, k1)。请问他有多少种取反的方案，把从源点到汇点的路径数变成偶数条？答案对 998244353 取模。 阅读全文 »
「雅礼day3」矩阵matrix - 动态规划 发表于 2017-10-11 更新于 2019-06-10 分类于 OI Valine： 题目大意 求出满足以下条件的 n*m 的 01 矩阵个数：（1）第 i 行第 1~li 列恰好有 1 个 1。（2）第 i 行第 ri~m 列恰好有 1 个 1。（3）每列至多有 1 个1。 阅读全文 »
「雅礼day3」字符串string - 线段树模拟 发表于 2017-10-11 更新于 2019-06-10 分类于 OI Valine： 题目大意 给定一个由小写字母组成的字符串 s。有 m 次操作，每次操作给定 3 个参数 l,r,x。如果 x=1，将 s[l]~s[r]升序排序；如果 x=0，将 s[l]~s[r]降序排序。你需要求出最终序列。 题目分析因为字符集大小$26$是一个常数，因此我们可以暴力查询区间中字符集的出现数量，然后暴力重置区间。 阅读全文 »
「雅礼day4」嘟嘟噜 - 约瑟夫环 发表于 2017-10-11 更新于 2019-06-10 分类于 OI Valine： 题目大意 多组询问求约瑟夫环问题答案。 题目分析经典的约瑟夫环问题。约瑟夫环有一种$O(n)$解法，若不会的推荐参考这里。 阅读全文 »
「雅礼day2」最大公约数gcd - 容斥原理+莫比乌斯反演 发表于 2017-10-11 更新于 2019-06-10 分类于 OI Valine： 题目大意 有$n$个正整数$x_1\ldots x_n$，初始时状态均为未选。有$m$个操作，每个操作给定一个编号$i$，将$x_i$的选取状态取反。每次操作后，你需要求出选取的数中有多少个互质的无序数对。 阅读全文 »
「雅礼day2」水流water - Bfs 发表于 2017-10-11 更新于 2019-06-10 分类于 OI Valine： 题目大意 有一块矩形土地被划分成 n*m 个正方形小块。这些小块高低不平，每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中，但是不能直接流入对角相连的小块中。一场大雨后，由于地势高低不同，许多地方都积存了不少降水。给定每个小块的高度，求每个小块的积水高度。注意：假设矩形地外围无限大且高度为 0。 阅读全文 »
「雅礼day2」扫雷mine - 动态规划 发表于 2017-10-11 更新于 2019-06-10 分类于 OI Valine： 题目大意 有一个 1 维的扫雷游戏，每个格子用*表示有雷，用 0/1/2 表示无雷并且相邻格子中有 0/1/2 个雷。给定一个仅包含?、*、0、1、2 的字符串 s，问有多少种方法将所有的?改为*/0/1/2 使其合法。 阅读全文 »
