20201003国庆day1

T1

求对S进行不超过k次“交换两个相邻的字符”操作，得到的字典序最小的字符串。

95pts：模拟即可。从每个位置出发，找出接下来k个字符中最小的移到前面。每次swap时k--直到k=0。时间复杂度(O(n^2))

#include<bits/stdc++.h>
using namespace std;
//struct node{
//	int pos,dis;
//	char num;
//}s[1005];
//bool cmp(node a,node b){
//	if(a.num==b.num)return a.pos<b.pos;
//	return a.num<b.num;
//}
int n,k;
char cc[1005];
int main(){
	scanf("%d%d
",&n,&k);
//	for(int i=1;i<=n;i++){
//		scanf("%c",&cc[i]);
//		s[i].num=cc[i];
//		s[i].pos=i;
//		
//	}
	scanf("%s",cc);
	if(k==0){ 
		for(int i=0;i<n;i++)printf("%c",cc[i]);
		return 0;
	}
	//for(int i=1;i<=n;i++)printf("%c",cc[i]);
	//sort(s+1,s+1+n,cmp);
	//int q=0;
	for(int i=0;i<=n;i++){
			//q++;
			int index=0;
			bool flag=0;
			int tmp=cc[i];
			for(int j=i+1;j<=i+k&&j<n;j++){
				if(tmp>cc[j]){
					tmp=cc[j];
					index=j;
					flag=1;
				}
			}
			if(flag){
				for(int j=index;j>=1;j--){
					if(cc[j]<cc[j-1]){
						swap(cc[j],cc[j-1]);
						k--;
					}
					if(k<=0)break;
				}
				flag=0;
			}
	}
	for(int i=0;i<n;i++)printf("%c",cc[i]);
	return 0;
}

100pts思路：每次选出字典序最小的字母，将它移到前面。若移动次数小于k就直接移动，否则不移动，选择字典序次小的移动（链表存字符）。计算移动次数用树状数组维护。时间复杂度(O(nlogn))。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
const int N=1e6+7,inf=2e9+7;
int head[N],go[N],nxt[N],cnt;
void add(int u,int v){
	go[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int n,s[N];
ll k;
char c[N];
int query(int x){
	int ans=0;
	for(int i=x;i>0;i-=i&-i){
		ans+=s[i];
	}
	return ans;
}
void pluss(int x,int a){
	for(int i=x;i<=n;i+=i&-i){
		s[i]+=a;
	}
}
int ans[N];
int main(){
	//freopen("escape.in","r",stdin);freopen("escape.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	scanf("%s",c+1);
	for(int i=n;i>=1;i--){
		add(c[i]-'a'+1,i);pluss(i,1);
	}
	for(int tmp=0,i=1;i<=n;i++){
		for(int u=1;u<=26;u++,tmp=0){
			if(!head[u])continue;
			if((tmp=query(go[head[u]]-1))<=k){
				pluss(go[head[u]],-1);
				k-=tmp;
				head[u]=nxt[head[u]];
				ans[i]=u;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)printf("%c",ans[i]+'a'-1);
	return 0;
}

T2

求出从每个点出发到每个子树海拔单调下降的路径数量，则以该点为海拔最高点的合法路径数为

[(sum_{i=1}^ks_i)^2-sum_{i=1}^ks_i^2 ]

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=300005;
int n,f[N];
vector<int>e[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;scanf("%d%d",&x,&y);
		e[x].push_back(y);e[y].push_back(x);
	}
	LL ans=0;
	for(int i=1;i<=n;i++){
		for(int x=0;x<e[i].size();x++)if(e[i][x]<i)f[i]+=f[e[i][x]]+1;
		for(int x=0;x<e[i].size();x++)if(e[i][x]<i)ans+=(LL)(f[i]-f[e[i][x]]-1)*(f[e[i][x]]+1);
	}
	printf("%lld
",ans);
	return 0;
}