A - Common Subsequence 题解：因为a数组和b数组里面的元素值都小于1000，所以我们可以开一个数组来存对于每个元素出现过的情况，最后遍历一遍1-1000，检查是否有同时出现的值即可 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1010; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c...

A. 打字机 题解：贪心只需要寻找最后一个d的位置，判断之前a的个数与b的个数是否相等。 如果a大于b则Sad，等于则为Happy 注意：在遍历字符串的同时，对于任何一个位置从开始到当前位置的a和b的个数，a都不可以小于b，如果小于，则输出Dead。 #include <bits/stdc++.h> const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int mod = 1e9 + 7; const int maxn=510; using namespace st...

题解： 我们首先枚举每个日期i，对于每个日期，对[1,i]区间内的值减去k，代表新增加了一天花费值 如果有了收入我们就把区间[第一天开始，这个工作开始得日子]加上val。 举个栗子： 首先：看这张图，我们先假设他没有活干，那么假设经过了6天，每天花费对应的值为上图， 1.如果你在第一天去了那个地方，那么到了第六天，对应得花费就是数字1下面对应得数字 2.如果你在第二天去了那个地方，那么到了第六天，对应得花费就是数字2下面对应得数字 ……6.如果你在第六天去了那个地方，那么到了第六天，对应得花费就是数字6下面对应得数字这样大概就明白了线段树储是如何储存得了。 其次： 如果我们在第4-6天有一份兼...

参考视频：https://www.bilibili.com/video/BV1wt411u7xL?t=1142讲的特别好！注释都在代码中了 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 2e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; c...

参考：https://www.bilibili.com/video/BV1Wt411L7te?t=1822大佬视频需要重构的条件是:当前结点的左子树或右子树的大小大于当前结点的大小乘一个平衡因子alpha或者以当前节点为根的子树内被删除的结点数量大于树大小的30%了 代码中有比较详细的注释 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 2e5+10; const...

题解：给n个数，询问q次，每次询问给出l,r. [l,r]区间求异或最大值为多少？所以用dp[l][r]来表示区间l,r的答案先对他进行预处理，预处理后就可以进行dp了。递推公式：f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j-1])); /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <stdli...

题解：树形dp对于每棵子树，有两种可能1.不删除这条边，两个点相连 2.删除这条边，两个点各自独立 定义dp[i][j] 表示 i 结点所在的连通块中节点数为 j 的方案数是多少 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <stdlib.h> #include <cstring> #include <...

题解：答案就是差距最大的逆序对的一半，因为两个数都减小一半就可以了。时间复杂度O（n） /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <stdlib.h> #include <cstring> #include <cmath> #include <math.h> #include <...

这题之前在kuangbin的专题做到过，用的是并查集题解：这里的话判断他是不是一棵树的条件1.一棵树只有一个根节点，所以我们记录所有点的入度，入度为0的点只能有一个。2.出了根节点，其他的点入度只能为1，不然就会出现图上这种情况3.所有点都必须要联通，不连通就是多棵树。 这样的话我们用并查集来给他进行合并即可最后遍历所有的点，检查是否符合条件即可 /*Keep on going Never give up*/ #include <iostream> #include <cstdio> #include <cstring> #include <cmath...

题意：X王国有n位官员，编号从1到n。国王是1号官员。除了国王以外，每个官员都有一个上司。我们称这个官员是这个上司的下属。上司的编号总比下属小。我们定义一个官员的影响力为他所有下属的影响力之和再加1。例如，一个没有下属的官员的影响力是1。国王的影响力总是n。任何一位有下属的官员总是选择他的下属中影响力最高的作为他的心腹（有若干下属影响力相同的话则会选择编号最小的）。一位官员得到一条消息后，他就要把消息传达给国王。我们定义一位官员的花费为他将消息传达给国王的花费。国王自己的花费为0。如果一位官员是他上司的心腹，则他的花费等于他上司的花费，否则他的花费为他上司的花费加1。由于时代和平，消息并不需要...

题解：这个题真的是停麻烦的，一不看题就要忘记干什么。。。首先这些个蚯蚓的长度是不断增加的（所有蚯蚓都在增加），所以在处理的过程中，先把增加的长度省去，只处理未增加长度。如果用优先队列复杂度就是O（m*logn） 这样的时间复杂度必然超时。看了看网上的题解，哦豁然开朗。用三个队列即可实现证明如下：如果a>=b那么a * p > = b * pa - a * > = b - b * p又因为他们之间同时增加长度，所以可以证明三个队列的单调性。之后按照题目的要求来进行输入输出即可。 代码： /*Keep on going Never give up*/ #pragma GCC op...

题意：华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：操作 1：输入格式1 i，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。操作 2：输入格式 2 i a表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。但是月月有时会检查华华有没有认真维护这...

题意：有 n 件货物， 第 i 件重 wiw_iwi​ 吨，另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。货物不能分拆，请判断这 x 个集装箱能否装下所有货物。题解：这题一开始TLE，无奈，看了dalao们的解法，感觉这题主要还是考这一个剪枝吧，在考虑要把这个货物装到哪个箱子的时候，对于每一个货物，我们单独给他开一个空箱子，如果是多个的话，那并没有什么意义，会有特别多的重复情况，（放到哪个空箱子不是放）。 for(int i=1;i<=min(steps,x);i++)代码： /*Keep on going Never give up*/ #pragma GCC opti...

题解：也是参考了网上大佬的解法才会的dp[i][j]表示到达第i岛屿，从上一岛屿跳过来的步长是D+j单位距离那么将会有三种递推情况1.这一步跳D+j的距离2.这一步跳D+j+1的距离3.这一步跳D+j-1的距离分别对应图上三个if为什么n最大只有250因为len=30000,并且每次步长最多递增1，1+2+3+...+n=n*(n+1)/2<=30000,n最多不超过250, 所以最长的步长不会超过D+250但是如果每次都-1的话，数组下标就成了负数了，所以这里把起点设置为250，就消除了负数的影响。 代码： /*Keep on going Never give up*/ #pragma...