AtCoder Beginner Contest 242（D，E)
D（二叉树搜索）
题目大意就是首先给你一个字符串，代表\(S^0\),然后我们可以操作得到\(S^1,S^2\)等等
我们可以知道\(S^i\)是拿\(S^(i-1)\)经过一系列替换而来的，因为这个字符串只有三种字符串，\(A,B,C\),这个替换方式就是把\(A\)替换成\(BC\),把\(B\)替换成\(CA\),把\(C\)替换成\(AB\)
题目会有\(q\)次询问，询问的是\(S^t\)的第\(k\)个字符
我们可以发现对于每一次替换，字符串的数量都会乘以二，而且原来在第\(x\)的字符，可能会变成\(2\times x\)的一个字符，和\(2\times x+1\)的一个字符，我们可以发现这个和二叉树左右子树很像，而且，这个替换也是有规律的，替换后的前一个字符和原来的字符相差为\(1\),第二个相差为\(2\),所以我们也可以根据位置一直往前找，知道那个序列是最初的序列，或者是已经出现了位置是\(0\)的情况，那么我们可以直接得出答案
对于如果此时的状态已经是最初的状态，即\(S^0\),我们直接输出\(s[k]\)
对于如果此时的\(k\)已经是\(0\)了，说明每一次它都是最开始的那一个字符，不过每一次字符都在改变，具体会改变多少次，需要根据此时的\(t\)而定，我们可以发现每转换一次，第一个字符都会相加一次（这个相加很像加一，然后对三取余，\(0\)代表\(A\),\(1\)代表\(B\),\(2\)代表\(B\),这个转换很像这样的一个循环），所以我们最后返回的就是\((s[0]-'A'+t)%3\)(记得不要忘记取余哦)
对于不是以上两种状态时，我们需要怎么样转移呢
我们这个就用到以上发现这一个转换过程很像二叉树的遍历过程，对于此时是一个\(k\)的字符，那么它对应的上一个序列\(S^{t-1}\)的位置是在\(\lfloor \frac{k}{2} \rfloor\),然后他的符号和\(S^{t-1}\)这个位置的关系是什么呢，还是根据上面发现的，前面一个是相差为\(1\)，后面一个相差为\(2\),因为这个字符串是从\(0\)开始的，所以前面的那一个一定是偶数，故我们可以根据奇偶性来判断这个字符和上一个序列字符的差
所以，我们可以返回\((find(t-1,k/2)+k\pmod2+1)\pmod3\)
具体的可以看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=998244353;
int n,q;
string s;
int find(int t,int k)
{
if(t==0)
{
return (s[k]-'A')%3;
}
else if(k==0)
{
return (s[0]-'A'+t)%3;
}
else
{
return (find(t-1,k/2)+k%2+1)%3;
}
}
void solve()
{
int t,k;
cin>>t>>k;
int p=find(t,k-1);
char ch='A'+p;
//cout<<p<<"\n";
cout<<ch<<"\n";
}
signed main()
{
cin>>s>>q;
while (q--)
{
solve();
}
system ("pause");
return 0;
}
E(组合问题)
这个题目是多种案列
题目给出一个字符串\(s\)和一个该字符串的长度\(n\)
然后问我们它可以构造出多少个满足一下条件的字符串\(t\)
\(1\),\(t\)是一个回文
\(2\),\(t\)的字典序比\(s\)小
题目告诉这个\(t\)是一个回文，我就觉得我们可以不用考虑后面半段了，因为如果前面一半固定了的话，那么后面一半也固定了，并且已经可以判断出字典序的大小了
所以我就通过改变前面半段
对于此时的一个字符，如果我要想让这个字符改变后才让\(t\)变得比\(s\)小，（那么前面的必须是一样的，这个字符只能变得更小，后面的可以改变的可以任意），那么对于这一个字符，可以得到的贡献为\((ch-'A')\times count^{26}\),其中\(count\)是后面还未固定的字符数量
最后，我们还需要考虑一种情况，那就是在前半段都不改变的情况下得到的回文，可不可以比\(s\)小，如果小，也记得要加上去
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=998244353;
string s;
int n;
int t;
int ksm(int x,int p)
{
int res=1;
while (p)
{
if(p&1)
{
res=res*x%mod;
}
x=x*x%mod;
p>>=1;
}
return res%mod;
}
void solve()
{
cin>>n>>s;
string t=s;
s=" "+s;
int ans=0;
int r=(n+1)/2;
string left = t.substr(0, (n + 1) / 2), right = left; // 分为两半
reverse(right.begin(), right.end()); // right为left的翻转，为最后的特判做铺垫
if (n & 1) right.erase(right.begin()); // 奇数长度的特殊处理
for (int i=1;i<=r;i++)
{
int now=s[i]-'A';
int count=(r-i);
ans=(ans+now*ksm(26,count)%mod)%mod;
}
string p=left+right;
p=" "+p;
if(p<=s) ans=(ans+1)%mod;
cout<<ans<<"\n";
}
signed main()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}