锐评自己：

暴露的问题，优化能力弱，E都想到思路了想偏了用二分实现

dp做的太少了根本无从下手

学习到的思路:

1.前缀异或和

2.优化复杂度，和D对k的优化是后缀最优值，E是变量分量

3.max-min+l-r模型,max min为[l,r]中元素最大最小值

4.搬运贪心思想Σ|preA[i]-preB[i]|

5.dp的INF开大一点防被卡

最近比赛有点多，先从周赛开始总结

A 小苯的时钟显示

由秒输出时分秒,就是/3600,%3600/60,%3600%60

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

void solve() {
    int t;cin >> t;
    int tmp = t % 3600;
    int h = t/3600;
    int s = tmp % 60;
    int m = tmp/60;
    cout << h << ' ' << m << ' ' << s;
}                                                          

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //int T;cin >> T;while(T--) 
    solve();
    return 0;
}

B 小苯的输入法

双端队列，最近做了两个，29苯环蓝桥模拟也有一个

因为每次出现"!"放置相反位置想到deque和bool变量

还有就是要注意队列空的时候"-"的情况

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

void solve() {
    int n;cin >> n;
    string s;cin >> s;
    deque<char> q;
    bool ok = 0;
    for(int i = 0;i <n;i ++){             
        auto t = s[i];
        if(s[i] == '!') ok = !ok;
        else if(s[i] == '-'){
            if(q.empty()) continue;
            if(ok) q.pop_front();
            else q.pop_back();
        }else{
            if(ok) q.push_front(t);
            else q.push_back(t);
        }
    }
    if(q.empty()){
        cout << "Empty\n";
        return;
    }
    while(!q.empty()){
        auto x = q.front();q.pop_front();
        cout << x;
    }
    cout << '\n';
}                                                          

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin >> T;while(T--) 
    solve();
    return 0;
}

C 小苯的观景路线

这题思路比较好想，升序排列后，p[i]-p[i-1]>=i-1，i-1单调增加一个，一个cnt控制即可

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

void solve() {
    int n;cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a.begin(),a.end());
    int cnt = 1,tar = a[0],ans = 1;
    for(int i = 1;i < n;i ++){
        if(a[i] - tar >= cnt){
            cnt ++;
            ans ++;
            tar = a[i];
        }
    }
    cout << ans << '\n';
}                                                          

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin >> T;while(T--) 
    solve();
    return 0;
}

D 小苯的序列涂色

线性dp

前缀知识：前缀异或和

[i,j]中:a[i]^a[i+1]^a[i+2]^......^a[j]=(a[1]^a[2]^......^a[i])^(a[1]^a[2]^......^a[j])

原理就是x^x=0,0^y=y

结合dp的思想，因为暂时没有再去回顾acwing线性dp网课，先大概讲一下实现吧

trick:dp[i]表示将前i个位置全部染成红色的最小代价值

pre[i]记录前缀异或和,a^a=0,0^x=x这种思想

init:dp[i]=pre[i],直接直线走完

考虑覆盖情况:推导状态转移方程

dp[i]的最后一次染色操作为[l,r],r=i,pre[l-1]^pre[r]为代价

设j=l-1,即pre[j]^pre[i]

这次操作覆盖[j+1,i]那么这次操作前，前j个位置也已经被成功覆盖了，

考虑重叠情况，之前可以覆盖到j,j+1,j+2...i-1中任意一个位置

则:dp[i] = min(dp[i],min(dp[k],j<=k<i)+pre[j]^pre[i],0<=j<i)

dp[k]需要考虑优化,O^3 -> O^2

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

void solve() {
    int n;cin >> n;
    vector<int> a(n+1),pre(n+1,0),dp(n+1,INF);
    dp[0] = 0;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        pre[i] = pre[i-1] ^ a[i];
        dp[i] = pre[i];
    }
    
    for(int i = 1;i <= n;i ++){
        int k = dp[i-1];
        for(int j = i - 1;j >= 0;j --){
            k = min(k,dp[j]);
            int t = pre[j] ^ pre[i];
            dp[i] = min(dp[i],k + t);
        }
    }
    
    cout << dp[n] << '\n';
}                                                          

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin >> T;while(T--) 
    solve();
    return 0;
}

E 小苯的序列涂色

做题的时候想到了思路，把(M-m+1)-(r-l+1)拆开来就是M+l-(m+r),

假设一段区间是包含m和M的要最大化M+l-(m+r),M和m固定了，l最大化不能再超过min(idx_M,idx_m)，r最小化不能小于max(idx_M,idx,m)

当时思路就卡在这里了，但是意识到了最大的时候就是M和m做端点的时候，然后二分去找，但是check里面放n^2肯定不行

换个同质化的公式来处理n^2问题

[i,j]中，

如果a[i] > a[j],那么M+l-(m+r)就是a[i] + i - (a[j] + j)

f(x) = a[x] + x

如果a[i] < a[j],那么M+l-(m+r)就是a[j] - j - (a[i] - i)

f(x) = a[x] - x

注意两个都是i < j的情况

所以第一种情况a[j] + j应该要尽可能小,a[i] + i要尽可能大

init:k = a[0] + 0

t = a[i] + i

mx = max(mx,t)

ans = max(ans,mx - t)

第二种情况只能init a[i] - i这和i < j以及a[i] - i 前的符号有关

那么此时只能最小化a[i] - i(t)

mn = min(mn,t)

ans = max(ans,t - mn)

这里对ans的优化其实和D对k的优化是同一个思想，一个是变量分量，一个是后缀最优值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int> a;

void solve(){
    cin >> n;
    a.resize(n);
    for(int i = 0;i < n;i ++) cin >> a[i];
    int ans = 0;
    int mx = a[0];
    for(int i = 1;i < n;i ++){
        int t = a[i] + i;
        mx = max(mx,t);
        ans = max(ans,mx - t);
    }
    int mn = a[0];
    for(int i = 1;i < n;i ++){
        int t = a[i] - i;
        mn = min(mn,a[i]-i);
        ans = max(ans,t-mn);
    }
    cout << ans << '\n';
}                                                          

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin >> T;while(T--) 
    solve();
    return 0;
}

F 小苯的糖果盒

贪心：搬运问题

dp:完全背包

贪心+dp

贪心：搬运问题

两个长度相同总和也相同的数组A B，

通过a[i] ++,a[j] --花费|i - j|的代价将A->B所需的min总代价为Σ|preA[i] - preB[i]|

pre为前缀和

那么这题就是a preA 数组都已知

for从小到大枚举所有可用数,那么其实B数组就被枚举出来了

f[i][j]表示:b数组当前考虑到第i位preB[i] = j的最小代价

初始dp值均为INF（设大一点不容易被卡） 最终再判断一下-1的输出

f[i][j] = min(f[i][j],f[i - 1][j - x] + abs(j-preA[i]));

形象一点就是当前位置i要不要转移满足b数组preB=j

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

void solve() {
    int n;cin >> n;
    vector<int> a(n+5),preA(n+5,0);
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        preA[i] = preA[i - 1] + a[i];
    }
    vector<vector<int>> f(n+5,vector<int> (preA[n] + 5,INF));
    f[0][0] = 0;
    for(int p = 0;p * p <= preA[n];p ++){
        int x = p * p;
        for(int i = 1;i <= n;i ++){
            for(int j = x;j <= preA[n];j ++){
                f[i][j] = min(f[i][j],f[i - 1][j - x] + abs(j - preA[i]));
            }
        }
    }
    if(f[n][preA[n]] > 1e16){
        cout << -1 << '\n';
        return;
    }
    cout << f[n][preA[n]] << '\n';
}                                                          

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin >> T;while(T--) 
    solve();
    return 0;
}