Solution记得寒假牛客有道题就是这道题的扩展，好像是求路径数目+博弈论。 表示以 i 为根的子树到 i 的距离为偶数/奇数的数目。那么在dfs过程中，以 u 为根且子结点为 v 对答案的贡献是:  (子结点与父节点距离相差1，所以应操作不同奇偶性)当然遍历完也需要把 v 的路径数合并到 u里面去:  Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define io std::ios::sync_with_stdio(false),cin....

Solution前缀和优化，用维护的区间异或和，那么的区间异或和即。那么遍历 i ，枚举 i 作为右端点统计区间异或和，再枚举 i+1 为左端点统计答案。关键点在于左边区间统计，右边区间更新而不统计，保证区间不重叠。 Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; inlin...

Solutionemm昨天看了但是没有写出来，因为不会处理回溯过程中的更有利涂黑的情况。题解很巧妙，没想到可以用另外一个数组d来记录可以最多涂黑到哪个点，当数组d为0时就代表需要多操作一次，而这个更新操作次数正是这道题的灵魂所在。简单来说就是：  更新回溯过程中最远可到达的距离  更新回溯过程中无须操作就可到达的距离而当为0时就代表需要多花一次操作次数。 Code #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define inf 0x3f3f3f3f #define mod...

A.Solution因为是非递减数列，所以只移动k位是最佳的，那么对于原数列的美丽值来说移动k位所造成的变化是增加了 而减少了，所以遍历大于k的部分， =，那遍历取max即可。Code #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define inf 0x3f3f3f3f using namespace std; inline ll read(){ll s=0,w=1;char ch=getchar(); while(ch&...

Solution因为是树，所以保证任意两点都可以到达，所以可以选择从一个叶子节点作为出发点思考，  表示这个叶子节点所在包含了 i 个节点的子图染了 j 种颜色的方案。考虑当前取的颜色是否和前 次取的颜色一样，就是两种决策：  若取的颜色相同则： 若取的是新的颜色,则有 种新颜色可以选择，则：  这样的话就可以从一个叶子节点开始染色到把整棵树染色。最后累加 n 个点取 1~k 种颜色的方案即可。 Code #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define m...

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++){ whil...