ww3113306

摘要： 题意：求节点数为n的，高度大于等于h的二叉树的个数。 题解： 一开始没看到二叉树的限制，，，想了好久。因为数据范围很小，所以可以考虑一些很暴力的做法。 有2种DP方式都可以过。 1，f[i][j]表示节点数为i，高度恰好为j的方案数，那么$ans = \sum_{i = h}^{i <= n}{f[ 阅读全文

摘要： ~~~题面~~~ 题解： 观察到拼接后的数据范围过大，无法O(n)解决，但是大区间是由很多小区间组成，而小区间是固定的，不会变化，所以可以考虑预处理出每个小区间的信息，然后根据给定序列按顺序一步一步合并区间信息。 跟线段树维护区间最大子段和类似，要合并2个区间我们只需要知道如下信息： 前缀最大子段和 阅读全文

摘要： ~~~题面~~~ 题解： 观察到字母只有26个，因此考虑对这26个字母分别维护，每个线段树维护一个字母，如果一个线段树的某个叶节点有值，表示当前叶节点所在位置的字母是现在这个线段树代表的字母。 那么对于每一个操作，我们已经知道最后排好序之后肯定是按aaaabbbbccccddd……这样的序列排下去的 阅读全文

摘要： ～～～题面～～～ 题解： 感觉还是比较妙的，复杂度看上去很高（其实也很高），但是因为n只有100，所以还是可以过的。 考虑一个很暴力的状态f[i][j][x][y]表示考虑取区间i ~ j的方格，左右端点颜色分别是x, y.的最大值。 那么有如下转移 1,直接继承子区间的答案 f[i][j][x][ 阅读全文

摘要： ～～～题面～～～ 题解： 做这道题的时候zz了，，，， 写了个很复杂的式子，然而后面重新想就发现很简单了。 考虑用总的情况减去重复的。 假设唯一重复的两个数的位置分别是l和r，那么唯一会导致重复的方案就是中间不取，只取l和r中的一个和两边的数。 那么$ans =\binom{k}{n} - \bin 阅读全文

摘要： ～～～题面～～～ 题解： 貌似一般c题都是递推。。。 观察到最后一个插入的数一定在第一个，倒数第二个插入的数一定在倒数第一个，倒数第三个插入的数一定在第2个，倒数第四个插入的数一定在倒数第2个…… O(n) 的把数填进数组即可。 要证明的话想一想构造方式就知道了。 1 #include<bits/s 阅读全文

摘要： ～～～题面～～～ 题解： 偶然翻到这道题，，，就写了。 观察到一个数被插在哪里只受前一个数的影响，如果明确了前一个数是哪个，那么我们就可以确定大小关系，就可以知道当前这个数插在哪里，而上一个插入的数就是上一个数，所以根据这个来设DP状态。 f[i][j]表示满足理想数列的i ~ j，且i是最后一个插 阅读全文

摘要： ～～～题面～～～ 题解： 首先题目要求删除一些颜色，换个说法就是要求保留一些颜色，那么观察到，如果我们设ll[i]和rr[i]分别表示颜色i出现的最左边的那个点和最右边的那个点，那么题目就是在要求我们选出的区间要满足区间[l, r]内所有颜色的max(rr[i]) <= r,并且min(ll[i]) 阅读全文

摘要： ～～～题面～～～ 题解： 题目大意：有2堆石子数分别为x, y的石子，你每次可以从中间的某一堆中取出2i个石子，扔掉i个，并把剩下的i个放到另一堆，无法操作的人就输了。 现在给定x,y，判断先手必赢还是先手必输。 表示这题推出了一个性质，，，然后，，，就没有然后了。 看题解还是比较妙的。 结论：如果 阅读全文

摘要： ～～～题面～～～ 题解： 观察到以决策点为分界线，以点数大的赢为比较方式的游戏都是它的前缀，反之以点数小的赢为比较方式的都是它的后缀，也就是答案是由两段答案拼凑起来的。 如果不考虑判断胜负的条件的变化，则有一个比较容易发现的贪心： 设f[i]为从1开始到i位， 比较方式为点数大的获胜，最多能赢几局。 阅读全文