P4683 [IOI2008] Type Printer 打印机 题解
一段时间没打字符串相关的题了,找道简单的 Trie 练练手。 题意 题目链接。 维护一个复古打印机,支持添加字母,删除字母,打印字母。求用最小步骤打印出所需的所有单词。 解析 首先容易想到建 Trie,然后在 Trie 上进行 dfs,每次走到一个结点就添加这个结点对应的字母,若走到了一个单词的结尾就打印,然后在每层 dfs 返回之前删除当前字母。…
生物|遗传病|基因|必修二综合练习一道遗传题|解答
题面 如图为某种常染色体隐性遗传病的系谱图(深色代表的个体是该遗传病患者,其余为表型正常的个体)。近亲结婚时,该遗传病发病率较高,假定图中第 Ⅳ 代的两个个体婚配生出一个患有该遗传病子代的概率是 $\frac{1}{48}$,那么,得出此概率值需要的限定条件是(  )。 A.Ⅰ-2 和Ⅰ-4 必须是纯合子 B.Ⅱ-1、Ⅲ-1 和 Ⅲ-4 必须是纯合…
OI 里的数学内容整理(提高组)
本博客仅罗列定理,不给出证明,如需要请自行搜索。 质数相关 线性筛素数 inline void sieve(int n){//线性筛求 pri 和 phi phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;} for(int j=1;j<=cnt&a…
CF1503B 3-Coloring 题解
题意 题目链接。 有一张 $n\times\ n$ 的网格,有 $1,2,3$ 三种颜色,每轮交互库会给出一种颜色,你需要在剩余两种颜色中选一种颜色涂在一个格子上,不可以使任何两个相邻格子颜色相同。你需要扮演涂色者将所有格子涂上颜色。 解析 首先我们考虑到,如果有一个空格子,其上下左右四个格子中有两种颜色,你就输了(因为交互库可以一直给出剩余的这种…
再一次谈个人的信息竞赛——想到什么写什么的胡言乱语而已
[hermit autoplay="false" mode="circulation" preload="auto"]netease_songlist#:551339691[/hermit] あぁ、少年の僕らよ 啊,少年的我们 情熱の日々も、約束もまた 如果热情的日子和约定也 消えてしまうなら 消逝的话 過ぎ去ってしまうなら 变成过去的话 ここに残…
P7473 [NOI Online 2021 入门组] 重力球 题解
题意 题目链接 给出一个正方形区域,其中有一些点是障碍。每次询问给出两个球的初始位置,询问至少需要改变几次重力才能使两球相遇。 解析 首先我们发现,实际上仅有障碍周围(包括地图边界)上的点是有意义的(因为任何位置的球经过一次操作一定会到这些点,显然一次操作是可以枚举的)。我们定义每一组有意义的 $(x,y)$ 为一个状态,显然最多状态数为 $200…
P2924 [USACO08DEC]Largest Fence G 题解
题意 题目链接 给定 $n$ 个点,求一个由若干个点连接成的凸多边形,所包含的点数最多,输出点数。 解析 先说解法:将所有边按照 atan2(y,x) 的值排序, 然后枚举凸多边形起点,再遍历排序后的边进行 dp 转移,复杂度为 $O(n^3)$。 大致思路与已有题解相同,但是我在这里想要阐述一个困惑我许久的点:为什么是 atan2 ? 搜索百度百…
数学|向量|高一下第一次月考卷填空题最后一题|解答
大概是要开一个文化课专题了,最近文化课有点崩,所以可能要抽点时间偶尔整理一些文化课的东西(基本都是错题)。 题面 设 $\vec{a},\vec{b},\vec{c}$ 为平面向量,$\vert \vec{a} \vert=\vert \vec{b} \vert=2,(2\vec{c}-\vec{a})\cdot(\vec{c}-\vec{b})=…
P7442 「EZEC-7」维护序列 题解
非常有意思的一道题(虽然确实容易想不出来)。 题意 题目链接 维护一个 $0 \sim 2^n-1$ 的序列,支持两个操作:将下标为偶数的数按序提前,将下标为奇数的数按序后置;将下标为偶数的数按序后置,将下标为奇数的数按序提前。 解析 我们考虑两种操作的实质。 第一种操作(偶前奇后):对于下标为 $x$ 的数,若 $x$ 为偶数,则它的新下标为 $…
P7443 「EZEC-7」加边 题解
题意 题目链接 树上的棋子博弈,每个点有权值。你可以添加一条边以试图反败为胜,不同的加边方法根据权值有一个代价,需要最小化这个代价。 解析 我们首先定义一个结点先手必败是 lose,先手必胜是 win,容易发现,叶子结点一定是 ​lose,然后对于每一个非叶子结点,只要它有一个儿子是 ​lose,它就是 win,否则,该结点也是 lose。一遍 d…