题解 | #牛客周赛 Round 123#

A.小红玩牌

按照题意比较即可。

void solve() {
    int n1,n2;
    char c1,c2;
    cin >> n1 >> c1 >> n2 >> c2;
    if(n1!=n2) cout << (n1>n2?"Yes":"No") << endl;
    else cout << (c1<c2?"Yes":"No") << endl;
}

B.小红作弊

我们计算 $ans=\sum_{i=1}^{13}{|a_i+b_i-4|}$ ，因为这样会重复，所以将 $ans/2$ 即为答案。

C.小红出对

因为相同的牌只能出现一次，所以我们对牌进行去重。然后得到的牌中，对于数字为 $x$ 的牌，那么最多有4张牌，进行匹配即可。

D.小红打牌

由飞机的定义，我们可以发现递增枚举 $a$ ，肯定能够得到不同的飞机，这个也很容易证明。

假设两次枚举为：

a a a a+1 a+1 a+1 b1 b1 c1 c1
a+1 a+1 a+1 a+2 a+2 a+2 b2 b2 c2 c2

那么要这两次得到集合相等，必然有：

a a a b1 b1 c1 c1=a+2 a+2 a+2 b2 b2 c2 c2

对于前面，因为需要三个 $a+2$ ，所以必然有 $b1=a+2$ ，但是这才两个，那么 $c1=a+2$ ，那么就出现了4个 $a+2$ ，同理后面出现4个 $a$ ，最后变为：

a a a a+2 a+2 a+2 a+2
a a a a a+2 a+2 a+2

二者不可能相等，得证。~~其实这也是很显然的了。~~

接下来考虑枚举 $a=x$ 时， $b,c$ 的选择。 $b$ 和 $c$ 不同时，我们从 $cnt[i]\geq 2$ 中的个数中选择两个，贡献为 $tot2*(tot2-1)/2$ ； $b=c$ 时，我们从 $cnt[i]\geq 4$ 的个数中选择一个，贡献为 $tot4$ 。

枚举 $a$ 时，我们动态维护 $tot2,tot4$ 。

void solve() {
    int n;
    cin >> n;
    int mx=0;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        mx=max(mx,a[i]);
    }
    if(n<10){
        cout << 0 << endl;
        return;
    }
    vector<int> cnt(mx+1);
    for(int i=1;i<=n;i++){
        cnt[a[i]]++;
    }
    int tot2=0,tot4=0;
    for(int i=1;i<=mx;i++){
        tot2+=(cnt[i]>=2);
        tot4+=(cnt[i]>=4);
    }
    int ans=0;
    auto update=[&](int x,int z){
        tot2-=(cnt[x]>=2);
        tot4-=(cnt[x]>=4);
        cnt[x]+=z;
        tot2+=(cnt[x]>=2);
        tot4+=(cnt[x]>=4);
    };
    for(int i=1;i<mx;i++){
        if(cnt[i]<3||cnt[i+1]<3) continue;
        update(i,-3);
        update(i+1,-3);
        ans=(ans+(tot2*(tot2-1)/2+tot4))%mod;
        update(i,3);
        update(i+1,3);
    }
    cout << ans << endl;
}

E和F

简单版本是每个数都不相同，这时候加入一张新的牌 $x$ 时：

如果 $cnt[x-1]>0\&\& cnt[x+1]>0$ ，那么我们加入 $x$ 时，可以使得 $ans--$ ；
如果 $cnt[x-1]>0||cnt[x+1]>0$ ，那么 $ans$ 不变；
否则 $ans++$ ；

所以我们维护一个 $cnt$ 数组， $\delta=1-(cnt[x-1]>0)-(cnt[x+1]>0)$ 。

这个 $E$ 题主播想到了， $F$ 没想出来。

其实 $F$ 是在 $E$ 上进行了拓展，只需要将结论拓展为 $\delta=1-(cnt[x-1]>cnt[x])-(cnt[x+1]>cnt[x])$ ，仔细想一下也可以知道。

G.小红出千

最后一定是一个长度为 $n$ 的连续区间，所以我们枚举 $[l,l+n-1]$ ，我们找到一个区间包含最多的不同点个数 $mx$ ， $n-mx$ 即为修改点个数。

我们枚举的区间一定是经过原来的点会发生改变，所以我们只需要枚举每一个 $a_i$ 结尾能够覆盖的最多不同点个数，这个可以通过二分来实现。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1),v;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int m=v.size();
    //找到以那个元素结尾
    int r=0,mx=0;
    for(int i=1;i<=n;i++){
        auto it2=upper_bound(v.begin(),v.end(),a[i]);
        auto it1=lower_bound(v.begin(),v.end(),a[i]-n+1);
        int cnt=it2-it1;
        if(cnt>mx){
            mx=cnt;
            r=a[i];
        }
    }
    cout << n-mx << endl;
    int l=r-n+1;
    map<int,int> ok;
    for(int i=l;i<=r;i++) ok[i]=1;
    for(int i=1;i<=n;i++){
        if(a[i]>=l&&a[i]<=r) ok[a[i]]=0;//ok[a[i]]=1表示还需要
    }
    vector<int> t;
    for(auto[v,c]:ok){
        if(c==1) t.push_back(v);
    }
    int idx=0;
    vector<pii> b;
    for(int i=1;i<=n;i++) b.push_back({a[i],i});
    sort(b.begin(),b.end());
    map<int,int> vis;
    int tot=r;
    for(int i=0;i<n;i++){
        int v=b[i].second;
        if(a[v]>=l&&a[v]<=r){
            if(!vis[a[v]]){
                vis[a[v]]=1;
            }else{
                int val=t[idx]<=0?++tot:t[idx];
                cout << v << " " << val << endl;
                idx++;
            }
        }else{
            int val=t[idx]<=0?++tot:t[idx];
            cout << v << " " << val << endl;
            idx++;
        }
    }
}