题意:给定n个从者,m个概念礼装,然后每个从者,概念礼装都有一定的ATK值和所需要的cost值,然后现在玩家的cost值上线为d,并且选择的从者数大于等于概念礼装数,从者数要小于5个题解:01背包加强版建立 数组,表示消耗cost值为i,获得j个从者,和k个概念礼装得到的ATK值因为输入的时候先输入从者的数据,所以先计算dp[i][k][0]所以对于计算从者的时候有:现在有一个增加x的ATK值,以及消耗y的cost值得从者消耗cost的j值获得k个从者与消耗j-y的cost值获得k-1个从者加上当前的从者的ATK值比较大小同理,接下来计算能有多少的概念礼装:然后再对于每一种情况进行比较,取最大...

题意:给n个物品，从中选出任意个，放在天平的两侧，使得天平相差小于 x ，你便可以拥有这些物品，问最终能获得多大的重量,可以操作多次题即:多次操作等于1次操作 表示前i个物品所取得得差值为j #include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define Inf 1e9 const int N=10005; int dp[110][N]; int main(){ ios::sync_with_stdio(0); int n,m; c...

题意:走迷宫,问能不能碰头,能的话,什么时候碰头题解:广搜,定义一个时间戳,分别把两个开始点能走到的点的时间戳+1,然后把这些能走到的点,的能走到的点的时间戳+2......(已经走过的点不能再往回走)如果最后队列为空,仍没有可以重合的点,输出NO否则输出YES,合最开始重合的时间戳 #include<bits/stdc++.h> using namespace std; struct qw { int x,y; }t; int n,m,vis[2][1005][1005],step=0; char a[1005][1005]; queue<qw> q[2]; ...

二分答案.对于答案可以保证是一个单调的函数,所以可以直接二分答案,然后对于二分的数字代入数组进行判断判断每次二分后的答案是否合法 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m; int a[200]; bool check(ll x) { ll cnt=0; for(int i=0;i<n;i++) if(a[i]<x) cnt+=x-a[i]; if(cnt>m||cnt>x) return 0; ret...

题意:有n个城市，它们之间通过n-1条道路联通。第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。最多能度过多少天?题解:分类讨论 表示在这个城市住下 表示不在这个城市住下那么最后答案肯定是然后如果我们要在第 个城市住下,那么 即第个城市住下,那么第个城市的子节点,全部不能入住如果我们不在第个城市住下,那么即,选取第个城市的子节点是否住下的最大值求和 #include<cstdio> #include<algorithm> #include&l...

题意:求解a,b,c三数组中 的个数,并且(x, y), (y, x)算一组。题解: ANSWER1: 这个就是帖子下面好多大佬写的CDQ分治直接求可能数不好求,那么求不符合题意得, 就是不符合要求得答案假设这种情况一共有ans种,那么答案等于然后说一下CDQ分治,把a,b,c分成三个维度先说一维的....直接sort再说二维的,把第一维度进行sort,然后对于第二维度进行分治或者对第二维进行树状数组维护下来说下三维的对于a维度直接快排,相当于满足 的条件再a维度快排后的基础上对于b维度进行二分分治1.将当前处理区间分为左右两个等大的子区间；2.递归处理左子区间；3.处理左区间对于右区间的影响...

题意:求管道输出的全部可能情况的个数的平方求和,有点绕比如样例:ABB输出:BAB 1种 BBA 2种,所以输出5题解:第一次知道可以把求平方,转化为两个人玩游戏.......两个人在两个独立的装置里取球，输出队列相同的方案数 因为对于每一种输出队列，第一个人有 种方案，第二个人有 种方案,那么两个人输出队列相同的方案总数就是 表示第一次取A串中的前i个,取B串中的前j个,第二次取A串中的前k个,B串中的前l个的方案数,并且然后就可以写出dp式子然后因为 可以压缩一维然后这样还是会超,可以把第一维再次压缩 #include<bits/stdc++.h> using namesp...

闲扯 A题当时在想排列组合,然后看了下过题数,这要是排列组合也太不科学了...E题是2019宁夏区域赛现场赛的原题,好像是B题,数据都没变,原代码直接acD不会,看不懂,看懂了想扇死自己,一个纯暴力map............C的写2的那种情况以为是直接写一个线段树,然后直接查改,然后没想到这东东是差分...然后3的那种情况没想到是差分做的,当时没理解2的那种情况的引导B没啥说的,第一眼想这是dp,我去,这咋dp,哦,数据范围30,那没了,直接爆搜 A---小A买彩票 题意:小A买n张彩票,然后每张中的金额为1,2,3,4之一,然后每种等可能出现,也就是 ,每张彩票3元,问不亏本的概率是多少...

题意:由n个奶牛,然后每个奶牛都有两个属性,让农夫牵会牛舍需要的时间,以及每分钟坏花的数量,然后问最少损失多少的花题解:贪心我们假设有两头奶牛,那么先牵那个回去比如如果先牵第一个奶牛,那么最后的损失量是第二个奶牛的损失花的量乘以第一个奶牛回牛舍所需要的时间同理先牵第二个奶牛,那么最后的损失量是第一个奶牛的损失花的量乘以第二个奶牛回牛舍所需要的时间然后就按照上面的推论,排下序,然后贪个心 #include<cstdio> #include<algorithm> struct node{ int t,d; }m[101000]; bool com(node a,no...

读完题目之后,内心一片祥和,除了想口吐芬芳........题意:给定n个数,然后问最后剩余多少个数的时候,还可以把原来的数全部表示出来举个例子:3 10 19 ,最后剩下2个数3和10即可,因为19=3+3+3+10题解看一波范围,额,有点小.....最多才那还想啥,直接暴力比如3 可以构成3 6 9 12 15......然后10可以构成10 20 30 40......然后3和10结合可以构成13 16 19 22 25.....23 26 29 32 35......33.....然后19,可以由前面比较小的两个数构成,n--先排下序,然后对于然后判断当前数字是否可以由比他小的前面的数构...

题意:给一个维修时间和一个报废的截至时间,然后有很多个,现在问最多抢救多少个这个题和每日一题第一次的那个题有点像:https://ac.nowcoder.com/discuss/390428然后回来说这个题.贪心:先修最先报废的那几个,再修后面的,然后可以用优先队列来实现然后对于修了x个建筑可能需要t秒,但是对于第y个建筑而言如果把修的x个建筑中的一个不修而修第y个,所需要的时间会小于t,此时有一个状态,即把第y个当x+1来修,还没修完第y个就报废了所以这用到优先队列每次返回x个里面消耗时间最多的,与第y个比较,看看那一个所需要的时间比较少 #include<bits/stdc++.h&...

见一次忘一次,见到求异或和之和的全部转换为二进制,然后判断 有多少种组合既然要求长度在[L,R]之间偶数的异或和之和,那啥都别说先来求一个前缀异或和,然后我们可以想一下下来暴力的求解怎么做比如枚举[L,R]之间偶数为长度,然后一遍一遍的过数组......铁定超时异或的性质所以做这种题有一个东西就是,把其转换为二进制,举个例子: 0到L-1和0到R的前缀异或和分别为5和10,那么 ,0101--->51001--->91100--->12所以我们要求异或和之和就是相当于找其中二进制下相同位能找到多少满足要求的长度为偶数就是L和R同为奇数,或者同为偶数所以我们可以枚举每个点为右边...

因为只要个数所以可以大于b的记作1,小于b的记作-1,然后如果b的左右相加之和为0,则算成立如: 写成 ,如果一个区间要成立的前提就是b左右两边的值相加为0,那么如果左边值相加为-2,右边值相加为2,并且b的左右两边的数的个数是大于2的,那么里面必定存在(-1,1)情况,所以就是可以确保求出得长度为奇数然后分情况讨论左区间位于b的位置右区间位于b的位置左右区间都不在b的位置针对前两种情况可以直接进行从b位置进行左右求和,如果和为0,ans++针对第三种情况,可以记录从b开始向左求和时到每一位的值,然后记录每一种值得数量然后b向右求和,每到一位求出得值,ans+=b得左边出现其乘以-1的个数最后...

E 题意:给定一个字符串,然后把给定的字符串变为合法序列,即每两个1之间的距离严格等于k题解:构建dp数组dp[i][0/1]当前第i位填0还是填1的最小操作数当前位置如果填0,所求值.即i-1位填0还是填1的最小加上这位是否为1当前位置如果填1,所求值即从i-k全部填0,所需要的数量再加上i-k位填1的操作数,或者从0到i全部填0,两者取最小,再加上该位是否为0 #include<bits/stdc++.h> #define ll long long using namespace std; int dp[maxn][2]; int sum[maxn]; char s[maxn...