ZR 集训 Day29 – 杂题选讲

ooliver 发布于 9 小时前 75 次阅读 OI

AI 摘要

从“暴力枚举”到“单调栈”，看似杂题，实则暗藏一个共同内核：用巧妙的观察砍掉冗余计算。四种不同套路，却都指向同一目标——让复杂度贴近本质。读题五分钟，代码一页纸，但其中的思维转折，才是真正值得玩味的地方。

题单：

CF1637E Best Pair

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

代码：

C++
#include<bits/stdc++.h>
using namespace std;

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

void solve(){
    int idx=0;
    ll ans=-1;
    map<int,int> mp,mp1;
    map<pair<int,int>,int> tag;
    int n,m;
    cin>>n>>m;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        mp1[x]++;
    }
    for(int i=1,x,y;i<=m;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;i<=idx;i++) sort(a[i].begin(),a[i].end());
    for(int i=1;i<=idx;i++){
        for(int j=i;j<=idx;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();
    }
    cout<<ans<<"\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>=b$。

对于 $g_i>=b$，它能产生贡献的情况应该是这个 $g_i$ 排在 $x$ 个 $g_i$ 的最后 $x-a$ 个，所以概率为 $\frac{x-a}{x}$。

对于 $g_i<b$，考虑插空，共 $x+1$ 个空，它能产生贡献的情况应该是插在了最后的 $x+1-a$ 个空，所以概率为 $\frac{x+1-a}{x+1}$。

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

代码：

C++
#include<bits/stdc++.h>
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<=n;i++) cin>>d[i];
    sort(d+1,d+1+n);
    for(int i=1;i<=n;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(x<a){
            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<bits/stdc++.h>
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<ull,int> mp;

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) base[i]=rnd()+1;
    for(int i=1;i<=n;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;i<=n;i++){
        cnt[a[i]]++;
        while(cnt[a[i]]>3){
            l++;
            cnt[a[l]]--,mp[ha[l-1]]--;
        }
        ans+=mp[ha[i]];
        mp[ha[i]]++;
    }
    cout<<ans;
    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<bits/stdc++.h>
using namespace std;

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

void solve(){
    int top=0;
    cin>>n;
    for(int i=1;i<=n;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};
        cout<<st[1].first<<" ";
    }
    cout<<"\n";
}

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