题目： 一棵二叉树的中序遍历是1、2、3...n。每个结点有点权a[i]。让你确定一棵树使val最大。最后输出val并给出先序遍历序列。 （n最大100） 做法： 一个区间DP的题。但感觉dfs码起来更清晰，思路是一样的。对[l,r]区间确定的一棵二叉树，它的我们通过枚举根节点的位置来转移： 转移时记录此区间的根，回头打印先序遍历时就很简单了。具体细节看代码咯。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout <&l...

题目： n部电影，有时长和若干放映起始时间。Bessie可以在某部电影的放映阶段去看这部电影或中途离开。他不会看同一部电影2次。问Bessie最少需要看几部电影使得他在0~L时间段内一直看电影。(n最大20) 做法： 状压DP。 表示在状态下Bessie能连续看电影到的最远时间。是二进制状态。第i位为1表示第i部电影已经看过，0表示没看过。转移的时候就找一个中的一个0将它置1。表示下一部要看的电影就是它。然后在这部电影的放映时间vector中二分第一个比当前时间小的放映时间。用+电影时长更新就好了。转移：统计最少的电影数量： 代码： #include <bits/stdc++.h&g...

题目： 2个4*n的图，表示后手和先手部署炮台的方案。问先手那方在消灭后手所有炮台的条件下最多能保留自己多少炮台。 做法： 先求出后手和先手炮台联通块数量和。若，无解。否则，由于先手每次打击后必定暴露一个联通块。我们贪心选择暴露炮塔数量少的联通块就行了。所以先手方最多能保留最大的个联通块中的炮台数。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << e...

题目： a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1 ≤ i ≤ N）和一高度Hi。a180285 能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是 a180285 滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够...

题目： 小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列{ap1,ap2,...,apm}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), 成立。输出答案mod 1,000,000,007。输入描述: 做法： 看似无从入手。但可以发现a[i]和下标i是捆绑的。 这个东西移项变形一下：。那么我们求出每个形成一个数组。问题就转化成在上的LIS（最长上升子序列）dp问题。解决问题。 代码： #include <bits/stdc++.h> ...

题目： n个点，m条边的无向图。有些边被标记为0或1，有些还未标记。问你将剩下的边用0或1标记，满足图中所有环边权异或和为0的方案数。mod998244353 做法： 这题不会，看题解才懂。。边权的方案不好弄，考虑点权。这里的思想就是，假如我确定了某个环上所有点的点权，使点权异或和为0。那么边（u，v）的边权用val[u]^val[v]得到，是满足边权异或和为0的。也就是点权与边权可以建立映射关系。但是请注意不是一一映射的关系。比如，点权(1,1)和(0，0)同时映射边权0。所以点权的2种方案对应边权的1种方案。而这两种点权方案互反。首先我们用已标记的边新建一个图。然后我们选一个未标记的点u...

题目： 一个长为n的序列a[]，所有长度≥k的区间取出第k大的数形成一个新序列b[]。问b[m]的值。 做法： 显然我们不可能求出b中所有数然后取出第m个。所以想到二分这个数，设为x。然后问题就转化成判定性问题：a[]中所有连续区间的第k大的数≥x的区间个数是否≥m。用滑动窗口的做法使这个judge复杂度为O(n)，可以解决问题。具体做法就是枚举每个位置作为区间的左端点l，找到对应的右端点r，使[l,r]区间中恰有k个≥x的数。这样我们就能一次统计出左端点为l的且第k大数≥x的区间个数：n-r+1。(r往后每一个位置都满足)。然后左端点l+1时右端点只需在当前的基础上向右扩展就行了。整个过程...

题目： 从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。 做法： 为每组开个优先队列。第个人加入时就在敌对队列中不断pop出的人就行了。至于题目中能力值的修改。由于是个整体修改。用一个全局变量维护就好。表示前面所有人能力的上升值。每个人的能力值就能用队列中的能力值...

题目： 二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？ 做法： 二分木棍的长度。O(n)judge，跑起来无压力。就这样无脑过了。 代码： ...

题目： 一棵树，边有流量。让你找一个点u到所有叶子结点路径上流量和最大。 做法： 换根dp。首先选定一个非叶子结点为根，一遍得到子树到该子树下叶子结点的流量。 （v是u的儿子结点，w是边的流量）。 表示以为树根点，到所有叶子结点路径上流量和。显然此时我们以此为基础再一遍将根换到儿子结点，求得所有值。考虑根从换到的影响。首先子树向下的流量加上去，然后截断向的流量，并加上从到的流量：最后PS:代码中为了处理方便，叶子结点的流量flow被设成了边的流量，在换根dp时需要减回来。PPS:感谢评论区指出错误：不能默认用1为根，因为1可能是叶子结点换根时会少算通向1的流量。所以我们要特判和的情况，当时，...

题目： 牛妹有一张连通图，由n个点和n-1条边构成，也就是说这是一棵树，牛妹可以任意选择一个点为根，根的深度为0，对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如1为根，1-4的；路径为1-3-5-4时，4的父节点是5，并且满足对任意非根节点。整棵树的价值。。即所有点的深度和。 牛妹希望这棵树的W最小，请你告诉她，选择哪个点可以使W最小。对于100%的数据， 做法： 有点诡异。做法1：盲猜最优点在重心上。一遍求重心。从开始再一遍求深度和。做完。做法2：换根dp。表示以为整棵树的根的深度和。我们可以一遍求出以1为根的深度和。然后从1在一遍求出将根转移到子树上的深度和...

题目： 求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。 做法： 由于到了。递推都做不了了，唯有推柿子大法。考虑每一位和前面的位对答案的贡献。第位上的0对答案无贡献。第位上的1对答案的贡献是前位上0的数量。前位形成个01串，每个串长。所以共有个数字。其中0和1各占一半！所以前位上0的数量：。而后面的位是0是1对当前第位的贡献没有影响，直接把乘进去即可。所以第的贡献就是。(第i位上的1配上前i-1位上的0)考虑每一位的贡献：快速幂求解即可。PS：特判掉。 代码： #include <bits...

题目： 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。1<=n<=1000,0<=数组元素<100000。 做法： 首先预处理出数组，表示这个区间元素的和。这样我们就可以得到任意区间的和。[l,r]区间的xor和 = prefix[r]^prefix[l-1]。设选出的互不重叠区间对为A、B，且A在B左侧。我们枚举B的左端点x。此时我我们已经记录下了所有右端点小于x的区间，也就是合法的A已经全部记录下来了。则对于每个x，我们再枚举右端点y，看有几个A能匹配就行了。枚举完x后，将右端点为x的区间记录一下，因为下一次我们将枚举x...

题目： 给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。1<=n<=100000 做法： 设1为根，树形DP求解。设： 表示以为根的子树中结点到的路径为偶数的数量。 表示以为根的子树中结点到的路径为奇数的数量。树上所有路径可以视为经过根节点和不经过根节点两种。而不经过根节点的路径可以看成经过子树上根节点的情况。也就是说我们只需统计经过每棵子树根节点的路径就可以了。经过根结点的偶数路径的数量 = 偶数配偶数+奇数配奇数的情况。可以一边dfs一边求解。请看代码。 代码： #include &l...