牛客周赛82

最简单的一集，第一次ak周赛。

本来没打算打的，但是吃饭的时候看到群里有人吐槽太简单了，有人说F题太简单了。。然后我回来也四十多分钟ak了。

A

B

C

肯定是按大小顺序去排队的。但是如果大小相同肯定不符合。所以排序然后按大小输出。

C++

void solve()
{
    int n;
    cin>>n;
    vector<pii>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].fi;
        a[i].se=i+1;
    }
    sort(all(a));
    for(int i=1;i<n;i++){
        if(a[i].fi==a[i-1].fi){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
    for(int i=0;i<n;i++)
        cout<<a[i].se<<" \n"[i+1==n];
}

D

给的数组是一个递减的数组，只有新的数字出现，这个数字才是确定的。其他的位置可以填满足条件的所有数字。

Text Only

7
6 2 2 1 1 1 1

比如看这个样例，显然我们可以确定 \(a_1=6\) ， \(a_2=2\) ， \(a_4=1\) ，其他地方我们不知道他能填多少。但是我们可以知道可以取多少个数，比如 \(a_3\) 可以是 \([3,4,5,7]\) ，那么这里就有4种情况。所以答案会乘4，再到后面的取值不确定的地方，结果的可能性就会少1。

所以我们可以总结一下，刚开始可以取值的数字数量为 \(n-a_1\) ，然后每次遇到一个新的数字，取值就会增加 \(a_i-a_{i-1}-1\) 种，然后如果相等的话，就会-1种。而不成立的情况显然只有数组为非递减时。

C++

constexpr int mod = 998244353;

void solve()
{
    int n;
    cin>>n;
    vi a(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int have=n-a[1];
    ll res=1;
    for(int i=2;i<=n;i++){
        if(a[i]==a[i-1]){
            res=res*have%mod;
            have--;
        }else if(a[i]<a[i-1]){
            have+=a[i-1]-a[i]-1;
        }else{
            cout<<"0\n";
            return;
        }
    }
    cout<<res<<'\n';
}

E

这个题就是说数组 \(a\) 和 \(b\) 都要取 \(m\) 个数字，且 \(a\) 取的 \(m\) 个数字，下标都比 \(b\) 选出来的数字要小。要使得他们的和最小。

所以我们可以算出前 \(i\) 个数字里面，\(a\) 取 \(m\) 个数字的最小值。还有 \(b\) 从 \([i,n]\) 之间选 \(m\) 个数字的最小值。

可以用优先队列或 multiset 来维护。当数字多于m个时删除最大的数字。

注意multiset删除val时会删除所有等于这个值的元素，所以可以用st.erase(st.lower_bound(val))或st.erase(st.find(val))或st.erase(prev(st.end())。

C++

void solve()
{
    int n,m;
    cin>>n>>m;
    vi a(n+1),b(n+1);
    vl s1(n+1),s2(n+1);
    multiset<int>st1,st2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    ll sum=0;
    for(int i=1;i<=n;i++){
        st1.insert(a[i]);
        sum+=a[i];
        while(sz(st1)>m){
            sum-=*st1.rbegin();
            st1.erase(prev(st1.end()));
        }
        s1[i]=sum;
    }
    sum=0;
    for(int i=n;i>=1;i--){
        st2.insert(b[i]);
        sum+=b[i];
        while(sz(st2)>m){
            sum-=*st2.rbegin();
            st2.erase(prev(st2.end()));
        }
        s2[i]=sum;
    }
    ll ans=LNF;
    for(int i=m;i+m<=n;i++){
        cmin(ans,s1[i]+s2[i+1]);
    }
    cout<<ans<<'\n';
}

F

意思就是说每一个子数组，必须有一个数字在这个子数组中只出现一次，且不同的数字最少。

我们先从小的情况开始考虑，

\(n\) = 3 时，很显然我们可以构造为 \([1,2,1]\) 或 \([2,1,2]\) 。

那我们继续 \(n=4\) 时，必须得多用一个 \(3\) 了。

然后这时候可以发现，在 \([1,2,1,3]\) 后面加一个 \([1,2,1]\) ，这仍然是一个合法的数组。

所以我们每次都会增加一个新的数字，然后把之前的数组拼在后面。

比如如果长度大于 7 ，那么肯定要加一个 4，后面又能在拼上 \([1,2,1,3,1,2,1]\) 。

C++

void solve()
{
    int n;
    cin>>n;
    vi ans;
    int x=1;
    ans.push_back(1);
    while(sz(ans)<n){
        vi tmp=ans;
        ++x;
        ans.push_back(x);
        for(auto y:tmp)
            ans.push_back(y);
    }
    cout<<x<<'\n';
    for(int i=0;i<n;i++)
        cout<<ans[i]<<" \n"[i==n-1];
}

感觉这题可以当div2B(没有尬黑

之前的很多周赛F还挺难的。这场应该是非常简单的一场。我也是看到大家说