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\n", ss+1);
return 0;
}
B. Chtholly's request
题意
定义\(zcy\ number\)为长度为偶数的回文的数字,对于给定的\(k\)和\(p\),求出最小的\(k\)个\(zcy\ number\)的数的和\(\mod p\)的值(\(k\leq 1e5, p\leq 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\n", sum);
return 0;
}
C. Nephren gives a riddle
题意
有递推式
\(f_0=s\)
\(f_i=Af_{i-1}Bf_{i-1}C\)
问\(f_n\)的第\(k\)位上的字符
\(n\leq 1e5, k\leq 1e18\)
思路
定义\(l_i\)为\(f_i\)的长度,则\(l_i=2*l_{i-1}+l_A+l_B+l_C\),可以据此估算一下,\(l_{53} = 1288029493427961788\),这就是考虑的上限了。
\(n\)的值那么大完全就是唬人的,预处理一下即可。
因为当\(n\gt 53\)时,有意义的部分必然形如\(AA...Af_{53}\)(前面是\(n-53\)个\(A\)),只需判断答案是落在前面的\(A\)中还是后面的\(f_{53}\)中即可。
再考虑问题本身,是个很优美的递归的形式。
可以写个优美的循环_(:з」∠)_
记\(len1=f_n,len2=f_{n-1}\)
-
\(k\gt len1\rightarrow\)无解
-
\(k\leq l_A\rightarrow\)答案在\(A\)中
-
\(l_A+len2\lt k\leq l_A+len2+l_B\rightarrow\)答案在\(B\)中
-
\(k\gt len1-l_C\rightarrow\)答案在\(C\)中
-
其他情况\(\rightarrow\)答案在\(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;
}