[supplementary question] 2021 Niuke summer multi school training camp 4-N

NO.4

I.Inverse Pair

The question ：

Find the number of pairs in reverse order , One more step , You can choose to put the elements in the sequence +1, To minimize the number of pairs in reverse order .

The sequence is 1 To n A full array of

Ideas ：

because +1 The difference can only be changed to 1 The reverse order of , therefore , For elements in one location x, If it exists in front of x+1, Then the present x Add 1, Make inverse logarithm -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);// Count the current series greater than a The number of elements of 
    }
    cout<<ans<<endl;
}

j.Average

Find the maximum interval average , The interval length is greater than 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

The question ：

Ideas ：

Fill from the smallest a, Refill b, Refill c, Then fill in 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

The question ：

A weighted tree , The range of weights for each point is known , And the weight after XOR of two points of each edge , seek $w_{1...n}$ All possible values of
Ideas ：
1. Start with 1 Point number is the root node , Let its weight be 0, Traverse the tree once , Get the weight of each point $w_i$
2. if 1 Number point $⨁x$ , Then the weights of other points will follow $⨁x$, And $w_i⨁x$, Add range
$L_i\le w_i⨁x\le R_i$, Suppose you can XOR both sides at the same time $w_i$,$L_i⨁w_i\le x\le R_i⨁w_i$, Then the problem turns into , seek n individual $[L_i⨁w_i,R_i⨁w_i]$ And ,
3. Suppose not , because [L_i,R_i] Interval XOR w_i The latter interval is not continuous $[L_i⨁w_i,R_i⨁w_i]$.
4. Find out [****0000,*****1111] Exclusive or d after , Is a continuous [----0000,----1111] Section ,
such as $[10100000,10101111]\oplus 10011010\Rightarrow [00110000,00111111]$
5. utilize $[0,2^{30}-1]$ The line segment tree , hold $[L_i,R_i]$ Divide into $logW$ A continuous interval , And the form of each interval is as above

#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 Maximum weight matching of bipartite graphs

#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;// Because this question card O(n4), This question needs to use bfs Version of 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();
	
}