2022NOIP A层联测35（结局）

T1：

《弹珠游戏》

\(n\) 个人，\(3n\) 个弹珠，分别为 \(R,G,B\)，每个人三种颜色分别取一个，不满意度为编号极差，求所有人不满意度和最小时的方案数。

壮压计数，至于之前每种颜色的个数有关，当当前为 \(R\) 时，前面若有 \(GB\) 则乘上其人数，否则若有 \(G\) 则乘上其人数，否则若有 \(B\) 则乘上其人数，否则乘上 \(0\) 的人数，之后更新对应人数。

#include<bits/stdc++.h>

using namespace std;

#define int long long
constexpr int N=3e5+5,mod=998244353;
int n,cnt[10],ans;
signed main(){
    freopen("A.in","r",stdin),freopen("A.out","w",stdout);
    ans=1;
    cin>>n;
    cnt[0]=n;
    n*=3;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        switch(c){
            case 'R':if(cnt[6])(ans*=cnt[6]--)%=mod;else if(cnt[4])(ans*=cnt[4]--)%=mod,cnt[5]++;else if(cnt[2])(ans*=cnt[2]--)%=mod,cnt[3]++;else (ans*=cnt[0]--)%=mod,cnt[1]++;break;
            case 'G':if(cnt[5])(ans*=cnt[5]--)%=mod;else if(cnt[4])(ans*=cnt[4]--)%=mod,cnt[6]++;else if(cnt[1])(ans*=cnt[1]--)%=mod,cnt[3]++;else (ans*=cnt[0]--)%=mod,cnt[2]++;break;
            case 'B':if(cnt[3])(ans*=cnt[3]--)%=mod;else if(cnt[2])(ans*=cnt[2]--)%=mod,cnt[6]++;else if(cnt[1])(ans*=cnt[1]--)%=mod,cnt[5]++;else (ans*=cnt[0]--)%=mod,cnt[4]++;break;
        }
    }
    cout<<ans;
    return 0;
}

T2：

《晚会》

定义一个三元组不合法，当且仅当出现 \(dis(i,j)<dis(i,k)\) 并且 \(dis(i,j)<dis(j,k)\) ，给出一些边，求合法时的 \(\sum_{i=1}^{n}\sum_{j=i+1}^{n}dis(i,j)\)，或者无解。

对于一个三元组而言，新加入的边是另外两条边的较小值，于是找出最大生成树，再进行重构，若给出的边的瓶颈权值不等于边权则无解，两个子图不连通时两边只连边权为 \(1\) 的点即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long
constexpr int N=6e5+5;
int n,m,ans,sz[N],fa[N][25],dep[N],lc[N],rc[N],val[N],num;
bool vis[N];
struct edge{int x,y,w;inline bool friend operator<(const edge&a,const edge&b){return a.w>b.w;}}e[N];
struct DSU{
    int f[N];
    inline void init(int n){for(int i=1;i<=n;i++)f[i]=i;}
    int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
}d;
void dfs(int x,int f){
    fa[x][0]=f;
    dep[x]=dep[f]+1;
    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    if(x<=n)return;
    dfs(lc[x],x);
    dfs(rc[x],x);
}
inline int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;~i;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=20;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs0(int x,int f){
    if(x<=n)return sz[x]=1,void();
    dfs0(lc[x],x),dfs0(rc[x],x);
    sz[x]=sz[lc[x]]+sz[rc[x]];
    ans+=sz[lc[x]]*sz[rc[x]]*val[x];
    num+=sz[lc[x]]*sz[rc[x]];
}
inline void exkruskal(){
    sort(&e[1],&e[m+1]);
    d.init(n);
    int cnt=n;
    for(int i=1;i<=m;i++){
        int x=d.find(e[i].x),y=d.find(e[i].y);
        if(x==y)continue;
        vis[i]=1;
        val[++cnt]=e[i].w;
        d.f[x]=d.f[y]=d.f[cnt]=cnt;
        lc[cnt]=x,rc[cnt]=y;
    }
    for(int i=cnt;i;i--)if(!fa[i][0])dfs(i,0);
    for(int i=1;i<=m;i++){
        if(vis[i])continue;
        if(e[i].w<val[LCA(e[i].x,e[i].y)])cout<<-1,exit(0);
    }
    for(int i=cnt;i>n;i--)if(!fa[i][0])dfs0(i,0);
    ans+=n*(n-1)/2-num;
    cout<<ans;
}
signed main(){
    freopen("B.in","r",stdin),freopen("B.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>e[i].x>>e[i].y>>e[i].w;
    exkruskal();
    return 0;
}

T4：

《选举》

有 \(n\) 个城市和 \(m\) 个党派，每个城市 \(i\) 会将自己全部的 \(b_i\) 张票投给自己支持的党派 \(a_i\)，每次询问城市区间 \([l,r]\) 和党派区间 \([vl,vr]\)，求党派区间内最大的得票数量。

回滚莫队维护。

#include<bits/stdc++.h>

using namespace std;

#define int long long
constexpr int N=3e5+5;
int n,m,qq,bln[N],blm[N],a[N],b[N],cnt[N],ans[N],mx[N],rem[N],len,lem;
struct node{
    int id,l,r,vl,vr;
    inline bool friend operator<(const node&a,const node&b){return bln[a.l]==bln[b.l]?a.r<b.r:a.l<b.l;}
}q[N];
void add(int x){
    cnt[a[x]]+=b[x];
    rem[x]=mx[blm[a[x]]];
    mx[blm[a[x]]]=max(mx[blm[a[x]]],cnt[a[x]]);
}
inline void del(int x){
    cnt[a[x]]-=b[x];
    mx[blm[a[x]]]=rem[x];
}
inline void clear(int r){
    while(r&&cnt[a[r]])mx[blm[a[r]]]=0,cnt[a[r]]-=b[r],r--;
}
inline int query(int l,int r){
    int re=0;
    if(blm[l]==blm[r]){
        for(int i=l;i<=r;i++)re=max(re,cnt[i]);
        return re;
    }
    re=max(query(l,blm[l]*lem),query((blm[r]-1)*lem+1,r));
    for(int i=blm[l]+1;i<blm[r];i++)re=max(re,mx[i]);
    return re;
}
signed main(){
    freopen("D.in","r",stdin),freopen("D.out","w",stdout);
    cin>>n>>m>>qq;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=qq;i++)cin>>q[i].l>>q[i].r>>q[i].vl>>q[i].vr,q[i].id=i;
    len=sqrt(n);
    for(int i=1;i<=n;i++)bln[i]=(i-1)/len+1;
    lem=sqrt(m);
    for(int i=1;i<=m;i++)blm[i]=(i-1)/lem+1;
    sort(&q[1],&q[qq+1]);
    int r=0;
    for(int i=1;i<=qq;i++){
        if(bln[q[i].l]!=bln[q[i-1].l])clear(r),r=min(bln[q[i].l]*len,n);
        while(r<q[i].r)add(++r);
        int lim=min(q[i].r,bln[q[i].l]*len);
        for(int j=q[i].l;j<=lim;j++)add(j);
        ans[q[i].id]=query(q[i].vl,q[i].vr);
        for(int j=lim;j>=q[i].l;j--)del(j);
    }
    for(int i=1;i<=qq;i++)cout<<ans[i]<<'\n';
    return 0;
}

这大概是我最后一篇题解了吧。
由于没有noip，再加上春季赛，还有消失的假期，未知的文化课，
我比赛根本没有认真打，许多人甚至连暴力都没有敲。

我和 \(Sakura\) 玩敲 \(01\) 串，他用小键盘敲 \(1\)，我用大键盘敲 \(0\)，显然是两人同时的，之后摩尔投票判断手速决定胜负。

我敲 \(0\) 的！

原文地址：http://www.cnblogs.com/safeng/p/16926070.html