CF-1077-C. Restricted Sorting（当发现一个条件取决于两个数字的时候，可以想想，是不是可以只取决于一个数字？）

Posted on 2026-01-30 Edited on 2026-02-19

题目大意

给定长度为 $n$ 的数组 $a$ 。对于整数 $k$ ，我们称其为piggy，当且仅当通过执行以下操作任意次数（可能为零），可以将 $a$ 以非递减顺序排序：

首先，选择两个索引 $i$ 和 $j$ （ $1 \le i < j \le n$ ），使得 $|a_i - a_j| \ge k$ ;
然后，交换 $a_i$ 和 $a_j$ 。

您需要确定最大的piggy整数 $k$ 。如果不存在这样的整数，则输出 $-1$ 。

思路讲解

不难注意到，我们可以选用最大的数字或者最小的数字去做中转站，

乍一看，好像选择最小的数字，还是选择最大的数字，取决于两个数字 $to$ 和 $now$ ？实际上不是的，我们完全可以换着来，比如说：

这样子就实现了 $to$ 用 $mn$ ， $now$ 用这个 $mx$ ，反之亦然，完全可以只根据一个数去选择。

okay，那就行了。我们发现，这个 $to$ 和 $now$ 一定都是和有序序列中的同位置值不一样的点，因此，我们的答案其实就是：（其中 $S$ 为所有和有序序列中的同位置值不一样的点的下标集合）

ans\gets\min_{i\in S}(\max(mx-a_i,a_i-mn))

当然，也可以使用代码中的这个贪心实现。

AC代码

AC
https://codeforces.com/contest/2188/submission/360594620

源代码

/**
 * Problem: C. Restricted Sorting
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/C
 * Created: 2026-01-30 00:31:10
 * Author: Gospel_rock
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <chrono>

#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 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 LD = long 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;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    if (is_sorted(all(A))) {
        cout<<-1<<"\n";
        return;
    }
    vector<ll> a_sort(all(A));
    sort(all(A));
    ll mn=*min_element(all(A)),mx=*max_element(all(A));
    auto check=[&](ll k) {
        for (int i=0;i<N;++i) {
            if (A[i]==a_sort[i]) {
                continue;
            }
            if (abs(A[i]-mn)<k && abs(mx-A[i])<k) {
                return false;
            }
        }
        return true;
    };
    ll l=0,r=mx;
    while (l<r) {
        ll mid=(l+r+1)>>1;
        if (check(mid)) {
            l=mid;
        }else {
            r=mid-1;
        }
    }
    cout<<l<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

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

CF-1077-D. Shortest Statement Ever（没招的时候可以尝试尝试 dp）（高位起到决定性作用）

Posted on 2026-01-30 Edited on 2026-02-19

题目大意

给定两个非负整数 $x$ ， $y$ 。找到两个非负整数 $p$ 和 $q$ ，使得 $p\;\&\;q=0$ ，且 $|x-p|+|y-q|$ 最小化。这里， $\&$ 表示按位与操作。

You are given two non-negative integers $x$ , $y$ . Find two non-negative integers $p$ and $q$ such that $p\;\&\;q=0$ , and $|x-p|+|y-q|$ is minimized. Here, $\&$ denotes the bitwise AND operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.

The only line of each test case contains two non-negative integers $x$ and $y$ ( $0 \le x,y < 2^{30}$ ).

Output

For each test case, output two non-negative integers $p$ and $q$ you found. If there are multiple pairs of $p$ and $q$ satisfying the conditions, you may output any of them.

It can be proven that under the constraints of the problem, any valid solution satisfies $\max(p,q)<2^{31}$ .

7
0 0
1 1
3 6
7 11
4 4
123 321
1073741823 1073741822

0 0
2 1
3 8
6 9
4 3
128 321
1073741824 1073741822

Note

In the first test case, one valid pair would be $p=0$ and $q=0$ , as $0\,\&\,0=0$ and $|x-p|+|y-q|=|0-0|+|0-0|=0$ is the minimum over all pairs of $p$ and $q$ .

In the third test case, one valid pair would be $p=3$ and $q=8$ , as $3\,\&\,8=0$ and $|x-p|+|y-q|=|3-3|+|8-6|=2$ is the minimum over all pairs of $p$ and $q$ . Note that $(p,q)=(3,4)$ is also a valid pair.

思路讲解

我们需要利用这个高位较优的这个特性，

我们设计了一个 dp， $dp_{i,0}$ 表示该位采用 $0,0$ 的配置， $dp_{i,1}$ 表示该位采用 $1,0$ 的配置， $dp_{i,2}$ 表示该位采用 $0,1$ 的配置。

不难写出这样的转移式子：

vector dp(40,vector<Diff_p_q>(3));
dp[36][0]=Diff_p_q(0,0);
dp[36][1]=Diff_p_q(1ll<<36,0);
dp[36][2]=Diff_p_q(0,1ll<<36);
for (int i=35;i>=0;--i) {
    dp[i]=dp[i+1];
    // dp[i][0]   自己重新开始     继承      继承       继承
    dp[i][0]=min({Diff_p_q(0,0),dp[i][0],dp[i+1][1],dp[i+1][2]});
    //             自己重新开始
    dp[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp[i+1][0].p+(1ll<<i),dp[i+1][0].q),
        Diff_p_q(dp[i+1][1].p+(1ll<<i),dp[i+1][1].q),
        Diff_p_q(dp[i+1][2].p+(1ll<<i),dp[i+1][2].q)});
    dp[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp[i+1][0].p,dp[i+1][0].q+(1ll<<i)),
        Diff_p_q(dp[i+1][1].p,dp[i+1][1].q+(1ll<<i)),
        Diff_p_q(dp[i+1][2].p,dp[i+1][2].q+(1ll<<i))});
}

然后你忐忑地提交了，结果 WA on 2。

你使用了对拍，或者其实你不需要使用对拍，你也知道，是因为上面的做法有一些激进，高位上比较好，那自然是比较好的，但是好分大的好和小的好。那么上面的做法，大的好，自然是可以得到的，但是小的好，就不是那么简单的可以得到的了。

_______________[ Testcase #1 INPUT ]_______________
1
78 88

_______________[ Testcase #1 OUTPUT]_______________
78 128
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:40
brute_diff:39
x_br:39
y_br:88

那么对拍也给了我们这个反馈，确实是这样的。

但是我们怎么样得到小的好呢？其实也简单，我们使用同样方法，整一个 dp，但是我们 dp 里存的的那个结构体的构造函数，我们传入一个指示参数，使得只要一出现大于的情况，就给他附上 $diff\gets\text{INF}$ ，使其不够优秀而被淘汰，强制得到这个我们所谓的小的好。

struct Diff_p_q {
    ll diff,p,q;
    bool operator<(const Diff_p_q &o) const {
        return diff<o.diff;
    }
    Diff_p_q()=default;
    explicit Diff_p_q(ll p,ll q,bool no_big=false) {
        if (!no_big) {
            diff=abs(p-X)+abs(q-Y);
            this->p=p;
            this->q=q;
        }else {
            if (p > X || q > Y) {
                diff=INF;
            }else {
                diff=abs(p-X)+abs(q-Y);
            }
            this->p=p;
            this->q=q;
        }

    }
};

一样的 dp 过程。

Diff_p_q Ans=min({dp[0][0],dp[0][1],dp[0][2]});
{
    vector dp2(40,vector<Diff_p_q>(3));
    dp2[36][0]=Diff_p_q(0,0,true);
    dp2[36][1]=Diff_p_q(1ll<<36,0,true);
    dp2[36][2]=Diff_p_q(0,1ll<<36,true);
    for (int i=35;i>=0;--i) {
        dp2[i]=dp2[i+1];
        // dp[i][0]   自己重新开始     继承      继承       继承
        dp2[i][0]=min({Diff_p_q(0,0,true),dp2[i][0],dp2[i+1][1],dp2[i+1][2]});
        //             自己重新开始
        dp2[i][1]=min({Diff_p_q(1ll<<i,0,true),Diff_p_q(dp2[i+1][0].p+(1ll<<i),dp2[i+1][0].q,true),
            Diff_p_q(dp2[i+1][1].p+(1ll<<i),dp2[i+1][1].q,true),
            Diff_p_q(dp2[i+1][2].p+(1ll<<i),dp2[i+1][2].q,true)});
        dp2[i][2]=min({Diff_p_q(0,1ll<<i,true),Diff_p_q(dp2[i+1][0].p,dp2[i+1][0].q+(1ll<<i),true),
            Diff_p_q(dp2[i+1][1].p,dp2[i+1][1].q+(1ll<<i),true),
            Diff_p_q(dp2[i+1][2].p,dp2[i+1][2].q+(1ll<<i),true)});
    }
    Ans=min({Ans,dp2[0][0],dp2[0][1],dp2[0][2]});
}
cout<<Ans.p<<" "<<Ans.q<<"\n";

okay，上面我们已经把我们的思路讲的比较清楚了。

我感觉这个代码对是因为，在确定好高位以后，绝对值距离最小的数一定贴在区间边界：要么贴上边界（低位全 0），要么贴下边界（低位全 1）；中间形态永远不可能比边界更近。

不过我们的第一种 dp 由于没有引入这个 loose 和 tight，实际上计算出来的，并不是严格的 $≥$ ，会有 $<$ 的情况出现，所以我心里也不太踏实。欢迎 hack 我的代码。

AC代码

AC
https://codeforces.com/contest/2188/submission/360662700

源代码

/**
 * Problem: D. Shortest Statement Ever
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/D
 * Created: 2026-01-30 01:18:00
 * Author: Gospel_rock
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <chrono>

#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 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 LD = long 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;

/*
 *
 */
ll X,Y;
struct Diff_p_q {
    ll diff,p,q;
    bool operator<(const Diff_p_q &o) const {
        return diff<o.diff;
    }
    Diff_p_q()=default;
    explicit Diff_p_q(ll p,ll q,bool no_big=false) {
        if (!no_big) {
            diff=abs(p-X)+abs(q-Y);
            this->p=p;
            this->q=q;
        }else {
            if (p > X || q > Y) {
                diff=INF;
            }else {
                diff=abs(p-X)+abs(q-Y);
            }
            this->p=p;
            this->q=q;
        }

    }
};
void Solve() {
    cin >> X >> Y;
    vector dp(40,vector<Diff_p_q>(3));
    dp[36][0]=Diff_p_q(0,0);
    dp[36][1]=Diff_p_q(1ll<<36,0);
    dp[36][2]=Diff_p_q(0,1ll<<36);
    for (int i=35;i>=0;--i) {
        dp[i]=dp[i+1];
        // dp[i][0]   自己重新开始     继承      继承       继承
        dp[i][0]=min({Diff_p_q(0,0),dp[i][0],dp[i+1][1],dp[i+1][2]});
        //             自己重新开始
        dp[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp[i+1][0].p+(1ll<<i),dp[i+1][0].q),
            Diff_p_q(dp[i+1][1].p+(1ll<<i),dp[i+1][1].q),
            Diff_p_q(dp[i+1][2].p+(1ll<<i),dp[i+1][2].q)});
        dp[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp[i+1][0].p,dp[i+1][0].q+(1ll<<i)),
            Diff_p_q(dp[i+1][1].p,dp[i+1][1].q+(1ll<<i)),
            Diff_p_q(dp[i+1][2].p,dp[i+1][2].q+(1ll<<i))});
    }
    Diff_p_q Ans=min({dp[0][0],dp[0][1],dp[0][2]});
    {
        vector dp2(40,vector<Diff_p_q>(3));
        dp2[36][0]=Diff_p_q(0,0,true);
        dp2[36][1]=Diff_p_q(1ll<<36,0,true);
        dp2[36][2]=Diff_p_q(0,1ll<<36,true);
        for (int i=35;i>=0;--i) {
            dp2[i]=dp2[i+1];
            // dp[i][0]   自己重新开始     继承      继承       继承
            dp2[i][0]=min({Diff_p_q(0,0,true),dp2[i][0],dp2[i+1][1],dp2[i+1][2]});
            //             自己重新开始
            dp2[i][1]=min({Diff_p_q(1ll<<i,0,true),Diff_p_q(dp2[i+1][0].p+(1ll<<i),dp2[i+1][0].q,true),
                Diff_p_q(dp2[i+1][1].p+(1ll<<i),dp2[i+1][1].q,true),
                Diff_p_q(dp2[i+1][2].p+(1ll<<i),dp2[i+1][2].q,true)});
            dp2[i][2]=min({Diff_p_q(0,1ll<<i,true),Diff_p_q(dp2[i+1][0].p,dp2[i+1][0].q+(1ll<<i),true),
                Diff_p_q(dp2[i+1][1].p,dp2[i+1][1].q+(1ll<<i),true),
                Diff_p_q(dp2[i+1][2].p,dp2[i+1][2].q+(1ll<<i),true)});
        }
        Ans=min({Ans,dp2[0][0],dp2[0][1],dp2[0][2]});
    }
    cout<<Ans.p<<" "<<Ans.q<<"\n";

#ifdef LOCAL
    if (X>100 || Y>100) {
        return;
    }
    ll brute_diff=INF,x_br,y_br;
    for (int i=0;i<=1000;++i) {
        for (int j=0;j<=1000;++j) {
            if ((i&j)==0) {
                ll lans=abs(i-X)+abs(j-Y);
                if (lans<=brute_diff) {
                    x_br=i;
                    y_br=j;
                    brute_diff=lans;
                }
            }
        }
    }
    if (brute_diff==Ans.diff) {
        return;
    }
    cout<<"WA\n";
    debug(Ans.diff);
    debug(brute_diff);
    debug(x_br);
    debug(y_br);
#endif

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2188/submission/360662700

_______________[ Stress test, testcase 187 OUTPUT]_______________
63 64
[+] SUCCESS: CORRECT ANSWER
_______________[ Stress test, testcase 188 INPUT ]_______________
1
41 9

_______________[ Stress test, testcase 188 OUTPUT]_______________
41 16
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:7
brute_diff:3
x_br:41
y_br:6



_______________[ Testcase #1 INPUT ]_______________
1
78 88

_______________[ Testcase #1 OUTPUT]_______________
78 128
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:40
brute_diff:39
x_br:39
y_br:88




{
        ll dp;
        vector dp2(40,vector<Diff_p_q>(3));
        dp2[0][0]=Diff_p_q(0,0);
        dp2[0][1]=Diff_p_q(1,0);
        dp2[0][2]=Diff_p_q(0,1);
        for (int i=0;i<=35;++i) {
            dp2[i]=dp2[i-1];
            // dp[i][0]   自己重新开始     继承      继承       继承
            dp2[i][0]=min({Diff_p_q(0,0),dp2[i][0],dp2[i-1][1],dp2[i-1][2]});
            //             自己重新开始
            dp2[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp2[i-1][0].p+(1ll<<i),dp2[i-1][0].q),
                Diff_p_q(dp2[i-1][1].p+(1ll<<i),dp2[i-1][1].q),
                Diff_p_q(dp2[i-1][2].p+(1ll<<i),dp2[i-1][2].q)});
            dp2[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp2[i-1][0].p,dp2[i-1][0].q+(1ll<<i)),
                Diff_p_q(dp2[i-1][1].p,dp2[i-1][1].q+(1ll<<i)),
                Diff_p_q(dp2[i-1][2].p,dp2[i-1][2].q+(1ll<<i))});
        }
        Ans=min({Ans,dp2[35][0],dp2[35][1],dp2[35][2]});
    }

*/

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

Edu-CF-184-D2. Removal of a Sequence (Hard Version)（如何优化这个多次的向下取整触发/向下取整分数，）

Posted on 2026-01-29 Edited on 2026-02-19

题目大意

这是问题的简单版本。版本之间的区别在于 $x$ 的约束；在这个版本中， $x \le 10^5$ 。

Polycarp有一个包含从 $1$ 到 $10^{12}$ 的所有自然数的序列。他决定通过执行以下操作$ x $次来修改这个序列：

同时删除所有在位置 $y$ ， $2 \cdot y$ ， $3 \cdot y$ ，…， $m \cdot y \le n$ 的数字，其中$ n $是当前序列的长度。

之后，Polycarp想要在剩余序列中找到第$ k $个数字，或确定结果序列的长度小于$ k $。

帮助Polycarp解决这个问题！

考虑一个例子。假设$ x = 2 $，$ y = 3 $，$ k = 5 $，那么：

红线划掉的数字在第一次操作后被删除，蓝线划掉的数字在第二次操作后被删除。因此，位置$ k = 5 $处的数字是数字$ 10 $。

思路讲解

D1 思路

二分答案。
思路参考了A_G 的代码。
将这道题目转化为二分答案的关键，就在于把找到剩余的第 $ k $ 个数字，转化为找到一个长度为 $len$ 的初始序列，使得其剩余至少 $k$ 个数字，那么不难发现，最小的，符合我们的要求的 $len$ 就是答案。
那么，一次操作会减少多少个数字（长度为 $len$ 时）？其实就是 $\lfloor \frac{len}{y}\rfloor$ 。
因此，简单版本，检查函数也不难书写，直接模拟改过程即可：

auto check=[&](ll len) {
    ll cnt=1;
    while (cnt<=X) {
        if (len<=0) {
            break;
        }
        len-=len/Y;
        ++cnt;
    }
    if (len>=K) {
        return true;
    }
    return false;
};

我们直接使用这个第一问当中的这个 check 函数，由于其是 $O(X)$ ，会超时。我们也可以优化这个二分检查器代码，让其一次性把 $subtract\gets \lfloor \frac{len}{y}\rfloor$ 相同的一起处理。这样子，使用二分的复杂度就是 $O(\sqrt A \log A)$ ，其中 $\sqrt A$ 是一个数字能够拥有的这个因数数量量级。

不过题目作者专门卡了我们二分答案一手，因此必须采用逆向还原的思路。

for (ll i=1;i<=X;++i) {
    ll subtract=0;
    if (len%(Y-1)==0) {
        subtract=len/(Y-1)-1;
        len+=subtract;
    }else {
        subtract=len/(Y-1);
        ll dis=((Y-1)*(subtract+1))-len;
        ll cnt=(dis+subtract-1)/subtract;
        cnt=min(X-i+1,cnt);
        i+=cnt-1;
        len+=cnt*subtract;
    }
    if (len>(ll)1e12) {
        cout<<-1<<"\n";
        return;
    }
}

逆向还原，我们知道，每出现 $y-1$ 个数字，那么就代表有一个数字被删除了，那么一次需要增长的长度就是 $\lfloor \frac{len}{y-1} \rfloor$ ？

这里有一个比较阴的特殊情况，就是 $len \equiv 0 \pmod {y-1}$ ，这个时候，能够增长的长度就是只有 $\lfloor \frac{len}{y-1} \rfloor-1$ 。

我们可以就像最简单的，当序列长度为 $y-1$ ，其达到 $y-1$ 需要多少长度，是 $y$ 吗？显然不是，其需要增长的就是 0 长度。

我们和优化二分的时候采用一样的思路，每次增长相同长度的，一起操作，这样子时间复杂度就是 $O(\sqrt A)$ 。

具体而言，就是先计算需要增长的长度 $subtract$ ，然后计算需要能够以 $subtract$ 继续增长的次数，即 $cnt$ ，然后 $cnt\gets \min(cnt,X-i+1)$ ，避免加上 $cnt$ 超过操作次数限制。不断重复这个过程，直到达到操作次数 $X$ 。

AC代码

AC
https://codeforces.com/contest/2169/submission/360686378

源代码

/**
 * Problem: D2. Removal of a Sequence (Hard Version)
 * Contest: Educational Codeforces Round 184 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2169/problem/D2
 * Created: 2026-01-29 21:32:03
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <chrono>

#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 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 LD = long 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;

/*
 *
 */

void Solve() {
    ll X,Y,K;
    cin >> X >> Y >> K;
    // X 是删除次数，Y 是删除参数，K 是查询的位置
    if (Y==1) {
        cout<<-1<<"\n";
        return;
    }
    ll len=K;
    if (K<Y) {
        cout<<K<<"\n";
        return;
    }
    for (ll i=1;i<=X;++i) {
        ll subtract=0;
        if (len%(Y-1)==0) {
            subtract=len/(Y-1)-1;
            len+=subtract;
        }else {
            subtract=len/(Y-1);
            ll dis=((Y-1)*(subtract+1))-len;
            ll cnt=(dis+subtract-1)/subtract;
            cnt=min(X-i+1,cnt);
#ifdef LOCAL
            assert(cnt>0);
#endif
            i+=cnt-1;
            len+=cnt*subtract;
        }
        if (len>(ll)1e12) {
            cout<<-1<<"\n";
            return;
        }
    }
    cout<<len<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2169/submission/360686378

*/

TLE

https://codeforces.com/contest/2169/submission/360461585

二分 TLE 代码

/**
 * Problem: D2. Removal of a Sequence (Hard Version)
 * Contest: Educational Codeforces Round 184 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2169/problem/D2
 * Created: 2026-01-29 15:52:48
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>

#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 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 LD = long 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;

/*
 *
 */

void Solve() {
    ll X,Y,K;
    // X 是删除次数，Y 是删除参数，K 是查询的位置
    cin >> X >> Y >> K;
    if (Y==1) {
        cout<<-1<<"\n";
        return;
    }
    // X=min((ll)1e5,X);
    auto check=[&](ll len) {
        if (len<Y) {
            if (len>=K) {
                return true;
            }
            return false;
        }
        for (ll i=1;i<=X;++i){
            if (len<=0) {
                break;
            }
            // 我们去计算这个 len/Y 能除多少次，就不是 Y 了？
            ll subtract=len/Y;
            if (subtract<=0) {
                break;
            }
            // 不一定所有的都是向上取整关系，比如说这道题目 rem 为 0，也是可以减 1 次。
            ll rem=len-(Y*subtract-1);
            ll cnt=(rem+subtract-1)/subtract;
            cnt=min(X-(i-1),cnt);
#ifdef LOCAL
            assert(cnt>0);
#endif
            i+=cnt-1;
            len-=cnt*subtract;
        }
        if (len>=K) {
            return true;
        }
        return false;
    };
    auto range=views::iota(1ll,(ll)1e12+1ll)|views::reverse;
    // #ifdef LOCAL
    //     debug(*range.begin());
    // #endif

    auto it=ranges::partition_point(range,check);
    if (it==range.begin()) {
        cout<<-1<<"\n";
        return;
    }
    ll ans=*ranges::prev(it);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

1
2 3 5

*/

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

Edu-CF-184-D1. Removal of a Sequence (Easy Version)（把找到剩余的第 k 个数字，转化为找到一个长度为 len 的初始序列，使得其剩余至少 k 个数字。）

Posted on 2026-01-29 Edited on 2026-02-19

题目大意

这是问题的简单版本。版本之间的区别在于 $x$ 的约束；在这个版本中， $x \le 10^5$ 。

Polycarp有一个包含从 $1$ 到 $10^{12}$ 的所有自然数的序列。他决定通过执行以下操作$ x $次来修改这个序列：

同时删除所有在位置 $y$ ， $2 \cdot y$ ， $3 \cdot y$ ，…， $m \cdot y \le n$ 的数字，其中$ n $是当前序列的长度。

之后，Polycarp想要在剩余序列中找到第$ k $个数字，或确定结果序列的长度小于$ k $。

帮助Polycarp解决这个问题！

考虑一个例子。假设$ x = 2 $，$ y = 3 $，$ k = 5 $，那么：

红线划掉的数字在第一次操作后被删除，蓝线划掉的数字在第二次操作后被删除。因此，位置$ k = 5 $处的数字是数字$ 10 $。

思路讲解

二分答案。

思路参考了A_G 的代码。

将这道题目转化为二分答案的关键，就在于把找到剩余的第 $ k $ 个数字，转化为找到一个长度为 $len$ 的初始序列，使得其剩余至少 $k$ 个数字，那么不难发现，最小的，符合我们的要求的 $len$ 就是答案。

那么，一次操作会减少多少个数字（长度为 $len$ 时）？其实就是 $\lfloor \frac{len}{y}\rfloor$ 。

因此，简单版本，检查函数也不难书写，直接模拟改过程即可：

auto check=[&](ll len) {
    ll cnt=1;
    while (cnt<=X) {
        if (len<=0) {
            break;
        }
        len-=len/Y;
        ++cnt;
    }
    if (len>=K) {
        return true;
    }
    return false;
};

AC代码

AC
https://codeforces.com/contest/2169/submission/360432707

源代码

/**
 * Problem: D1. Removal of a Sequence (Easy Version)
 * Contest: Educational Codeforces Round 184 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2169/problem/D1
 * Created: 2026-01-29 12:53:23
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#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 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 LD = long 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;

/*
 *
 */

void Solve() {
    ll X,Y,K;
    // X 是删除次数，Y 是删除参数，K 是查询的位置
    cin >> X >> Y >> K;
    if (Y==1) {
        cout<<-1<<"\n";
        return;
    }
    auto check=[&](ll len) {
        ll cnt=1;
        while (cnt<=X) {
            if (len<=0) {
                break;
            }
            len-=len/Y;
            ++cnt;
        }
        if (len>=K) {
            return true;
        }
        return false;
    };
    auto range=ranges::views::iota(1ll,(ll)1e12+1)|views::reverse;
    auto it=ranges::partition_point(range,check);
    if (it==range.begin()) {
        cout<<-1<<"\n";
        return;
    }
    ll ans=*ranges::prev(it);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2169/submission/360432707

*/

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

Edu-CF-184-C. Range Operation（仅有一次的，进行奇奇怪怪操作的，均可以用 dp 解决）（式子中有 r，l，一定要想办法分离）

Posted on 2026-01-28 Edited on 2026-02-19

题目大意

CF2169C Range Operation

题目描述

给定一个长度为 $n$ 的整数数组 $a$ 。

你可以进行以下操作：选择一个区间 $[l, r]$ （ $1 \le l \le r \le n$ ），并将区间内的元素 $a_l, a_{l+1}, \dots, a_r$ 全部替换为 $l + r$ 。

你的任务是计算，在最多允许进行一次上述操作的情况下，数组的和可能达到的最大值。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ （ $1 \le n \le 2 \cdot 10^5$ ）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $0 \le a_i \le 2n$ ）。

输入额外限制：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数，表示在至多进行一次操作后数组的最大和。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

在第一个样例中，可以对子数组 $[3,3]$ 执行操作，得到数组 $[2, 5, 6]$ ，其和为 $13$ 。

在第二个样例中，不需进行任何操作。

在第三个样例中，可以对子数组 $[1,4]$ 执行操作，得到数组 $[5, 5, 5, 5]$ ，其和为 $20$ 。

在第四个样例中，可以对子数组 $[2,3]$ 执行操作，得到数组 $[3, 5, 5, 9, 10]$ ，其和为 $32$ 。

由 ChatGPT 5 翻译

思路讲解

类似于求解最大字段和的 dp。

思路参考了 starsilk 的代码。

首先，我们必须要把 $r,l$ 两者分开。

我们就会发现，总答案就可以写为：（ $S_{x}$ 表示 $x$ 的前缀和）

ans=S_{l-1}+l(1-l)+S_n-S_{r}+r(r+1)

这个明显可以使用这个 dp，因为我们只需要最优化 $S_{l-1}+l(1-l)$ 这个值，就直接最优化了左端点。而右端点的转移，一旦不用考虑这个左端点是不是最优的，就容易多了。

那我们定义， $dp_{i,0}$ 为前缀和（操作前）， $dp_{i,1}$ 表示从 $i$ 及之前开始转化的最大化 $S_{l-1}+l(1-l)$ 值（可以理解为操作中，但是不严谨）， $dp_{i,2}$ 表示 $i$ 以及之前转化结束，所能达到的最大和（操作后）。

之所以定义三个状态，而不是两个，是为了避免重复操作。

dp_{i,0}=dp_{i-1,0}+a_i\\ dp_{i,1}=\max(dp_{i-1,1},dp_{i-1,0}+i(1-i))\\ dp_{i,2}=\max(dp_{i-1,2}+a_i,dp_{i,1}+i(i+1))

这个状态转移式子中 $dp_{i,2}$ 之所以有两个来源，就是其状态定义，在 $i$ 之前转化结束一个来源，在 $i$ 结束一个来源。

$i$ 定义为这个长整型，小心溢出。

// dp[i][0] 就是前缀和，dp[i][1]是这个预备变量
for (ll i=1;i<=N;++i) {
    dp[i][0]=dp[i-1][0]+A[i];
    // dp[i][1] 代表从 i 开始变换，我们能得到的最大值（左端）
    // 即 S[i-1]+i*(1-i) 的最大值
    dp[i][1]=max(dp[i-1][1],dp[i-1][0]+i*(1-i));
    dp[i][2]=max(dp[i-1][2]+A[i],dp[i][1]+i*(i+1));
}
cout<<max(dp[N][0],dp[N][2])<<"\n";

AC代码

AC
https://codeforces.com/contest/2169/submission/360407408

源代码

/**
 * Problem: C. Range Operation
 * Contest: Educational Codeforces Round 184 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2169/problem/C
 * Created: 2026-01-28 19:45:52
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#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 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 LD = long 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;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> dp(N+2,vector<ll>(3));
    // (r-l+1)*(r+l)
    //
    // dp[i][0] 就是前缀和，dp[i][1]是这个预备变量
    for (ll i=1;i<=N;++i) {
        dp[i][0]=dp[i-1][0]+A[i];
        // dp[i][1] 代表从 i 开始变换，我们能得到的最大值（左端）
        // 即 S[i-1]+i*(1-i) 的最大值
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]+i*(1-i));
        dp[i][2]=max(dp[i-1][2]+A[i],dp[i][1]+i*(i+1));
    }
    cout<<max(dp[N][0],dp[N][2])<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2169/submission/360407408


vector<ll> pre_sum(N+2);
    partial_sum(A.begin()+1,A.begin()+N+1,pre_sum.begin()+1);
    ll up_pos=1;
    for (int i=1;i<=N;++i) {
        up_pos=max(up_pos,(ll)i);
        for (int j=up_pos;j<=N;++j) {
            up_pos=j;
            ll len=j-i+1;
            ll add=len*(i+j);
            if (i==j) {
                if (add>A[i]) {

                }
            }else {
                if () {

                }
            }
        }
    }
*/