做法 先记录每种体积的背包数以及下标因为每两个体积为的背包能合成一个体积为的背包所以我们只需要把背包从小到大开始合并，判断体积为的背包数是否大于等于2个即可然后按照体积从大到小开始找背包，初始是需要2个体积为的背包，该层不满足则需要调到下一层，并且数量是当前的两倍 代码 // Problem: 奇怪的背包问题增加了 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/204441 // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP...

思路 我们可以把终点看成距离为d，价格为0的加油站每次到达加油站我们都要把油箱加满如果每站之间距离大于油箱容量（第一站是否达到看当前容量），输出-1假设油箱中的油有区别，并且可被替换我们优先使用价格低的油，到下一个加油站时可以把当前油箱中比当前加油站的油贵的油替换成当前加油站的油用双端队列维护模拟即可 代码 // Problem: Fuel Economy // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/24408 // Memory Limit: 65536 MB // Time Limit: 2000 ms ...

思路 把a看成0，把b看成1这样就形成了01字符串用类似字典树的样子来建树求每层s，t字典序大小之间（包括是s，t）的个数设为d答案即为每层min(d,k)的和 代码 // Problem: The Fair Nut and Strings // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/113276 // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #includ...

  五一回去补之前落下的课以及作业

思路  把每一种冰淇淋被牛喜欢用bitset存起来，第i头喜欢用第i-1位为1表示。 然后遍历每一头牛的每一种喜欢的冰淇淋，并或起来可得该牛和其他牛能否和谐共处的关系，1表示能和谐共处，0表示不能和谐共处。不能和谐共处的数量即为n-s.count() 因为不能和谐共处的关系被重复计算了两次，所以最后答案除2即可  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0)...

时间复杂度： 思路  长度为n的环形首先把它拆成长度为2n的链 我们只要求即可 我们可以枚举i,就是个定值，用有限队列维护的最大值，同时要保证这一条件，不符合弹出即可  代码 // Problem: 环路运输 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/51187 // Memory Limit: 65536 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++....

做法：组合数 思路  因为是的网格，所以一共有个点所以三角形数量为在所有点中任意选取三点中减去三点共线的情况即可 不合理的情况分为三种  1.横线2.竖线3.斜线 前两种情况很好求，所有横着（竖着）的点中选取三个点乘上竖着（横着）的点数即可 第三种情况我们可以先找到一个直角边为i,j的直角三角形，然后其斜边上的两个端点为两个所需要的点，第三点上这斜线上除了端点还存在的格点上找，数量为。因为斜线存在两种，即斜率为正和斜率为负，因此需要乘2. 代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #d...

做法：dp 思路： 因为音量范围在0~maxx之间并且maxx<=1000，所以我们设dp[i][j]为第i次音量变化后此时音量为j的方案是否存在 在符合条件的音量内进行转移 和 代码 // Problem: [HAOI2012]音量调节 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/19990 // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #inclu...

题意： 给定一个长度不超过10^5的字符串和不超过m次操作。每个操作 L R K 表示给区间[L,R]的字符串排序，K=1为升序，K=0为降序。最后输出最终的字符串。 做法：线段树 思路：  根据计数排序的原理，只要知道了有几个数比t小，就可以知道t的位置 这道题只有26个字母，我们只需建26颗线段树 在每次操作时，首先求出这个区间中a~z每个数出现的次数 再分别对每一位字母进行区间覆盖。 对下一个区间进行覆盖要加上之前覆盖的长度 如果是升序排序，我们从a到z依次查询所有线段树，降序就从z到a依次查询 最后遍历整棵线段树输出最终的字符串  代码 #include <bits/stdc++...

题意 给你一个的矩阵，有个颜色在一个矩阵中涂色（每种颜色必须要涂），求出第一个涂色的颜色可能有多少种 做法：二维差分 思路  首先把明面上留下的颜色给记录下来，并且存可能涂色的最小矩阵的四个顶点坐标 然后模拟涂色，w[i][j]表示这个位置最小被涂色的次数，这里可以采用二维差分来优化 如果这个位置被多次（大于1次）涂色，那么明面上留下的颜色必不可能是第一次涂色，减去即可 注意n=1和明面上只留下一种颜色的情况时进行特判即可  代码 // Problem: Modern Art // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/pr...

思路 对于每缺一单位的土，我们有两种选择1.买1单位土2.从别的地方转移过来一单位的土同理，每多一单位的土1.移除1单位土2.从别的地方转移出去一单位的土在这两种方案中要取最优的方案 可以用两个大根堆堆顶来记录，q1表示多土的花盆 q2表示缺土的花盆根据贪心来选择最优的方案 代码 // Problem: Landscaping // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/24444 // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered ...

来自23届的学生，想问下近几年需要哪些方面的实习生，需要有哪些方面的技术或者项目