题解：P11858 [CCC 2025 Senior] 破译 / Cryptogram Cracking Club

· · 题解

题目简述

一段连续的相同字母可以压缩成字母+出现次数 ak 的形式。

给定压缩后的字符串 s 和整数 c，求 s 无限重复后的第 c 个字符是什么，下标从 0 开始。

主要思路

（虽然题目要求下标从 0 开始，但题解中仍以下标从 1 开始的方式描述字符串）

由于 k 可能超过 10^{12}，所以不能将字符串展开。对于 c，由于下标从 0 开始，也就是说假设 c=10 时，求得是字符串无限重复后的第 11 个字符。并且由于无限重复字符串是有周期性的，所以可以先 c \to c+1，再 c \to (c-1) \bmod |s| + 1。

我们可以维护一个 pair<long long, char> 前缀和数组 pre，pre_{i} 的 first 表示字符串不无限重复时 s_{pre_{i-1}+1} \sim s_{pre_{i}} 都为同一个字符 second。

维护好后，遍历 pre 数组，当 c \le pre_{i} 的 first 时，则表示 c 在 s_{pre_{i-1}+1} \sim s_{pre_{i}} 这个范围内，所以答案就为 c \le pre_{i} 的 second，立即输出并结束循环。

AC Code

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

namespace IO {
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    #define pc putchar
    #define gc getchar
    template<typename T> void read(T &x) { int f = 1; x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }x *= f; }
    template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
    template<typename T> void print(T x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
    template<typename T, typename ...Args> void print(T &x, Args &...args) { print(x); pc(' '); print(args...); }
    inline void readstr(string& x) { x.clear(); char ch = gc(); while (isspace(ch)) ch = gc(); while (!isspace(ch) && ch != EOF) { x.push_back(ch); ch = gc(); } }
    inline void printstr(char* x) { for (int i = 0; i < (int)strlen(x); i++) pc(x[i]); }
    inline void printstr(string& x) { for (auto i = x.begin(); i != x.end(); i++) pc(*i); }
};
using namespace IO;

#define OUT 0
#define MAMBA return
typedef long long ll;
typedef long double db;
const int N = 1e5 + 10;
const int INT_INF = 0x3f3f3f3f;
int man();int main(){MAMBA man();}
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
inline int _abs(int a) { if (a < 0) return -a; return a; }
inline int _pow(int a, int b) { int x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------

// ----------------------------
pair<ll, char> pre[N];
// ----------------------------

int man() {
    string s; readstr(s);
    ll c; read(c);
    // ----------------------------
    ll k, sum = 0;
    int j, cnt = 0;
    for (int i = 0; i < (int)s.length(); ) {
        k = 0;
        j = i + 1;
        while (j < (int)s.length() && isdigit(s[j])) {
            k = k * 10 + s[j] - '0';
            j++;
        }
        pre[cnt + 1] = make_pair(k + pre[cnt].first, s[i]);
        cnt++;
        sum += k;
        i = j;
    } 
    // ----------------------------
    c++;
    c = (c - 1) % sum + 1;
    for (int i = 1; i <= cnt; i++) {
        if (c <= pre[i].first) {
            pc(pre[i].second);
            break;
        }
    }
    MAMBA OUT;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/