这道题目用C++怎么做？

问题描述

这道题目用C++怎么做？

一个字符串t是半回文的条件是，对于所有的奇数i(1≤i≤|t|+12)，ti = t|t| ? i + 1 始终成立，|t|表示字符串t的长度。下标从1开始。例如"abaa", "a", "bb", "abbbaa"都是半回文，而"ab", "bba"和"aaabaa"则不是。
现在有一个字符串s，只由小写字母a,b构成，还有一个数字k。现在要求找出s的半回文子串中字典序排在第k位的串，字符串可以是一样，只要所在的位置不同就是不一样的串。
样例解释：
这个样例中半回文子串是 a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab,bab, bb, bbab, bbabaab (按照字典序排序).

解决方案

我们可以先考虑O(n^2)预处理出所有的半回文串．我们假设DP[i][j]=true表示子串s[i,j]是半回文子串，反之，不是半回文子串．那么可以得出dp[i+2][j-2]也是半回文串，所以可以得出状态转移方程dp[i][j]=dp[i+2][j-2].　然后可以考虑以s[i]开头的所有半回文串，建一棵Trie（字典树），然后就可以通过DFS搜索出第ｋ小的半回文子串．这部分的时间复杂度也为kO(n^2),所以总的算法时间复杂度为kO(n^2).k为字符串的字符种类．

解决方案二：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int N = 5005;
char s[N];
int k,n,l,r;
bool dp[N][N];
int vis[N];
string ans;

struct Tree
{
Tree()
{
val = 0;
memset(next,0,sizeof next);
}
int val;
Tree *next[2];
}*tree_head;

void init()
{
tree_head = new Tree();
n = strlen(s);
memset(dp,false,sizeof dp);
for(int i = n - 1; i >= 0; --i)
{
dp[i][i] = true;
vis[i] = i;
for(int j = i + 1; j < n; ++j)
{
if(s[i] == s[j])
{
if(i + 2 >= j - 2)
dp[i][j] = true;
else dp[i][j] = dp[i + 2][j - 2];
}
if(dp[i][j]) vis[i] = j;
}
}
}

void insert_tree(Tree *ptemp, char *s)
{
if(*s == '') return;
if(r > vis[l]) return;
int c = *s - 'a';
if(ptemp->next[c] == NULL)
ptemp->next[c] = new Tree();
if(dp[l][r]) ptemp->next[c]->val++;
r++;
insert_tree(ptemp->next[c], s + 1);
}

void dfs(Tree *ptemp)
{
string temp = ans;
if(k > 0 && ptemp->next[0])
{
k -= ptemp->next[0]->val;
ans = ans + 'a';
dfs(ptemp->next[0]);
}
if(k > 0 && ptemp->next[1])
{
ans = temp;
k -= ptemp->next[1]->val;
ans = ans + 'b';
dfs(ptemp->next[1]);
}
}

void solve()
{
scanf("%s %d",s,&k);
init();
for(int i = 0; i < n; ++i)
{
l = r = i;
insert_tree(tree_head,s + i);
}
dfs(tree_head);
cout << ans << endl;
}

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
solve();

return 0;
}

解决方案三：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int N = 5005;
char s[N];
int k,n,l,r;
bool dp[N][N];
int vis[N];
string ans;

struct Tree
{
Tree()
{
val = 0;
memset(next,0,sizeof next);
}
int val;
Tree *next[2];
}*tree_head;

void init()
{
tree_head = new Tree();
n = strlen(s);
memset(dp,false,sizeof dp);
for(int i = n - 1; i >= 0; --i)
{
dp[i][i] = true;
vis[i] = i;
for(int j = i + 1; j < n; ++j)
{
if(s[i] == s[j])
{
if(i + 2 >= j - 2)
dp[i][j] = true;
else dp[i][j] = dp[i + 2][j - 2];
}
if(dp[i][j]) vis[i] = j;
}
}
}

void insert_tree(Tree *ptemp, char *s)
{
if(*s == '') return;
if(r > vis[l]) return;
int c = *s - 'a';
if(ptemp->next[c] == NULL)
ptemp->next[c] = new Tree();
if(dp[l][r]) ptemp->next[c]->val++;
r++;
insert_tree(ptemp->next[c], s + 1);
}

void dfs(Tree *ptemp)
{
string temp = ans;
if(k > 0 && ptemp->next[0])
{
k -= ptemp->next[0]->val;
ans = ans + 'a';
dfs(ptemp->next[0]);
}
if(k > 0 && ptemp->next[1])
{
ans = temp;
k -= ptemp->next[1]->val;
ans = ans + 'b';
dfs(ptemp->next[1]);
}
}

void solve()
{
scanf("%s %d",s,&k);
init();
for(int i = 0; i < n; ++i)
{
l = r = i;
insert_tree(tree_head,s + i);
}
dfs(tree_head);
cout << ans << endl;
}

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
solve();

return 0;
}

解决方案四：

 #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;
const int N = 5005;
char s[N];
int k,n,l,r;
bool dp[N][N];
int vis[N];
string ans;

struct Tree
{
    Tree()
    {
        val = 0;
        memset(next,0,sizeof next);
    }
    int val;
    Tree *next[2];
}*tree_head;

void init()
{
    tree_head = new Tree();
    n = strlen(s);
    memset(dp,false,sizeof dp);
    for(int i = n - 1; i >= 0; --i)
    {
        dp[i][i] = true;
        vis[i] = i;
        for(int j = i + 1; j < n; ++j)
        {
            if(s[i] == s[j])
            {
                if(i + 2 >= j - 2)
                    dp[i][j] = true;
                else dp[i][j] = dp[i + 2][j - 2];
            }
            if(dp[i][j]) vis[i] = j;
        }
    }
}

void insert_tree(Tree *ptemp, char *s)
{
    if(*s == '') return;
    if(r > vis[l]) return;
    int c = *s - 'a';
    if(ptemp->next[c] == NULL)
        ptemp->next[c] = new Tree();
    if(dp[l][r]) ptemp->next[c]->val++;
    r++;
    insert_tree(ptemp->next[c], s + 1);
}

void dfs(Tree *ptemp)
{
    string temp = ans;
    if(k > 0 && ptemp->next[0])
    {
        k -= ptemp->next[0]->val;
        ans = ans + 'a';
        dfs(ptemp->next[0]);
    }
    if(k > 0 && ptemp->next[1])
    {
        ans = temp;
        k -= ptemp->next[1]->val;
        ans = ans + 'b';
        dfs(ptemp->next[1]);
    }
}

void solve()
{
    scanf("%s %d",s,&k);
    init();
    for(int i = 0; i < n; ++i)
    {
        l = r = i;
        insert_tree(tree_head,s + i);
    }
    dfs(tree_head);
    cout << ans << endl;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}

解决方案五：

这道题目你会做吗？

时间： 2024-08-03 11:55:32

这道题目用C++怎么做？的相关文章

测试-求这道题目代码 我只能做这种弹出提示框的 不能把分数和相应错题答案连接到新窗口

问题描述 求这道题目代码 我只能做这种弹出提示框的 不能把分数和相应错题答案连接到新窗口 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" > &

c语言问题-求高手解答这道题目，，有点挑战喔。。

问题描述 求高手解答这道题目,,有点挑战喔.. 我想了好久不太会写.......................第五题 解决方案 这难道不是只有四个题目 解决方案二: 第3题打错了........ 解决方案三: 可以用单向链表来实现. 解决方案四: 用java我还知道怎么做,,数据结构还是不怎么会

请教各位这题目我该怎么做啊？求高手解答谢谢

问题描述 1.下面是一个类的定义,请完成程序填空.publicclass____________{intx,y;Myclass(inti,_______){//构造方法x=i;y=j;}}2.阅读下列程序.publicclassFoo{inti;staticStrings;voidimethod(){}staticvoidsmethod(){}}设f是Foo生成的一个对象,下列语句正确吗?如果inti用private修饰呢?System.out.println(f.i);System.out.p

谁帮忙看看这道题目，我写的代码一直过不了

问题描述 谁帮忙看看这道题目,我写的代码一直过不了 B:马走日 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 1024kB 描述 马在中国象棋以日字形规则移动. 请编写一段程序,给定n*m大小的棋盘,以及马的初始位置(x,y),要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点. 输入 第一行为整数T(T < 10),表示测试数据组数. 每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标n,m,x,y.(0<=x<=n-1,0&l

设计-请问这道测试面试题怎么做？有哪位大神能告诉我吗？？？？非常感谢！

问题描述 请问这道测试面试题怎么做?有哪位大神能告诉我吗????非常感谢! Background: As a airline company, I've cooperated with some car companies as my partner. The user can get discount if they book the car after booking our airline tickets. Therefore, in our airline app, we support

这道题目如何解决，请帮我解答一下，谢谢

问题描述 这道题目如何解决,请帮我解答一下,谢谢 [问题描述] 一个二元多项式f(x)=ax^2+bx+c?(x为整数),给定a,b,c的值以及两个整数l,r,你的任务是求出x的取值分别为l,l+1,l+2......r-1,r时该多项式的值. [输入格式] 一行,5个整数,a,b,c,l,r [输出格式] 1行,包含r-l+1个数,第i个数表示x值为l+i-1时多项式的值 [输入样例] 2?3?5?7?11 [输出样例] 124?157?194?235?280 解决方案 #include <s

java源码-求解这道题目，求源代码????

问题描述 求解这道题目,求源代码???? 这道题求解,用scanner输入流和一维数组和循环怎么解决呢????????? 解决方案 循环体里面 用数组接收传进来的值(选手姓名 和 分数) 然后按照计算分数的逻辑进行计算 输出(循环的i的值 +1 , 姓名 ,分数)

高手指点一下！！这道题目有没有其他做法或可不可以做得更简单一些！！感激不尽！！！

问题描述 问题描述:病人到医院看病,首先必须要挂号,如果没挂号,就会抛出一个异常来,提醒病人先去挂号:如果已经挂号了,就可以看医生.医生根据肺炎病人的病情,进行开药(可以简单模拟三种不同肺炎病的类型及其用药用量情况,请参见图).假设三种类型的肺炎病都用青霉素来治疗,但是药的用量是不同的.比如:支气管肺炎的用量为40万―50万单位每日,肺炎链球菌肺炎为60-100万单位每日,金黄色葡萄球菌肺炎为120-160万单位每日.如果现在病人得的是支气管肺炎,用量如果在40万―50万单位每日,则说明用药正确

有几个面试的题目。高手帮做一下。非常感谢

问题描述 题目一:请用C#.NET将一个浮点整型数转换为以下格式的字符串格式:1,234,567.00publicstaticstringFormat(doublenum){}题目三:1.用最简单的方法实现下面这个排序函数,分别用Java和C#.NET实现(不是2选1)Java:publicstaticList<Integer>sort(Integer[]array){-}C#.NET:publicstaticList<Int32>Sort(int[]array){-}2.请列出U