首页 > 试题广场 >

优美的回文串

[编程题]优美的回文串

热度指数：710 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛在书上看到一种字符串叫做回文串,当一个字符串从左到右和从右到左读都是一样的,就称这个字符串为回文串。牛牛又从好朋友羊羊那里了解到一种被称为优美的回文串的字符串,考虑一个长度为N只包含大写字母的字符串,写出它所有长度为M的连续子串(包含所有可能的起始位置的子串,相同的子串也要计入),如果这个字符串至少有K个子串都是回文串,我们就叫这个字符串为优美的回文串。现在给出一个N,牛牛希望你能帮他计算出长度为N的字符串有多少个是优美的回文串(每个位置都可以是'A'~'Z'的一个。)

输入描述:

输入数据包括三个整数N, M, K(2 ≤ N ≤ 11, 2 ≤ M ≤ N, 0 ≤ K ≤ 11).

输出描述:

输出一个整数,表示所求的字符串个数.

示例1

输入

2 2 1

输出

26 长度为2的字符串,它长度为2的子串只有它自身。长度为2的回文串有"AA","BB","CC"..."ZZ",一共26种。

算法知识视频讲解

Graphene

#include <cstdio>

long long fac[27], res;
int n, m, k, a[12];

bool ok(int from) {
  for (int i = 0; i < m / 2; ++i) {
    if (a[from + i] != a[from + m - i - 1]) {
      return false;
    }
  }
  return true;
}

bool ok() {
  int cnt = 0;
  for (int i = 0; i <= n - m; ++i) {
    if (ok(i)) {
      ++cnt;
    }
  }
  return cnt >= k;
}

void dfs(int pos, int num) {
  if (pos == n) {
    if (ok()) {
      res += fac[num];
    }
  } else {
    for(int i = 0; i < num; i++) {
      a[pos] = i;
      dfs(pos + 1, num);
    }
    a[pos] = num;
    dfs(pos + 1, num + 1);
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  fac[0] = 1;
  for (int i = 1; i <= 26; ++i) {
    fac[i] = fac[i - 1] * (27 - i);
  }
  dfs(0, 0);
  printf("%lld\n", res);
}

编辑于 2017-03-24 13:05:18 回复(1)

Scruel

import java.util.Scanner;

/**
 * Created by Scruel on 2017/3/25.
 * Personal blog : http://blog.csdn.net/scruelt
 * Github : https://github.com/scruel
 */
public class BeautyStringMy {
        //定义数组a为一种模式，a中a[i]与a[j]相同代表两个位置处为同一字符
        private static int[] a = new int[12];
        //定义P(26,i)代表使用i个字母所组成的每位互不相同的全排列，fac[0]=P(26,0)代表用了一个字母每位都不相同的全排列(=26种)，fac[1]=P(26,1)代表用了2个字母每位都不相同的全排列(=650种),.....
        private static long[] fac = new long[12];
        private static int n, m, k, cnt = 0;


        private static boolean check(int from) {
                for (int i = 0; i < m / 2; ++i) {
                        if (a[from + i] != a[from + m - i - 1]) {
                                return false;
                        }
                }
                return true;
        }


        private static boolean check() {
                //检验模式
                int cnt = 0;
                for (int i = 0; i <= n - m; ++i) {
                        if (check(i)) {
                                ++cnt;
                        }
                }
                return cnt >= k;
        }

        //num代表在n长度的字符串上用了几种不同的字母，num=0为用了1种，比如AAA，BBB；num=1为用了2种，比如ABA，CCB，依此类推(所有例子的n都为3)，注意，这里都是模式匹配！
        //pos代表当前是第几个字符完成了模式填充
        private static void dfs(int pos, int num) {
                if (pos == n) {
                        if (check())
                                //a模式下，有num个位置必须不同，其它的位置都只有按照（check后的可行的）模式匹配的1种选择，所以直接+即可
                                cnt += fac[num];
                        return;
                } else {
                        //当前pos位置有num个数字可用，枚举当前层num种可能性，下一层会继续枚举穷尽

                        //i<num，所以下面这个循环会枚举出(....,[0 - (n - 1)],[0 - n],....)的所有模式，例：{0, 0, 0}，{0, 0, 1}
                        //要注意的是，枚举模式{0, 0, 1}，{0, 0, 2}表达的意思是一样的，所以下一层处理的不同字母数应该与当前层相同，即num不变
                        for (int i = 0; i < num; i++) {
                                a[pos] = i;
                                dfs(pos + 1, num);
                        }
                        //pos位置的最后一个枚举，下一层会枚举出(....,[n],[0 - (n + 1)],....)的所有模式,例：{0, 1, 0}, {0, 1, 1},{0, 1, 2}，这样可以做到模式的不重复和不遗漏
                        a[pos] = num;
                        dfs(pos + 1, num + 1);
                }
        }

        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
//                n = 3;
//                m = 2;
//                k = 1;
                n = scanner.nextInt();
                m = scanner.nextInt();
                k = scanner.nextInt();
                fac[0] = 1;
                for (int i = 1; i < 12; ++i) {
                        fac[i] = fac[i - 1] * (27 - i);
                }
                dfs(0, 0);
                System.out.println(cnt);
        }
}

编辑于 2017-04-05 21:47:27 回复(3)

牛客511771125号

#include<iostream>
#include<cmath>
using namespace std;

int N, M, K;
char str[11];
long long answer = 0;
long long type[12];//表示用了i个字母的排列方式有type[i]种

bool IsElegantPalideome()//判断某个字符串是否是优美回文串
{

	int subNum=0;//子串中是回文串的个数

	for (int i = 0; i < N - M + 1; i++)//有N-M+1个子串，i表示子串的个数
	{
		int flag = 1;
		for (int j = 0; j < M / 2; j++)
		{
			if (str[i + j] != str[i + M - 1 - j])
			{
				flag = 0;
				break;
			}
		}
		if(flag)
			subNum++;
	}
	if (subNum >= K)
		return true;
	else
		return false;
}

void dfs(int len, int num)//len表示待填充的字符个数，num表示已经使用了num个字母
{
	if (len == 0)//不需要再填充字符了
	{
		if (IsElegantPalideome())//这个字符串是优美回文串
		{
			answer += type[num];//这种模式符合要求，通过替换这种模式的字符串共有type[num]种
		}
		return;
	}
	else
	{
		for (int i = 0; i <= num; i++)
		{
			str[len - 1] = 'A' + i;//用i控制字母的变化
			if (i == num)//出现此前没有用到的字母
				dfs(len - 1, num + 1);//所用字符数+1;
			else
				dfs(len - 1, num);
		}
	}
}
int main()
{
	cin >> N >> M >> K;

	type[0] = 0, type[1] = 26;
	for (int i = 2; i < 12; i++)
	{
		type[i] = type[i - 1] * (27 - i);
	}
	dfs(N, 0);
	cout << answer;
}

发表于 2020-05-27 11:15:10 回复(0)

xfhy

确实没看懂题目.....是我语文不好么?

发表于 2017-09-19 21:54:02 回复(0)

一条大咸鱼

总共8道题，2道题没看懂要干嘛，我还是先去补个语文再来

发表于 2017-09-06 15:13:39 回复(1)

武汉加油

题目都没看懂，有没有人解释下题目什么意思啊

发表于 2017-06-27 09:41:53 回复(0)

atyhnfjgj

// 这个答案由 @Graphene 给出，我的算法超时了
#include
using namespace std;
int model[12];
long long fac[13];
int N, M, K;
long long res;
bool isok() {
    int samecnt = 0;
    for (int i = 0; i <= N - M; i++) {
        int s = i;
        int e = s + M - 1;
        bool same = true;
        while (s <= e) {
            if (model[s++] != model[e--]) {
                same = false;
                break;
            }
        }
        samecnt = same ? samecnt + 1 : samecnt;
    }
    return samecnt >= K;
}
void dfs(int pos, int num) {
    if (pos == N) {
        if (isok()) {
            // 这里以结尾的数字判断当前数列中一共有多少个数字（即num个），设为一种可行的模式，并由下面的循环可知，这一模式是唯一的，从26个字母中选num个（由排列组合求出，记为fac[num])，可知这一模式能重复fac[num]次，加入res
            res += fac[num];
        }
        return;
    }
    for (int i = 0; i < num; i++) {
        model[pos] = i;
        dfs(pos + 1, num);
    }
    // 下面这一步保证数列中的数字是连续的，既把model中的数字从小到达排列，1 ～ num 中的数字每一个最少出现一次
    model[pos] = num;
    dfs(pos + 1, num + 1);
}
int main() {
    fac[0] = 1;
    for (int i = 1; i <= 12; i++) {
        fac[i] = fac[i - 1] * (27 - i);
    }
    while (cin >> N >> M >> K) {
        res = 0;
        for (int i = 0; i < 12; i++) model[i] = 0;
        dfs(0, 0);
        cout << res << endl;
    }
    return 0;
}

发表于 2017-04-12 09:50:51 回复(0)