C

//二刷这道题，我嘞个1800的贪心
//给你一个01序列，分组后分差要等于k
//很显然可以看出第一个性质01互相消，多1少单位1贡献，多0多1贡献；
//第二个性质藏在题意里面，分组后产生0 1 2 3 4的系数，后者比前者多1，
//对于每条鱼来说，它的价值等于它所在组之前的组数。因此，两组之间的每条 "边界 "都会使边界后的每条鱼的价值增加 1
//怎么贪心这个结算呢；。得分差异=0⋅(sa1−sa2)+1⋅(sa2−sa3)+⋯+(m−1)⋅sa是从第个个分组位置开始，到最后的鱼所涉及的 si 值
//得分差异=这个总和可以重写为 0⋅sa1+(2−1)⋅sa2+(3−2)⋅sa3+⋯+sam
//由于这个分组在全部集合里面是任意取的
//括号里面代表鱼差那么就可以贪心的去拿最佳的几个分割点
//感觉需要三刷
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = '?' + s;
    //cout<<s;
    vector<int> sur(n + 2, 0);  //一定要注意初始化，
    for (int i = n; i >= 1; --i) {
        if (s[i] == '1') {
            sur[i] = sur[i + 1] + 1;//不然这一行会错误
        } else {
            sur[i] = sur[i + 1] - 1;
        }
    }


    vector<int> ans;

    for (int i = n; i >= 2; --i) {
        if (sur[i] > 0) {
            ans.push_back(sur[i]);
        }
    }

    sort(ans.begin(), ans.end());
    reverse(ans.begin(),ans.end());

    int sum = 0;
    int cnt = 0;

    for (auto i:ans) {
        //cout<<i<<endl;
        if (sum < k) {
            sum += i;
            cnt++;
        }
    }

    if (sum >= k) {
        cout << cnt+1<< "\n";
    } else {
        cout << "-1\n"; 
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

//分奇偶数讨论，但是对奇数得多一步判断是否可以转化为偶
//记得用纸
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;

    if(n&1){
    if(n<27){
        cout<<"-1\n";
    }else{
       cout<<"1 3 3 4 4 5 5 6 6 1 2 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1 2 ";
       int c=(n-27)/2;
       for(int i=14;i<14+c;i++){
           cout<<i<<" "<<i<<" ";
       }
        cout<<"\n";

    }

    }else{
        int c=(n)/2;
        for(int i=1;i<=c;i++){
            cout<<i<<" "<<i<<" ";
        }
        cout<<"\n";
    }

}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }



}

D

//本题就是模拟，加前后缀分解，然后加动态规划优化
//任意一个都可以跳到pre_max,如果pre_max>sur_min。那么不要二分去模拟，直接ans【i】=ans【i+1】从后更新
//集合分析，ans【i】=ans【i+1】，ans要么只能跳zuobian，要么跳左后向右。前一个也是这样，所以就算不重不漏
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; 
    cin >> t; 
    while (t--) {
        int n;
        cin >> n; 
        vector<int> ar(n), pref(n), suff(n), ans(n);

        for (int i = 0; i < n; i++) {
            cin >> ar[i];
        }

        pref[0] = ar[0];
        for (int i = 1; i < n; i++) {
            pref[i] = max(pref[i-1], ar[i]); 
        }

        suff[n-1] = ar[n-1]; 
        for (int i = n - 2; i >= 0; i--) {
            suff[i] = min(suff[i+1], ar[i]); 
        }

        ans[n-1] = pref[n-1];
        //运用了动态规划的思想
        for (int i = n - 2; i >= 0; i--) {
            if (pref[i] > suff[i+1]) {
                ans[i] = ans[i+1];  
            } else {
                ans[i] = pref[i];
            }
        }

        for (int i = 0; i < n; i++) {
            cout << ans[i] << " "; 
        }
        cout << "\n";
    }
    return 0;
}

D

//两个关键点1，区间字段和是否重复出现，可以一维扫描加线性dp
//关键点2，dpi的设计
//1继承dpi-1
//来自新组合dpl+1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    ll n;
    cin >> n;
    ll arr[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    ll dp[n+1]; // dp[i] 表示前 i 个元素能找到的最大美丽子段数
    ll pre[n+1]; // pre[i] 是从 arr[1] 到 arr[i] 的前缀和
    map<ll, ll> ma; // ma 存储前缀和最后一次出现的位置
    dp[0] = 0; // 初始时，dp[0] 为 0（没有子段）
    pre[0] = 0; // pre[0] 为 0，表示空数组的前缀和
    ma[0] = 0; // 初始情况下，前缀和为 0 的位置是 0
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + arr[i];
        dp[i] = dp[i - 1]; 
        if (ma.find(pre[i]) != ma.end()) { 
            ll r = ma[pre[i]]; 
            dp[i] = max(dp[i], dp[r] + 1); 
        }
        ma[pre[i]] = i;
    }

    cout << dp[n] << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}