C++|AtCoder Beginner Contest 242 C~E 题解 AtCoder|c++|算法|动态规划|算法竞

本文同步发布于：https://goodcoder666.github.io/post/abc242/

ABC242 C~E

[C - 1111gal password](https://atcoder.jp/contests/abc242/tasks/abc242_c)
- 题目大意
- 输入格式
- 输出格式
- 样例
- 分析
- 代码
[D - ABC Transform](https://atcoder.jp/contests/abc242/tasks/abc242_d)
- 题目大意
- 输入格式
- 样例
- - 样例输入1
  - 样例输出1
  - 样例输入2
  - 样例输出2
- 分析
- 代码
- - 代码1（标准）
  - 代码2（优化）
[E - (?x?)](https://atcoder.jp/contests/abc242/tasks/abc242_e)
- 题目大意
- 分析
- 代码

C - 1111gal password 题目大意给定正整数 N N N，求符合下列条件的整数 X X X的个数，对 998244353 998244353 998244353取模：

X X X是 N N N位的正整数
X X X的每一位数都在 [ 1 , 9 ] [1,9] [1,9]之间（0不行）；
X X X的相邻两位数之差的绝对值不超过 1 1 1。

2 ≤ N ≤ 1 0 6 2\le N\le 10^6 2≤N≤106
输入格式 N N N
输出格式输出答案。
样例

N N N	输出
4 4 4	203 203 203
2 2 2	25 25 25
1000000 1000000 1000000	248860093 248860093 248860093

分析根据乘法原理可得，符合条件的 N N N位数最多有 9 N 9^N 9N个，显然不能暴力求解。
但是，由于每一位会被上一位所限制，所以我们很容易想到使用 DP \text{DP} DP求解。
令 f ( i , j ) = X f(i,j)=X f(i,j)=X的第 i i i位上出现 j j j的可能数，易得：
f ( i , j ) = { 1 ( i = 1 ) f ( i ? 1 , 1 ) + f ( i ? 1 , 2 ) ( j = 1 ) f ( i ? 1 , 8 ) + f ( i ? 1 , 9 ) ( j = 9 ) f ( i ? 1 , j ? 1 ) + f ( i ? 1 , j ) + f ( i ? 1 , j + 1 ) ( i > 1 , 2 ≤ j ≤ 8 ) f(i,j)=\begin{cases} 1&(i=1)\\ f(i-1,1)+f(i-1,2)&(j=1)\\ f(i-1,8)+f(i-1,9)&(j=9)\\ f(i-1,j-1)+f(i-1,j)+f(i-1,j+1)&(i>1,2\le j\le8) \end{cases} f(i,j)=??????????1f(i?1,1)+f(i?1,2)f(i?1,8)+f(i?1,9)f(i?1,j?1)+f(i?1,j)+f(i?1,j+1)?(i=1)(j=1)(j=9)(i>1,2≤j≤8)?
因此，直接输出 ∑ i = 1 9 f ( n , i ) \sum\limits_{i=1}^9f(n,i) i=1∑9?f(n,i)即可。
代码本代码运用了滚动表的优化，当然也可以直接开 N × 9 N\times9 N×9大小的数组，但这样会导致内存占用大，不建议使用。

#include #define MOD 998244353 using namespace std; inline void mod(int& x) { if(x >= MOD) x -= MOD; }int dp[9], ldp[9]; int main() { int n; scanf("%d", &n); for(int i=0; i<9; i++) dp[i] = 1; while(--n) { for(int i=0; i<9; i++) ldp[i] = dp[i]; mod(dp[0] += dp[1]), mod(dp[8] += dp[7]); for(int i=1; i<8; i++) mod(dp[i] += ldp[i - 1]), mod(dp[i] += ldp[i + 1]); } int ans = 0; for(int i=0; i<9; i++) mod(ans += dp[i]); printf("%d\n", ans); return 0; }

D - ABC Transform 题目大意给定由A、B、C组成的字符串 S S S。令 S 0 = S S_0=S S0?=S， S i = S i ? 1 S_i=S_{i-1} Si?=Si?1?将A、B、C分别替换为BC、CA、AB的新字符串。
回答 Q Q Q个查询，第 i i i个查询的问题如下：

求 S t i S_{t_i} Sti??的第 k i k_i ki?个字母。

1 ≤ ∣ S ∣ ≤ 1 0 5 1\le |S|\le 10^5 1≤∣S∣≤105
1 ≤ Q ≤ 1 0 5 1\le Q\le 10^5 1≤Q≤105
1 ≤ t i ≤ 1 0 18 1\le t_i\le 10^{18} 1≤ti?≤1018
1 ≤ k i ≤ m i n ( 1 0 18 , S t i 1\le k_i\le min(10^{18},S_{t_i} 1≤ki?≤min(1018,Sti??的长度 ) ) )
输入格式 S S S
Q Q Q
t 1k 1 t_1~k_1 t1? k1?
? \vdots ?
t Qk Q t_Q~k_Q tQ? kQ?
样例样例输入1

ABC 4 0 1 1 1 1 3 1 6

样例输出1

A B C B

S 0 =S_0=~ S0?= ABC
S 1 =S_1=~ S1?= AABCB

样例输入2

CBBAACCCCC 5 57530144230160008 659279164847814847 29622990657296329 861239705300265164 509705228051901259 994708708957785197 176678501072691541 655134104344481648 827291290937314275 407121144297426665

样例输出2

A A C A A

注意小心整数溢出问题。
分析令 f ( t , k ) = ( S 0 f(t,k)=(S_0 f(t,k)=(S0?为AAA..时 S t S_t St?的第 k k k个字母，其中A、B、C分别对应 0 , 1 , 2 0,1,2 0,1,2且 k k k从 0 0 0开始 ) ) )，则通过找规律可得：
f ( t , k ) = { 0 ( t = 0 ) g ( 0 , t ) ( k = 0 ) g ( f ( t ? 1 , ? k 2 ? ) , ( k ? m o d ? 2 ) + 1 ) ( t > 0 , k > 0 ) f(t,k)=\begin{cases} 0 & (t=0)\\ g(0,t) & (k=0)\\ g(f(t-1,\lfloor\frac k2\rfloor),(k\bmod2)+1) & (t>0,k>0) \end{cases} f(t,k)=??????0g(0,t)g(f(t?1,?2k??),(kmod2)+1)?(t=0)(k=0)(t>0,k>0)?
其中 g ( c , x ) g(c,x) g(c,x)为字符 c c c在A,B,C,A,...这个环中 c c c后面的第 x x x个字符，即 g ( c , x ) = ( c + x ) ? m o d ? 3 g(c,x)=(c+x)\bmod3 g(c,x)=(c+x)mod3。
因此，我们只要求出 x x x在 S S S的哪个字符分解后的结果中，再计算 f f f即可。
答案为 a n s = g ( f ( t , ( k ? 1 ) ? m o d ? 2 t ) , S ? k ? 1 2 t ? ) \mathrm{ans}=g(f(t,(k-1)\bmod2^t),S_{\lfloor\frac {k-1}{2t}\rfloor}) ans=g(f(t,(k?1)mod2t),S?2tk?1???)。
代码以下两种示范代码均使用非递归形式，当然也可使用递归形式。
代码1（标准）

#include using namespace std; char s[100005]; int main() { scanf("%s", s); int q; scanf("%d", &q); while(q--) { long long t, k; scanf("%lld%lld", &t, &k); k --; int x = s[t < 64? k >> t: 0] - 'A'; // 防止t太大导致RE while(t > 0 && k > 0) { x = (x + int(k & 1LL) + 1) % 3; k >>= 1LL, t --; } putchar((t + x) % 3 + 'A'); putchar('\n'); } return 0; }

代码2（优化）

#include using namespace std; char s[100005]; int main() { scanf("%s", s); int q; scanf("%d", &q); while(q--) { long long t, k; scanf("%lld%lld", &t, &k); k --; int c = 0; if(t < 64) { c = s[k >> t] - 'A'; k &= (1LL << t) - 1LL; } else c = s[0] - 'A'; for(c+=t%3; k>0; k&=k-1) c ++; putchar(c % 3 + 'A'); putchar('\n'); } return 0; }

E - (?x?) 题目大意对于 T T T个测试点，分别解决下列问题：
给定整数 N N N和字符串 S S S，求合法字符串 X X X的个数，使其符合下列条件：

∣ X ∣ = N |X|=N ∣X∣=N
X X X由大写英文字母组成，是一个回文串
按字典序， X ≤ S X\le S X≤S

1 ≤ T ≤ 250000 1\le T\le 250000 1≤T≤250000
1 ≤ N ≤ 1 0 6 1\le N\le 10^6 1≤N≤106
1 ≤ ∑ N ≤ 1 0 6 1\le \sum N\le 10^6 1≤∑N≤106
∣ S ∣ = N |S|=N ∣S∣=N且由大写英文字母组成。
分析显然，通过 X X X的前 ? N 2 ? \lceil\frac N2\rceil ?2N??个字符就可以确定唯一的 X X X。下面，我们以ABCDE为例：

ABCDE的前 ? N 2 ? \lceil\frac N2\rceil ?2N??个字符分别为ABC
字典序小于ABC的字符串有 28 28 28个（可看作一个 26 26 26进制数来计算）
判断ABCBA是否可行，与ABCDE比较
可行，答案增加 1 1 1得到 29 29 29

【C++|AtCoder Beginner Contest 242 C~E 题解】因此，我们输出 29 29 29。其他情况类似。
代码

#include #define maxn 1000005 #define MOD 998244353 using namespace std; using LL = long long; char s[maxn]; int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d%s", &n, s); long long x = 0LL; int j = n - 1 >> 1; for(int i=0; i<=j; i++) (x = x * 26LL + s[i] - 'A') %= MOD; bool ok = true; while(j >= 0) { if(s[j] < s[n - 1 - j]) break; if(s[j] > s[n - 1 - j]) { ok = false; break; } j --; } if(ok && ++x == MOD) x -= MOD; printf("%lld\n", x); } return 0; }