好题整理

· · 个人记录

可能更好的观赏体验

前言：本篇文章整理的在洛谷上均为 \color{purple}{紫} - \color{black}{黑} 的难度的题目

UPDATE LOG

1.1 二分

做这道题之前，我们需要看出这道题是满足单调性的，换句话说，假设比赛最多的人比赛了 x 场，正确答案为 y。那么 x 到 y 的答案都是可以达成的。具体来说，我们可以让比赛最多的人赢 y 场，这是可以达到的，然后不断让他输的比赛再赢回来，即可证明满足单调性。

1.2 网络流

假设我们当前二分到了 x，我们可以将比赛结果假想为汇点，从源点连 x 的容量向每一个人，代表他们有 x 次赢的机会，每个人再向自己参加的比赛连一条容量为 1 的边，表示他们可以消耗一次机会去赢下这局，然后我们再将每场向汇点连一条容量为 1 的边，表示每场比赛是否有人赢。如果这个网络流的最大流为比赛场数，我们就可以知道 x 是合法的。

1.3 方案输出

我们此时已经二分出来答案了，那么我们根据这个答案再建一次网络流，重新跑一遍，然后我们对于每场比赛，根据反悔操作，我们可以发现流向这里为 1 的边的反边必定容量为 1。暴力枚举即可。

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
const int N=2e4+5,M=1e5+5;
struct Graph{
    int head[N],nxt[M],to[M],limit[M],edge=1;
    int cur[N],dis[N];
    void init(){
        edge=1;
        memset(head,0,sizeof(head));
        return;
    }
    void add(int u,int v,int w){
        nxt[++edge]=head[u];
        head[u]=edge;
        to[edge]=v,limit[edge]=w;
    }
    int dfs(int u,int t,int res){
        if(u==t)return res;
        int flow=0;
        for(int i=cur[u];i;i=nxt[i]){
            cur[u]=i;
            int c=min(res,limit[i]);
            int v=to[i];
            if(dis[v]==dis[u]+1&&c){
                int k=dfs(v,t,c);
                flow+=k,res-=k,limit[i]-=k,limit[i^1]+=k;
            }
        }
        if(!flow)dis[u]=-1;
        return flow;
    }
    int MaxFlow(int s,int t){
        int ans=0;
        while(1){
            memcpy(cur,head,sizeof(head));
            memset(dis,-1,sizeof(dis));
            dis[s]=0;
            queue<int> q;
            q.push(s);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                for(int i=head[u];i;i=nxt[i]){
                    int v=to[i];
                    if(dis[v]==-1&&limit[i]){
                        dis[v]=dis[u]+1;
                        q.push(v);
                    }
                }
            }
            if(dis[t]==-1)return ans;
            ans+=dfs(s,t,1e18);
        }
    }
}F;
int n,m;
vector<int> G[N];
pii ed[N];
bool check(int x){
    int s=0,t=n+m+1;
    F.init();
    rep(i,n){
        F.add(s,i,x);
        F.add(i,s,0);
    }
    rep(i,m){
        int u=ed[i].first,v=ed[i].second;
        F.add(u,n+i,1);
        F.add(n+i,u,0);
        F.add(v,n+i,1);
        F.add(n+i,v,0);
        F.add(n+i,t,1);
        F.add(t,n+1,0);
    }
    int k=F.MaxFlow(s,t);
    return (k==m? 1:0);
}
signed main(){
    n=read(),m=read();
    rep(i,m){
        int u=read(),v=read();
        ed[i]=mpr(u,v);
    }
    int l=1,r=m,ans=m;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            ans=mid,r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    out(ans);
    puts("");
    check(ans);
    for(int u=n+1;u<=n+m;u++){
        for(int i=F.head[u];i;i=F.nxt[i]){
            if(F.limit[i]){
                int v=F.to[i];
                if(v==ed[u-n].first)puts("1");
                else puts("0");
            }
        }
    }
    return 0;
}

2.[SDOI2011]染色（洛谷题面）

2.1 树链剖分

观察下这句话：

我们不难可以想出可以用树链剖分来维护树上线段树，然后进行区间修改，查询等操作。而区间修改比较简单，下面我们来将一下如何统计答案。

2.2 区间查询

首先是对于在线段树上的上传操作我们如何计算答案。假设我们现在要合并区间 [l1,r1] 和区间 [l2,r2] 且 l2=r1+1，那么我们可以维护这样的信息：

那么我们在合并 [l1,r1] 和 [l2,r2] 至 [l1,r2] 时，总答案为 [l1,r2].ans=[l1,r1].ans+[l2,r2].ans-([l1,r1].en==[l2,r2].st? 1:0)

然后对于树上链的答案合并也是同理。

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define ls p<<1
#define rs p<<1|1
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
const int N=100005;
int n,m;
vector<int> G[N];
int a[N],dfn[N],rnk[N],top[N],fa[N],son[N],sz[N];
int dep[N];
struct SegTree{
    int st=0,sum=0,en=0,l=0,r=0,tag;
}tree[N<<2];
void up(int p){
    tree[p].sum=tree[ls].sum+tree[rs].sum;
    if(tree[rs].st==tree[ls].en)tree[p].sum--;
    tree[p].st=tree[ls].st;
    tree[p].en=tree[rs].en;
    return;
}
void down(int p){
    if(!tree[p].tag)return;
    tree[ls].tag=tree[p].tag;
    tree[ls].st=tree[p].tag;
    tree[ls].en=tree[p].tag;
    tree[ls].sum=1;
    tree[rs].tag=tree[p].tag;
    tree[rs].st=tree[p].tag;
    tree[rs].en=tree[p].tag;
    tree[rs].sum=1;
    tree[p].tag=0;
    return;
}
void build(int l,int r,int p){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].st=tree[p].en=a[rnk[l]];
        tree[p].sum=1;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    up(p);
    return;
}
int cnt;
void dfs1(int u,int f){
    sz[u]=1;
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(auto v:G[u]){
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])son[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    dfn[u]=++cnt;
    rnk[cnt]=u;
    if(son[u])dfs2(son[u],tp);
    for(auto v:G[u]){
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void update(int l,int r,int x,int p){
    if(l<=tree[p].l&&r>=tree[p].r){
        tree[p].st=x;tree[p].en=x;
        tree[p].sum=1;
        tree[p].tag=x;
        return;
    }
    down(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)update(l,r,x,p<<1);
    else if(l>mid)update(l,r,x,p<<1|1);
    else{
        update(l,mid,x,p<<1);
        update(mid+1,r,x,p<<1|1);
    }
    up(p);
    return;
}
SegTree query(int l,int r,int p){
    if(l<=tree[p].l&&r>=tree[p].r){
        return tree[p];
    }
    down(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)return query(l,r,p<<1);
    else if(l>mid)return query(l,r,p<<1|1);
    else{
        SegTree x=query(l,mid,p<<1);
        SegTree y=query(mid+1,r,p<<1|1);
        SegTree res;
        res.sum=x.sum+y.sum;
        res.st=x.st;
        res.en=y.en;
        if(x.en==y.st)res.sum--;
        return res;
    }
}
void calc(int x,int y,int c){
    int fx=top[x],fy=top[y];
    while(fx!=fy){
        if(dep[top[x]]>=dep[top[y]]){
            update(dfn[fx],dfn[x],c,1);
            x=fa[fx];
        }
        else{
            update(dfn[fy],dfn[y],c,1);
            y=fa[fy];
        }
        fx=top[x],fy=top[y];
    }
    if(dfn[x]<dfn[y]){
                update(dfn[x],dfn[y],c,1);
    }
        else{
                update(dfn[y],dfn[x],c,1);
    }
    return;
}
int querysum(int x,int y){
    int ans=0,fx=top[x],fy=top[y];
    SegTree prex,prey;
    while(fx!=fy){
        if(dep[top[x]]>=dep[top[y]]){
            SegTree nowx=query(dfn[fx],dfn[x],1);
            ans+=nowx.sum;
            if(prex.st==nowx.en)ans--;
            x=fa[fx];
            prex=nowx;
        }
        else{
            SegTree nowy=query(dfn[fy],dfn[y],1);
            ans+=nowy.sum;
            if(prey.st==nowy.en)ans--;
            y=fa[fy];
            prey=nowy;
        }
        fx=top[x];
        fy=top[y];
    }
    if(dfn[x]<dfn[y]){
                SegTree a=query(dfn[x],dfn[y],1);
                ans+=a.sum;
                if(a.st==prex.st)ans--;
                if(a.en==prey.st)ans--;
    }
        else{
                SegTree a=query(dfn[y],dfn[x],1);
                ans+=a.sum;
                if(a.en==prex.st)ans--;
                if(a.st==prey.st)ans--;
    }
    return ans;
}
signed main(){
    scanf("%lld %lld",&n,&m);
    rep(i,n)scanf("%lld",a+i);
    rep(i,n-1){
        int u,v;
        scanf("%lld %lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    build(1,n,1);
    while(m--){
        char op;
        cin>>op;
        if(op=='C'){
            int a,b,c;
            scanf("%lld %lld %lld",&a,&b,&c);
            calc(a,b,c);
        }
        else{
            int a,b;
            scanf("%lld %lld",&a,&b);
            printf("%lld\n",querysum(a,b));
        }
    }
    return 0;
}

3.Unique Occurrences（洛谷题面）

3.1 计算

发现直接计算不容易做，可以考虑对于每个边权求贡献。对于一个条边，其贡献为 (左端点不经过相同边权点的总数)*(右端点不经过相同边权点的总数)

3.2 并查集

考虑用可撤销并查集进行分治，对于一种颜色，我们可以用并查集将不等于这个边权的边用并查集连接起来。用递归分治进行维护，最后计算答案。

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int n,fa[500005],sz[500005];
vector<pii> G[500005];
int getfa(int x){
    if(x==fa[x])return x;
    return getfa(fa[x]);
}
int rk[100005];
void Merge(int x,int y,vector<pii>& v){
    x=getfa(x),y=getfa(y);
    if(x==y)return;
    if(sz[x]>sz[y])swap(x,y);
    fa[x]=y;
    sz[y]+=sz[x];
    v.push_back(mpr(x,y));
}
void del(vector<pii>& v){
    while(v.size()){
        int top=v.size();
        int x=v[top-1].first,y=v[top-1].second;
        fa[x]=x,sz[y]-=sz[x];
        v.pop_back();
    }
    return;
}
int ans;
void solve(int l,int r){
    if(l==r){
        for(auto ed:G[l]){
            int x=getfa(ed.first),y=getfa(ed.second);
            ans=(ans+sz[x]*sz[y]);
        }
        return;
    }
    int mid=l+r>>1;
    vector<pii> v;
    repe(i,mid+1,r){
        for(auto ed:G[i]){
            Merge(ed.first,ed.second,v);
        }
    }
    solve(l,mid);
    del(v);
    repe(i,l,mid){
        for(auto ed:G[i]){
            Merge(ed.first,ed.second,v);
        }
    }
    solve(mid+1,r);
    del(v);
    return;
}
signed main(){
    n=read();
    rep(i,n-1){
        int u=read(),v=read(),w=read();
        G[w].pb(mpr(u,v));
    }
    rep(i,n)sz[i]=1,fa[i]=i;
    solve(1,n);
    out(ans);
    return 0;
}

4.[AGC003F] Fraction of Fractal（洛谷题面）

下文定义 block 为 level-1 的黑块个数，match_i 表示在 level-i 中上下或左右对应的黑块个数，side 表示 level_1 中上下或左右相邻的黑块个数。

4.1 分类讨论

对于这道题，直觉告诉我们连通块的个数取决于边界上的点对。那么我们可以分类讨论。

4.1.1 情况一

对于上下左右都没有对应的黑块对，很显然的，最后连通块的个数取决于 level-1 被复制了几次，即为 {block}^{k-1}

4.1.2 情况二

和情况一完全相反，上下左右都有对应的点对，显然怎么复制答案都是 1。

4.1.3 情况三

如果只有上下或左右有对应的话，这时候就有些复杂了。显然的，当我们每次复制的时候，答案将会乘上 block。但肯定是会有多算的情况的，而 level-i 多算的个数即为 side \times match_i，而 match_i=match_{i-1}\times match_1

ans_i=ans_{i-1} \times block - side \times match_{i-1} (2 \leq i \leq k)

最后用矩阵快速幂解决即可。

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define debug(x) cerr<<#x<<':'<<x<<endl;
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int h,w,k;
char s[1005][1005];
int cnt1,cnt2,block,num;
const int P=1e9+7;
struct Matrix{
    int a[4][4];
    Matrix(){memset(a,0,sizeof(a));}
    void init(){a[1][1]=a[2][2]=1;}
}st1,st2,ans;
Matrix operator*(Matrix a,Matrix b){
    Matrix c;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                c.a[i][j]=((c.a[i][j]+a.a[i][k]*b.a[k][j])%P+P)%P;
    return c;
}
Matrix ksm(Matrix A,int b){
    Matrix res;
    res.init();
    while(b){
        if(b&1)res=res*A;
        A=A*A;
        b>>=1;
    }
    return res;
}
signed main(){
    h=read(),w=read(),k=read();
    for(int i=1;i<=h;i++)scanf("%s",s[i]+1);
    rep(i,h)rep(j,w)block+=s[i][j]=='#';
    rep(i,h){
        if(s[i][1]==s[i][w]&&s[i][w]=='#')cnt1++;
    }
    rep(i,w){
        cnt2+=(s[1][i]==s[h][i]&&s[1][i]=='#');
    }
    if(cnt1&&cnt2)die("1");
    else if(!cnt1&&!cnt2)die(fast(block,k-1,P));
    else{
        if(cnt1){
            for(int i=1;i<=h;i++){
                for(int j=1;j<w;j++){
                    num+=(s[i][j]==s[i][j+1]&&s[i][j]=='#');
                }
            }
        }
        else{
            for(int j=1;j<=w;j++){
                for(int i=1;i<h;i++){
                    num+=(s[i][j]==s[i+1][j]&&s[i][j]=='#');
                }
            }
        }
        // cout<<block<<' '<<num<<' '<<cnt1+cnt2<<endl;
        st2.a[1][1]=st2.a[1][2]=1;
        st1.a[1][1]=block;
        st1.a[2][1]=-num;
        st1.a[2][2]=cnt1+cnt2;
        ans=st2*ksm(st1,k-1);
        out(ans.a[1][1]);
    }
    return 0;
}

5.Non-equal Neighbours

前言：本题为 CF1591F，一模一样题目还有 CF1585F 和 ARC115E(数据范围有改动)。其中两题洛谷评蓝，一题评紫，笔者认为难度更加偏向紫一些。

5.1 容斥

这道题如果直接计算答案，显然是不容易计算的。正难则反反更难，我们可以令函数 F(k) 表示 \sum^{n-1}_{i=1}b_{i}==b_{i+1}\geq k 的 b 数组个数，然后容斥 ans=\sum^{n-1}_{i=0} (-1)^{i}\times F(i)。

5.2 思路转化

但是考虑完容斥之后，我们会发现这道题仍然 unsolvable。我们需要将问题转化一下。思考一下 unique 函数是如何执行的，我们会发现可以将最终的 b 数组拆解成一些字串，而这些字串的数内部是相同的。此时我们可以设计出一个方程 dp_{i,j} 表示截至到第 i 个数我们将序列划分为了 j 个字串。而 F(k)=dp_{n,n-k}。转移方程则为 dp_{i,j}=\sum^{i-1}_{a=0}(dp_{a,j-1}*\min^{i}_{l=a+1}a_l)。

读者可以思考一下，为什么这个动态规划方程表示的是 \sum^{n-1}_{i=1}b_{i}==b_{i+1}\geq k，而不是 \sum^{n-1}_{i=1}b_{i}==b_{i+1}= k，答案在代码末尾注释。

5.3 空间时间优化

先咕着，有空时再写