Solution很奇妙的思路，看了第一篇题解才懂，先用结构体存每个士兵，然后按团数排序，再用优先队列存战力，用一个遍历cnt由n遍历到0，保证遍历保证每种可能都枚举到。注意在枚举时，如果队列里的元素超过当前限制，出队并减去这个元素对sum的贡献。 Code #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define lowbit(x) (x&(-x)) #define mp make_pair #define pb push_back #define ins ...

Solution鬼鬼，鬼知道我这道题做了多少次，一直卡在83，今天才发现ans的初始值没处理好，一开始ans初始化为0一直过不去，这么多天终于过了。取区间里两段长度为k的子区间使和最大，肯定是dp。设pre[i]前i个数的长度为k的区间的最大和，那么只要遍历的时候再加上i-k的另一段k区间就可以了。 Code #include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; inline ll read(){ll s=0,w=1;char ch=getchar(); wh...

Solutionn个点n-1条双向边明显是树，而且保证必定是偶数个节点，那么就肯定是两两配对。就一个节点来说，跟兄弟节点配对，或者跟父亲节点配对肯定是最优的。所以只需要判断节点所在子树里面的节点数是否为偶数，如果是偶数说明不用和此节点的父亲节点配对，若为奇数则需要加上这条边，那么可设 dp[i] 为以 i 为根节点的子树的配对后的路径和，dfs下去判断子树节点即可。 Code #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define mp make_pair #de...

Solution判断子序列的话让我想起了上次cf的一道C题，哪一场已经忘了，但是做法的话不外乎两种：1.二分查找2.序列自动机因为上次是二分过的，这次就写一下序列自动机。nexts[i][j]表示的是i位置之后j字符在原串中的索引，那么预处理nexts数组之后，直接对输入的每个串遍历判断 i 位置之后的 s[i] 字符是否存在即可。最后讲一下预处理，因为是i位置之后的索引，所以要逆序遍历原串,遍历 j = ' a ' -> ' z '，nexts[i-1][j] = nexts[i][j] ，特殊地 nexts[ i-1 ][ c[i]-'a' ]=i。 Code #include&lt...

Solution简单来说题目就是求在有根树中，每个叶子节点到根节点的路径上的边权最小值之和，很典型的树形DP。s为根，考虑 dp[s] 为答案，即每个叶子节点到s的路径上的边权最小值之和，那么 dp[s]= Σ min（dp[s.son] , s->s.son的边权) 。最后注意一下叶子节点是没有出边的，所以 dp 值设为 inf 。 Code #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define mp make_pair #define pb push_...

Solution 求树上的简单路径很明显是LCA的题目，那么：直接预处理父节点数组和深度数组直接暴力把 u 和 v 往上提 ？那就错了。其实题目里有保证 v 在 u 前往首都的最短路径上，所以只需要直接把 u 向上遍历就可以了。而珠宝购入的前提是当前城市的珠宝严格大于手中的所有珠宝，所以只需要再用两个变量维护珠宝的最大值和购入次数即可。显然在数据小的情况下以上暴力可以AC，但是数据量一大超时就必不可免了。可以优化的过程便是 u 找 v 这个过程，那么就要用到本文第一句话的LCA。由于出发节点的价值大的时候也会购入，所以可以处理询问的时候可以把每组询问离线，出发点作为新节点的父亲，带着的珠宝价值...

3月30日每日一题 : https://ac.nowcoder.com/discuss/394776 Solution 滑动窗口最值问题，就是单调队列的模板题。 先讲一下个人对单调队列的理解：举个维护区间最小值的例子，主要就是用 head 和 tail 双指针来对队列里的元素进行维护，当 q[head]+m<=i 说明队首元素已经跟不上滑动窗口，所以移动 head 指针，当 a[ q[tail] ]>a[i] 说明队尾元素比当前元素大，失去优先级，移动尾指针，这样的话，那么 q[head] 就是窗口中最小元素的索引了。 for(int i=1;i<=n;i++){ ...