前言: 之前对前缀和的了解仅仅局限与一维前缀和、二维前缀和以及前缀和的变形如前缀积、前缀异或。经过zngg的讲解后，才发现我对前缀和的了解远远不够。很喜欢智乃上课讲过的一句话：“不能把前缀和仅仅看作是前缀和，而是看成一种思想。”  OI Wiki对于前缀和的详解：https://oi-wiki.org/basic/prefix-sum/ upd:  A 智乃酱的区间乘积 这是一题很裸的前缀积的题，没有做过前缀积的可以通过前缀和也能联想过来ps:注意因为取模的原因不能使用除法，因此需要使用乘法逆元 代码链接：https://ac.nowcoder.com/acm/contest/view-sub...

做法  任意交换两个数后，逆序对数的奇偶性改变  先求出原始序列的逆序对数的奇偶性(可以通过归并排序或者树状数组的方法求逆序对数) 对于操作1==>交换1次(l与r不相等)对于操作2==>对半交换对于操作3==>依次向左（或向右）逐位交换 代码 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=200010; int a[N],b[N]; long long ...

做法： 把二进制中的每一位看作是一个点，改位为1就建立长度为的边跑dij即可 代码 // Problem: 最短路 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11233/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define pb push_b...

做法 每次用最小的号来上分掉分即可用优先队列或者multiset维护当前最小的号即可 代码  #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);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #de...

做法 对于寻找一个"aab"的子序列只要枚举“b”，并在'b'之前的'a'中取两个就能求出子序列的数量。因为可以在任意位置中插入一个字符。很容易想到最优的插法：1.在最前面插入'a';2.在最后面插入'b'在这两种方案中取到最大的一种即可 注意：答案会爆long long 代码 // Problem: 子序列 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11233/B // Memory Limit: 1048576 MB // Time Limit: 2000 ms // // Powe...

做法 根据平行四边形的判定条件：一组对边平行而相等 然后套用几何板子就能解决问题 代码 #include <bits/stdc++.h> using namespace std; const double eps=1e-8; const double PI=acos(-1.0); const double INF = 1e100; int sgn(double x){ if(fabs(x)<=eps)return 0; return x>0?1:-1; } int dcmp(const double& a, const double& b){ if(fa...

做法：构造 思路： 说不明白，参考了别人的题解，给几组情况就能够理解明白了设x,y,z是a,b,c二进制中1的个数假设x>y 分类讨论 1) z=1  000001111111111011110000000001100000000000000  2) 1<z<y  000111111111101100000001111000000000110  3) z=y  011111111110000001111110000011110  4) y<z⩽x  011111111110001111100010011110111  5) x<z<x+y  01111111...

做法 先记录每种体积的背包数以及下标因为每两个体积为的背包能合成一个体积为的背包所以我们只需要把背包从小到大开始合并，判断体积为的背包数是否大于等于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++....