题意：n个点的一棵树，选出n/2个点对，使得点对之间两点距离之和最小，n保证偶数sum[i]是以结点i包括结点i的子树结点个数，当sum[i]为偶数时，只需要让这颗子树中的点两两相连，代价就是该子树的所有边；当sum[i]为奇数时，就需要另外一个点与外面(即除这颗子树外)的点相连，最优当然是选择这颗子树的根，这时这颗子树的根与它的父节点相连的这条边就会对答案贡献 #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 1e4+10; str...

题意：在文本串a中能否找到一个子序列等于字符串bi，有m个询问 对a串预处理一个nxt[i][ch],表示是s[i]以及之后字符 ch 第一次出现的下标，这个预处理就是逆着推，从后面往前面做，每次先把nxt[i+1][ch]赋值给nxt[i][ch],然后再用当前字母更新nxt数组即nxt[i][s[i]] = i；预处理好后，对于每一个bi，从idx = 0开始看nxt[idx][b[0]]是不是等于-1，如果不是-1，就让idx = nxt[idx][b[0]]+1,再去做b[1],若做完整个b串都没有遇到-1则可以，否则不行；这题和CF1295C差不多 #include <cstd...

题意：原本一颗无根树，以s为根结点拉起，求这颗树中任意叶子结点都不可到达s的最小代价 dp[u]表示以u为根的子树中的所有叶子结点都到达不了u的最小代价 ①u是叶子结点时dp[u] = inf; ②其余 dp[u]:for(int v : son[u]){ dp[u] += min(dp[v],edge(u,v));}对于叶子结点无法做到自己不可达自己，而对于其他结点u要么令叶子结点不可达u的子节点，要么自己断去子节点的边(另外忘了无向图边数乘2，一直RE。。。。。。) #include <cstdio> #include <cstring> #include &...

维护一个单调队列，以最小值为例，队首是最小值的下标，将新加入的元素加入到队尾，但要pop掉那些比新加入元素还要大的元素再加入队尾（即如果比队首最小值还要小将整个队列pop掉再加入队尾），但是队首元素不一定就是这个窗口的答案，它可能在窗口的左边，所以从队首开始pop掉那些下标比i-m还要小的元素，最大值同理； #include <cstdio> #include <queue> using namespace std; const int N = 1e6+10; int n,m,a[N]; void mi_deque(){ deque<int> q;...

思路：先求得一个东西：sum[i]表示从区间[ai...ai+k-1]的区间和，求到n-k+1就OK了，后面的没用；然后呢，搞一个结构体，这个结构体有id和val：分别对应就是i和sum[i]；这个结构体按val排序；然后就可以干坏事了。。。。先枚举左区间的开头，从1到n-2k+1，对于每一个左区间可用的右区间开头都至少要大于或等于i+k；然后因为按val排好了序，所以取的肯定是最大的区间值，判断最大的这个右区间是否可用，不可用就可以把他扔掉了，因为对于i都是不可用的，那么i+1，i+2...更加是不可用的，然后枚举完左区间开头不断更新最大值自然得到答案； #include <cstdi...