题意：lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次？题...

题意：牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n行m列，第i行第j列的单元格的权值为，牛妹可以进行k个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。牛妹想最大化她的得分，球球你帮帮她吧！题解：如果这个题想直接暴力对所有行和列进行dfs的话，这样应该是会超时的，试了好几种方法，都T了，很遗憾。这题无论是dfs或者是二进制枚举，核心都是，枚举行或者枚举列，再去贪心，也就是说，如果你枚举的是行，那么你就去贪心列，如果你枚举的是列，那你就去贪心行。假设我们枚举的是列，那么我们求所...

题意：上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生...

菜鸡还没学二分图。。。题意：给定一个序列，问能否双栈排序，如果能，请输出字典序最小的方案；操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列题解：题目让以字典序最小的顺序输出，那么这样的话我们操作顺序直接以abcd来操作即可。对于一个数，我们应该把他放进栈a呢，还是放进栈b呢。因为字典序最小，所以我们如果能放进栈a实现这些操作，那么我们必然不会把他放进栈b实现这个操作。 我们先考虑一个栈的情况。如果序列是 3 1 4 2 5不难看出，这个...

上面是爆搜+剪枝下面是正解 爆搜加剪枝你值得拥有。 if(sum>=ans) return; if(sum>=ans) return; if(sum>=ans) return;对加了这句话，就ok了。爆搜的代码也不需要多解释了，今天突然想起来剪枝一下好像可以就试了试。其实就是dfs暴力所有路径。。。加了一个再普通不过的剪枝。 代码： /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> #define endl '\n' #...

题意：小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？题解：dij的一个变式题，只需要，虽然这只是一个变式题，但我还真没想出来，看了题解才会的。。。只需要把visited和dis这两个数组多开出一...

题意：在遥远的东方，有一家糖果专卖店。这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖果，第i天的第j个糖果价格为C[i][j]元。现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买m个。（因为最多只生产m个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这n天中每天你都能吃到至少一个糖果。这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。那么问题来了，你最少需要多少钱才能达成自己...

题解：首先我们知道，一个点肯定不可能只出现一次的，他会出现好多次，但是根据二进制a xor a =0a xor a xor a =a所以我们发现当某个点出现的次数为偶数次时，这个点相当于没有出现过，奇数次时，答案异或一下这个点的权值即可。没有见过这种题的建议先看求树上任意两点之间距离之和的平均值这个典型题下面我们借用巨雨的分类方法做这个题1.x作为一条路径的顶点时，它会被经过n-1次对应代码： int ans=n-1;2.从x的子树内连到子树外，这样的话，子树每一个点都会与树外面每一个点相连树内的每一点 size[u]-1树外的点 n-size[u]所以答案是：树内的每一点 × 树外的点 ...

题目描述：小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。题解：可以理解为LCA的模板题了，因为他N个点只有N-1条边，所以是一棵树，但是这个题有一个比较特别的地方，有两个点之间是不需要花体力就可以到达的，这样的话我们就多了在模板题的基础上，也就是他在这棵树上搭了一个通道，所以只需要每次特判一下是否通过这个通道会更近即可...

题意：有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：只有解开密码，才能够出去。可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。提示：异或指在二进制下一位位比较，相同则 0 不同则 1例如2=(010)22=(010)_22=(010)2​ 5=(101)25=(101)_25=(101)2​所以2 xor...

题意： 小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有n层，第i层有n-i+1个技能，每个技能只能够学习一次。除了第1层的技能可以直接学习外，其他技能学习都要学习前置技能，即你要学习第i(i>=2)层第j列的技能，那么你要先学习第i-1层的第j列和第j+1列的技能。每个技能学习后都会获得一定的战力加成。现在小卤蛋有m个技能点，一个技能点可以学习一个技能，他想知道加完点后他可以获得的最大战力加成为多少。题解：我们使用dp[i][j][k]学会了i j这个点及其右上角的技能花费了k个技能点的最大值。因为如果我们想学会当前技能先，就要学会这个点他右上方所有点的技...

题意：给你目标字符串的状态，现可以将连续一段字符串染色，求最小的染色次数题解：我们定义dp[i][j]是区间i到区间j最小的涂色次数区间dp的核心思想实际上是由一个个小区间进行合并成为大区间，所以我们在dp的时候应该从长度最短的下手，也就是长度为1的。1.长度为1的区间，涂色次数为1.2.长度区间为2的值：它可以由两个长度为1的区间和并，但是这个题目比较特殊的一点就是，你图一次可以连续涂一个区间，所以如果s[i]==s[j]那么这个区间只需要涂一次，如果不同，那么就是两个区间次数的相加了。3.长度为n的值：仿照区间长度为2的时候，我们可以枚举区间中的某个分割点来进行递推，这就跟Floyd的核心...

题目：有n个格子，你有m张牌，每张牌上面有个数字，用了这张牌你就可以走这张牌上对应的数字了，每到达一个格子，你就会获得格子上相应的分数，问你如何合理的出牌，使分数最大化。 记忆优化搜索可能会好写一点 题解：我们让他从0开始，dfs的四个元素，表示的是当前使用了多少个1，2，3，4号牌。 但是为什么我们计算的位置是a + b * 2 + c * 3 + d * 4 + 1，为什么要有个+1，原因很简单，是因为他是从1位置开始的，自动获取1位置上面的分数。 边界如何判断呢，当所有扑克牌用完以后也就是说到达边界了，当a+b+c+d==m时，即为到达边界。 代码： /*Keep on going Ne...

好像是单调栈的模板题了，但是稍稍改动了一下也就是柱状图的宽度可能会变。题解：这个题数据范围1e6，如果我们暴力解，肯定会超时，那么我们这里用单调栈。单调栈，分为单调递增栈和单调递减栈，这个题用的是单调递增栈。首先我们枚举每个柱子的高度，枚举时，对于这个柱子先不做计算，而是把他放进栈内。因为要保证这个栈是单调递增的，所以我们在放进这个柱子的时候，要判断这个柱子是不是比栈内元素都要大，如果都大的话，我们就可以直接把他放进栈内，但是如果小的话，我们就要让一些栈内元素出栈，直到栈的元素不比当前元素小为止。在出栈的过程中，我们对于当前出栈柱子做计算。因为栈元素是单调递增的，所以我们保证在出栈的这个元素到...