C - 回文子串

问题陈述

给你一个长度为 $N$ 的字符串 $S$ ，它只由小写英文字母组成。

求将 $S$ 的字符（包括字符串 $S$ 本身）置换后得到的字符串中，不包含个长度为 $K$ 的回文字符串作为子串的字符串的个数。

在这里，当且仅当存在一个不大于 $(N-K)$ 的非负整数 $i$ ，使得每个整数 $j$ 与 $1 \leq j \leq K$ 之间都存在 $T_{i+j} = T_{i+K+1-j}$ 时，长度为 $N$ 的字符串 $T$ 才被称为 “包含一个长度为 $K$ 的回文字符串作为子串”。
这里， $T_k$ 表示字符串 $T$ 的第 $k$ 个字符。

输入样本 1

3 2
aab

样本输出 1

1

将 aab 置换得到的字符串是 aab、 aba 和 baa 。其中， aab 和 baa 包含长度为 $2$ 的回文子串 aa 。
因此，唯一满足条件的字符串是 aba ，所以打印 $1$ 。

分析

首先全排列函数别忘了

sort(a.begin(),a.end())//先排序
do
{
    //里面的a即为排列的结果
}while(next_permutation(a.begin(),a.end())

然后是对题意的理解，这里我错误地想先找出回文串然后判断全排列字符串是否有这个子串，显然错误。判断回文确实很久没练习了，正解应该是对于全排列字符串去枚举k个长度的子串，只要有一次回文那就不计数。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
string s;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k>>s;
    sort(s.begin(),s.end());
    do
    {
        int cnt=1;
        for(int i=0;i<=n-k;i++)
        {
            bool f=true;
            int l=i,r=i+k-1;
            while(l<r)
            {
                if(s[l]!=s[r])f=false;
                l++,r--;
            }
            if(f)cnt=0;
        }
        ans+=cnt;
    }while(next_permutation(s.begin(),s.end()));
    cout<<ans;
    return 0;
}

使用$dfs$去全排列也可以，不过记得去重，这里我试过$vector$但不知为何没有去重，只好用set了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,ans;
string s;
bool st[N];
//vector<string>a;
set<string>a;
void dfs(string s,string str)
{
    if(str.length()==n)
    {
        a.insert(str);
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            dfs(s,str+s[i]);
            st[i]=false;
        }
    }
}
int main()
{
    cin>>n>>k>>s;
    sort(s.begin(),s.end());
    dfs(s,"");
    for(auto &str:a)
    {
        int cnt=1;
        for(int i=0;i<=n-k;i++)
        {
            bool f=true;
            int l=i,r=i+k-1;
            while(l<r)
            {
                if(str[l]!=str[r])f=false;
                l++,r--;
            }
            if(f)cnt=0;
        }
        ans+=cnt;
    }
    //for(auto &w:a)cout<<w<<endl;
    //a.erase(unique(a.begin(),a.end()),a.end());
    //for(auto &w:a)cout<<w<<endl;
    cout<<ans;
    return 0;
}

D - 第n小的回文数

问题陈述

如果一个非负整数 $X$ 的十进制表示（不含前导零）是一个回文数，那么这个非负整数 $X$ 就叫做回文数。
例如， $363$ 、 $12344321$ 和 $0$ 都是回文数。

求 第 $N$ 个最小的回文数。

输入样本 1

46

样本输出 1

363

第 46 个最小的回文数是 $363$ 。

分析

首先列举出具有一定位数的回文数：

• $1$ 个位数的回文数： $1, 2, 3, \dots, 9$ ，有 $9$ 个。
• $2$ 个位数的回文数： $11, 22, 33, \dots, 99$ ，它们有 $9$ 个
• $3$ 个位数的回文数字： $111, 121, 131, \dots, 999$ ，它们有 $90$ 个
• $4$ 个位数的回文数字： $1111, 1221, 1331, \dots, 9999$ ，它们有 $90$ 个
• $\vdots$

规律：数位每增加1位，相应的该数位回文数就会是上位的10倍。（但是代码我没看懂，求第n个回文数我就当作板子背过）

求第n位回文数模板

int find(int x)
{
    int cnt=0,num=9,w=0;
    int half,res,hl=1;
    while(true)
    {
        if(w>0&&w%2==0)num*=10;
        w++;
        if(cnt+num>x)break;
        cnt+=num;
    }
    x-=cnt;
    for(int i=0;i<(w-1)/2;i++)hl*=10;
    half=hl+x;
    res=half;
    if(w%2)half/=10;
    while(half)
    {
        res=res*10+half%10;
        half/=10;
    }
    return res; 
}

注意本题数据范围很大，所以$long long$也会爆掉，用__int128,需要使用快读，输出就转换为字符串输出。

#include<bits/stdc++.h>
#define int __int128
#define endl '\n'
using namespace std;
int n;
int find(int x)
{
    int cnt=0,num=9,w=0;
    int half,res,hl=1;
    while(true)
    {
        if(w>0&&w%2==0)num*=10;
        w++;
        if(cnt+num>x)break;
        cnt+=num;
    }
    x-=cnt;
    for(int i=0;i<(w-1)/2;i++)hl*=10;
    half=hl+x;
    res=half;
    if(w%2)half/=10;
    while(half)
    {
        res=res*10+half%10;
        half/=10;
    }
    return res; 
}
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void print(int x)
{
    if(x/10)print(x/10);
    putchar(x%10+'0');
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    n=read();
    print(find(n-2));
    return 0;
}