A. Scarborough Fair
题意
对给定的长度为(n)的字符串进行(m)次操作，每次将一段区间内的某一个字符替换成另一个字符。
思路
直接模拟
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int n, m, s,t ; char c1, c2;
char ss[110];
scanf("%d%d", &n, &m);
scanf("%s", ss+1);
for (int i = 0; i < m; ++i) {
scanf("%d%d %c %c", &s, &t, &c1, &c2);
for (int j = s; j <= t; ++j) {
if (ss[j] == c1) ss[j] = c2;
}
}
printf("%s
", ss+1);
return 0;
}
B. Chtholly's request
题意
定义(zcy number)为长度为偶数的回文的数字，对于给定的(k)和(p)，求出最小的(k)个(zcy number)的数的和(mod p)的值（(kleq 1e5, pleq 1e9)）
思路
稍微估算一下，
长度为(2)的有(9)个，
长度为(4)的有(90)个，
长度为(6)的有(900)个，
……
好的，题目要求的所有的(zcy number)都在(long long)范围内，接下来就随便怎么做了。
可直接生成。用数组。每次从中间往两边增。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int k, p, ans[20];
LL num(int* ans, int tot) {
LL ret = 0;
for (int i = (tot<<1); i >= 1; --i) (ret *= 10) += ans[i];
return ret % p;
}
int main() {
scanf("%d %d", &k, &p);
ans[2] = ans[1] = 1;
LL sum = 11 % p, tot = 1;
for (int i = 1; i < k; ++i) {
int temp = tot;
while (temp >= 1 && ans[temp] == 9) {
ans[(tot<<1)-temp+1] = ans[temp] = 0;
--temp;
}
if (!temp) {
++tot;
ans[1] = ans[tot<<1] = 1;
}
else ++ans[temp], ++ans[(tot<<1)-temp+1];
(sum += num(ans, tot)) %= p;
}
printf("%I64d
", sum);
return 0;
}
C. Nephren gives a riddle
题意
有递推式
(f_0=s)
(f_i=Af_{i-1}Bf_{i-1}C)
问(f_n)的第(k)位上的字符
(nleq 1e5, kleq 1e18)
思路
定义(l_i)为(f_i)的长度，则(l_i=2*l_{i-1}+l_A+l_B+l_C)，可以据此估算一下，(l_{53} = 1288029493427961788)，这就是考虑的上限了。
(n)的值那么大完全就是唬人的，预处理一下即可。
因为当(ngt 53)时，有意义的部分必然形如(AA...Af_{53})（前面是(n-53)个(A)），只需判断答案是落在前面的(A)中还是后面的(f_{53})中即可。
再考虑问题本身，是个很优美的递归的形式。
可以写个优美的循环_(:з」∠)_
记(len1=f_n,len2=f_{n-1})
-
(kgt len1 ightarrow)无解
-
(kleq l_A ightarrow)答案在(A)中
-
(l_A+len2lt kleq l_A+len2+l_B ightarrow)答案在(B)中
-
(kgt len1-l_C ightarrow)答案在(C)中
-
其他情况( ightarrow)答案在(f_{n-1})中
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[110] = "What are you doing at the end of the world? Are you busy? Will you save us?";
char A[110] = "What are you doing while sending "";
char B[110] = ""? Are you busy? Will you send "";
char C[110] = ""?";
int l1 = 34, l2 = 32, l3 = 2;
LL arr[60] = {75,218,504,1076,2220,4508,9084,18236,36540,73148,146364,292796,585660,1171388,2342844,4685756,9371580,18743228,37486524,74973116,149946300,299892668,599785404,1199570876,2399141820,4798283708,9596567484,19193135036,38386270140,76772540348,153545080764,307090161596,614180323260,1228360646588,2456721293244,4913442586556,9826885173180,19653770346428,39307540692924,78615081385916,157230162771900,314460325543868,628920651087804,1257841302175676,2515682604351420,5031365208702908,10062730417405884,20125460834811836,40250921669623740,80501843339247548,161003686678495164,322007373356990396,644014746713980860,1288029493427961788};
int main() {
int q;
scanf("%d", &q);
while (q--) {
int n; LL k;
scanf("%d%I64d", &n, &k);
if (n > 53) {
LL len = (n-53) * l1;
if (k <= len) {
k = (k-1) % l1 + 1;
cout << A[k-1]; continue;
}
else {
k -= len;
n = 53;
}
}
if (k > arr[n]) { cout << '.'; continue; }
while (true) {
if (n == 0) { cout << s[k-1]; break; }
LL len1 = arr[n], len2 = arr[n-1];
if (k <= l1) { cout << A[k-1]; break; }
else if (k >= len1-l3+1) { cout << C[k-len1+l3-1]; break; }
else if (k > l1+len2 && k <= l1+len2+l2) { cout << B[k-l1-len2-1]; break; }
else {
--n;
if (k <= l1+len2) k -= l1;
else k -= (l1+len2+l2);
}
}
}
puts("");
return 0;
}