Znzryb's Blog

Educational Codeforces Round 188 (Rated for Div. 2)——CF-2204-E. Sum of Digits (and Again)（什么时候不适合反向思考？）

Posted on 2026-03-17 Edited on 2026-04-06

题目大意

题目描述
对于一个严格大于 0 的正整数 $x$ ，按以下过程构造字符串 $S(x)$ ：

初始字符串为空。
将 $x$ 的十进制表示（无前导零）追加到字符串右侧。
如果 $x \le 9$ ，过程结束；否则，将 $x$ 替换为其各位数字之和，并返回步骤 2 继续执行。

例如：

$S(75)$ 为 “75123”（75 的数位和为 12，12 的数位和为 3，依次拼接为 75 + 12 + 3 = 75123）。
$S(30)$ 为 “303”（30 的数位和为 3，拼接为 30 + 3 = 303）。
$S(9)$ 为 “9”。

现在给定一个由数字组成的字符串 $s$ ，要求重新排列该字符串中的所有字符，使其能够构成某个正整数 $x$ 对应的生成字符串 $S(x)$ 。不允许添加或删除字符。如果给定的 $s$ 已经是合法的 $S(x)$ ，可以保持不变。数据保证一定存在至少一种合法的排列方式。

输入格式
第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。
每个测试用例包含一行数字字符串 $s$ （ $1 \le |s| \le 10^5$ ）。
所有测试用例中 $|s|$ 的总和不超过 $10^5$ 。

输出格式
对于每个测试用例，输出重排后的字符串。如果有多个合法答案，输出其中任意一个即可。

样例

Input:
5
12735
1
011
99999299999999299959999999999999
4621467

Output:
75123
1
101
99999999999999999999999999992529
6442167

样例解释

第一个样例 12735：重排为 75123，对应 $x = 75$ 的生成结果（75 -> 12 -> 3）。
第二个样例 1：重排为 1，对应 $x = 1$ 的生成结果。
第三个样例 011：重排为 101，对应 $x = 10$ 的生成结果（10 -> 1）。

思路讲解

首先，对于重排问题，原来的顺序是一点用都没有的，我们只考虑原来的个数！也就是 freq 统计一手频数。

说白了就是，字符串的最后一位数状态很少，但是光枚举那个东西想反推出来一整个答案，难如登天。

说白了，一个东西的状态少，不一定就是去枚举他，因为枚举的越少，难度一般来说越大。所以说，我们一般要枚举的是不多不少的东西。

因此，这个不多不少的东西，是什么呢？结合这个不太好反向思考的这个特性，我们发现，可以枚举第一部分的这个数位和。枚举了第一部分的数位和以后，你会发现，后面的东西全部都定下来了。那后面的东西都定下来了，确定是否能够取得第一部分的这个数位和，是不是也是非常 easy 的呢？

实现上来说：（还是用这个 while condition 写法比较好）

ll d=sum;
while (d>9) {
    ans+=to_string(d);
    d=count_digit(d);
}
ans+=to_string(d);

AC代码

AC
https://codeforces.com/contest/2204/submission/367073785

源代码

/**
 * Problem: E. Sum of Digits (and Again)
 * Contest: Educational Codeforces Round 188 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2204/problem/E
 * Created: 2026-03-17 12:30:35
 * 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() {
    string s;
    cin>>s;
    if (SZ(s)==1) {
        cout<<s<<"\n";
        return;
    }
    vector<ll> freq(12);
    for (auto ch:s) {
        freq[ch-'0']++;
    }
    ll sum_digit=0;
    for (int i=1;i<=9;++i) {
        sum_digit+=freq[i]*i;
    }
    for (ll sum=1;sum<=sum_digit;++sum) {
        vector<ll> lfreq=freq;
        auto count_digit_minus=[&](ll x) {
            ll res=0;
            while (true) {
                if (x==0) {
                    break;
                }
                res+=x%10;
                lfreq[x%10]--;
                x/=10;
            }
            return res;
        };
        auto count_digit=[&](ll x) {
            ll res=0;
            while (true) {
                if (x==0) {
                    break;
                }
                res+=x%10;
                x/=10;
            }
            return res;
        };
        ll d=sum;
        while (d>9) {
            d=count_digit_minus(d);
        }
        count_digit_minus(d);
        if (*min_element(all(lfreq))<0) {
            continue;
        }
        ll lsum_digit=0;
        for (int i=1;i<=9;++i) {
            lsum_digit+=lfreq[i]*i;
        }
// #ifdef LOCAL
//         if (sum==1) {
//             debug1d(freq);
//             debug1d(lfreq);
//             debug(lsum_digit);
//             debug(sum);
//         }
// #endif

        if (lsum_digit==sum) {
            string ans;
            for (int i=9;i>=0;--i) {
                for (int j=1;j<=lfreq[i];++j) {
                    ans.push_back('0'+i);
                }
            }
            ll d=sum;
            while (d>9) {
                ans+=to_string(d);
                d=count_digit(d);
                // if (d<=9) {
                //     ans+=to_string(d);
                //     break;
                // }
            }
            ans+=to_string(d);
            cout<<ans<<"\n";
// #ifdef LOCAL
//             debug1d(freq);
//             debug1d(lfreq);
// #endif

            return;
        }
    }

}

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://codeforces.com/contest/2204/submission/367073785

*/

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

Educational Codeforces Round 188 (Rated for Div. 2)——CF-2204-D. Alternating Path（无向图下，二分图与没有奇数环是等价的）

Posted on 2026-03-16 Edited on 2026-04-06

题目大意

题目总结

给定一个无向图（无重边、无自环），你要给每条边指定一个方向，得到有向图。

定义一条点序列 $v_1,v_2,\dots,v_k$ （长度可任意大，点可重复）是“交替路径”，当且仅当相邻边方向按如下模式交替：

第 1 条边是 $v_1 \to v_2$ ；
第 2 条边是 $v_3 \to v_2$ ；
第 3 条边是 $v_3 \to v_4$ ；
第 4 条边是 $v_5 \to v_4$ ；
之后继续这样“顺、逆、顺、逆”交替。

一个点 $v$ 被称为“beautiful”，如果在原图中所有从 $v$ 出发的路径（不要求简单路径，允许重复点和边）在你定向后都满足上面的交替性质。

目标：对每个测试用例，求最多能让多少个点成为 beautiful。

输入输出要求（题意层面）

输入有多组测试。
每组给 $n,m$ 和 $m$ 条无向边。
需要输出一个整数：该组图中可成为 beautiful 的点数最大值。

样例

Output
2
4
4
1

样例解释

第 1 组输出 2：最多只能让 2 个点满足“从该点出发的任意路径都交替”。
第 2 组输出 4：图中没有边，任意从点出发的路径都平凡成立，所以 4 个点都可 beautiful。
第 3 组输出 4：最多可让 4 个点满足条件。
第 4 组输出 1：只有 1 个点且无边，因此这个点可 beautiful。

思路讲解

不难发现，有奇数环的环，搞出来一个这个矛盾的方案是非常容易的。

当然，这个是反向论证，我们再正向论证一下，为什么我们一定要求这张图是一个二分图。不难发现，一张图上，一个点要么其所有的边都是出去的，要么所有边都是进去的。

你说你如果违反这一要求会怎么样？那么就会一定不符合这个题设要求（这个应该是非常显然的，因为这样子会导致一个 a→b→c 序列，但是题设要求是 a→b<-c）。

AC代码

源代码

/**
 * Problem: D. Alternating Path
 * Contest: Educational Codeforces Round 188 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2204/problem/D
 * Created: 2026-03-16 23:42:43
 * 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 U_step{
    ll u,step/*,fa*/;
};
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<char> vis(N+2);
    vector<char> color(N+2);
    ll ans=0;
    for (int i=1;i<=N;++i) {
        if (vis[i]) {
            continue;
        }
        queue<U_step> q;
        q.push({i,1});
        vis[i]=true;
        color[i]=1;
        vector<ll> cnt(2);
        cnt[color[i]]++;
        bool is_erfen=true;
        while (!q.empty()) {
            auto [u,step]=q.front();
            q.pop();
            for (auto v:g[u]) {
                // if (v==fa) continue;
                if (vis[v]) {
                    if (color[v]!=(step+1)%2) {
                        is_erfen=false;
                    }
                    continue;
                }
                vis[v]=1;
                color[v]=(step+1)%2;
                cnt[color[v]]++;
                q.push({v,step+1});
            }
        }
        if (!is_erfen) continue;
        ans+=max(cnt[0],cnt[1]);
        // ans+=(lans+1)/2;
    }
    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://codeforces.com/contest/2204/submission/367015011

1
6 2
1 5
2 3

1
8 9
1 3
1 4
2 3
2 4
5 6
6 7
7 8
8 5
6 8

*/

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

2026天梯赛选拔赛-L3-1-辉夜的幻想世界

Posted on 2026-03-16 Edited on 2026-04-06

题目大意

题目总结：

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

对任意区间 [l, r]，定义其权值为：

w=\sum_{i=l}^{r}\sum_{j=l}^{r}(a_i \oplus a_j)

其中 ⊕ 表示按位异或。

要求你计算数组中所有非空子区间的权值之和，并对 10^9+7 取模后输出。

输入范围为：

1 ≤ n ≤ 2×10^5
0 ≤ a_i ≤ 10^6

输出一个整数，表示最终答案。

样例：

输入：
6
1 1 4 5 1 4

输出：
422

样例含义：对数组 [1,1,4,5,1,4] 的所有非空子区间分别计算上述双重异或和权值，再把这些权值全部累加，最终结果为 422。

思路讲解

注意，题目中的是非有序对双重求和，所以结果不要忘记乘以一个 2。

vector<vector<ll>> suf_bits(N+2,vector<ll>(26));
vector<vector<ll>> suf_nobits(N+2,vector<ll>(26));
for (ll i=N;i>=1;--i) {
    for (int j=0;j<25;++j) {
      // 注意，我们这里写的是（N-i+1），是指的包含 i 的可以选择的右端点数量
        suf_bits[i][j]=suf_bits[i+1][j]+(A[i]>>j&1)*(N-i+1);
        // (A[i]>>j&1)^1，不要偷懒，不加这个 &1，一定要有 &1 才对
        suf_nobits[i][j]=suf_nobits[i+1][j]+((A[i]>>j&1)^1)*(N-i+1);
    }
}
ll ans=0;
for (int i=1;i<=N;++i) {
    for (int j=0;j<25;++j) {
        if (A[i]>>j&1) {
            ll suf=suf_nobits[i+1][j];
            ll lans=suf%mod*i%mod;
            lans*=(1ll<<j);
            lans%=mod;
            ans+=lans*2;
            ans%=mod;
        }else {
            ll suf=suf_bits[i+1][j];
            ll lans=suf%mod*i%mod;
            lans*=(1ll<<j);
            lans%=mod;
            ans+=lans*2;
            ans%=mod;
        }
    }
}

AC代码

AC
http://10.199.227.101/contest/1005/problem/L3-1/submission-detail/2157

源代码

/**
 * Problem: ${PROBLEM_NAME}
 * Contest: ${PROBLEM_GROUP_NAME}
 * Judge: ${ONLINE_JUDGE_NAME}
 * URL: ${PROBLEM_URL}
 * Created: 2026-03-16 11:05:01
 * 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 debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
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 = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> suf_bits(N+2,vector<ll>(26));
    vector<vector<ll>> suf_nobits(N+2,vector<ll>(26));
    for (ll i=N;i>=1;--i) {
        for (int j=0;j<25;++j) {
            suf_bits[i][j]=suf_bits[i+1][j]+(A[i]>>j&1)*(N-i+1);
            suf_nobits[i][j]=suf_nobits[i+1][j]+((A[i]>>j&1)^1)*(N-i+1);
        }
    }
    ll ans=0;
    for (int i=1;i<=N;++i) {
        for (int j=0;j<25;++j) {
            if (A[i]>>j&1) {
                ll suf=suf_nobits[i+1][j];
                ll lans=suf%mod*i%mod;
                lans*=(1ll<<j);
                lans%=mod;
                ans+=lans*2;
                ans%=mod;
            }else {
                ll suf=suf_bits[i+1][j];
                ll lans=suf%mod*i%mod;
                lans*=(1ll<<j);
                lans%=mod;
                ans+=lans*2;
                ans%=mod;
            }
        }
    }
    ans%=mod;
    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
http://10.199.227.101/contest/1005/problem/L3-1/submission-detail/2157

*/

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

2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

Posted on 2026-03-15 Edited on 2026-04-06

题目大意

给定 $n$ 个人从左到右站成一排。每个人的身份只有两种：诚实者或欺诈者。

诚实者一定说真话。
欺诈者可能说真话，也可能说假话。
第 $i$ 个人会报一个数 $a_i$ ，表示“自己左边有多少个欺诈者”。
额外保证：不存在两个相邻的欺诈者。

任务是统计：一共有多少种身份安排（每个人是诚实者或欺诈者）能够与所有人的发言同时不矛盾。结果对 998244353 取模输出。

输入为两行：

第一行是 $n$ 。
第二行是 $n$ 个整数 $a_i$ 。

输出为一行：满足条件的方案数（取模后）。

样例：

输入：
6
0 0 0 0 0 0

输出：
2

样例含义：6 个人都说自己左边有 0 个欺诈者。在“欺诈者不相邻”的前提下，能成立的身份安排共有 2 种。

思路讲解

// 0 shuo huang
for(int i=1;i<=N;++i){
    if(i==1){
        if(A[i]==0){
            dp[i][1]=1;
            dp[i][0]=1;
        }else{
            dp[i][0]=1;
        }
        continue;
    }
    // 说谎者只能从前面一个的诚实者转移过来
    // 因为不能连续两个都是说谎者
    dp[i][0]=dp[i-1][1];
    if(A[i]==A[i-1]){
      // 可以从诚实者转移过来的条件
        dp[i][1]+=dp[i-1][1];
        dp[i][1]%=mod;
    }
    if(A[i]==A[i-2]+1){
      // 可以从说谎者转移过来的条件
      // 之所以是这个，是因为如果前面一个是说谎者的话，那么再前面一个就是诚实者
        dp[i][1]+=dp[i-1][0];
        dp[i][1]%=mod;
    }
}

AC代码

http://10.199.227.101/contest/1005/problem/L1-7/submission-detail/2146

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]\n";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N;
    cin>>N;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    vector<array<ll,2>> dp(N+2);
    // 0 shu huang
    for(int i=1;i<=N;++i){
        if(i==1){
            if(A[i]==0){
                dp[i][1]=1;
                dp[i][0]=1;
            }else{
                dp[i][0]=1;
            }
            continue;
        }
        dp[i][0]=dp[i-1][1];
        if(A[i]==A[i-1]){
            dp[i][1]+=dp[i-1][1];
            dp[i][1]%=mod;
        }
        if(A[i]==A[i-2]+1){
            dp[i][1]+=dp[i-1][0];
            dp[i][1]%=mod;
        }

    }
    ll ans=dp[N][0]+dp[N][1];
    ans%=mod;
    cout<<ans<<"\n";

    // mod
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*




 */

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

2026天梯赛选拔赛-赛后总结

Posted on 2026-03-15 Edited on 2026-04-06

基本情况

还是有继续进步的这个空间的。

心得感悟

l1-3（while 写成 if）

l1-5（map 效率不够高）

原来使用了这个 map，对于 2e6 的这个数据，1000ms 的时限，可能不是很够。

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
//const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N,mod;
    cin>>N>>mod;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    // map<ll,ll> mp;
    ll ans=0;
    vector<ll> cnt(mod+2);
    for(int i=1;i<=N;++i){
        ll r=A[i]%mod;
        cnt[r]++;
        if (cnt[r]==2) {
            ++ans;
        }
    }
    // for(auto it=mp.begin();it!=mp.end();++it){
    //     if(it->second>=2){
    //         ++ans;
    //     }
    // }
    cout<<ans<<"\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*
AC
http://10.199.227.101/contest/1005/problem/L1-5/submission-detail/2134



 */

l1-7（+，-搞错了）

2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

l1-9（二分范围设置错误）

http://10.199.227.101/contest/1005/problem/L1-9/submission-detail/2144

赛时 r 写了r=N。（确实是比较搞笑了，因为 n 可能比 diff 小，diff 是一个值，N 是数组大小）