A - Farmer John’s Challenge

构造

大概思路

可以证明， $k$ 要么为 $1$，要么为 $n$，不然无解。

参考代码

void solve(){
    CIN(n);CIN(k);
    if(k!=1&&k!=n){cout<<-1<<ET;return;}
    if(k==1){
        cout<<1<<" ";
        n--;
        while(n--)cout<<2<<" ";
    }else{
        while(n--)cout<<1<<" ";
    }
    cout<<ET;
}

B - Bessie and MEX

模拟

大概思路

正着模拟，如果当前收到的值大于等于 $1$，说明mex在这里发生了更新，让 $mex$ 自增 $1$ 后更新 $mex$ 的值，然后记录当前出现的数，输出当前出现的数即可。

参考代码

void solve(){
    CIN(n);
    vector<bool> a(n+2,0);
    int mex=0;
    FOR(i,1,n){
        CIN(tmp);
        if(tmp>=1)mex++;
        while(a[mex]&&mex<n)mex++;
        a[mex-tmp]=1;
        //cout<<mex<<"[";
        cout<<mex-tmp<<" ";
    }
    cout<<ET;
}

C1 - Bessie’s Birthday Cake (Easy Version)

大概思路

$y$ 为 $0$，也就是说不能自己加点，考虑已经围成的多边形，内部最多可产生 $x-2$ 个三角形，然后再统计一下外部不小心构造的三角形有几个，加上就行。

参考代码

void solve(){
    CIN(n);CIN(x);CIN(y);
    vector<int> a(x);
    FOR(i,0,x-1)cin>>a[i];
    sort(a.begin(),a.end());
    ll cnt=0;
    FOR(i,1,x-1){
        if(a[i]-a[i-1]==2)cnt++;
    }
    if(a[0]+n-a[x-1]==2)cnt++;
    cout<<cnt+x-2<<ET;
}

C2 - Bessie’s Birthday Cake (Hard Version)

排序

大概思路

和上题一样，多一步收集相邻两点间距大于2的距离，然后按照 $(1.0 * a / (a»1))>(1.0 * b/(b»1))$ 的方式排序一遍（即每加一点，能获得的三角形数量的期望（一般来说，每加一个点能获得两个三角形，但是奇数情况在最后能获得三个，比如4和5同样是加2个点，一个能获得4个三角形，另一个却能获得5个三角形，贪心时肯定优先选5；然后对于5和999，它们在最后都能获得3个三角形，但显然我们选5的话，到达“产生3个三角形”的状态所消耗的y值显然更少，所以按这里我们按 $1.0*a/(a»1)$ （贡献度）的值排序的话，可以达到既避免了奇偶讨论，又能准确识别出最小的奇数的目的（奇数越小，每加一个点获得的三角形数量的期望更大）））。跑一边贪心收集答案即可。

参考代码

void solve(){
    CIN(n);CIN(x);CIN(y);
    vector<int> a(x);
    FOR(i,0,x-1)cin>>a[i];
    sort(a.begin(),a.end());
    ll cnt=0;
    vector<int> can;
    FOR(i,1,x-1){
        if(a[i]-a[i-1]==2)cnt++;
        if(a[i]-a[i-1]>2)can.push_back(a[i]-a[i-1]-1);
    }
    if(a[0]+n-a[x-1]==2)cnt++;
    if(a[0]+n-a[x-1]>2)can.push_back(a[0]+n-a[x-1]-1);
    sort(can.begin(),can.end(),[&](int a,int b){
        return (1.0*a/(a>>1))>(1.0*b/(b>>1));
    });
    for(auto &res:can){
        //cout<<res<<"]";
        if(y>=res/2){
            cnt+=res;
            y-=res/2;
        }else{
            cnt+=y*2;
            break;
        }
    }
    cout<<cnt+x-2<<ET;
}

D

优先队列优化DP

大概思路

直接按列优先队列DP，设 $dp[i]$ 为前 $i$ 列的前 $k$ 大数组，然后按列进行状态转移即可。每次转移时按列 $j$ 收集 $dp[j-2]$ 的最大项，加到当前 $dp[i]$，收集完一列的值后截断 $dp[i]$ 的前 $k$ 大，进入下一列的 $dp$ 即可。关于状态的转移，可以自己画图理解：

参考代码

struct P{
    int v,j_,x;//保存的值，所属列下标，第几大的数
    bool operator<(const P b)const{
        return v<b.v;
    }
};

void solve(){
    CIN(n);CIN(k);
    vector<vector<int>> dp(n+1),a(n+1,vector<int>(n+1,0));//小心爆空间，题目的范围不会超过int型
    FOR(i,1,n)FOR(j,i,n)cin>>a[i][j];
    dp[0].push_back(0);
    //dp状态：dp[j][i]表示前j列的第i大的答案（实际上是dp[i]，表示前i列的前k大数组）
    FOR(j,1,n){//按列dp
        priority_queue<P> q;
        FOR(j_,1,j){//把这一列的最大值收集完，整理到优先队列里面暂存
        //这里可能要点理解，我放个图出来
            q.push(P(a[j_][j]+(j_-2==-1?0:dp[j_-2][0]),j_-2,0));//收集前j_-2列的答案，可以证明，任意大于j_-2列的答案均无法递推到第j_行
        }
        dp[j]=dp[j-1];//复制上一列的结果
        FOR(u,1,k){//最多收集k个就行
            if(q.empty())break;//或者q被倒空了，就退出
            auto [v,j_,x]=q.top();q.pop();
            dp[j].push_back(v);
            if(j_>=0&&x+1<dp[j_].size())q.push(P(v-dp[j_][x]+dp[j_][x+1],j_,x+1));//尽可能把q里的东西倒光，如果第x个倒出来，那么第x+1个就可以加进去继续倒
        }
        sort(dp[j].begin(),dp[j].end(),greater<int>());//排序，掐断dp[i]，限制为k大小的数组
        if(dp[j].size()>k)dp[j].erase(dp[j].begin()+k,dp[j].end());
    }
    for(auto& i:dp[n])cout<<i<<" ";
    cout<<ET;
}

pre附录

翻别人代码看到的奇怪写法。

vector<int> a(x);
for(auto& i:a)cin>>i;

附录

这里贴上用到的头部和main函数(有更新，for循环没事别开long long，常数大)：

#include<iostream>
#include<vector>
#include<cmath>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(a);i>=(b);i--)
//双向for循环
#define rep(i,a,b) for(int i=(a);i!=(b)+2*(a<b)-1;i+=2*(a<b)-1)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define SCIN(a) string a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
//没有C++20就不能用ranges了
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
//string ANS[2]={"No\n","Yes\n"};
int M=1e9+7;
inline ll MO(ll x){return (x%M+M)%M;}

void solve(){

}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    CIN(t);while(t--)
    solve();
    return 0;
}