lis on tree 题目链接 题目大意 给一棵树，每个点都有点权 求根节点（1号）到每个点的路径上的最大递增子序列 题解 怎么求最大递增子序列？（没有必须要包含当前这个点） 要么是父节点的答案，要么是前面点权比它小的点的ans最大值+1. 怎么求前面比它小的点的ans的最大值？ 用一个数据结构维护就好。 用一个线段树存维护最大值。 代码： #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <map> #inclu...

青蛙过河 题目链接 题目大意 规定：青蛙只能站在比他大一号的青蛙的身上，荷叶上只能站一个青蛙，石墩上可以最底下站一个青蛙然后 按照规定往他身上站。 初始时，青蛙在河的岸边也是按规定摞起来的（1~n，最底下是n） 并且要跳到岸对面的时候也要按规定摞起来。 河上有n个石墩，m个荷叶，问最多可以让多少个青蛙过河。 题解 别人的题解 无从下手的我，害 菜啊我 上面的那个题解就很好了， int main() {  int n,m; scanf("%d%d",&n,&m); printf("%lld\n",(1ll << n) * (m ...

珂朵莉树（老司机树） 别人的博客。。 看别人博客学的，链接在上面。 算法比较暴力，应该都看得懂 主要用set实现 一般什么时候用？ 推平一段区间（把区间里的数变为一个数） 数据随机（数据水）哈哈哈哈哈哈哈 具体实现 存的东西 mutable ：可变的， set中的东西只能读不能改。 但是加上这个也可以改。 因为不知道这个，ce的我快崩溃了 struct Node {  int l,r;//区间 mutable ll v;//值 Node(int lp,int rr = -1,ll vv = 0):l(lp),r(rr),v(vv){ };//初始化 bool operator < (co...

C - Greetings! 题目链接 题目大意 给n种信，每种信wi,hi,pi 分别代表长、宽、数量。 让选择k种信封来装这些信，每个信封里装一个。 如果把w,h的信装到了x,y的信封里，那么造成的浪费为x * y - w * h; 问装完这些最小造成多少浪费 n，k <= 15 题解 dp数组： dp[i][j] 表示用i种信封装集合为j的信造成的浪费最小是多少。 j怎么表示一个集合? 状压。 主要是想不到怎么表示dp数组。害~ 想到这里就变得很简单了。 先预处理出每种集合的浪费数量s：  for (int i= 0; i < (1 << n); i ++ ) {...

H - Hash Code Hacker 题目链接 大意 hash的算法: s [0]*31^( n -1) + s [1]*31^( n -2) + … + s [n -1] 给出一个k，让找出k个hash值相等的字符串，（只能由大小写英文字母构成）。 题解 这道题，毫无头绪，我又菜了。 好菜好菜 把它看成31进制，，， 前一位数-1，后一位数+31. 与原来的串相等。 代码 #include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include...

D - Yet Another Yet Another Task 题目链接 题目大意 让你从一段区间里删除一个最大值，求他们的和。 问这个和的最大值是多少。 n是1e5. 但是数组里数字的大小只有 -30~30 题解 求一段区间删除最大值后的和。 可以枚举一个数，假设这个数是删除的数 然后求 这个数的前面连续的小于等于这个数的和的最大值 和 这个数后面的连续的小于等于这个数的和的最大值 这怎么求？ dpl[i][j] 表示第i个以及第i个左边小于等于j的数的和的最大值。 dpr同理 然后从左到右处理一遍，从右到左处理一遍就好了 怎么处理？ 假设这个值是a[i] 然后在他后面比a[i]大的值都可...

C - Cent Savings 题目链接 题目大意 给n个东西，每个东西ai块钱，付钱的时候四舍五入，让把这n个东西分成最多k+1块，问付的最少的钱是多少。 题解 dp[i][j] 表示前i个物品分成 j 块至少需要多少钱。 转移方程就是前i个物品分成j块，可从前k个物品分成j - 1块转移来。然后取最小值就好。 代码 #include <iostream> #include <cstdio> #include <vector> #include <stack> #include <queue> #include <map&g...

C - Folia 题目链接 题目大意 有一棵二叉树，总共n层（1e5），每层有ai个叶子节点（1e8）. 问这个二叉树里最多有多少个节点。 肯定优先这种情况：一个连一个的这种  二叉树最多有两个儿子，所以我比赛的时候总想着从上往下推万一多了，不能满足下面的，从下往上又不一定上面有那么多。 于是我就懵逼了。 题解 如果这一层下面总共有x个叶子节点，最好分出x个分支，每个叶子节点一个分支，随便到第几层截至，只要是在这层下面即可。 但是x个分支不一定能分出来，因为还受上层不是叶子结点的分支有多少个限制。  这个图的过程就是： 想在1的下面分出4各分支，但是1的下面最多有2个分支，所以分两个。 2的...

莫的难题 题目链接 题目大意 给你五个数，每个数字可以重复选，让你找出第C(n,m) % 1e9+7大的数。 题解 可以先写出C(n,m)的表， 于是题就变成了求由这些数组合成的第k大的数。 怎么求？ 把k变成五进制~~（哇妙啊 太妙了）~ 然后输出第几位就好了。 #include <algorithm> #include <cstdio> #include <iostream> #include <vector> #include <stack> #include <queue> #include <map>...

古老的牛市，遗迹的天梯 题目链接 题目大意 有n个台阶每个台阶的高度是ai（保证递增），刚开始在第一个台阶上面 可以跨到比当前台阶高1的台阶上 可以后退一步（如果过当前在第一个台阶上就不能后退） 如果后退了k步，可以走到高度小于等于2的k次方的台阶上。 问最少多少步走到第n个台阶上，如果不能输出-1. 题解 肯定是dp题， dp表示的状态是走到第i个台阶所需要的最小步数。 状态转移： 这个台阶可以是从他前面的任何一个过来的。 所以枚举一下它前面的，还得枚举他往后退了多少步。 因为这样才能判断能不能跳到这个地方。 所以转移方程是 dp[i] = min(dp[i],dp[j + k] + k +...

异或 题目链接 题意 给一个带边权的无向联通图（5e4个点）。 x到y的路径距离定义为x点到y点的路径上的边权异或和。 问从1到n的最远路径是多少（异或和）。 一个边、点可以走无数次。 题解。 题解很聪明，而我很笨拙 hhhhhh 因为要求1~n的路径上的边权异或和最大。 1、如果有环，如果想要这个权值，那么这个环的权值一定是取的。 因为是异或，所以  这样走，会发现只多了一个环的贡献。 2、可以选一个从1~n的路径然后从环里面选几个使得异或最大。 为什么可以这样？ 因为如果只有这一条路径从1~n。那么答案就是那个。 如果有其他路径，那么一定会构成环！！（因为是无向图） 构成环，在上面已经统计...

月出皎兮，佼人僚兮。 题目链接 题意 给一棵树，每个点有两个属性a,b 代表这个点有b个a颜色。 颜色不一样的点可以匹配（不管有没有连）。 1是根节点。 让求每颗子树的最大匹配。 题解。 性质：在一堆颜色中找个个数的最大值， 如果最大值小于等于所有颜色的个数的和，那么所有的都可以匹配即sum/2。 如果最大值大于所有颜色个数的和，那么匹配的数量是sum - maxx。 这个我怎么不知道？ 我咋想不到。。一直在纠结怎么快速得到匹配的数量，就是想不出来 最近太差劲了。菜 知道这个性质就好做了，因为是统计子树的问题，很容易想到dsu on tree。 所以代码: #include <algor...

[SCOI2005]最大子矩阵 题目链接 题意 给你n * m 的矩阵 n <= 100 m <= 2; 让你从这个矩阵中选k个不相交的子矩阵，问最大的和是多少。 题解 这题，，一看到我就不知道该怎么下手，想半天想不出来个啥，啥都想不出来，遇到这种多维的dp就不知道怎么下手，很烦。 题解： 因为最多有两列 dp数组：dp[i][j][k] 表示 第一列前i个跟第二列前j个可以出k组的最大值是多少。 状态转移： dp[i][j][p] = max(dp[i][j - 1][p],dp[i - 1][j][p]); for (int t = 0; t < i; t ++ ) { ...

失衡天平 题目链接 题意 给一个数组（代表一个东西的重量），每次选一些东西出来分成两堆，两堆的重量的差不能超过m，问最多可以获得的重量是多少。 （可以选多次，但一个东西只能选一次） 题解。 被他可以选多次忽悠了。 例如样例给的： 5 4 1 5 61 65 100 第一次选 1 5 第二次选 61 65 答案就是132. 但是选多次跟选一次是一样的。因为 可以选1 + 65 5 + 61. 这样的话，就dp dp[i][j]代表 前i个分成两组，两边的差的绝对值为j的最大重量和。 于是遍历到当前i点的时候ai可以放到左边也可以放到右边。 所以状态转移： dp[i][j + a[i]] = ma...