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;
    }
    
    • 1
      @ 2026-10-24 11:38:52

      急了,难道我真是贪心低手..

      对于 Ci=1C_i = 1 的数据,我们可以通过经典结论做出。对于每一个 WiW_i,找比 WiW_i 大的最小的 BiB_i。

      然后,剩下的部分,直接做就是对的。因为我们一定可以找到一个点 xx,使得从 xx 开始,按顺时针考虑每一个 BiB_i 不会有剩余,此时再使用上面的结论就是正确的。因为不会有比 xx 靠前的 WiW_i 会影响当前的 BiB_i。

      考虑如何找到点 xx。我的做法是把每个位置看成 -1,因为会消耗一匹马。记 cnti=∑1≤j≤n[Cj=i]cnt_i = \sum\limits_{1 \le j \le n} [C_j=i] ,一个位置的权值就是 cnti−1cnt_i -1。

      然后从 1 到 nn 扫一遍整个序列,找前缀和最小的点 xx,x+1x+1一定是一个合法起点。

      #include<bits/stdc++.h>
      using namespace std;
      #define int long long
      #define psb push_back
      const int N=5e5+1000,inf=1e15;
      int n,c[N],a[N],b[N<<1];
      vector<int>vec[N];
      set<int>st;
      signed main(){
      	ios::sync_with_stdio(0);
      	cin.tie(0);
      	cin>>n;
      	for(int i=1;i<=n;i++){
      		cin>>c[i];
      		vec[c[i]].psb(i);
      	}
      	for(int i=1;i<=n;i++) cin>>b[i],b[i+n]=b[i];
      	for(int i=1;i<=n;i++) cin>>a[i];
      	int minn=n,mini=0,sum=0;
      	for(int i=1;i<=n;i++){
      		sum=sum-1+vec[i].size();
      		if(sum<minn){
      			minn=sum;mini=i;
      		}
      	}
      	int ans=0;
      	for(int i=mini+1;i<=mini+n;i++){
      		for(int x:vec[(i%n==0?n:i%n)]) st.insert(a[x]);
      		auto it=st.lower_bound(b[i]);
      		if(it==st.end()){
      			st.erase(st.lower_bound(-1));
      		}else{
      			ans++;
      			st.erase(it);
      		}
      	}cout<<ans;
      	return 0;
      } 
      
      • 1

      信息

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