@Dmaxiya
2018-08-17T10:13:31.000000Z
字数 4402
阅读 1132
Codeforces
Contests 链接:Codeforces Round #449(Div.2)
过题数:3
排名:549/7594
给定一个长度为 的字符串,有 次操作,对于第 次操作,将区间 上的所有的字符 改为字符 。输出最终的字符串。
所有字符为小写字符。
数据范围很小,直接 暴力。
#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;
}
定义 数,如果无前导零的整数位数为偶数,且这个数是回文的,则这个数就是 数。
给定数字 和 ,求前 小的 数求和 的结果。
手动对前几个 数排序可得:可以发现,所有的 数前半部分是从 开始的连续的自然数,因此只要从 到 枚举自然数,生成对应的 数,求和再对 取膜就是答案,时间复杂度为 。
#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;
}
首先定义字符串 ="What are you doing at the end of the world? Are you busy? Will you save us?"。
对于任意的 ,有 ="What are you doing while sending ""? Are you busy? Will you send ""?"。
对于 次询问,每次询问输出字符串 的第 个字符。
由定义可以知道,字符串的长度呈 指数增长,所以不能递归生成字符串。
通过观察可以发现 ,每个 由五部分组成,所以只要记录这五个部分的起始下标和终止下标,就可以递归找到第 个字符,每个部分的起点和终点都可以由 计算得到,所以从 到 预处理所有字符串五个部分的起点与终点即可。
虽然字符串的长度很快就会爆 ,但是 的范围在 内,所以对于所有超出 的范围,都设为 ,该 应比 的上界 大。
时间复杂度为 。
#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;
}