思路：题中给定的是一棵树，要求把分成n/2对 让权值最小看一下范围 在加上是一棵树 所以做法应该是dfs 复杂度为on直接去考虑贡献设当前父节点为x 如果x的子树(包括x自己)的大小是个奇数 意味着什么呢因为要两两配对，那么意味着这奇数个数中，一定有一个数要有外界配对那么他就一定会经过x到x的父节点的那条边所以dfs 计算子树的大小 如果子树大小是个奇数，那么对答案有贡献 就要加上父节点往上连接的那一条边 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e4+5;...

有一说一这题对我来说难度还是挺大的，看了大佬的题解才懂得，确实还是个dp小白思路：用dp[i][k][j][l]表示 第一个串从i到k位置 和第二个串从j到l位置是不是可以组成回文串是的话值为1，否则为0 那么考虑转移有2*2种 (两个头 两个尾) a[i]==a[k] dp[i][k][j][l] |= dp[i+1][k-1][j][l] 这里要注意k-i+1 也就是长度需要≥2 因为i和k代表不同位置b[j]==b[l] dp[i][k][j][l] |= dp[i][k][j+1][l-1] 这里要注意l-j+1 也就是长度需要≥2 理由同上*b[j]==a[k] ...

思路：m次询问看字符串是不是给定字符串的子序列暴力的做法就是直接两个循环去匹配 复杂度m * strlen(a) * Σ(strlen(b)) 这复杂度显然是不可接受的那么考虑一下预处理cnt[i][j] 表示当前位置为i下一个字符为j的位置 倒着遍历字符串即可预处理一遍之后，每次循环跑的次数就只有strlen(b)题中给定Σ(strlen(b)) 不大于1e6而预处理的复杂度为 strlen(a) * 26 所以总共在3e7左右 这是允许的 然后既可以ac了注意一下下标应该从1开始 或者你从0开始 但是表头位置是一个大于strlen(a)的位置也可以就是说表头位置不能与字符串a的任一位置...

思路：注意题中的M M=N-1 并且图联通 说明这是一棵树然后题意就是说 让重要点s 到不了其他度为1的点度为1的点 那不就是叶子节点嘛所以我们只要从点s开始dfs，计算出到叶子节点的路上的最短的边权加起来即可复杂度O(n)用dp[x]表示节点x到每个叶子节点的最小边权值那么dp[x]+=min(dp[u],v) 其中x是当前节点，u是x的子节点，v表示u-x的边权想好之后 就可以快乐ac了 注意对根节点赋值一个无穷大的数 还有记得开ll #include<bits/stdc++.h> using namespace std; typedef long long ll; s...

思路：这题对于每个士兵多了一个si的限制，也就是对要选择的人数有了限制，如果没有这个限制的话，我们肯定是直接按照武力值从大到小去选取，有了这个限制就不行了考虑把si从大到小排序这样的话 对于si就是不升序的排列，那么我们能选取的个数就是取决于已经选择的人的si限制了所以对于每个vi我们先加进去到要选择的集合内，然后看集合的个数是不是＞si 是的话就把武力值小的从集合里拉出来所以需要的是一个支持加入删除 和自动排序的数据结构 自然就是一个维护小顶堆的优先队列了注意数据运算可能会炸int #include<bits/stdc++.h> using namespace std; type...

思路:最暴力的做法就是模拟过程，枚举每一个长度为k的区间，然后遍历一遍找最值，复杂度为n^2这题n的范围到了1e6 n^2 在规定时间内是跑不完的 所以这题要用数据结构优化什么样的数据结构呢 对于当前区间为l到r那么往后移动了之后 区间变为了 l+1 到 r+1也就是a[l]被弹出 a[r+1]加入所以我们考虑一个双端队列(双端队列与队列的区别在于 队列是一边只能进 另一边只能出 双端队列两边都可以进出)首先对于已经在队列内的 我们要去把不属于当前区间的弹出 这样就满足队列内的都是在此区间的然后我们队列要维护什么呢比如要求最小值 维护一个单调递增的队列 保证队首就是所要求的...

A让求一个和式的值，按照和式内容模拟要两个for，n^2复杂度会TLE，所以显然是不可取的那么因为是位运算& 所以我们考虑去按位算贡献，对于每一位，我们会进行k*(k-1)次计算 也就是排列数A(k,2) 那么该位对答案的贡献就是就是(1<<i) * k * (k-1) 其中k为该位上为1的个数所以存下来每个数的每一位1的个数 (因为只有1&1才能对答案有贡献)然后遍历每一位计算贡献的值即可 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define me(a...

链接：https://ac.nowcoder.com/acm/problem/15553来源：牛客网 题目描述今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。输入描述:第一行一个整数T（T<=10）,代表有T组数据接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <...