【补题】2021牛客暑期多校训练营4-n

NO.4

I.Inverse Pair

题意：

求逆序对数量，多了一步操作，可以选择将序列中的元素+1，使得逆序对数量最少。

序列为1到n的一个全排列

思路：

因为+1只能改变差值相差为1的逆序对，所以，对于一个位置的元素x，如果它前面存在x+1,则将现在的x加1，使得逆序对数-1

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
ll c[N],vis[N];
int n;
int lowbit(int i){
    
    return i&(-i);
}
void insert(int i,int x){
    
    for(;i<=n;i+=lowbit(i)){
    
        c[i]+=x;
    }
}
ll getsum(int i){
    
    ll sum=0;
    for(;i;i-=lowbit(i)){
    
        sum+=c[i];
    }
    return sum;
}
int main(){
    
    cin>>n;
    ll ans=0;
    for(ll i=1;i<=n;i++){
    
        ll a;
        cin>>a;
        if(vis[a+1])a++;
        else vis[a]=1;
        insert(a,1);
        ans+=i-getsum(a);//统计当前序列中大于a的元素的个数
    }
    cout<<ans<<endl;
}

j.Average

求最大的区间平均值，区间长度大于x

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2e5+5;
double sum[maxn],a[maxn],b[maxn];
int n,m,x,y;
bool check(double mid,double p[],int num,int d){
    
	for(int i=1;i<=num;i++){
    
		sum[i]=sum[i-1]+p[i]-mid;
	}
	double mn=0;
	for(int i=0,j=d;j<=num;j++,i++){
    
		mn=min(mn,sum[i]);
		if(sum[j]-mn>=0)return 1;
	}
	return 0;
}
int main(){
    
    scanf("%d%d%d%d",&n,&m,&x,&y);
    double l=0,r=1e5+10,ans=0;
    for(int i=1;i<=n;i++){
    
    	scanf("%lf",&a[i]);
    }
    while(r-l>1e-7){
    
    	double mid=(l+r)/2;
    	if(check(mid,a,n,x))l=mid;
    	else r=mid;
	}
    ans+=r;
    for(int i=1;i<=m;i++){
    
    	scanf("%lf",&b[i]);
    }
    l=0,r=1e5+10;
    while(r-l>1e-7){
    
    	double mid=(l+r)/2;
    	if(check(mid,b,m,y))l=mid;
    	else r=mid;
	}
    ans+=r;
    printf("%.6lf\n",ans);
}

C.LCS

题意：

思路：

从最小的开始填充a，再填充b，再填充c，再分别填充x，y，z

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2e5+5;
int n,a,b,c;
string s1,s2,s3;
int main(){
    
    scanf("%d%d%d%d",&a,&b,&c,&n);
    int m3=min(a,min(b,c)),m1=max(a,max(b,c)),m2=a+b+c-m1-m3;
    if(a+b+c-2*m3>n){
    
    	printf("NO");
    	return 0;
	}
	for(int i=1;i<=m3;i++)
	    s1+="a",s2+="a",s3+="a";
	for(int i=1;i<=m2-m3;i++)
	    s2+="b",s3+="b";
	for(int i=1;i<=m1-m3;i++)
	    s1+="c",s3+="c";
	for(int i=m1+1;i<=n;i++)
	    s1+="x";
	for(int i=m2+1;i<=n;i++)
	    s2+="y";
	for(int i=a+b+c-2*m3+1;i<=n;i++)
	    s3+="z";    
	if(a<=b&&b<=c)cout<<s1<<endl<<s2<<endl<<s3<<endl;
	else if(a<=c&&c<=b)cout<<s2<<endl<<s1<<endl<<s3<<endl;
	else if(b<=a&&a<=c)cout<<s3<<endl<<s2<<endl<<s1<<endl;
	else if(b<=c&&c<=a)cout<<s3<<endl<<s1<<endl<<s2<<endl;
	else if(c<=a&&a<=b)cout<<s2<<endl<<s3<<endl<<s1<<endl;
	else if(c<=b&&b<=a)cout<<s1<<endl<<s3<<endl<<s2<<endl;
}

E.Tree Xor

题意：

一颗带权树，已知每个点的权值的范围，以及每条边的两个点异或后的权值，求$w_{1...n}$的所有可能的取值个数
思路：
1.先以1号点为根节点，令其权值为0，遍历一次树，得到每个点的权值$w_i$
2.若1号点 $⨁x$ ，则其他点的权值也跟着 $⨁x$，及$w_i⨁x$，加上范围
$L_i\le w_i⨁x\le R_i$，假设可以两边同时异或$w_i$，$L_i⨁w_i\le x\le R_i⨁w_i$，则问题转化成，求n个$[L_i⨁w_i，R_i⨁w_i]$的并，
3.假设不成立，因为[L_i，R_i]区间异或w_i后的区间并不是连续的$[L_i⨁w_i，R_i⨁w_i]$。
4.发现[****0000，*****1111]异或d后，是连续的[----0000，----1111]区间，
比如$[10100000,10101111]\oplus 10011010\Rightarrow [00110000,00111111]$
5.利用$[0,2^{30}-1]$的线段树，把$[L_i，R_i]$分成$logW$个连续的区间，且每个区间的形式如上

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2e5+5;
int n,cnt,rt,k,L[maxn],R[maxn],w[maxn],head[maxn],to[maxn],nex[maxn];
vector<pair<int,int>>tor;
struct node{
    
	int l,r;
}tree[maxn*20];
void add(int x,int y,int z){
    
	to[++k]=y;
	nex[k]=head[x];
	w[k]=z;
	head[x]=k;
}
void update(int &now,int l,int r,int x,int y,int val){
    
	if(!now)now=++cnt;
	if(x<=l&&r<=y){
    
		int dl=l^(val&~(r-l));
		int dr=dl+r-l;
		tor.push_back({
    dl,1});
		tor.push_back({
    dr+1,-1});
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(tree[now].l,l,mid,x,y,val);
	if(y>mid)update(tree[now].r,mid+1,r,x,y,val);
}
void dfs(int x,int f,int val){
    
	update(rt,0,(1<<30)-1,L[x],R[x],val);
	for(int i=head[x];i;i=nex[i]){
    
		int y=to[i];
		if(y==f)continue;
		w[i]^=val;
		dfs(y,x,w[i]);
	}
}
int solve(){
    
	int ans=0,he=0;
	sort(tor.begin(),tor.end());
	
	for(int i=0;i<tor.size()-1;i++){
    
		he+=tor[i].second;
		if(he==n)ans+=tor[i+1].first-tor[i].first;
	}
	return ans;
}
int main(){
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
    
		scanf("%d%d",&L[i],&R[i]);
	}
	for(int i=1,x,y,z;i<n;i++){
    
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	dfs(1,0,0);
	printf("%d\n",solve());
}

NO.5

J.Jewels

KM二分图最大权匹配

#include<bits/stdc++.h>
#define int long long
#define N 505
using namespace std;
const int INF=1e18;
int n,m;
int la[N],ra[N],w[N][N],vis[N],slack[N],match[N],pre[N];
void bfs(int u){
    
    int x,y=0,yy=0,delta;
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++) slack[i]=INF;
    match[y]=u;
    while(1){
    
        x=match[y],delta=INF,vis[y]=1;
        for(int i=1;i<=n;i++){
    
            if(vis[i]){
    
                continue;
            }
            if(slack[i]>la[x]+ra[i]-w[x][i]){
    
                slack[i]=la[x]+ra[i]-w[x][i];
                pre[i]=y;
            }
            if(slack[i]<delta) delta=slack[i],yy=i;
        }
        for(int i=0;i<=n;i++){
    
            if(vis[i]){
    
                la[match[i]]-=delta;
                ra[i]+=delta;
            }else{
    
                slack[i]-=delta;//由于本题卡O(n4)，所本题需要用到bfs版的KM
            }
        }
        y=yy;
        if(match[y]==-1){
    
            break;
        }
    }
    while(y){
    
        match[y]=match[pre[y]];
        y=pre[y];
    }
}
int KM(){
    
    memset(match,-1,sizeof(match));
    memset(la,0,sizeof(la));
    memset(ra,0,sizeof(ra));
    for(int i=1;i<=n;i++){
    
        memset(vis,0,sizeof(vis));
        bfs(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
    
        if(match[i]!=-1){
    
            ans+=w[match[i]][i];
        }
    }
    return ans;
}
int dis(int x){
    
	return x*x;
}
signed main(){
    
	scanf("%d",&n);
	int d=0;
	for(int i=1,x,y,z,v;i<=n;i++){
    
		cin>>x>>y>>z>>v;
		for(int j=1;j<=n;j++){
    
			w[i][j]=-dis(x)-dis(y)-dis(z+1ll*(j-1)*v);
		}
	}
	cout<<-KM();
	
}