Znzryb's Blog

P1412 经营与开发

Posted on 2025-08-17 Edited on 2026-04-06

思路讲解

// 以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-04-06

思路讲解

$(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-04-06

题目大意

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

题目描述

给定 $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$ ✓

影石Insta360杯-2025牛客暑期多校训练营10 原——[F] Sensei and Yuuka Going Shopping

Posted on 2025-08-16 Edited on 2026-04-06

思路讲解

思路不能说是一模一样吧，只能说是非常相似。

AC代码

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

源代码

// by Gospel_rock
#include <algorithm>
#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 << "}"; }
#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 __();
// 来自wida github仓库 https://github.com/hh2048/XCPC/tree/main 加了一些新功能
//46 ms https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14912 读入字符getc(a) 的AC记录
// https://www.luogu.com.cn/record/230330447 科学计数法小数，小数
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    void getc(char &a){
        char c=getc();
        while (isspace(c)) {
            c=getc();
        }
        a=c;
    }
    template <typename T> void Cinf(T &a) { // 新增：读取浮点数，支持科学计数法
        T ans = 0;
        bool f = 0; // 负号
        char c = getc();
        // 跳过非数字和小数点前的空白/符号
        while ((c < '0' || c > '9') && c != '.') {
            if (c == '-') f = 1;
            c = getc();
        }
        // 读取整数部分
        while (c >= '0' && c <= '9') {
            ans = ans * 10 + (c - '0');
            c = getc();
        }
        // 如果有小数点，读取小数部分
        if (c == '.') {
            c = getc();
            T frac = static_cast<T>(1);
            while (c >= '0' && c <= '9') {
                frac /= 10;
                ans += (c - '0') * frac;
                c = getc();
            }
        }
        a = f ? -ans : ans;
        // 处理科学计数法部分
        if (c == 'E' || c == 'e') {
            c = getc();
            bool exp_neg = false;
            if (c == '+') {
                c = getc();
            } else if (c == '-') {
                exp_neg = true;
                c = getc();
            }
            int exp = 0;
            while (c >= '0' && c <= '9') {
                exp = exp * 10 + (c - '0');
                c = getc();
            }
            T multiplier = pow(10.0, exp_neg ? -exp : exp);
            a *= multiplier;
        }
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T> void writef(T x) { // 新增：输出浮点数，默认输出6位小数，支持四舍五入
        if (x < 0) putchar('-'), x = -x;
        using ll = long long;
        int prec = 6; // 默认精度6，可根据需要调整
        // 添加圆整因子
        T round_add = static_cast<T>(5);
        for (int i = 0; i < prec + 1; ++i) {
            round_add /= 10;
        }
        x += round_add;
        ll int_part = static_cast<ll>(x);
        write(int_part); // 输出整数部分
        putchar('.');
        T frac_part = x - int_part;
        for (int i = 0; i < prec; ++i) {
            frac_part *= 10;
            int digit = static_cast<int>(frac_part);
            putchar(digit + '0');
            frac_part -= digit;
        }
    }
} // namespace QuickRead
using namespace QuickRead;


// 参考了（抄了）beta99999 的提交  https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用1-based，闭区间（调用的时候，实际上是0-based左闭右开区间）
// AC https://www.luogu.com.cn/record/231280893 扶苏的问题
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19134 矩形框选卡常
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887134 测试_find_l
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887151 测试_find_r
template <typename T,typename value_type> struct base_segtree{
    int n,sz;
    vector<value_type> tr;
    static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
    // zkw线段树开两倍大小，identity为默认值
    base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity){}    
    T *derived() { return static_cast<T*>(this); }
    void pushup(int o){
        tr[o]=T::op(tr[o<<1],tr[o<<1|1]);
    }
    value_type val(int o) { 
        return tr[o];
    }
    // zkw选配  
    int dis(int o){return __lg(sz)-__lg(o);}    // 倒数第几层？有倒数第0层
    int len(int o){return 1<<dis(o);}   // （直接调用就可以，就是左闭右开区间长度）
    int le(int o){return (o<<dis(o))-sz; }  // 左闭
    int rr(int o){return (o+1<<dis(o))-sz;} // 右开

    // 单节点的下推 在子类中实现
    // void pushdown(int o){}
    void call_pushdown(int i){  // 把路径上的所有点向下推
        int o=i+sz; // 1的__lg(1)=0，相当于就是从根节点慢慢推下来
        for(int k=__lg(o);k>=__builtin_ctz(o) + 1;--k){
            derived()->pushdown(o>>k);
        }
    }
    void call_pushup(int i){
        int o=i+sz;
        // 这个下界你可能会很奇怪，为什么不是1？那么答案不在这里，而是在update函数
        for(int k=__builtin_ctz(o) + 1;k<=__lg(o);++k){
            derived()->pushup(o>>k);
        }
    }
    void build(){
        for(int o=sz-1;o>=1;--o){
            derived()->pushup(o);
        }
    }
    template<typename D> 
    void upd(int l,int r,D x){
        l--;    // 实现1-based -> 0-based
        call_pushdown(l),call_pushdown(r);
        int l0=l,r0=r;l+=sz,r+=sz;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) derived()->settag(l++,x);
            if(r&1) derived()->settag(--r,x);  // 毕竟是右开区间
        }
        call_pushup(l0);call_pushup(r0);
    }
    value_type query(int l, int r){
        l--;
        call_pushdown(l);call_pushdown(r);
        l+=sz;r+=sz;    // T:: 调用的是类的静态成员，无需实例化
        value_type resl=T::identity,resr=T::identity;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) resl=T::op(resl,val(l++));
            if(r&1) resr=T::op(val(--r),resr);
        }
        return T::op(resl,resr);
    }
    void assign(int i,value_type a){
        i--;
        tr[i+sz]=a;
    }
    template <typename F> int _find_r(int r, F &&fun) { // 找到0-r中fun为true的最后一个数，因为开区间
        // r--;
        call_pushdown(r), r += sz;
        do r >>= __builtin_ctz(r); while (r != 1 && !fun(val(--r)));
        if (r == 1) return 0;
        while (r < sz) derived()->pushdown(r), r = r << 1 | fun(val(r << 1 | 1));
        return r - sz + 1;
    }
    template <typename F> int _find_l(int l, F &&fun) { // 均为1-based
        // l--;
        call_pushdown(l), l += sz;
        do l >>= __builtin_ctz(l); while (l != 1 && !fun(val(l++)));
        if (l == 1) return n;
        l--; while (l < sz) derived()->pushdown(l), l = l << 1 | !fun(val(l << 1));
        return l - sz + 1;
    }
};

struct segtree: base_segtree<segtree, ll> {
    static constexpr ll identity = 0;
   
    static ll op(ll a, ll b) { return max(a, b); }
    vector<ll> tag;
    vector<bool> fixed;
    segtree(int n): base_segtree(n), tag(sz), fixed(sz) {}
    void settag(int o, pair<int, ll> t) {
        int op = t.first;
        ll x = t.second;
        if (op == 1) {
            tr[o] = x;
            if (o < sz) tag[o] = 0, fixed[o] = 1;
        } else {
            tr[o] += x;
            if (o < sz && !fixed[o]) tag[o] += x;
        }
    }
    void pushdown(int o) {
        if (fixed[o]) {
            settag(o << 1, make_pair(1, tr[o]));
            settag(o << 1 | 1, make_pair(1, tr[o]));
            fixed[o] = 0;
        }
        if (tag[o]) {
            settag(o << 1, make_pair(2, tag[o]));
            settag(o << 1 | 1, make_pair(2, tag[o]));
            tag[o] = 0;
        }
    }
};
constexpr ll segtree::identity;
// tr.upd(1,N,(pll){1,0})    是清空操作
// 采用1-based 索引
// 记得改 identity 默认值为-INF 

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

*/
inline void __(){
    Cin(N);
    vll A(N+5);
    map<ll,vll> Pos;
    FOR(i,1,N){
        Cin(A[i]);
       Pos[A[i]].EB(i);
    }
    // for(auto &[u,v]:Pos){
    //     if(SZ(v)<=2) continue;

    // }
    segtree tr(N+5);
    set<ll> vis;
    ll ans1=2,ans2=3;
    ll ans=0;
    FOR(i,1,N-1){
        if(SZ(Pos[A[i]])<=2) continue;
        if(!vis.count(A[i])){
            vis.insert(A[i]);
            // 要给中间一个区间留下第二个
            tr.upd(Pos[A[i]][1]+1,Pos[A[i]].back(),(pll){2,1});
            if(tr.tr[1]>ans){
                ans=tr.tr[1];
                ans1=i+1;
                ans2=tr._find_r(N, [&](ll x){
                    if(x==ans){
                        return true;
                    }
                    return false;
                });
            }
        }else{
            ll id=i;
            if(Pos[A[id]].back()==id) continue;
            tr.upd(id+1,*(++lower_bound(all(Pos[A[id]]),id)),(pll){2,-1});
            // if(Pos[A[id]][SZ(Pos[A[id]])-2]==id){
            //     tr.upd(id+1,Pos[A[id]].back(),(pll){2,-1});
            //     b2.erase(Pos[A[id]].back());
            // }else{
            //     tr.upd(id+1,*(++lower_bound(all(Pos[A[id]]),id)),(pll){2,-1});
            // }
        }
    }
    
    // FOR(i,2,N){
    //     ans=max(ans,tr.ask(i,i));
    // }
    cout<<ans<<"\n";
    cout<<ans1<<" "<<ans2<<"\n";
}
/*
AC 
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887134
1
9
1 2 3 3 2 1 2 3 1

hack:
1
8
1 1 2 2 2 1 3 1

ans:
1
2 3
*/

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

2025-钉耙编程-中国大学生算法设计暑期联赛（9）——1006括号匹配（manacher 解决的是最长回文子串问题）

Posted on 2025-08-15 Edited on 2026-04-06

思路讲解

不难发现，合法字符串必须包含 $()$ 字符。

于是套用manacher就行，注意特判radius=1的奇数长度回文串

FOR(i,0,SZ(res)-1){
    ll radius=res[i];radius/=2;
    if(i&1){
        
        if(radius<2) continue;
        ll id1=i/2,id2=i/2+1,l=id1-radius+1,r=id2+radius-1;
        // l=max(ban[id1]+1,l);
        // r=min(Fban[id2]-1,r);
        ll lans=0;
        if(Pos[id1]!=-1){
            if(Pos[id1]>=l){
                lans=max(lans,Pos[id1]-l+1);
            } 
        }
        if(Fpos[id2]!=-1){
            if(Fpos[id2]<=r){
                lans=max(lans,r-Fpos[id2]+1);
            }
        }
        ans+=lans;
    }else{
        if(radius<2) continue;
        ll id=i/2;
        ll l=id-radius+1,r=id+radius-1;
        // l=max(ban[id]+1,l);
        // r=min(Fban[id]-1,r);
        ll lans=0;
        if(Pos[id]!=-1){
            if(Pos[id]>=l){
                lans=max(lans,Pos[id]-l+1);
            } 
        }
        if(Fpos[id]!=-1){
            if(Fpos[id]<=r){
                lans=max(lans,r-Fpos[id]+1);
            } 
        }
        ans+=min(radius-1,lans);
    }
}

AC代码

https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078

源代码

// 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 << "}"; }
#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;
}
/*

*/
// refer cp algorithm 
// https://cp-algorithms.com/string/manacher.html
vll manacher_odd(string s){
    int n=SZ(s);
    s='$'+s+'^';
    vll p(n+2);
    ll l=0,r=1;     // (l,r) 是开区间，其内部是这个回文子串
    FOR(i,1,n){
        // 保底半径
        p[i]=min(r-i,p[l+r-i]);
        // 暴力外扩
        while (s[i-p[i]]==s[i+p[i]]) { // 因为有哨兵，永不越界
            p[i]++;
        }
        if(i+p[i]>r){
            l=i-p[i],r=i+p[i];
        }
    }
    return vll(p.begin()+1,p.end()-1);
}
vll manacher(const string &s){
    string t;
    for(auto c:s){
        t+='#';     // 千万不要    t+='#'+'c'
        t+=c;
    }
    t+='#';
    auto res=manacher_odd(t);
    return vll(res.begin()+1,res.end()-1);
}
// vector<int> manacher_odd(string s) {
//     int n = s.size();
//     s = "$" + s + "^";
//     vector<int> p(n + 2);
//     int l = 0, r = 1;
//     for(int i = 1; i <= n; i++) {
//         p[i] = min(r - i, p[l + (r - i)]);
//         while(s[i - p[i]] == s[i + p[i]]) {
//             p[i]++;
//         }
//         if(i + p[i] > r) {
//             l = i - p[i], r = i + p[i];
//         }
//     }
//     return vector<int>(begin(p) + 1, end(p) - 1);
// }
// vector<int> manacher(string s) {
//     string t;
//     for(auto c: s) {
//         t += string("#") + c;
//     }
//     auto res = manacher_odd(t + "#");
//     return vector<int>(begin(res) + 1, end(res) - 1);
// }


inline void __(){
    // cin>>N;
    string s;
    cin>>s;
    N=SZ(s);
    auto res=manacher(s);
    vll Pos(N,-1);
    FOR(i,0,N-2){
        if(s[i]=='(' && s[i+1]==')'){
            Pos[i]=i;
        }else{
            if(i==0) continue;
            Pos[i]=Pos[i-1];
        }
    }
    vll Fpos(N,-1);
    ROF(i,N-2,0){
        if(s[i-1]=='(' && s[i]==')'){
            Fpos[i]=i;
        }else{
            if(i==N) continue;
            Fpos[i]=Fpos[i+1];
        }
    }
#ifdef LOCAL
    _print(Fpos);
    _print(Pos);
    _print(res);
    cend;
#endif
    ll ans=0;
    FOR(i,0,SZ(res)-1){
        ll radius=res[i];radius/=2;
        if(i&1){
            
            if(radius<2) continue;
            ll id1=i/2,id2=i/2+1,l=id1-radius+1,r=id2+radius-1;
            // l=max(ban[id1]+1,l);
            // r=min(Fban[id2]-1,r);
            ll lans=0;
            if(Pos[id1]!=-1){
                if(Pos[id1]>=l){
                    lans=max(lans,Pos[id1]-l+1);
                } 
            }
            if(Fpos[id2]!=-1){
                if(Fpos[id2]<=r){
                    lans=max(lans,r-Fpos[id2]+1);
                }
            }
            ans+=lans;
        }else{
            if(radius<2) continue;
            ll id=i/2;
            ll l=id-radius+1,r=id+radius-1;
            // l=max(ban[id]+1,l);
            // r=min(Fban[id]-1,r);
            ll lans=0;
            if(Pos[id]!=-1){
                if(Pos[id]>=l){
                    lans=max(lans,Pos[id]-l+1);
                } 
            }
            if(Fpos[id]!=-1){
                if(Fpos[id]<=r){
                    lans=max(lans,r-Fpos[id]+1);
                } 
            }
            ans+=min(radius-1,lans);
#ifdef LOCAL
    if(i==2){
        debug(r);
        debug(Fpos[id]);
        debug(r-Fpos[id]+1);

    }
#endif
        }
#ifdef LOCAL
    debug(i);
    debug(ans);
#endif
    }
    cout<<ans<<"\n";
}

/*

*/

思路讲解

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²) 预处理所有对）

公式

平移性质

验证

思路讲解

AC代码

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

思路讲解

AC代码

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

这就是经典的"刷油漆"公式——每当 $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$ ）。