ZR 集训 Day29 - 杂题选讲

2026年8月14日 ooliver OI

题单：

CF1637E Best Pair

考虑不同的 $c n t$ 最多只有 $\sqrt{n}$ 种，所以我们直接记录每个 $c n t$ 对应的 $a_{i}$ ，对其排序，然后暴力枚举两个 $c n t$ 对应的 $a_{i}$ ，从大到小看是否满足条件，最多 $m$ 次不满足条件。

代码：

C++

#include
using namespace std;

typedef long long ll;
const int N=3e5+5;
int s[3000];
vector a[3000];

void solve(){
    int idx=0;
    ll ans=-1;
    map mp,mp1;
    map,int> tag;
    int n,m;
    cin>>n>>m;
    for(int i=1,x;i>x;
        mp1[x]++;
    }
    for(int i=1,x,y;i>x>>y;
        if(x>y) swap(x,y);
        tag[{x,y}]=1;
    }
    for(auto[x,y]:mp1){
        if(mp[y]) a[mp[y]].push_back(x);
        else mp[y]=++idx,s[idx]=y,a[idx].push_back(x);
    }
    for(int i=1;i=0){
                int r=a[j].size()-1;
                int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]);
                if(xx!=yy&&!tag[{xx,yy}]){
                    ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r]));
                    break;
                }
                else{
                    while(r>0){
                        r--;
                        int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]);
                        if(xx!=yy&&!tag[{xx,yy}]){
                            ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r]));
                            break;
                        }
                    }
                }
                l--;
            } 
        }
        a[i].clear();
    }
    cout>t;
    while(t--) solve();
    return 0;
}

`#include
using namespace std;

typedef long long ll;
const int N=3e5+5;
int s[3000];
vectorint> a[3000];

void solve(){
    int idx=0;
    ll ans=-1;
    mapint,int> mp,mp1;
    mappairint,int>,int> tag;
    int n,m;
    cin>>n>>m;
    for(int i=1,x;in;i++){
        cin>>x;
        mp1[x]++;
    }
    for(int i=1,x,y;im;i++){
        cin>>x>>y;
        if(x>y) swap(x,y);
        tag[{x,y}]=1;
    }
    for(auto[x,y]:mp1){
        if(mp[y]) a[mp[y]].push_back(x);
        else mp[y]=++idx,s[idx]=y,a[idx].push_back(x);
    }
    for(int i=1;iidx;i++) sort(a[i].begin(),a[i].end());
    for(int i=1;iidx;i++){
        for(int j=i;jidx;j++){
            int l=a[i].size()-1;
            while(l>=0){
                int r=a[j].size()-1;
                int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]);
                if(xx!=yy&&!tag[{xx,yy}]){
                    ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r]));
                    break;
                }
                else{
                    while(r>0){
                        r--;
                        int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]);
                        if(xx!=yy&&!tag[{xx,yy}]){
                            ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r]));
                            break;
                        }
                    }
                }
                l--;
            } 
        }
        a[i].clear();
    }
    coutans"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}`

CF1418E Expected Damage

对于一个询问 $a, b$ ，分两种情况计算贡献。

假设一共有 $x$ 个 $g_{i} [PARSE ERROR: Ampersand] g t; = b$ 。

对于 $g_{i} [PARSE ERROR: Ampersand] g t; = b$ ，它能产生贡献的情况应该是这个 $g_{i}$ 排在 $x$ 个 $g_{i}$ 的最后 $x - a$ 个，所以概率为 $\frac{x - a}{x}$ 。

对于 $g_i不难发现，对于求期望，我们对 $g$ 排序并求前缀和即可。

代码：

C++

#include
using namespace std;

typedef long long ll;
const int mod=998244353;
const int N=2e5+5;
int n,m;
int d[N],sum[N];

ll qpow(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        y>>=1,(x*=x)%=mod;
    }
    return res;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i>d[i];
    sort(d+1,d+1+n);
    for(int i=1;i>a>>b;
        int k=lower_bound(d+1,d+1+n,b)-d,x=n-k+1;
        if(x

`#include
using namespace std;

typedef long long ll;
const int mod=998244353;
const int N=2e5+5;
int n,m;
int d[N],sum[N];

ll qpow(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        y>>=1,(x*=x)%=mod;
    }
    return res;
}

signed main(){
    cin>>n>>m;
    for(int i=1;in;i++) cin>>d[i];
    sort(d+1,d+1+n);
    for(int i=1;in;i++) sum[i]=(sum[i-1]+d[i])%mod;
    while(m--){
        int a,b,ans=0;
        cin>>a>>b;
        int k=lower_bound(d+1,d+1+n,b)-d,x=n-k+1;
        if(xa){
            cout"0\n";
            continue;
        }
        ans=(((qpow(x,mod-2)*(x-a))%mod)*(sum[n]-sum[k-1]))%mod;
        ans=(ans+(((qpow(x+1,mod-2)*(x+1-a))%mod)*(sum[k-1]))%mod)%mod;
        cout(ans%mod+mod)%mod"\n";
    }
    return 0;
}`

CF1418G Three Occurrences

把每个值对应出现次数模三的这个序列进行哈希，枚举右端点，并维护一个左端点，使得区间内所有数出现次数不超过 $3$ ，再用一个 map 记录有多少符合要求的前缀哈希即可。

代码：

C++

#include
using namespace std;

typedef unsigned long long ull;
const int N=5e5+5;
const int mod=1e9+7;
mt19937_64 rnd(random_device{}());
int n;
ull ans;
int a[N],cnt[N];
ull base[N],ha[N];
map mp;

signed main(){
    cin>>n;
    for(int i=1;i>a[i];
        (cnt[a[i]]+=1)%=3;
        if(cnt[a[i]]==0) ha[i]=ha[i-1]-2*base[a[i]];
        else ha[i]=ha[i-1]+base[a[i]];
    }
    memset(cnt,0,sizeof cnt);
    int l=0;
    mp[0]=1;
    for(int i=1;i3){
            l++;
            cnt[a[l]]--,mp[ha[l-1]]--;
        }
        ans+=mp[ha[i]];
        mp[ha[i]]++;
    }
    cout

`#include
using namespace std;

typedef unsigned long long ull;
const int N=5e5+5;
const int mod=1e9+7;
mt19937_64 rnd(random_device{}());
int n;
ull ans;
int a[N],cnt[N];
ull base[N],ha[N];
mapull,int> mp;

signed main(){
    cin>>n;
    for(int i=1;in;i++) base[i]=rnd()+1;
    for(int i=1;in;i++){
        cin>>a[i];
        (cnt[a[i]]+=1)%=3;
        if(cnt[a[i]]==0) ha[i]=ha[i-1]-2*base[a[i]];
        else ha[i]=ha[i-1]+base[a[i]];
    }
    memset(cnt,0,sizeof cnt);
    int l=0;
    mp[0]=1;
    for(int i=1;in;i++){
        cnt[a[i]]++;
        while(cnt[a[i]]>3){
            l++;
            cnt[a[l]]--,mp[ha[l-1]]--;
        }
        ans+=mp[ha[i]];
        mp[ha[i]]++;
    }
    coutans;
    return 0;
}`

CF2002E Cosmic Rays

不难发现，一般情况下，答案就是 $\max {b_{i}}$ ，但是对于一个连续段： $A, B, C$ ，若 $A, C$ 颜色相同，且 $A, C$ 的长度都大于 $B$ ，那此时 $A, C$ 可以合并，得到的长度为 $b_{A} + b_{C} - b_{B}$ 。

所以我们用单调栈维护这个操作即可，答案即栈底。

代码：

C++

#include
using namespace std;

#define int long long
const int N=3e5+5;
int T,n;
pair st[N];

void solve(){
    int top=0;
    cin>>n;
    for(int i=1;i>a>>b;
        b++;
        while(top>0&&a>st[top].first){
            if(st[top-1].second==b){
                a+=(st[top-1].first-st[top].first);
                top--;
            }
            top--;
        }
        st[++top]={a,b};
        cout>T;
    while(T--) solve();
    return 0;
}

`#include
using namespace std;

#define int long long
const int N=3e5+5;
int T,n;
pairint,int> st[N];

void solve(){
    int top=0;
    cin>>n;
    for(int i=1;in;i++){
        int a,b;
        cin>>a>>b;
        b++;
        while(top>0&&a>st[top].first){
            if(st[top-1].second==b){
                a+=(st[top-1].first-st[top].first);
                top--;
            }
            top--;
        }
        st[++top]={a,b};
        coutst[1].first" ";
    }
    cout"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}`