Codeforces Round #673 (Div. 1)

A

模拟一下？

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=3e5+11;
int T,N,Ans[MAXN];vector<int> vec[MAXN];
int main(){
    //freopen("1.in","r",stdin);
    T=read();
    while(T--){
        memset(Ans,127/3,sizeof(Ans));
        N=read();for(int i=1;i<=N;i++) vec[i].clear(),vec[i].pb(0);for(int i=1;i<=N;i++) vec[read()].pb(i);
        for(int i=1;i<=N;i++) vec[i].pb(N+1);
        for(int i=1;i<=N;i++){
            int Maxn=0;
            for(int j=1;j<vec[i].size();j++) Maxn=max(Maxn,vec[i][j]-vec[i][j-1]);
            Ans[Maxn]=min(Ans[Maxn],i);
        }
        for(int i=1;i<=N;i++) Ans[i]=min(Ans[i],Ans[i-1]);
        for(int i=1;i<=N;i++){
            if(Ans[i]>N) printf("-1 ");
            else printf("%d ",Ans[i]);
        }printf("
");
    }return 0;
}
View Code

B

由于 $1$ 的特性，先通过 $2n$ 次操作将所以数移到 $1$，再通过 $2n$ 次操作，移回去即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#include<bitset>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e4+11;
int T,N,A[MAXN],sum,tot;
pair<pii,int> Ans[MAXN<<2];
int main(){
    //freopen("B.in","r",stdin);
    T=read();
    while(T--){
        N=read(),sum=0;
        for(int i=1;i<=N;i++) A[i]=read(),sum+=A[i];tot=0;
        if((sum%N)){printf("-1
");continue;}sum/=N;
        for(int i=2;i<=N;i++){
            int x=(i-(A[i]%i))%i;
            ++tot;Ans[tot].fi.fi=1,Ans[tot].fi.se=i,Ans[tot].se=x;
            ++tot;Ans[tot].fi.fi=i,Ans[tot].fi.se=1,Ans[tot].se=(x+A[i])/i;
        }
        for(int i=2;i<=N;i++){
            ++tot;Ans[tot].fi.fi=1,Ans[tot].fi.se=i,Ans[tot].se=sum;
        }printf("%d
",tot);
        for(int i=1;i<=tot;i++) printf("%d %d %d
",Ans[i].fi.fi,Ans[i].fi.se,Ans[i].se);
    }return 0;
}
View Code

C

按位枚举。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#include<bitset>
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=3e5+11;
int N,A[MAXN],cur,now;pii B[MAXN];
vector<int> vec[MAXN];
bool cmp(int a,int b){return a>b;}
signed main(){
//    /freopen("C.in","r",stdin);
    N=read();for(int i=1;i<=N;i++) A[i]=B[i].fi=read(),B[i].se=i;sort(B+1,B+N+1);
    for(int i=31;i>=1;i--){
        for(int j=1;j<=N;j++) vec[j].clear();
        int cnt=0;vec[++cnt].pb(B[1].se);
        for(int j=2;j<=N;j++){
            int pre=(B[j-1].fi>>i),now=(B[j].fi>>i);
            if(now==pre) vec[cnt].pb(B[j].se);
            else{++cnt;vec[cnt].pb(B[j].se);}
        }
        int S0=0,S1=0,Sum=0;
        for(int j=1;j<=cnt;j++){
            sort(vec[j].begin(),vec[j].end(),cmp);
            int t0=0,t1=0,siz=vec[j].size(); Sum+=(siz*(siz-1))/2;
            for(auto p:vec[j]){
                bool ww=(A[p]>>(i-1))&1;
                if(ww) S0+=t0,t1++;
                else t0++,S1+=t1;
            }
        }
        if(S0<=S1) now+=S0;
        else cur|=(1ll<<(i-1)),now+=S1;
        //cerr<<"cnt:"<<cnt<<" now:"<<now<<" cur:"<<cur<<" i:"<<i<<" "<<S0<<" "<<S1<<endl;
    }printf("%lld %lld
",now,cur);return 0;
}
View Code

D

由于删除不太好做考虑变为增加，而由于操作有后效性考虑建 $kruskal$ 重构树，保证当时间为 $t$ 时当前子树里的点联通。线段树维护。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#include<bitset>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=4e5+11;
int N,M,T[MAXN];vector<int> vec[MAXN];
struct Segment{
    int Maxn[MAXN<<2];
    void Modify(int k,int l,int r,int ps,int w){
        if(l==r){Maxn[k]=w;return;}
        int mid=(l+r)>>1;if(ps<=mid) Modify(k<<1,l,mid,ps,w);else Modify(k<<1|1,mid+1,r,ps,w);
        Maxn[k]=max(Maxn[k<<1],Maxn[k<<1|1]);return;
    }
    int Query(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y) return Maxn[k];int mid=(l+r)>>1,res=0;
        if(x<=mid) res=max(res,Query(k<<1,l,mid,x,y));
        if(mid<y) res=max(res,Query(k<<1|1,mid+1,r,x,y));
        return res;
    }
}S;
struct Edge{int u,v,tim;}E[MAXN];
bool cmp(Edge x1,Edge x2){return x1.tim>x2.tim;}
struct Union{
    int f[MAXN];void init(){for(int i=1;i<=2*N;i++) f[i]=i;return;}
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
}U;pii Que[MAXN];
int dfn[MAXN],siz[MAXN],INF=INT_MAX,MM[MAXN],Val[MAXN],dep[MAXN],tot,fa[MAXN][21],cnt,Q;
void dfs(int u,int fath){
    dep[u]=dep[fath]+1;fa[u][0]=fath;if(u<=N) siz[u]=1,dfn[u]=++dfn[0];
    for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:vec[u]) if(v!=fath) dfs(v,u),siz[u]+=siz[v],dfn[u]=min(dfn[u],dfn[v]);return;
}
int Qmax(int u,int t){
    for(int i=20;i>=0;i--) if(T[fa[u][i]]>=t&&fa[u][i]) u=fa[u][i];
    return u;
}
int main(){
    //freopen("D.in","r",stdin);
    N=read(),M=read(),Q=read();U.init();tot=N;
    for(int i=1;i<=N;i++) Val[i]=read(),MM[Val[i]]=i;
    for(int i=1;i<=M;i++) E[i].u=read(),E[i].v=read(),E[i].tim=INF;int ps=0;
    for(int i=1;i<=Q;i++){int opt=read(),u=read();if(opt==1) Que[++cnt].fi=u,Que[cnt].se=ps;else E[u].tim=ps=i;}sort(E+1,E+M+1,cmp);
    for(int i=1;i<=M;i++){
        int u=E[i].u,v=E[i].v,tim=E[i].tim;
        if(U.find(u)==U.find(v)) continue;
        u=U.find(u),v=U.find(v);
        ++tot;U.f[u]=U.f[v]=tot;T[tot]=tim;
        vec[tot].pb(u),vec[tot].pb(v);
    }memset(dfn,127/3,sizeof(dfn));dfn[0]=0;
    for(int i=1;i<=tot;i++) if(U.find(i)==i) dfs(i,0);
    for(int i=1;i<=N;i++) S.Modify(1,1,N,dfn[i],Val[i]);
    for(int i=1;i<=cnt;i++){
        int u=Que[i].fi,tim=Que[i].se+1;
        int G=Qmax(u,tim),L=dfn[G],R=dfn[G]+siz[G]-1,WW;
        printf("%d
",WW=S.Query(1,1,N,L,R));if(!WW) continue;
        S.Modify(1,1,N,dfn[MM[WW]],0);
    }return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/si-rui-yang/p/13755547.html