题目链接 题解 这次的题目真的都还挺不错的，考的比较活 two times more这个关键信息告诉我们序列变化的规律，即为 $2^i$ 变换一次 于是我们可以考虑倍增 我们用 $s[i]$ 来表示第1到i段(每一次变化称为一段)的数字和 $ls1$ 为奇数序列，$ls2$ 为偶数序列 $lst1$ 表示当前奇数序列的首项，$lst2$ 同理 假设…
题目链接 题解 学OI学傻了，一开始想到一个 $O(m^n)$ 的暴力，显然是过不了的，后面想到一个 $O(2^nm)$ 的做法，就没思路了 其实正解很简单。 我们先取好一组（这里默认就是第一列），如果它的值大于0，那就是答案了，输出即可。 如果不大于0，它的值肯定就为0了，对于每一行，如果能找到一个数与当前所选的数不一致的数，那就选它（因为它们的…
题目链接 题解 人生第一道交互题，感觉很神奇（还好并不难） 考虑以下情况： 如果我们没有框中头尾，势必有一条“进入”矩形的边，就有一条“出去”的边。 如果我们只框中头或尾，肯定少一条“进入”或“出去”的边。 如果我们同时框中了头尾，肯定少两条“进入”或“出去”的边。 综上，当ask的答案为奇数时，我们框中了头或尾，为偶数时可能同时框中，可能同时没框…
题目链接 题解 贪心大水题，然后比赛的时候就被疯狂hack，至少现在下面的策略是能过的。 首先n要是偶数才有解 最左边是左括号，最右边是右括号（如果是问号直接变成对应的括号） 如果有解，肯定是左括号数目=右括号数目的，于是扫一遍字符串计数，当左括号没满足数目上限的时候一直填左括号 就这样~ 代码 [crayon-67eae2a5d403543374…
题目链接 题解 题目大意：给两个串，S，T，问S中有多少个子串与T的差异是在3个字符以内的。 这道题解法有很多，像什么SAM，FFT，NTT之类的，然而我只会哈希orz 二分找它们的最长公共前缀，最多能跳3次，没了…… 设N为S的长度，M为T的长度 时间复杂度 $O((N-M)\times (logM))$ 代码 [crayon-67eae2a5d…
题目链接 题解 哈希真的是个好东西,在O(N)预处理之后,能在O(1)的时间内枚举任意子串. 这道题我们可以考虑对每种字母进行哈希. 具体来讲,hash1[i][c]存储的是字母c的哈希值(位置) 这样处理之后,就在S串里面枚举长度为T串的子串,再枚举两种字母,如果26个字母哈希值能够相等,那么这样的变化是没问题的 时间复杂度 $O(N\times…
题目链接 题解 其实这题要不是当时在学莫队，真的没想过会用莫队解决（粗略估计一下复杂度会炸） 用bitset维护的这个想法很赞，不看题解想不出来 大概就是下面这样的一个思路 首先对于操作1，第一个bitset维护的是当前位出现与否，比如$bitset[3]==1$说明当前区间内，3出现过 如果说让bitset里面所有的数-x或者+x后，还有和原bi…
题目链接 首先这是一颗树。 这一题我们用贪心的方法来解决，首先来看看样例： 样例1很不友好，不如不给，显然我们可以经过3个点。 我们可以从样例2发现我们的贪心策略。 为了实现经过的点最多的这一条件，我们希望每次走一步都多走一个点，如果我们选择最长链的话，在链上每走一步就多走了一个点，如果走不完最长链，那答案就是步数+1，而如果走完最长链还有剩余步数…
T1 引子（水箱） 非常简单的模拟题目，错误点有两处： 1. 没有读入多位数字 2. 出现顺序和编号无关 然就是从1号水箱，开始递归，优先从箱底的水管递归下去，然后输出自身的编号。 [crayon-67eae2a5d471e199102915/] T2 可爱精灵宝贝 一道区间dp题，考场上写挂了，最后10分钟乱搞居然也有60分，考试完调了一下，有9…
T1 改造二叉树 题面 洛谷上的数据有水，过了不代表正确； 这题还是比较难想的（至少我是这么认为的） 首先如果我们对一颗平衡树进行中序遍历，得到的一个遍历的序列是单调上升的。 于是我们这道题就转化成一个这样的问题： 给一棵二叉树，让它的中序遍历序列变为严格单调上升序列，最少需要多少次修改 《算法竞赛进阶指南（第二版）》的263面提过一个思考题： 把…