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;
}