Codeforces Round #449(Div.2)

Codeforces

Contests 链接：Codeforces Round #449(Div.2)
过题数：3
排名：549/7594

A. Scarborough Fair

题意

给定一个长度为 $n$ 的字符串，有 $m$ 次操作，对于第 $i$ 次操作，将区间 $[l_i, r_i]$ 上的所有的字符 $c_{i1}$ 改为字符 $c_{i2}$。输出最终的字符串。

数据范围

$1\leq n,m\leq100\\1\leq l\leq r\leq n$
所有字符为小写字符。

题解

数据范围很小，直接 $O(nm)$ 暴力。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 200;
int n, m, l, r;
char ch1[5], ch2[5];
char str[maxn];
void change(int l, int r, char c1, char c2) {
    for(int i = l; i <= r; ++i) {
        if(str[i] == c1) {
            str[i] = c2;
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%df", &n, &m) != EOF) {
        scanf("%s", str + 1);
        for(int i = 0; i < m; ++i) {
            scanf("%d%d%s%s", &l, &r, ch1, ch2);
            change(l, r, ch1[0], ch2[0]);
        }
        printf("%s\n", str + 1);
    }
    return 0;
}

B. Chtholly's request

题意

定义 $zcy$ 数，如果无前导零的整数位数为偶数，且这个数是回文的，则这个数就是 $zcy$ 数。
给定数字 $k$ 和 $p$，求前 $k$ 小的 $zcy$ 数求和 $\mod p$ 的结果。

数据范围

$1\leq k\leq 10^5\\1\leq p\leq 10^9$

题解

手动对前几个 $zcy$ 数排序可得：$11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441\cdots$可以发现，所有的 $zcy$ 数前半部分是从 $1$ 开始的连续的自然数，因此只要从 $1$ 到 $k$ 枚举自然数，生成对应的 $zcy$ 数，求和再对 $p$ 取膜就是答案，时间复杂度为 $O(k)$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, p;
LL ten[18];
LL num[maxn];
LL get_num(LL thenum) {
    LL nn = thenum;
    int dig = 0;
    while(nn != 0) {
        ++dig;
        nn /= 10;
    }
    thenum *= ten[dig];
    dig *= 2;
    for(int i = dig / 2; i < dig; ++i) {
        thenum += thenum / ten[i] % 10 * ten[dig - i - 1];
    }
    return thenum;
}
void Init() {
    LL thenum = 1;
    int cnt = 0;
    while(cnt < n) {
        num[cnt++] = get_num(thenum);
        ++thenum;
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    ten[0] = 1;
    for(int i = 1; i < 18; ++i) {
        ten[i] = ten[i - 1] * 10;
    }
    while(scanf("%d%d", &n, &p) != EOF) {
        Init();
        LL ans = 0;
        for(int i = 0; i < n; ++i) {
            ans = (ans + num[i]) % p;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

C. Nephren gives a riddle

题意

首先定义字符串 $f_0$="What are you doing at the end of the world? Are you busy? Will you save us?"。
对于任意的 $i\geq1$，有 $f_i$="What are you doing while sending "$f_{i-1}$"? Are you busy? Will you send "$f_{i-1}$"?"。
对于 $q$ 次询问，每次询问输出字符串 $f_n$ 的第 $k$ 个字符。

数据范围

$1\leq q\leq10\\0\leq n\leq10^5\\1\leq k\leq 10^{18}$

题解

由定义可以知道，字符串的长度呈 $2^n$ 指数增长，所以不能递归生成字符串。
通过观察可以发现 $len_{f_i}=34+len_{f_{i-1}}+32+len_{f_{i-1}}+2$，每个 $f_i$ 由五部分组成，所以只要记录这五个部分的起始下标和终止下标，就可以递归找到第 $k$ 个字符，每个部分的起点和终点都可以由 $f_{i-1}$ 计算得到，所以从 $1$ 到 $10^5$ 预处理所有字符串五个部分的起点与终点即可。
虽然字符串的长度很快就会爆 $long\quad long$，但是 $k$ 的范围在 $10^{18}$ 内，所以对于所有超出 $10^{18}$ 的范围，都设为 $INF$，该 $INF$ 应比 $k$ 的上界 $10^{18}$ 大。
时间复杂度为 $O(n)$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
using namespace std;
#define LL long long
const LL INF = 1e18 + 100;
const int maxn = 100000 + 100;
struct Node {
    LL ls, le, ms, me, rs, re;
    LL len;
};
int T;
LL n, k;
char str0[100] = " What are you doing at the end of the world? Are you busy? Will you save us?";
char strL[100] = " What are you doing while sending \"";
char strM[100] = " \"? Are you busy? Will you send \"";
char strR[100] = " \"?";
Node node[maxn];
void Init() {
    node[0].len = 75;
    for(int i = 1; i < maxn; ++i) {
        node[i].ls = 1;
        node[i].le = 34;
        node[i].ms = node[i - 1].len + 34 + 1;
        node[i].ms = min(node[i].ms, INF);
        node[i].me = node[i].ms + 31;
        node[i].me = min(node[i].me, INF);
        node[i].rs = node[i].me + node[i - 1].len + 1;
        node[i].rs = min(node[i].rs, INF);
        node[i].re = node[i].rs + 1;
        node[i].re = min(node[i].re, INF);
        node[i].len = node[i].re;
    }
}
char dfs(LL n, LL k) {
    if(n == 0) {
        if(k <= node[0].len) {
            return str0[k];
        }
        return '.';
    }
    if(k <= 34) {
        return strL[k];
    }
    if(k < node[n].ms) {
        return dfs(n - 1, k - 34);
    }
    if(k <= node[n].me) {
        return strM[k - node[n].ms + 1];
    }
    if(k < node[n].rs) {
        return dfs(n - 1, k - node[n].me);
    }
    if(k <= node[n].re) {
        return strR[k - node[n].rs + 1];
    }
    return '.';
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    Init();
    while(scanf("%d", &T) != EOF) {
        while(T--) {
            scanf("%I64d%I64d", &n, &k);
            printf("%c", dfs(n, k));
        }
        printf("\n");
    }
    return 0;
}