2 条题解

  • 1
    @ 2026-10-24 14:37:30

    题解

    为了洛谷写的,懒得改了,注意 敌人->黑马,己方->白马,力量值->速度

    竞选最简单做法。

    典型的田忌赛马问题,如果可以任意选对手,那么从大到小考虑每一个对手,维护一个当前己方力量值的集合。如果当前集合里有能打败当前对手的,就让最小的能打败他的人出战。否则直接让力量值最小的出去送死。不再证明其正确性。

    在本题中,我们顺时针考虑每一个敌人,并维护己方力量值集合,按上述策略决策。

    假设当前点不需要依赖他之前的点延后的人就能完成全部决斗,也就是从他开始,没有己方轮空的情况,那么从他开始枚举敌人就是正确的。

    现在我们解决了决策的问题,我们只需要找到这个开头位置,一切就迎刃而解了。

    具体地,因为涉及到取模,我们把操作转为 0-index 的,也就是令所有 a[i]--。

    考虑维护一个森林结构,对每一个 aia_i,我们从 aia_i 的根向 (ai+1)mod  n(a_i+1) \mod n 连一条边,显然在最后一次连边之前,所有点已经全部连通。

    这时的局面可能是这样的:

    考虑那个没有入度的点,设其为 ss,这些边的意义可以认为是,从 ss 开始顺时针枚举,可以在所有点对决。

    显然 ss 是一个合法的起点。

    发现我们不需要真的维护这个环,只需要维护他的连通关系,这样就可以用并查集维护了。

    容易做到 O(Nlog⁡N)O(N \log N)。

    代码

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,m;
    int a[501000],b[501000],c[501000];
    int fa[501000];
    void init(){
        for(int i=0;i<n;i++) fa[i]=i;
    }
    int find(int x){
        if(fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    int s;
    void merge(int i){
        int x=find(i);
        if(find(i)==find((find(i)+1)%n)) s=(find(i)+1)%n;
        else fa[find(i)]=find((find(i)+1)%n);
    }
    vector<int> vec[501000];
    set<int> st;
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>n;
        init();
        for(int i=0;i<n;i++){
            cin>>c[i],c[i]--,merge(c[i]),vec[c[i]].push_back(i);
        }
        for(int i=0;i<n;i++){
            cin>>b[i];
        }
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int i=s,ans=0;
        do{
            for(int j:vec[i]) st.insert(a[j]);
            auto it=st.upper_bound(b[i]);
            if(it==st.end()) st.erase(st.begin());
            else st.erase(it),ans++;
            i=(i+1)%n;
        }while(i!=s);
        cout<<ans<<'\n';
        return 0;
    }
    

    信息

    ID
    941
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    45
    已通过
    4
    上传者