牛客周赛82

头文件

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

template <typename T1, typename T2>
void cmin(T1& x, const T2& y)
{
    x = x < y ? x : y;
}
template <typename T1, typename T2>
void cmax(T1& x, const T2& y)
{
    x = x > y ? x : y;
}
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fixset(x) fixed << setprecision(x)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ALL(x) (x).begin() + 1, (x).end()
constexpr int INF = 1000000000;
constexpr ll LNF = 1000000000000000000LL;

A

B

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

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

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种。而不成立的情况显然只有数组为非递减时。

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())。

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]$ 。

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];
}