思路： 求区间内逆序对个数，可以找出逆序对之后求它对整个区间的贡献。 例如 j，k是一个逆序对，那么它对整个区间的贡献应该是(j-0)*(n-k+1)，因此，用树状数组枚举k，找出（1~k-1）范围内大于a[k]的数的坐标和就行了。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include &l...

题目大意： 有n天可以租教室，给出每天可以租用的教室数量，有m次询问，找出最小值判断能不能完成租借。思路：线段树求区间最小值。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927...

题意：用3元买一张彩票，等概率获得1,2,3,4元奖品，求买n张不亏本的概率。思路：dp[j][i]表示买了i张获得的钱，转移方程就是： dp[j][i]=dp[j-1][i-1]+dp[j-2][i-1]+dp[j-3][i-1]+dp[j-4][i-1]; #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue&g...

题意：求前n个数的最小质因子的和。思路：素数筛的时候求一下和即可。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #define inf 0x3f3f3f3f #defin...

思路：如果是凸多边形的时候，就是三角剖分问题了，状态转移方程就是dp[i][j]=min( dp[i][j] , max( triangle(a[i],a[j],a[k]) , max( dp[i][k] , dp[k][j] ) ) );其中（i<k<j） triangle()计算的是三角形的面积如果是凹多边形的话，就直接不计算就好了，所以提前进行枚举，看看有没有点在选的这个三角形内，判断方法是，计算一下枚举的这个点和这个三角形的两个点组成的三个三角形的面积是否等于这个三角形。 #include <cstdio> #include <iostream> #...

思路：使用尺取法，简单来说就是先固定左边，右边逐次遍历，如果满足条件了，再将左边缩短，以此来寻找最短的满足条件的字符串。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #d...

思路：我们分为奇数和偶数的情况。如果是奇数，相当于在左右两边各取m/2个数，如果是偶数，左边取m/2-1个，右边取m/2个。因此，我们先枚举出每一个可能是中位数的数左右两边要取的数的和。首先先对物品按照价值进行排序，然后利用优先队列维护已存物品的体积，如果放的数量超过了要取的数，就去掉占用体积最大的。最后求的时候，奇数时，枚举每一个数，判断当前数能不能满足背包的大小，然后取最大数就行了。偶数时，我们枚举左边的那个中位数，然后右边的中位数利用二分来求，因为如果左边的数确定了，那么右边的中位数肯定是越大越好，而我们又是按照物品的价值进行排序的，因此可以直接用二分来查找，只要查找到的数满足背包的大小...

思路： 我们拿到一个新的武器之后，有三种状态：①放到天平左边②放到天平右边③不要这个武器那么状态转移方程就为：dp[i][j]=max( dp[i-1][j] , max( dp[i-1][j+va[i]] , dp[i-1][abs(j-va[i])] )+va[i] );(dp[i][j]表示前i个武器在天平差值为j的时候的最大值，va[i]表示第i个武器的重量) #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include &lt...

思路：二分的思想，枚举可能的套数 x ，判断的时候，只需要计算有x套时需要多少个joker，如果joker比手中的jioker大或者比套数x大（说明至少有一套不止有一个joker）就不成立，否则都成立。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #de...

思路：因为m最大只有2，所以可以先算m==1的时候，就相当于求最大m子串和，状态转移方程为 :dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][1][k]);dp[i][k][1]=max(dp[i-1][k][1],max(dp[i-1][k-1][1],dp[i-1][k-1][0]))+num[i]; 然后m==2的时候，用dp[i][j][k]来表示，第一列为1-i，第二列为1-j，k为选的k个矩形。 sum[n][1]表示第一列的前缀和，sum[n][2]表示第二列的前缀和。计算的时候，我们可以当做是分别计算第一列和第二列的最大m子串和，然后再把他们两列进行...

大意：小A小B从两个点出发，想尽快相见，求最短时间。思路： 同时对小A和小B进行bfs，相遇了就直接输出，一直遇不到就是NO，详细的写到注释里了。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi...

题目大意：有n个队伍参加三场比赛，如果队伍x有一场比赛赢了队伍y，y也有一场比赛赢了x，就算一组，求有多少组。 思路：这里我用了树状数组求逆序对的方法，先对第一场比赛进行排序，然后求第二场和第三场的逆序对，之后再对第二场比赛进行排序，求第三场比赛的逆序对，最后再除个2即可。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <...