Educational Codeforces Round 102 (Rated for Div. 2)

做的有点慢 但是准确性很高

C. No More Inversions

分析：

首先算出该序列的逆序对显然对构造没有任何帮助 pass

一般这样的题目都会有巧妙点 也就是思维题

随便构造一组数据 1 2 3 4 3 2 1 最差的情况就是p为原序列 1 2 3 4 然后想办法优化 使得字典序最大

发现只有 3 2 1 这三个点会产生贡献

3 产生的贡献对应于 4

2 产生的贡献对应于 3 4

1 产生的贡献对应于 2 3 4

显然对于最长的连续对应点降序排序就好 因为对应点只会在前k个位置 不会对贡献产生变化

又因为k后面的点原来是降序 经过变化以后全部变成升序 不会产生新贡献

题目挺巧妙的 也不是很难想 找找规律应该就能发现

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
int n,k;
int a[maxn];
bool cmp(int aa,int bb){
	return aa>bb;
}
void solve();
int main(){
	int T;cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
	a[i]=i;
    int cha=n-k+1;
    int r=k;
    int l=k-cha+1;
    sort(a+l,a+1+k,cmp);
    for(int i=1;i<=k;i++)
    printf("%d ",a[i]);
    printf("\n");
}

D. Program

分析：

首先因为是连续变化的 所以对于一段前缀操作 他的答案为出现的最大值和最小值之差 max-min+1

将区间划分为 前段和后段

现在问题变为后段应该怎么维护

换个想法 后段能为前段造成什么样的贡献

考虑维护 每个后段的前缀的最大最小 只要维护后缀的最小最大 用总的相减即可

最后看后段能否跟新前段的最大最小值即可

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=2e5+5;
void solve();
int n,m,maxx,minn,res,l,r;
int premax[maxn],premin[maxn],now[maxn],sufmax[maxn],sufmin[maxn];
string s; 
int main(){
	int T;cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
	scanf("%d%d",&n,&m);
	cin>>s;premax[0]=maxx=0;premin[0]=minn=0;
	now[0]=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='-')now[i+1]=now[i]-1;
		else now[i+1]=now[i]+1;
		premax[i+1]=max(premax[i],now[i+1]);
		premin[i+1]=min(premin[i],now[i+1]);
	}
	res=0;
	sufmax[s.size()+1]=sufmin[s.size()+1]=0;
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]=='-')res--;
		else res++;
		sufmax[i+1]=res-minn;
		sufmin[i+1]=res-maxx;
		maxx=max(maxx,res);
		minn=min(minn,res);
	}
	while(m--){
		scanf("%d%d",&l,&r);
		int pmax=premax[l-1];
		int pmin=premin[l-1];
		int U=now[l-1];
		pmax=max(pmax,U+sufmax[r+1]);
		pmin=min(pmin,U+sufmin[r+1]);
		printf("%d\n",pmax-pmin+1);
	}
}

E. Minimum Path

针对这个模型 专门写了一篇

https://www.cnblogs.com/wzxbeliever/p/16898755.html