2023?？投嘈Ｓ?xùn)練第五場(chǎng)銅銀牌題解

A

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,d=700;
int n,m,a[N],bl[N],ans[N],p[N],c[N],s[N],tr[N],t;
struct node{int l,r,id;}q[N];
bool cmp(node a,node b){
    if(bl[a.l]!=bl[b.l])return bl[a.l]<bl[b.l];
    if(bl[a.l]&1)return a.r<b.r;
    else return a.r>b.r;
}

void add(int x){for(int i=x;i<=n;i+=i&-i)tr[i]+=1;}
int sum(int x){int a=0;while(x)a+=tr[x],x-=x&-x;return a;}
void addr(int x){int v=a[x];t+=p[x]*c[v]-s[v],c[v]++,s[v]+=p[x];}
void addl(int x){int v=a[x];t+=s[v]-p[x]*c[v],c[v]++,s[v]+=p[x];}
void delr(int x){int v=a[x];c[v]--,s[v]-=p[x],t-=p[x]*c[v]-s[v];}
void dell(int x){int v=a[x];c[v]--,s[v]-=p[x],t-=s[v]-p[x]*c[v];}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(a[i]);
        bl[i]=i/700;
        p[i]=sum(a[i]-1);
    }
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        int ql=q[i].l;
        int qr=q[i].r;
        int id=q[i].id;
        while(r<qr)addr(++r);
        while(l>ql)addl(--l);
        while(r>qr)delr(r--);
        while(l<ql)dell(l++);
        ans[id]=t;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}

B

對(duì)于一個(gè)長度為n的環(huán),最小逆序?qū)閚-1 在序列中，刪掉一些點(diǎn)，如果只選x個(gè)的話，剩下的len-x個(gè)也會(huì)對(duì)逆序?qū)ψ龀鲐暙I(xiàn)，所以總貢獻(xiàn)為n-1+n-x

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;
int n,k,a[N];
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=1e9;
    for(int i=1;i<=n;i++){
        priority_queue<int>q;
        int sum=0,x=0;
        for(int j=i;j<=n;j++){
            if(a[j]>=0)sum+=a[j],x++;
            else q.push(a[j]);
            if(sum>=k){
                while(q.size()&&sum+q.top()>=k)sum+=q.top(),q.pop(),x++;
                if(x)ans=min(ans,j-i+ j-i+1-x);
            }
        }
    }
    if(ans==1e9)ans=-1;
    cout<<ans;
}

C

估計(jì)是數(shù)據(jù)太弱了，過了太多人 下面這個(gè)樣例要輸出6,絕大多數(shù)人的答案都是7是錯(cuò)的題解也是錯(cuò)的

7
0 1 0 1 1 1 1
0 0 1 1 1 1 1
1 0 0 1 1 1 1
0 0 0 0 1 1 1
0 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 1 0 0

把一組匹配i,j+n 視為連邊ij ，那么這張圖存在完美匹配即為可以將其所有點(diǎn)劃分進(jìn)若干回路 中。根據(jù)競(jìng)賽圖的性質(zhì)，其一定存在一條哈密頓路徑，所以顯然最大匹配至少為n-1 。再根據(jù)競(jìng)賽圖 的性質(zhì)，每個(gè)強(qiáng)連通分量必然存在一條哈密頓回路，所以答案為 等價(jià)于圖中所有強(qiáng)連通分量大小均大 于等于2 。

所有的強(qiáng)連通分量大小至少為2則輸出n，否則輸出n-1

我們可以這樣理解，這道題把二分圖最大匹配和競(jìng)賽圖的性質(zhì)結(jié)合在一起 對(duì)于二分圖的一個(gè)個(gè)匹配連通塊，它其實(shí)是一個(gè)哈密頓回路，那么我們對(duì)ij連邊，tarjan縮點(diǎn)，只要強(qiáng)連通塊的sz>=2說明這是一個(gè)哈密頓回路

#include<bits/stdc++.h>
using namespace std;
const int N=3030;
int n,dfn[N],sz[N],low[N],o,scc_cnt,stk[N],id[N],top;
vector<int>g[N];
void tarjan(int u){
    dfn[u]=low[u]=++o;
    stk[++top]=u;
    for(auto j:g[u]){
        if(!dfn[j])tarjan(j),low[u]=min(low[u],low[j]);
        else if(!id[j])low[u]=min(low[u],dfn[j]);//min( low[j]
        
    }
    if(dfn[u]==low[u]){
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            if(x)g[i].push_back(j);
        }
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int i=1;i<=scc_cnt;i++){
        if(sz[i]<2){
            cout<<n-1;
            return 0;
        }
    }
    cout<<n;
}

競(jìng)賽圖相關(guān)技巧的學(xué)習(xí) 對(duì)于一個(gè)競(jìng)賽圖，一定有哈密頓通路

對(duì)于一個(gè)強(qiáng)連通競(jìng)賽圖,一定有哈密頓回路

競(jìng)賽圖縮點(diǎn)后肯定是一條鏈 有環(huán)一定是三元環(huán)

E

//對(duì)每一個(gè)區(qū)間交換最前面的r就好了
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,p[N],f[N],ne[N],ans[N],A[N];
struct node{
    int l,r,w;
}a[N];
bool cmp(node a,node b){
    int la=a.r-a.l;
    int lb=b.r-b.l;
    return la<lb;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i,ne[i]=i,A[i]=i;
    for(int i=0;i<m;i++)cin>>a[i].l>>a[i].r>>a[i].w;
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++){
        int l=a[i].l;
        int r=a[i].r;
        int w=a[i].w;
        if(l==r){
            if(w==1){cout<<-1;return 0;}
        }
        int ji=0;
        for(int x=l;x<=r;x++)ji+=f[x];
        if(w!=ji%2){
            swap(p[ne[l]],p[ne[l]+1]);
            
            f[l]++;
        }
        ne[l]=r;
    }
    for(int i=1;i<=n;i++)ans[p[i]]=i;
    
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

I

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,a[N],s[N],pre[N],suf[N],f[2][31];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    //處理前綴和,j=(0~i-1)
    
    memset(f,0,sizeof f);
    for(int j=0;j<=30;j++)f[0][j]=1;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum^=a[i];
        pre[i]=pre[i-1];
        for(int j=0;j<=30;j++){
            int x=sum>>j&1;
            pre[i]+=(1<<j)*f[x^1][j];
            pre[i]%=mod;
        }
        for(int j=0;j<=30;j++)f[sum>>j&1][j]++;
    }
    
    //處理后綴和 j=(i+1,n)
    memset(f,0,sizeof f);
    for(int j=0;j<=30;j++)f[0][j]=1;
    for(int i=n;i>=1;i--){
        s[i]=s[i+1]^a[i];
        suf[i]=suf[i+1];
        for(int j=0;j<=30;j++){
            int x=s[i]>>j&1;
            suf[i]+=(1<<j)*(f[x^1][j]);
            suf[i]%=mod;
        }
        for(int j=0;j<=30;j++)f[s[i]>>j&1][j]++;
    }
    //計(jì)算總的,j=i+1~n
    memset(f,0,sizeof f);
    for(int j=0;j<=30;j++)f[0][j]=suf[n+1];//其實(shí)也就是0
    int ans=0;
    for(int i=n;i>=1;i--){
        int x;
        for(int j=0;j<=30;j++){
            x=s[i]>>j&1;
            ans+=pre[i-1]*f[x^1][j]%mod*(1<<j)%mod;
            ans%=mod;
        }
        for(int j=0;j<=30;j++){
            x=s[i]>>j&1;
            f[x][j]+=suf[i];
            f[x][j]%=mod;
        }
    }
    cout<<ans;
    
}

異或運(yùn)算技巧知乎傳送門

也可以直接看下面兩張圖