%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.求所有骚区间个数.容易想到枚举一个端点，求另外一个端点的有效个数，然后依次累加.原序列定义为 . 对于当前下标为 的元素作为区间左端点 , 是下标大于 并且值小于 的下标最小的元素， 是下标大于 并且值小于 的下标最小元素。那么有效右端点一定是在 中.表示为： 对于当前下标为 的元素作为区间右端点 , 是下标小于 并且值大于...

#Robot Sends Red Packets > https://ac.nowcoder.com/acm/contest/8829/E n个硬币分成若干堆，每堆硬币的价值相同，求最堆最小价值的分配方案。 思路：三层dfs剪枝. #include<bits stdc++.h> using namespace std; typedef long long ll; ll dp[100][2]; int sum=0; int b[100],a[100]; int m; int n; vector<int> gg; bool f; int cnt=0; bo...

1.求01矩阵中最大子正方形的面积.(n<=1e3) https://leetcode-cn.com/problems/maximal-square/ 分析：考虑动态规划。 表示以 为当前最大正方形的右下角时的正方形的最大边长。那么转移方程： #include<bits/stdc++.h> using namespace std; const int maxn=3e3+10; int dp[maxn][maxn],a[maxn][maxn]; int main() { int n,m,ans=0; cin>>n>>m; ...

1.条件类型最短路 https://ac.nowcoder.com/acm/contest/370/B 题意：n个点，m无向边，n个点有一部分是特殊的点，求从1走到n最短路是多少。并且该最短路满足走过的特殊点不超过K.分析: 将所有点的状态分离成K个点(K分层图)，表示到当前该点的走过的特殊点有 个。然后跑一遍dij即可。(dis多建一维条件跑dij也可以) #include<bits/stdc++.h> #define ll long long #define inf 0x7f7f7f7f #define pr pair<ll,ll> using namespa...

大致题意：给定一个序列，求 . 表示 和 十进制下的位数差.分析：方法一:离散+树状数组我们可以逆序遍历序列，计算当前 作为 的左参数的贡献，那么我们与 相加能产生数位差 .举个例子：能至少产生一位数位差，设比 大的最小十进制数位 ，那么 的大小一定要大于等于 .依次枚举至少产生两位数位差.....其实就是遍历所有的十进制数字进行查找.那么当我们求解 的数位差贡献时，必须要有一个数据结构存储 ,并且使其有序才能进行二分查找符合条件的 的个数。-------离散所有可能出现的值(大概9e5)，然后树状数组维护即可. #include<bits/stdc++.h> #define l...

[CQOI2011]动态逆序对

1.费马小定理运算推公式https://ac.nowcoder.com/acm/contest/5945/D

大致题意：一个序列，可以执行两种操作。 对区间 内的元素依次对x取 ，然后将结果赋值给 . 求区间元素和。 分析：这道题跟区间开方思路类似。每次对一个区间进行gcd的话一般会有大部分会变成1，可以用一些小技巧来保证复杂度不会太差，用一个tag变量去标记一下这个区间是不是全都相等，再用一个sam变量去标记区间全相等的时候的元素大小，这样修改的时候对于区间元素都相等的直接对sam进行gcd即可。最后用一个线段树维护标记。(虽然区间开方的题目我是用分块,不过线段树还是挺好写的 #include<bits/stdc++.h> #define ls cur<<1 ...

规律题，挂一个暴力打表的代码。 #include<bits/stdc++.h> using namespace std; int a[1005]; int n; int vis[2005],b[1005]; int ans; void dfs( int x,int y ) { if( x>n ) { if( y==2*n ) { ans++; for( int i=1;i<=n;i++ ) printf("%d ",a[i]); p...

1.三分+最短路参考 苟且的狮子 博客 https://blog.nowcoder.net/n/1fb0276367aa44df861b17f185653058 #include<bits/stdc++.h> #define ll long long #define pr pair<ll,ll> using namespace std; const int N=2e5+10; const ll inf=1e18; struct node{ int v,len,next; }a[N*2]; int pre[N],cnt=0; ll dis[N],vis...

树状数组简单应用，逆序数转换为：求前i个数小于x的和。 #include<bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; typedef long long ll; const int maxn=2e5+10; int sum[maxn],cnt=maxn-1; void add( int x ) { while( x<=cnt ) sum[x]++,x+=lowbit(x); } int query( int x ,int ans=0 ) { while( x ) ans+=sum[x],...

大致题意： 给定 头牛，每头牛每分钟都会造成破坏 ，农夫可以将牛拉回牛栏里面花费的时间是 .请问农夫拉回牛的顺序是多少可以使得破坏最少。 分析：贪心。考虑第 头牛和第 头牛，哪头先拉入牛栏.如果 先 后，那么破坏为：.如果 先 后，那么破坏为： .要使得破坏程度最少，即：化简： 那么我们就按照上式子进行排序从小到大拉入牛进牛栏。然后依次算破坏程度即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; pair<int,int> ...

D. The Best Vacation 大致题意：规定一个日历有 个月，每个月有 天，在第 个月的第 天活动你可以获得 的贡献，你只能连续 天活动，请问你能获得的最大贡献是多少. 分析：方法一：尺取法.考虑我们选的天数是连续，那么对应月份也是连续的，并且假设中间月份的天数都是取得到的，但是还可以再两边去取天数，显然我们应该是去最左边的天数，因为贡献是从 开始递减的，而右边的天数是从 开始递增的。那么我们依次遍历月份，用双指针去维护可满足的连续天数并计算对应贡献.但是月份天数就跟环一样，是首尾相接的，对于环而言的尺取，我们一般都是多开一倍空间，数组循环一遍，然后从 的位置开始计算贡献(这样可...

题目大意：有n中货币，每种货币都有无限多个，问是否可以简化货币个数，使得能表示的数个数不变。 分析：容易想到货币中最小的面值肯定要留下，那么考虑第二小的货币是否可以去掉，如果第二小的货币是最小货币的倍数，那么就能去掉。那么考虑第i小的货币是否能够留下，那么我们是要查看已留下的货币能否表示当前的货币，那么这个就是一个多重背包问题。先将所有物品按照面值排序，然后从小到大枚举物品进行背包前判断改物品是否能被表示，如果可以那么这个物品就不拿， 否则进行背包。 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7...