Znzryb's Blog

START199——XOR Game

Posted on 2025-08-18 Edited on 2026-02-18

思路讲解

不难发现，题目中的操作，对题目中总值的影响是

$Sum’=Sum\oplus A_i \oplus A_i \oplus A_j = Sum\oplus A_j$

那么如果把两次操作全部选出来。

$Sum‘=Sum\oplus A_{j1} \oplus A_{j2}$ ，当然， $i_1≠j_2$ ，

$i_1=j_2$ ，那么就是 $Sum’=Sum\oplus A_{j1} \oplus A_{i1} \oplus A_{j1}=Sum\oplus A_{i1}$

那么，这种需要用到01trie树。

// j1,j2
ll ans=0;
FOR(j1,1,N){
    ll a=sum^A[j1];
    ll mne=tr.argmin_xor(a),mn=tr.min_xor(a);
    bool ise=tr.erase(mne);
    //  那么 bob 有两种选择，一种是避开我们删除的mne，另一种是就选我们删除的mne
    ll lans=min<ll>(tr.min_xor(a),mne^sum);
    // 那么删除 mne 可能导致负面影响，那么我们不删除mne的结果是什么那？就是bob选择mne呗
    lans=max(lans,mn);
    ans=max<ll>(ans,lans);
    if(ise) tr.insert(mne);
}
// tr.erase(sum);
// 就是sum^A[i1] 也是一种单独的，虽然上面是又包含，但是是取Max的
ans=min<ll>(ans,tr.max_xor(sum));

AC代码

https://www.codechef.com/viewsolution/1183578991

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
// https://threadsiiithyderabad.quora.com/Tutorial-on-Trie-and-example-problems
// AC https://judge.yosupo.jp/submission/308823 test min_xor erase insert 有0
// AC https://codeforces.com/contest/706/submission/334623853 test arg_max max 
// AC https://www.codechef.com/viewsolution/1183578991 综合运用 有0 
struct XORTrie {
    int B; // 最高位（含）
    struct Node {
        int nxt[2];
        int cnt; // 经过该节点的数的个数（叶子 = 出现次数）
        Node() { nxt[0] = nxt[1] = -1; cnt = 0; }
    };
    vector<Node> tr;
    explicit XORTrie(int max_bit = 63) : B(max_bit) {
        tr.reserve(1 << 20);
        tr.emplace_back(); // root
    }
    void clear() { tr.clear(); tr.emplace_back(); }
    inline void insert(unsigned long long x) {
        int u = 0;
        for (int b = B; b >= 0; --b) {
            int bit = int((x >> b) & 1ull);
            if (tr[u].nxt[bit] == -1) {
                tr[u].nxt[bit] = (int)tr.size();
                tr.emplace_back();
            }
            u = tr[u].nxt[bit];
            ++tr[u].cnt;
        }
    }
    inline int count(unsigned long long x) const {
        int u = 0;
        for (int b = B; b >= 0; --b) {
            int bit = int((x >> b) & 1ull);
            int v = tr[u].nxt[bit];
            if (v == -1) return 0;
            u = v;
        }
        return tr[u].cnt;
    }
    inline bool erase(unsigned long long x) {
        if (tr.size() == 1) return false;
        static int pathBit[70];
        int u = 0, depth = 0;
        for (int b = B; b >= 0; --b) {
            int bit = int((x >> b) & 1ull);
            int v = tr[u].nxt[bit];
            if (v == -1 || tr[v].cnt == 0) return false;
            pathBit[depth++] = bit;
            u = v;
        }
        if (tr[u].cnt == 0) return false;
        u = 0;
        for (int i = 0; i < depth; ++i) {
            int bit = pathBit[i];
            int v = tr[u].nxt[bit];
            --tr[v].cnt;
            if (tr[v].cnt == 0) tr[u].nxt[bit] = -1; // 懒回收
            u = v;
        }
        return true;
    }
    inline unsigned long long max_xor(unsigned long long x) const {
        if (tr.size() == 1) return 0ull;
        int u = 0;
        unsigned long long ans = 0;
        for (int b = B; b >= 0; --b) {
            int bit = int((x >> b) & 1ull);
            int prefer = tr[u].nxt[bit ^ 1];
            int same   = tr[u].nxt[bit];
            if (prefer != -1 && tr[prefer].cnt > 0) {
                u = prefer;
                ans |= (1ull << b);
            } else {
                u = same; // 至少有一条有效路
            }
        }
        return ans;
    }
    inline unsigned long long min_xor(unsigned long long x) const {
        if (tr.size() == 1) return 0ull; // empty
        int u = 0;
        unsigned long long ans = 0;
        for (int b = B; b >= 0; --b) {
            int bit = int((x >> b) & 1ull);
            int same  = tr[u].nxt[bit];
            int other = tr[u].nxt[bit ^ 1];
            if (same != -1 && tr[same].cnt > 0) {
                u = same;                 
            } else {
                u = other;                
                ans |= (1ull << b);
            }
        }
        return ans;
    }
    inline unsigned long long argmax_xor(unsigned long long y) const {
        if (tr.size() == 1) return 0ull;
        int u = 0;
        unsigned long long chosen = 0;
        for (int b = B; b >= 0; --b) {
            int bit = int((y >> b) & 1ull);
            int prefer = tr[u].nxt[bit ^ 1];
            int same   = tr[u].nxt[bit];
            if (prefer != -1 && tr[prefer].cnt > 0) {
                u = prefer;
                chosen |= (unsigned long long)(bit ^ 1) << b;
            } else {
                u = same;
                chosen |= (unsigned long long)bit << b;
            }
        }
        return chosen;
    }
    inline unsigned long long argmin_xor(unsigned long long x) const {
        if (tr.size() == 1) return 0ull; // 空集时随便返 0
        int u = 0;
        unsigned long long chosen = 0;
        for (int b = B; b >= 0; --b) {
            int bit   = int((x >> b) & 1ull);
            int same  = tr[u].nxt[bit];
            int other = tr[u].nxt[bit ^ 1];
            if (same != -1 && tr[same].cnt > 0) {
                u = same; // 让该位 XOR=0
                if (bit) chosen |= (1ull << b);          // chosen 的该位 = bit
            } else {
                u = other; // 只能走相反位，该位 XOR=1
                if (bit ^ 1) chosen |= (1ull << b);      // chosen 的该位 = bit^1
            }
        }
        return chosen;
    }    
}tr;
// 处理无符号数

inline void __(){
    cin>>N;
    vll A(N+5);
    tr.clear();
    ll sum=0;
    FOR(i,1,N){
        cin>>A[i];
        tr.insert(A[i]);
        sum^=A[i];
    }
    // j1,j2
    ll ans=0;
    FOR(j1,1,N){
        ll a=sum^A[j1];
        ll mne=tr.argmin_xor(a),mn=tr.min_xor(a);
        bool ise=tr.erase(mne);
        //  那么 bob 有两种选择，一种是避开我们删除的mne，另一种是就选我们删除的mne
        ll lans=min<ll>(tr.min_xor(a),mne^sum);
        // 那么删除 mne 可能导致负面影响，那么我们不删除mne的结果是什么那？就是bob选择mne呗
        lans=max(lans,mn);
        ans=max<ll>(ans,lans);
        if(ise) tr.insert(mne);
    }
    // tr.erase(sum);
    ans=min<ll>(ans,tr.max_xor(sum));
    cout<<ans<<"\n";
}
/*
1
4
1 0 3 4
AC
https://www.codechef.com/viewsolution/1183578991
*/

心路历程（WA，TLE，MLE……）

P7074 [CSP-J2020] 方格取数

Posted on 2025-08-17 Edited on 2026-02-18

思路讲解

其实关键在于这个格子只能走一遍，那么可以建两个dp数组，一个从上面转移过来，一个从下面转移过来。

AC代码

https://www.luogu.com.cn/record/231568236

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
        __();
    return 0;
}
/*

*/
inline void __(){
    cin>>N>>M;
    vector<vll> A(N+5,vll(M+5));
    vector<vll> dp(N+5,vll(M+5,-INF));
    vector<vll> dp2(N+5,vll(M+5,-INF));
    FOR(i,1,N){
        FOR(j,1,M){
            cin>>A[i][j];
        }
    }
    dp[0][1]=0;
    dp[1][0]=0;
    FOR(y,1,M){
        FOR(x,1,N){
            ll val=A[x][y];
            dp[x][y]=max(max(dp2[x][y-1],dp[x][y-1])+val,dp[x-1][y]+val);
        }
        ROF(x,N,1){
            ll val=A[x][y];
            dp2[x][y]=max(max(dp2[x][y-1],dp[x][y-1])+val,/* (x+1>N)?-INF: */dp2[x+1][y]+val);
        }
    }
    cout<<max(dp2[N][M],dp[N][M]);
#ifdef LOCAL
    _print(dp);
    _print(dp2);
#endif
}
/*
WA  https://www.luogu.com.cn/record/231567313
AC  https://www.luogu.com.cn/record/231568236
*/

心路历程（WA，TLE，MLE……）

P1412 经营与开发

Posted on 2025-08-17 Edited on 2026-02-18

思路讲解

// 以i为起点，初始值为w，所能够获得的最大收益
vdb dp(N+5);
ROF(i,N,1){
    auto [type,val]=A[i];
    if(type==1){
        dp[i]=max(dp[i+1],dp[i+1]*(1-cost*0.01)+val*W);
    }else{
        dp[i]=max(dp[i+1],dp[i+1]*(1+grow*0.01)-val*W);
    }
}
cout<<fsp(2)<<dp[1]<<"\n";

这道题目，我认为关键点在这里，因此我们推一下

$W\times val+W\times (1-0.01\times cost)\times val_2 +W\times (1-0.01\times cost)^2\times val_3$

不难发现，无论怎么样操作，一个星球的收益一定是一个连乘的式子，因此上述操作就不难理解了。

AC代码

https://vjudge.net/solution/62959677

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,T,lT,W;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
        __();
    return 0;
}
/*

*/
struct planet{
    ll type,val;
};
inline void __(){
    ll cost,grow;
    cin>>N>>cost>>grow>>W;
    vector<planet> A(N+5);
    FOR(i,1,N){
        cin>>A[i].type>>A[i].val;
    }
    // 以i为起点，初始值为w，所能够获得的最大收益
    vdb dp(N+5);
    ROF(i,N,1){
        auto [type,val]=A[i];
        if(type==1){
            dp[i]=max(dp[i+1],dp[i+1]*(1-cost*0.01)+val*W);
        }else{
            dp[i]=max(dp[i+1],dp[i+1]*(1+grow*0.01)-val*W);
        }
    }
    cout<<fsp(2)<<dp[1]<<"\n";
}
/*
AC
https://vjudge.net/solution/62959677
*/

心路历程（WA，TLE，MLE……）

ABC-419-E - Subarray Sum Divisibility（len连续段和都是M倍数的所需最少操作数，操作是让一个元素增加1）

Posted on 2025-08-16 Edited on 2026-02-18

思路讲解

$(A[1]+\dots+A[len]) \bmod M = 0$

$(A[2]+\dots+A[len+1]) \bmod M = 0$

$(-A[1]+A[len+1])\bmod M=0$

$Sum_{i+L}≡Sum_i(\bmod M)(∀i=0,…,N−L).$

https://chatgpt.com/c/68a1e9d2-d4f4-832a-bc89-13ae40f158c5

br 是指的差值的模（模M）。具体来讲，就是 $(-A[1]+A[len+1])\bmod M=0$ ， $(-A[0]+A[len])\bmod M=0$ 这种位置很多，他们成周期性出现，即是：

$b_1=A[1]\bmod M=A[len+1]\bmod M=A[2len+1]\bmod M \cdots$

那么，不难发现，除了要满足传递性，还要满足初始条件，即：

$b_1+b_2+⋯+b_{len}≡0 \pmod M$

然后可以定义一个dp数组， $dp[i][j]$ 表示已经选了前 i 个数字，且 $sum\equiv j\pmod M$ 所需的代价为几（ $sum=b_1+b_2+\cdots+b_i$ ）？

为了快速计算这个dp，可以使用一个辅助数组 $g[i][j]$ 是指 $b[i]$ 到达 $b[i]\equiv j \pmod M$ 所需要的总代价。朴素计算需要 $O(LM \frac{N}{L}) \Rightarrow O(MN)$ （好像还可以？）

AC代码

https://atcoder.jp/contests/abc419/submissions/68614283

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <numeric>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end()) 
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL 
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,L;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
        __();
    return 0;
}
/*
a1+...+al
a2+...+al+1     al+1 - a1 % M ==0
*/
inline ll MOD(const ll &a,const ll &b){
    ll res=a%b;
    if(res<0) res+=b;
    return res;
}
inline void __(){
    cin>>N>>M>>L;
    vll A(N+5);
    FOR(i,1,N){
        cin>>A[i];
    }
    // 为了快速计算这个dp，可以使用一个辅助数组$g[i][j]$ 是指$b[i]$ 到达$b[i]\equiv j \pmod M$ 所需要的总代价。朴素计算需要$O(LM \frac{N}{L}) \Rightarrow O(MN)$ （ 好像还可以？）
    vector<vll> g(L+5,vll(M+5));
    auto cal=[&](ll x,ll obj){
        // if(MOD(x,M)==obj) return 0ll;
        if(x/M*M+obj>=x){
            return x/M*M+obj-x;
        }else{
            return (x+M-1)/M*M+obj-x;
        }
    };
    FOR(i,1,L){
        FOR(j,0,M-1){
            ll res=0;
            for(int p=i;p<=N;p+=L){
                res+=cal(A[p],j);
            }
            g[i][j]=res;
        }
    }
    vector<vll> dp(L+5,vll(M+5,INF));
    dp[0][0]=0;
    FOR(i,1,L){
        FOR(sum,0,M-1){
            FOR(j,0,M-1){
                ll res=MOD(sum-j,M);
                dp[i][sum]=min(dp[i-1][res]+g[i][j],dp[i][sum]);
            }
        }
    }
#ifdef LOCAL
    _print(dp);
    _print(g);
#endif
    ll ans=dp[L][0];
    cout<<ans;
}
/*
AC
https://atcoder.jp/contests/abc419/submissions/68614283
*/
    // vll Sum(N+5);
    // partial_sum(all(A),Sum.begin());
//     ll ans=0;
//     auto cal=[&](ll x){
//         x=abs(x);
//         ll res=x-x/M*M;
//         res=min(res,(x+M-1)/M*M-x);
//         return res;
//     };
//     FOR(i,1,N-L){
//         ll diff=A[L+i]-A[i];
//         // ll lans=MOD(diff,M);
//         // diff=diff%M;
//         // diff=abs(diff);
//         ll lans=cal(diff);
// #ifdef LOCAL
//     debug(i);debug(diff);debug(lans);
// #endif
//         ans+=cal(diff);
//     }
    
//     cout<<ans<<"\n";

心路历程（WA，TLE，MLE……）

影石Insta360杯 2025牛客暑期多校训练营10——[E] Sensei and Affection（使得数组趋同，所需要的最少区间+1操作数量。）

Posted on 2025-08-16 Edited on 2026-03-14

题目大意

使得数组趋同，所需要的最少区间加一操作数量。

题目描述

给定 $n$ 个学生的初始好感度序列 $a_1, a_2, \dots, a_n$ 。
每天可以且必须进行一次操作：选择一个区间 $[l, r]$ ( $1 \le l \le r \le n$ )，将该区间内所有学生的好感度加 1（即对于所有 $l \le i \le r$ ，执行 $a_i := a_i + 1$ ）。
求使得最终序列中最多出现 $m$ 种不同数值所需的最小操作次数（最小天数）。

输入描述

第一行包含一个整数 $T$ ( $1 \le T \le 10$ )，表示测试数据组数。
对于每组测试数据：
第一行包含两个整数 $n, m$ ( $1 \le n \le 400, 1 \le m \le 2$ )，分别表示学生数量和允许的最大不同数值种数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 100$ )，表示初始好感度。

输出描述

对于每组测试数据，输出一行一个非负整数，表示所需的最小操作次数。

样例

样例解释

第一组数据 ( $n=3, m=1$ )：
初始序列为 [3, 1, 3]，目标是让所有数字相同（最多 1 种数值）。

选择区间 $[2, 2]$ 进行操作，序列变为 [3, 2, 3]。
再次选择区间 $[2, 2]$ 进行操作，序列变为 [3, 3, 3]。
共需 2 次操作，序列中只有数值 3，满足条件。

第三组数据 ( $n=5, m=2$ )：
初始序列为 [5, 1, 6, 1, 8]，目标是让序列中最多只有 2 种不同的数值。
最小需要 3 次操作。

思路讲解

首先我们注意到一件事情，就是这个 M 等于一或者 M 等于二。说白了要么变成同一个数，要么变成两个数。

我是这么感觉的，修改一个数，就是把所有的值修改为最大值。修改两个数其实也简单。修改两个数就是一个最大值，一个次大值，然后把其他的值都修改为次大值就好了。

上面就是我的感觉啊，我们先尝试一下，看看对不对。先尝试手磨一下样例。

不，手磨样例以后，我们发现把所有值修改为最大值，在只修改一个数的时候应该是对的。但是修改两个数的时候，这个情况就比较复杂了。修改两个数的话，我们之前的想法应该是错的。只有一个是对的，就是应该就是先要把这些数，其中的一些数肯定是要变为最大值的，其中的一些数肯定是要变为最大值的。但是至于另外一个值需要怎样取，就比较麻烦了。

AI 提示 1

看了下你的代码，你目前只写了平凡情况的判断。让我分步给你提示。

提示一：操作次数的计算公式

这是整道题的基础。假设目标数组是 $b$ （满足 $b_i \ge a_i$ ），从 $a$ 变到 $b$ 的最少操作次数是多少？
令 $d_i = b_i - a_i \ge 0$ （每个位置需要增加的量）。最少操作数 = 区间覆盖次数，等于：

d_1 + \sum_{i=2}^{n} \max(0,\ d_i - d_{i-1})

这就是经典的"刷油漆"公式——每当 $d$ 序列往上爬一个台阶，就需要新开一批区间操作。
你可以先验证一下样例 1 和样例 2（ $m=1$ 的情况）。

提示二：m=1 的情况

$m=1$ 时，所有值必须相同。由于只能增加，目标只能是 $v = \max(a)$ 。代入公式即可， $d_i = M - a_i$ 。

提示三：m=2 时，你的想法哪里有问题

你说"一个最大值，一个次大值"——错在"次大值"。
看样例 3： $a = [5, 1, 6, 1, 8]$ ，最优方案是把数组变成 $[8, 3, 8, 3, 8]$ ，两个值是 $8$ 和 $3$ 。但 $3$ 根本不在原始数组里！所以小的目标值不是"次大值"，而是需要枚举的。

提示四：m=2 的核心思路

大的目标值一定是 $v = M = \max(a)$ （因为原数组最大值的那个位置只能往上走，强制拉高这一组的目标， $v < M$ 不可能， $v > M$ 只会更贵）。
小的目标值 $u$ ：枚举 $u$ 从 $0$ 到 $M-1$ 。对于每个固定的 $u$ ：

$a_i > u$ 的位置：强制进大组（目标 $M$ ）；
$a_i \le u$ 的位置：可以进小组（目标 $u$ ）或大组（目标 $M$ ），用 DP 最优决定。

提示五：DP 的定义

对于固定的 $u$ ，定义：

dp[i][g] = \text{处理前 } i \text{ 个位置，第 } i \text{ 个位置属于第 } g \text{ 组时的最小操作数}

$g=0$ ：小组， $d_i = u - a_i$ （仅当 $a_i \le u$ ）
$g=1$ ：大组， $d_i = M - a_i$
转移：从 $(i-1, g')$ 到 $(i, g)$ 的代价是 $\max(0,\ d_i(g) - d_{i-1}(g'))$ 。
每个 $u$ 跑一次 $O(n)$ 的 DP， $u$ 最多枚举 $M \le 100$ 个值，总复杂度 $O(T \cdot M \cdot n)$ ，完全够用。

你可以用 $u=3$ 、样例 3 手跑一遍 DP 验证答案是 3，感受一下正确性。然后就可以动手实现了。

OK 啊，偷偷看了一眼题解，这个题解写的还是可以的。比这垃圾 AI 提示写的好。这 AI 提示，我告诉他我的思路，我干脆比不告诉他我的思路还好，写的还好一点。这真的纯纯傻逼，还不如不写。

M 等于一的情况，一种比较方便的实现方法呢，就是直接选择一个极长段，这个极长段中的所有数都比最大值小。不断地选择这样的极长段进行操作，记录一下找不到这个这样子的极长段所需要的操作数量。说白了，这个做法就是一个贪心。

M = 2 的时候的错误解法（不过，这里面他这个段内逻辑求解写的还是非常好的，要可以参考参考。嗯，不是可以参考一下，是非常好，要参考）（这里面也有一些我画的图，因为前面我以为这个做法是正确的，不过呢，现在是现在发现是错的）

现在问题在于 M 等于2的情况下，另外一个值怎样取？但是你会发现，其实这道题目它的值域非常小啊，另外一个值怎样取？你不知道怎样取，你直接枚举就行了，一共就100个值，它总归是变成比最大值小的值，是吧？
OK 啊，我已经想到了一种可以解决 M 等于2的情况下的 DP 的方法。

不过这个方法目前的瓶颈在于，就是说从转移过来的位置到我的这个 pos 之间，这一段的求解，如果使用贪心法有点慢了。
我们现在的问题如下：
对于段 $[l, r]$ ，把它所有元素变成 $\max(a[l..r])$ 所需的最小操作数，如何快速预处理？
（对于任意目标值 $T = \max(a[l..r]) + k$ ，代价只比 $T = \max$ 时多 $k$ ，而目标值 T 又不可能比 Max A 从 L 到 R 还小，这是不可能的。）

进一步追问公式细节（**讲的非常清楚非常清楚，好好看仔细看**。）

好，从头推。

第一步：最少操作次数的一般公式

操作是"选一个连续区间，全体 +1"。目标是把 $a$ 变成 $b$ （ $b_i \ge a_i$ ）。
令 $d_i = b_i - a_i$ ，即每个位置还需要增加的量。问题变成：用最少次"选连续区间全体 -1"操作，把 $d$ 清零。
从左到右看 $d$ 数组：

位置 $l$ （最左）：这里有 $d_l$ 层需求，必须有 $d_l$ 条操作从这里开始或经过。由于左边没有别的位置了，这 $d_l$ 条操作全都必须从这里新起。贡献 $d_l$ 。
位置 $i$ $i$ （ $i > l$ $i > l$ ）：从位置 $i-1$ $i - 1$ 延伸过来的操作最多 $d_{i-1}$ $d_{i - 1}$ 条。位置 $i$ $i$ 需要 $d_i$ $d_{i}$ 条操作覆盖。
- 若 $d_i \le d_{i-1}$ ：左边延过来的操作绰绰有余，多余的在 $i-1$ 和 $i$ 之间结束就行，不需要新开。贡献 $0$ 。
- 若 $d_i > d_{i-1}$ ：左边延过来的不够，还差 $d_i - d_{i-1}$ 条，必须从位置 $i$ 新起。贡献 $d_i - d_{i-1}$ （贡献即需要新开这么多条）。
  合起来：

\text{操作数} = d_l + \sum_{i=l+1}^{r} \max(0,\ d_i - d_{i-1})

第二步：代入目标值 = $mx$

令目标 $b_i = mx = \max(a[l..r])$ ，则 $d_i = mx - a_i$ 。
看差值：

d_i - d_{i-1} = (mx - a_i) - (mx - a_{i-1}) = a_{i-1} - a_i

$mx$ 抵消了。所以：

\max(0,\ d_i - d_{i-1}) = \max(0,\ a_{i-1} - a_i)

这个东西跟 $mx$ 无关，只跟原数组相邻元素有关**。（这也是后续我们可以 O1 求的这个原因啊。）**
代回去：

\text{cost}(l,r) = \underbrace{(mx - a_l)}_{\text{第一项}} + \sum{i=l+1}^{r}\max(0,\ a_{i-1} - a_i)

第三步：前缀和预处理

定义：

P[i] = \sum_{j=2}^{i}\max(0,\ a_{j-1} - a_j)

则 $\sum_{i=l+1}^{r}\max(0, a_{i-1}-a_i) = P[r] - P[l]$ 。
最终：

\text{cost}(l,r) = (mx[l][r] - a_l) + P[r] - P[l]

这就是完整的推导过程。

</div>

如果说我们画一张图具体来表达的话，就如下图：

哎，上面的思路都被op4.6带歪了。我们应该让他先写一下这个程序，然后看看AC的以后，再写完这个顺序，发现他这个思路根本完全就是错的，提交上去以后，忘了以后，我仔细想一下，他这个思路完全是错的。嗯，当然也没有说错的那么明显，但是段间的这个逻辑不是很清楚，段间的这个逻辑是实际上是有问题的，段内的逻辑它的这个求解的逻辑是非常正确的，但是段间的这个逻辑有问题。

还有这个错误解法，还有一个问题就是反例，在M=二的情况下，最就是这两个值不一定就是一个最大值，就是这两个值中不一定包含最大值，即最优解当中相同的这两个数不一定包含最大值。

反例`[0, 3, 0, 1]`，最优是`[1,4,1,1]`

你这个判断直觉很强，但结论确实不成立。
我不跟你抬杠，直接给你一个最小反例：

初始：[0, 3, 0, 1]
m = 2
mx = 3
如果强行要求答案值里包含 3，最优至少是 2 天。
例如变成 [1,3,1,1]（两值 {1,3}）：
需要增量 d=[1,0,1,0]
代价 = d1 + Σmax(0,di-di-1) = 1+0+1+0 = 2
但如果不包含 3，取两值 {1,4}，变成 [1,4,1,1]：
增量 d=[1,1,1,0]
代价 = 1+0+0+0 = 1
也就是：把原来的最大值位置也抬高，反而更优。
所以“mx 必须是最终两值之一”这个约束会 WA。

如果你仍然坚持“固定 mx 来写”，我可以按这个约束给你写一个版本，但我会明确标注：这是受限解法，不是题目的全局最优解。

其实说白了这个判断，细想一下就是不对的，虽然最大值增加没有太大意义，但是如果说在有两个数的情况下，我去跨越它，去进行一些增加，也是有可能的。

AI （代码已经 AC）对 M = 2 思路的提示

可以，我把这版 DP 的核心讲清楚，尽量不绕。

1）先说为什么推翻原思路

你原来那版本质上是“分段 + 两个目标值”。问题不在“分段”，而在两个隐含假设：

把“大目标值”固定成 mx（全局最大初值）是错的。
反例就是你看到的：最优两值可能是 {3,7} 这类，不一定包含 mx。
段转移时容易把“段内代价”和“边界衔接代价”混在一起，公式很容易写错（你之前 max(dp, cost) 那个就是典型错位）。
所以我改成了“固定两目标值后，逐位置 DP”。

2）固定两目标值后的数学模型

假设最后只保留两个值：low <= high。
每个位置 i 只能选其中一个目标，且必须满足 a[i] <= target（只能加不能减）。
定义：

若位置 i 选了目标 t_i，则该位置需要增量 d_i = t_i - a_i >= 0。
把数组 d 造出来后，最少操作数是经典式子：

\text{cost} = d_1 + \sum_{i=2}^{n}\max(0,\ d_i-d_{i-1})

这个式子说明：代价只和相邻两位有关。

3）DP 状态与转移

设 f[i][g]：

处理到第 i 位；
第 i 位选的是第 g 个目标（g=0 表示 low，g=1 表示 high）；
的最小代价。
记：
tar(g) = (g==0 ? low : high)
d(i,g) = tar(g) - a[i]
初始化（i=1）：
若 a[1] <= low，f[1][0] = low - a[1]
若 a[1] <= high，f[1][1] = high - a[1]
转移（i>=2）：
从上一位状态 pg 转到 g：

f[i][g] = \min\Big(f[i][g],\ f[i-1][pg] + \max(0,\ d(i,g)-d(i-1,pg))\Big)

最终固定 (low,high) 的答案是：

\min(f[n][0],f[n][1])

4）外层枚举什么

a_i <= 100，值域小，所以直接枚举 low, high 就行。
复杂度大约 O(V^2 * n * 4)，V 在 100 量级，n<=400，完全够。

如果你愿意，我下一条可以专门按你现在这份代码变量名，给你写“逐行对应解释”（哪一行是 d_1，哪一行是 max(0, d_i-d_{i-1})），这样你对照起来会最快。

那么，他写的还是挺好的。嗯，思路其实很简单，就是在已知upper和已知lower的情况下，那么这个实际上可以使用一个 $O(n)$ 的DP就可以去解决这个问题。因为其实一个位置，他对答案的贡献只取决于他前面一个位置和它自己的这个位置，它取什么值。

这个下面就是已经知道了upper和lower以后，怎么样去DP的这个过程的代码。嗯，然后加粗高亮的地方呢，是有点问题。但是当时挖的地方，当时upper写成了max，然后这个DPI1呢，写成了DPI0。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82501084

我感觉想规避DPI1的错误，我们在这里取命只是为了让他不要比infinite高。那么我们直接命里面放一个INF就行了，不要写真实的东西，参有的时候会造成问题，不要写真实的东西，就写一个常数进去，就是能用常数的地方就用常数。

vector<array<ll,2>> diff_arrays(N+2);
for (int i=1;i<=N;++i) {
    if (A[i]<=lower) {
        diff_arrays[i][0]=lower-A[i];
    }
    diff_arrays[i][1]=upper-A[i];
}
vector<array<ll,2>> dp(N+2,{INF,INF});

for (int i=1;i<=N;++i) {
    if (i==1) {
        if (A[i]<=lower) {
            dp[i][0]=lower-A[i];
        }
        dp[i][1]=upper-A[i];
        continue;
    }
    ll add01=INF,add00=INF;
    if (A[i-1]<=lower) {
        add01=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][0]);
        if (A[i]<=lower) {
            add00=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][0]);
        }
    }
    ll add10=INF,add11=INF;
    if (A[i]<=lower) {
        add10=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][1]);
    }
    add11=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][1]);
    dp[i][0]=min({dp[i][0],dp[i-1][0]+add00,dp[i-1][1]+add10});
    dp[i][1]=min({dp[i][1],dp[i-1][0]+add01,dp[i-1][1]+add11});
}

AC代码

AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82503145

源代码

/**
 * Problem: Sensei and Affection (affection)
 * Contest: 
 * Judge: NowCoder
 * URL: https://ac.nowcoder.com/acm/contest/108307/E
 * Created: 2026-02-22 20:44:42
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */


void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    ll mx=*max_element(all(A));
    ll mn=*min_element(A.begin()+1,A.begin()+N+1);
    set<ll> st;
    for (int i=1;i<=N;++i) {
        st.insert(A[i]);
    }
    if (SZ(st)<=M) {
        cout<<0<<"\n";
        return;
    }

    if (M==1) {
        ll ans=0;
        // A[0]=INF;
        while (true) {
            bool finded=false;
            ll up=-1;
            for (int i=1;i<=N;++i) {
                if (A[i]<mx) {
                    finded=true;
                    A[i]++;
                    if (i-1!=up) {
                        ++ans;
                    }
                    up=i;
                }
            }
            if (!finded) {
                break;
            }
        }
        cout<<ans<<"\n";
    }else {
        ll ans=INF;
       // 这里的逻辑应该就是直接去枚举lower和upper
        for (ll lower=mn;lower<=100;++lower) {
            for (ll upper=mx;upper<=200;++upper) {
                vector<array<ll,2>> diff_arrays(N+2);
                for (int i=1;i<=N;++i) {
                    if (A[i]<=lower) {
                        diff_arrays[i][0]=lower-A[i];
                    }
                    diff_arrays[i][1]=upper-A[i];
                }
                vector<array<ll,2>> dp(N+2,{INF,INF});

                for (int i=1;i<=N;++i) {
                    if (i==1) {
                        if (A[i]<=lower) {
                            dp[i][0]=lower-A[i];
                        }
                        dp[i][1]=upper-A[i];
                        continue;
                    }
                    ll add01=INF,add00=INF;
                    if (A[i-1]<=lower) {
                        add01=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][0]);
                        if (A[i]<=lower) {
                            add00=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][0]);
                        }
                    }
                    ll add10=INF,add11=INF;
                    if (A[i]<=lower) {
                        add10=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][1]);
                    }
                    add11=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][1]);
                    dp[i][0]=min({dp[i][0],dp[i-1][0]+add00,dp[i-1][1]+add10});
                    dp[i][1]=min({dp[i][1],dp[i-1][0]+add01,dp[i-1][1]+add11});
                }
                ll lans=min(dp[N][0],dp[N][1]);
                ans=min(lans,ans);
// #ifdef LOCAL
//                 if (lans==0) {
//                     debug(lower);debug(upper);
//                     debug2d(dp);
//                 }
// #endif
            }
        }
        cout<<ans<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82503145

1
5 2
5 1 6 1 8

1
5 2
1 3 2 3 1

*/

数据生成器

/**
 * Problem: Sensei and Affection (affection)
 * Contest: 
 * Judge: NowCoder
 * URL: https://ac.nowcoder.com/acm/contest/108307/E
 * Created: 2026-02-22 21:38:47
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
    cout<<1<<"\n";
    ll N=uniform_int_distribution<ll>(1,7)(rng),M=2;
    cout<<N<<" "<<M<<"\n";
    for (int i=1;i<=N;++i) {
        cout<<uniform_int_distribution<ll>(0,7)(rng)<<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

暴力程序（bfs，暴力直接采用A数组作为状态，记忆化BFS）

/**
 * Problem: Sensei and Affection (affection)
 * Contest: 
 * Judge: NowCoder
 * URL: https://ac.nowcoder.com/acm/contest/108307/E
 * Created: 2026-02-22 21:22:12
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct Status {
    vector<ll> A;
    ll step;
};
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    queue<Status> q;
    q.push({A,0});
    set<vector<ll>> a_memo_st;
    a_memo_st.insert(A);
    auto check=[&](const vector<ll> &a) {
        set<ll> st;
        for (int i=1;i<=N;++i) {
            st.insert(a[i]);
        }
        return SZ(st)<=M;
    };
    while (!q.empty()) {
        auto [a,step]=q.front();
        q.pop();
        if (check(a)) {
            cout<<step<<"\n";
            return;
        }
        for (int l=1;l<=N;++l) {
            for (int r=l;r<=N;++r) {
                vector<ll> opa=a;
                for (int i=l;i<=r;++i) {
                    opa[i]++;
                }
                if (!a_memo_st.contains(opa)) {
                    a_memo_st.insert(opa);
                    q.push({opa,step+1});
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
3
3 1
3 1 3
5 2
5 1 6 1 8
5 2
1 3 2 3 1

*/

心路历程（WA，TLE，MLE……）

AI 纠错 2

我理解你的想法了——你在枚举"段的边界"，然后对每一段内部用贪心求代价，这样确实是 $O(n^2)$ 甚至更高。
但其实完全不需要"分段"的思维。

关键观察：操作数公式是逐位累加的

回顾代价公式：

\text{cost} = d_1 + \sum_{i=2}^{n} \max(0,\ d_i - d_{i-1})

这个公式里，每一项 $\max(0, d_i - d_{i-1})$ 只和相邻两个位置的 $d$ 值有关，和更远的位置无关。
所以 DP 不需要跳跃，直接逐位转移即可，每步转移 $O(1)$ 。

正确的 DP 定义

对于固定的小目标值 $u$ （外层枚举），令：

$d_i(0) = u - a_i$ （位置 $i$ 分配到小组，仅当 $a_i \le u$ ）
$d_i(1) = M - a_i$ （位置 $i$ 分配到大组）
定义：

dp[i][g] = \text{处理完前 } i \text{ 个位置、第 } i \text{ 个位置属于第 } g \text{ 组时的最小总操作数}

转移（每步 $O(1)$ ，无需关心段的内部）：

dp[i][g] = \min_{g' \in \{0,1\}} \left( dp[i-1][g'] + \max\left(0,\ d_i(g) - d_{i-1}(g')\right) \right)

这里 $d_{i-1}(g')$ 就是上一个位置在 $g'$ 组时的 $d$ 值，是常数，查表即可。
每个转移只需要做一次 $\max$ 和一次 $\min$ ， $O(1)$ 。
初始化： $dp[1][0] = d_1(0)$ （若 $a_1 \le u$ ）， $dp[1][1] = d_1(1)$ 。
答案： $\min(dp[n][0], dp[n][1])$ 。

总复杂度

层次	复杂度
枚举 $u$ （0 到 $M \le 100$ ）	$O(M)$
每个 $u$ 跑一遍 DP	$O(n)$
总计	$O(M \cdot n) \approx O(100 \times 400)$
远远够用，不需要任何段内贪心。

你之前思路里的"段"其实并不是必要的抽象——相邻两位之间的 $\max(0, d_i - d_{i-1})$ 本身就已经捕捉了所有段的边界信息，DP 直接逐位推进即可。

AI 纠错 3

选第二条路，在你的思路上解决。

你的 DP 定义

`dp[pos][g]` = 前 pos 个位置处理完毕、最后一段（以 pos 结尾的连续段）属于第 g 组时的最小操作数。
转移从所有 `prev`（0 到 pos-1）来，段 `[prev+1, pos]` 全部是第 g 组。

段代价的拆解

对于段 [prev+1, pos] 全在 g 组（目标值 $t_g$ 为 $u$ 或 $M$ ），它对总操作数的贡献分两部分：
① 边界项（连接前一段和本段，O(1)）：

\max\!\left(0,\ t_g - a_{prev+1} - (t_{g'} - a_{prev})\right)

② 段内部项：

\sum_{i=prev+2}^{pos} \max(0,\ d_i^{(g)} - d_{i-1}^{(g)}) = \sum_{i=prev+2}^{pos}\max(0,\ a_{i-1} - a_i)

关键：这个内部项与 $t_g$ （即 $u$ 还是 $M$ ）完全无关！ 可以预处理前缀和：

P[i] = \sum_{j=2}^{i} \max(0,\ a_{j-1} - a_j)

则段内部项 = $P[pos] - P[prev+1]$ ，O(1) 查询。

转移公式

dp[pos][g] = \min_{\substack{prev \in [0, pos-1] \\ g' \in \{0,1\}}} \left(\ dp[prev][g'] + \underbrace{\max(0,\ t_g - a_{prev+1} - t_{g'} + a_{prev})}{\text{边界项，O(1)}} + \underbrace{P[pos] - P[prev+1]}{\text{内部项，O(1)}}\ \right)

特殊地，`prev=0` 时边界项 = $t_g - a_1$ （无前一段， $d_0 = 0$ ）。

复杂度

枚举 $u$ ： $O(M) = O(100)$
每个 $u$ ，枚举 pos 和 prev： $O(n^2) = O(160000)$
合计： $O(M \cdot n^2) \approx 1.6 \times 10^7$ ，完全够用

一句话总结：预处理前缀和 $P[i]$ ，段内部项变 O(1) 查询，转移总体 O(n²)，搞定。

这两个 AI 回答都写的比较招笑，我们再看一看它有没有更好的回答。

AI 的回答（不小心换成 Sonnet 4.6了。我想它前面的和这个回答怎么都这么招笑啊？OPUS 4.6和 Sonnet 4.6搞混了，绷不住了。）

答案

预处理前缀和，令：

P[i] = \sum_{j=2}^{i} \max(0,\ a[j-1] - a[j])

（O(n) 预处理，O(1) 查询）
预处理区间最大值：

mx[l][r] = \max(a[l],\ldots,a[r])

（O(n²) 预处理所有对）

公式

\text{cost}(l, r) = \bigl(mx[l][r] - a[l]\bigr) + P[r] - P[l]

推导：令 $d_i = mx[l][r] - a[i]$ ，代入操作数公式：

d_l + \sum_{i=l+1}^{r} \max(0, d_i - d_{i-1}) = (mx - a[l]) + \sum_{i=l+1}^{r}\max(0,\ a[i-1]-a[i]) = (mx - a[l]) + P[r] - P[l]

平移性质

目标值变为 $mx[l][r] + k$ ，代价恰好增加 $k$ （因为 $d_l$ 增加 $k$ ，内部差值不变）：

\text{cost}(l, r, \text{target} = mx + k) = \text{cost}(l, r) + k

验证

$a = [5,1,6,1,8]$ ， $P = [0, 4, 4, 9, 9]$ ，整段 $[1,5]$ ： $mx=8$ ， $\text{cost} = (8-5) + 9 - 0 = 12$ ✓

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

看了下你的代码，你目前只写了平凡情况的判断。让我分步给你提示。

提示一：操作次数的计算公式

这就是经典的"刷油漆"公式——每当 ddd 序列往上爬一个台阶，就需要新开一批区间操作。 你可以先验证一下样例 1 和样例 2（m=1m=1m=1 的情况）。

提示二：m=1 的情况

m=1m=1m=1 时，所有值必须相同。由于只能增加，目标只能是 v=max⁡(a)v = \max(a)v=max(a)。代入公式即可，di=M−aid_i = M - a_idi​=M−ai​。

提示三：m=2 时，你的想法哪里有问题

提示四：m=2 的核心思路

提示五：DP 的定义

好，从头推。

第一步：最少操作次数的一般公式

第二步：代入目标值 = mxmxmx

第三步：前缀和预处理

1）先说为什么推翻原思路

2）固定两目标值后的数学模型

这个式子说明：代价只和相邻两位有关。

3）DP 状态与转移

4）外层枚举什么

AC代码

心路历程（WA，TLE，MLE……）

我理解你的想法了——你在枚举"段的边界"，然后对每一段内部用贪心求代价，这样确实是 O(n2)O(n^2)O(n2) 甚至更高。 但其实完全不需要"分段"的思维。

关键观察：操作数公式是逐位累加的

这个公式里，每一项 max⁡(0,di−di−1)\max(0, d_i - d_{i-1})max(0,di​−di−1​) 只和相邻两个位置的 ddd 值有关，和更远的位置无关。 所以 DP 不需要跳跃，直接逐位转移即可，每步转移 O(1)O(1)O(1)。

正确的 DP 定义

总复杂度

选第二条路，在你的思路上解决。

你的 DP 定义

dp[pos][g] = 前 pos 个位置处理完毕、最后一段（以 pos 结尾的连续段）属于第 g 组时的最小操作数。 转移从所有 prev（0 到 pos-1）来，段 [prev+1, pos] 全部是第 g 组。

段代价的拆解

则段内部项 = P[pos]−P[prev+1]P[pos] - P[prev+1]P[pos]−P[prev+1]，O(1) 查询。

转移公式

特殊地，prev=0 时边界项 = tg−a1t_g - a_1tg​−a1​（无前一段，d0=0d_0 = 0d0​=0）。

复杂度

答案

（O(n²) 预处理所有对）

公式

平移性质

验证

这就是经典的"刷油漆"公式——每当 $d$ 序列往上爬一个台阶，就需要新开一批区间操作。
你可以先验证一下样例 1 和样例 2（ $m=1$ 的情况）。

$m=1$ 时，所有值必须相同。由于只能增加，目标只能是 $v = \max(a)$ 。代入公式即可， $d_i = M - a_i$ 。

第二步：代入目标值 = $mx$

我理解你的想法了——你在枚举"段的边界"，然后对每一段内部用贪心求代价，这样确实是 $O(n^2)$ 甚至更高。
但其实完全不需要"分段"的思维。

这个公式里，每一项 $\max(0, d_i - d_{i-1})$ 只和相邻两个位置的 $d$ 值有关，和更远的位置无关。
所以 DP 不需要跳跃，直接逐位转移即可，每步转移 $O(1)$ 。

`dp[pos][g]` = 前 pos 个位置处理完毕、最后一段（以 pos 结尾的连续段）属于第 g 组时的最小操作数。
转移从所有 `prev`（0 到 pos-1）来，段 `[prev+1, pos]` 全部是第 g 组。

则段内部项 = $P[pos] - P[prev+1]$ ，O(1) 查询。

特殊地，`prev=0` 时边界项 = $t_g - a_1$ （无前一段， $d_0 = 0$ ）。