题意：找出m个不超过V的最大权值的中位数；题解：中位数的找法要区别奇偶，奇数直接就是中间，偶数就是中间两边数相加>>1,首先我们要知道如何处理这个问题，先找M>>1,就是先找中位数左右两边的数字，由于我们要找最大的权值，所以我们按照权值升序，在排大小，那么我们是不是就要尽量使两边的大小尽量小，然后，中位数权值尽量大，因为大小是没有顺序的，只是权值有序，所以我们可以扫一次m/2前面前缀，m/2后面后缀，然后这样子是我们在枚举中位数的时候就可以直接枚举终点，想办法把左右两边的大小尽量最小就是，因为权值必然是左边小右边大，所以中间只要满足总大小<V那么就可以随便搞，然后...

一看题意首先想了求最值，那么就是二分 但是操作过程中是很灵活的，然后果断pass掉，然后DP，很明确题目就是三种情况，要么放左边，要么不放，要么放右边，反正最后取得的武器必然左右两边差值不过M，那么就要想DP方程式，DP[i][j]=代表前i个物品左右最多相差j的质量，我们可以很容易想到要是本次不放那么就是dp[i][j]=dp[i-1][j],直接就是继承上一次的，然后就是放左边，我们应该是dp[i][j+x]=max(dp[i-1][j]+x),放在右边那就是dp[i][abs(j-x)]=dp[i-1][j]+x; #include <bits/stdc++.h> #defi...

题意：就是一个人走八个方向，每次走一步，一个人走四个方向，每次走2步，问最少基几步两个人相遇。题解：首先我们要考虑好走两步的如何走，我们不能简单的把他弄成每一次直接就走2步，比如，...#D，这样子的话如果你走2步他直接就跳过障碍物了，但是实际上是走不通的，我们就可以把他处理一下，把两部变成走两次不就好啦，进行2次bfs，然后就可以解决啦，然后再同时进行另一个人的BFS，那么我们就判断他们在哪儿相遇就好啦。 #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)...

题意：就是选出K个ab的子矩阵（a<n,b<m），不能选选过的点，然后问你这个K个子矩阵MAX;题解：首先这题一定要看范围，M=2，那么矩阵就是最大就是N2，我们是不是可以直接枚举暴力来做。（我们每一列求一个前缀和，第一列sum1,第二列sum2） 首先.我们讨论M=1，是不是矩阵就是一列，然后我们就是dp求区间最大值，dp[i][j]代表前i行里面选择j个的值，dp[i][j]=max(dp[h-1][j-1]+sum1[i]-sum[h-1]); 2.m==2,我们这时候就要开始讨论了 ，首先开一个f[i][j][k],代表选第一列前i行第二列前j行k个子矩阵最大值，那么我...

题意就是给你N+1个种类的牌 然后N+1个牌是万能牌 ，这N+1种牌每个牌都有Ci个，然后问你这N+1个牌能够组成牌数为N，而且每个N张牌里面没有重复的牌，问你一共可以组成多少种。题解：这题慕然一看感觉就是贪心，但是我们贪心做的话比如 1 2 3 （万能牌）10，答案很明显就是3，是不是可以贪心就是所有牌排序一次然后最少的2个数相加就是答案，但是如果样列是 100 100 （万能牌）100，这样答案岂不是是200，所以贪心有问题，那么换一个思想，我们来猜测答案，如果K种满足答案，那么K-1种也是满足答案，只不过种类数减少了，没有计算完全，那么是不是就是单调的了，我们很容易想到二分，直接去二分答...

题目范围非常小，一眼看就觉得要不是搜索要不是DP,但是是题意弄明白后就发现如果搜索的话很是麻烦，我们不能很顺利的去选择方案，然后就转换位dp，关键dp如何写，我们仔细看样列，是不是写的非常好，一行一行的就像是一个二进制串，那么是不是就可以想到状压，状压与二进制关联，然后我们就应该去判断条件，如何去写，首先 我们处理每行里面的列，j&(j>>)代表是我的这一行里面的人，(以下的01串我是代表二进制数)没有相邻的，比如101，然后>>1，就是010,然后&是不是就是0那就是说明这个情况可以满足条件，然后我们又去判断是否满足当前行的要求呢（(mp[i]&amp...

首先题意说的很清楚，必须从一开始，然后去找最长的旅游天数，那么我们可以看出是在一颗树上面操作的，那么就是树形dp来解决，我们可以定义dp[i][1/0],什么意思呢，就是第i个地方我是选择住宿还是不住宿（1/0）的最长停留时间，那么我们如果到了以X为根的节点，如果要住那就是dp[x][1]=dp[y][0]+1,父节点住宿了那么儿子节点必然不可以住宿，然后如果没有住宿是不是就是dp[x][0]+=max(dp[y][1],dp[y][0]) #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.t...

这题很厉害 我读了很久才真正的搞懂题意，答案+1的情况是 任意一组a，b队必须三次比赛中a任何一次至少排名大于b一次和bd大于a一次，这样两个才算一次，那么是不是我们就可以把a第一次排序 然后后面的就是 查找第二次的逆序对啦，但是有三次比赛，我们是不是需要选择任意两次 那就是C（n,2),对吧 ，组合一下（1.2）（1，3）（2，3），那么是不是就是直接求逆序对的数然后最后>>1还有一件事 不知道如何使用树状数组来求逆序对的可以百度一下，然后我是看这个大佬的看懂的 谢谢大佬，https://blog.nowcoder.net/n/41e0d9ce2e3543fab11fe0fd27...

直接入手似乎有些困难，不妨将原问题作一点转化：输出第i种特定序列的方案数a[i]即为二元组(X, Y)（其中X, Y分别代表一种输出第i种序列的方式，且X与Y相互独立）的组数。设X所对应的方案为(ix, jx)（从上管道取出了ix个，从下管道取出了jx个），Y所对应的方案为（iy, jy)（含义类似于ix, jx）。于是，可以用状态f[ix][jx][iy][jy]作一下更新： 1) 若上管道的第(ix + 1)个小球和上管道的第(iy + 1)个小球，那么更新状态f[ix + 1][jx][iy + 1][jy]； 2) 若上管道的第(ix + 1)个小球和下管道的第(jy + 1)个小球...

每次走2步，然后要求每个点都要去遍历到，那么转换一下思想就是判断奇数环，比如1-2-3-1；那么就是可以全部遍历到每个点，首先是1然后是3然后是2，那么我们是不是就是去找这个图的联通分量，然后去判断是否有奇环，如果有一个奇环，那么就是所有的联通分量-1，如果没有答案那就是所有的联通分量，手动枚举一下就可以得出结论了 #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ":...

我看很多大佬都是最短路做的 ，然后我最短路学的不好 ，然后偶然间看到一个大佬和我一样想法，首先直接BFS，但是这个bfs要开一个dis数组，代表该点的最短距离是多少，然后每次去更新，分别去入队每次正常走和进入传送门的，然后每次更新。 #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define debug...

根据中序遍历特性，在根节点前面的节点，一定在左子树；根节点后面的节点，一定在右子树。我们可以根据这个特性，结合递归的方式确定出最高加分的二叉树。我们每次查询的过程中，查询max(dp[l][i-1]*dp[i+1][r]+ans[i]); #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define de...

这道题其实就是找一个连通块的个数，就是直接找八个方向，然后比较两个人的3*3范围的扩散开连通块的个数，利用DFS都跑一下两个人的连通块个数 ，然后就是直接贪心一下，用齐齐连通块里面个数最少的去攻打司机，最后剩下的连通块加起来就是ans了； #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define d...

这题如果一看我们首先会想贪心，但是之后我们却不能找到一个合适的时间去替换，如何再看完时间的条件下，找到最少的电影次数，那么贪心不行那就只有想想DP了，这题就是用状压来过，所谓状压其实就是以二进制来处理各种位置的关系这是雨状压有关的二进制的处理。言归正传。dp[k]代表什么呢 就是k在二进制下，有多少个1就可以看多少个电影，那么dp[k]就是看的时间长度，我们每次处理的时间更新是dp[k]=max(dp[k],ans[j][pos]+d[j]);然后就是一个很6的操作，如何快速找K的1的个数 int solve(int x) { int cnt=0; while(x) { cnt++; ...