首页 > 试题广场 >

魔法权值

[编程题]魔法权值
  • 热度指数：3150 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

给出 n 个字符串，对于每个 n 个排列 p，按排列给出的顺序(p[0] , p[1] … p[n-1])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。

一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量，i 的取值为 [1 , 字符串长度]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。

注：定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。


输入描述:
每组测试用例仅包含一组数据，每组数据第一行为两个正整数 n, K ， n 的大小不超过 8 ， K 不超过 200。接下来有 n 行，每行一个长度不超过 20 且仅包含大写字母的字符串。


输出描述:
输出一个整数代表权值为 K 的字符串数量。
示例1

输入

3 2
AB
RAAB
RA

输出

3
算法知识视频讲解
添加回答
牛客66666666号头像 牛客66666666号 
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> strs;
vector<int> flag;
int n, k;
int count;

void backTracking(int pos, vector<int> &sequence)
{
	if(pos == n)
	{
		string s;
		
		for(int i = 0; i < n; i++)
			s += strs[sequence[i]];

		string tmps = s;
		int lcount = 1;
		for(int i = 0; i < s.length() / 2; i++)
		{
			tmps = tmps.substr(1) + tmps[0];
			if(tmps == s)
			{
				lcount = s.length() / (i + 1);
				break;
			}
		}
		if(lcount == k)
			count++;
		return;
	}
	for(int i = 0; i < n; i++)
	{
		if(flag[i])
		{
			sequence.push_back(i);
			flag[i] = false;
			backTracking(pos + 1, sequence);
			flag[i] = true;
			sequence.resize(sequence.size() - 1);
		}
	}
}

int main()
{
	count = 0;
	cin>>n>>k;
	strs.resize(n);
	flag.resize(n);
	vector<int> seq;
	
	for(int i = 0; i < n; i++)
	{
		cin>>strs[i];
		flag[i] = true;
	}
	backTracking(0, seq);
	cout<<count<<endl;
	return 0;
}

发表于 2016-04-29 17:28:01 回复(0)
更多回答
JQK2020头像 JQK2020
全排列+map记录提高效率（这题数据挺强的） 
#include<bits/stdc++.h>
using namespace std;
string s[9];
map<string,int>m;
int main(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>s[i];
    int a[10];
    for(int i=1;i<=n;i++)a[i]=i;
    do{
        string k;
        for(int i=1;i<=n;i++)k+=s[a[i]];
        m[k]++;
    }while(next_permutation(a+1,a+1+n));
    int ans=0;
    map<string,int>::iterator it=m.begin();
    for(;it!=m.end();it++){
        string x=(*(it)).first;
        int now=0;
        for(int i=0;i<x.size();i++){//偏移量
            int f=1;
            for(int j=0;j<x.size();j++){
                if(x[j]!=x[(j+i)%x.size()]){f=0;break;}
            }
            now+=f;
            if(now>k)break;
        }
        if(now==k)ans+=m[x];
    }
    cout<<ans;
}


编辑于 2020-05-12 00:25:10 回复(1)
Alex-大伟头像 Alex-大伟 
import java.util.ArrayList;
import java.util.Scanner;

public class JRTT4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int K = scanner.nextInt();
			String[] strs = new String[n];
			for (int i = 0; i < n; i++) {
				strs[i] = scanner.next();
			}
			System.out.println(getNumWeightK(n, K, strs));
		}
	}

	public static int getNumWeightK(int n, int K, String[] strs) {
		int count = 0;
		ArrayList<String> strings = new ArrayList<String>();
		permutation(strings, strs, 0);
		for (int i = 0; i < strings.size(); i++) {
			int weightTemp = getWeight(strings.get(i));
			if (weightTemp == K) {
				count++;
			}
		}
		return count;
	}

	// 循环移位得到的权重 超时
	/*public static int getWeight(String s) {
		int weight = 0;
		char[] cs = s.toCharArray();
		for (int i = 0; i < s.length(); i++) {
			char temp = cs[0];
			for (int j = 0; j < s.length() - 1; j++) {
				cs[j] = cs[j + 1];
			}
			cs[s.length() - 1] = temp;
			String rotateS = new String(cs);
			if (rotateS.equals(s)) {
				weight++;
			}
		}
		return weight;
	}*/
	//求一个字符的权重
	public static int getWeight(String s) {
		int weight = 0;
		int len = s.length();
		for(int i=0;i<s.length();i++){
			if(s.substring(0, i).equals(s.substring(len - i, len)) && s.substring(0, len-i).equals(s.substring(i, len))){
				weight++;
			}
		}
		return weight;
	}

	// 全排列
	public static void permutation(ArrayList<String> strings, String[] strs, int k) {
		if (k == strs.length) { 
			String temp = "";  //一开始用StringBuffer类来保存，就超时了。所以尽量不要用StringBuffer
			for (int i = 0; i < strs.length; i++) {
				temp += strs[i];
			}
			strings.add(temp);
		}
		else{
			for (int i = k; i < strs.length; i++) {
				swap(strs, i, k);
				permutation(strings, strs, k + 1);
				swap(strs, i, k);
			}
		}
	}

	public static void swap(String[] strs, int i, int j) {
		if (i != j) {
			String t = strs[i];
			strs[i] = strs[j];
			strs[j] = t;
		}
	}
}


编辑于 2016-09-30 22:56:30 回复(1)
D_L头像 D_L
此题主要是理解题意，编程倒是不难。

按照输入和输出给的样例，结合题干，就基本可以正确猜出出题人的意思了。

第一行输入 3 2，即 n = 3, K = 2
紧接着是 n 行输入：
AB
RAAB
RA

主要是 K 表达的含义： K 代表一个字符串的权值，最终结果让程序输出 权值等于K 的数量（count(K)），权值就是等于把一个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量 ，又特么是数量。

假设 一个字符串循环左移 i 次后 得到的字符串仍和原字符串全等 情况设为 is_eq_after_move(i) ， 其中 i 的取值为 [1, 字串长度]， 则 K = count (is_eq_after_move(i) )， 即这些情况的总数。因为 i 最大值可以取到 字符长度， 所以 K 的最小值是 1。

K 的含义基本清楚了，那字符串有如何生成？

根据题意 字符串会有 n! 个情况，能将 n 个字符串组装成 n! 个 新的 字符串，想到的只有 全排列 了 。可以根据 输入输出例子 验证这个猜测。

验证如下：
n = 3, K = 2
全排列：
AB RAAB RA   (偏移后和原串相等的偏移量 i = 4， 8) ，则 K = count(i) = 2
AB RA RAAB   (偏移量 i = 8), 则 K = count(i) = 1
RAAB AB RA ( 偏移量 i = 8), 则 K = count(i) = 1
RAAB RA AB ( 偏移量 i = 4, 8), 则 K = count(i) = 2
RA AB RAAB ( 偏移量 i = 4, 8), 则 K = count(i) = 2
RA RAAB AB ( 偏移量 i = 8), 则 K = count(i) = 1

则 输出 K == 2 的数量： count(K == 2) = 3
正是 输出例子给出的数字 3。

至此理解题意了。
接下来只需搞定， 生成全排列 的 算法，和 验证 偏移 offset 个字符 后和原串相等 的算法 就可以了。

后面的就不啰嗦了，给出一种实现

验证 循环偏移时候，不用真的移动字符，做几个判断即可 

#include <iostream>
#include <vector>
#include <assert.h>
#include <cstring> // for strncmp
#include <algorithm> // for std::next_permutation
using namespace std;

bool is_eq_after_move(const string& str, const size_t offset) {
    const size_t len = str.size();
    if (offset == len) return true;
    
    assert(offset >= 1 && offset < len);
    // 左移 offset 位数后，与原串相等的情况之一：
    //      每 offset 个数据块 都要相等
    //      所以 这种情况 的字符串，长度首先必须是 offset 的 整数倍。
    //
    // 情况之二，串长不是 offset 的 整数倍，像这种: ABABAB , offset = 4
    // 这种情况可以用递归来化解:
    if (len % offset != 0) {   
        if (len % offset > len / 2) return false; // 加上此句可减少复杂度
        return is_eq_after_move(str, len % offset);
    }
    
    // 程序能走到这的都是 之前提到的 情况一:
    char* s = (char*)&str[0]; // 先指向首地址
    for (size_t loop = 0, max_loop = len / offset - 1; 
        	loop < max_loop; ++loop) {
        if ( 0 != strncmp(s, s + offset, offset) ) {
            return false;
        }
        s += offset;
    }
    return true;
}

void get_ret(size_t& ret, const int* pos, const size_t size,
             const vector<string>& input, const size_t K) {
    size_t count = 1; // 自身整体移动算一个
    string newstring;
    for (size_t i = 0; i < size; ++i) {
        newstring += input[pos[i]];
    }

    const int len = newstring.size();
    for (int offset = 1; offset < len; ++offset) {
        // 只判断 和第一个相等的字符即可
        if (newstring[offset] == newstring[0]) {
            if (is_eq_after_move(newstring, offset)) {
                count++;
            }
        }
    }

    if (count == K) {
        ret++;
    }
}


int main() {
    size_t n, K;
    cin >> n >> K;
    vector<string> input(n);
    size_t newstrlen = 0;
    for (size_t i = 0; i < n; ++i) {
        cin >> input[i];
    	newstrlen += input[i].size();
    }
    
    // 生成 0 ~ n-1 的全排列
	int pos[n];
	for (int i = 0; i < n; ++i) pos[i] = i;

	size_t ret = 0;
    do {
	    get_ret(ret, pos, n, input, K);
    } while (std::next_permutation(pos, pos + n));

    cout << ret << endl;
    return 0;
}

编辑于 2016-06-05 21:19:43 回复(4)
Java
Holiday_12138头像 Holiday_12138 

	递归生成全排列，判断权值，也就是串能分出多少个相同的子串，用KMP可解，





	判断n-next[n]能否整除n，可以知道串是否由多个相同字串组成,





	除完的商就是权值，不能整除的串权值为1.





	
	

		import java.util.*;
public class Main{
	static ArrayList<String> res;
    public static int next(String arr){
    	int[] next=new int[arr.length()+1];
    	int res=1;
    	next[0]=next[1]=0;
    	int j=0;
    	for(int i=1;i<arr.length();i++){
    		while(j>0&&arr.charAt(i)!=arr.charAt(j)) j=next[j];
    		if(arr.charAt(i)==arr.charAt(j)) {
    			j++;
    		}
    		next[i+1]=j;
    	}
    	if(arr.length()%(arr.length()-next[arr.length()])==0)
    		res=arr.length()/(arr.length()-next[arr.length()]);
    	return res;
    }
    public static void allString(String[] strr,int s,int n){
    	String tmp;
    	if(s==(n-1)){
    		tmp="";
    		for(int i=0;i<n;i++){
    			tmp+=strr[i];
    		}
    		res.add(tmp);
    	}  
    	for(int i=s;i<n;i++){
    		tmp=strr[s];
    		strr[s]=strr[i];
    		strr[i]=tmp;
    		allString(strr,s+1,n);
    		tmp=strr[s];
    		strr[s]=strr[i];
    		strr[i]=tmp;
    	}
    }
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n,k,count;
		String[] strr;
		while(sc.hasNext()){
			res=new ArrayList<String>();
			count=0;
			n=sc.nextInt();
			k=sc.nextInt();
			strr=new String[n];
			for(int i=0;i<n;i++){
				strr[i]=sc.next();
			}
			allString(strr,0,n);
			for(int i=0;i<res.size();i++){
				if(next(res.get(i))==k)
					count++;
			}
			System.out.println(count);
		}
		sc.close();
	}
}

编辑于 2016-09-03 17:56:59 回复(2)
AlgorithmM头像 AlgorithmM 
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 06 19:10:02 2016
@author: duzejie
python测试通过

基本思想：
1.生成全排列
2.减少测试次数
a.如果字符串循环左移 i 次后得到的字符串仍和原字符串全等，
则要求i是该字符串长度的因数,所以不必测试全部i
b.对于权为k的字符串，测试通过的最小i为imin= strlen / k,
所以不必测试大于imin的i
c.测试通过的i小于imin= strlen / k，可提前退出
"""
import itertools
'''测试字符串循环左移 i 次后得到的字符串是否仍和原字符串全等'''
def test(s,i):
    strl = s[:i]
    strr = s[i:]
    newstr = strr + strl
    if cmp(s,newstr)==0:
        return True 
        
lis = raw_input().split() #获取n,k
n=int(lis[0])
k=int(lis[1])
i = 0
mystring = [] #存放输入字符串列表
strlen = 0 #统计所有字符串长度

while(i<n):  #从用户输入获取各个字符串，放入mystring[]
    ms = raw_input()
    strlen += len(ms)
    mystring += [ms]
    i+=1
'''mybei[]中存放所有可能的i。如果字符串循环左移 i 次后得到的字符串仍和原字符串全等，
则要求i是该字符串长度的因数'''
mybei = [x for x in range(1,strlen+1) if strlen % x == 0]

 
coutk = 0
newlist = range(n)
strlist = list(itertools.permutations(newlist,n)) #存放所有字符串的可能组合方式

imin = strlen / k #对于权为k的字符串，测试通过的最小i为imin

for x in strlist : #遍历所有可能组合
    if strlen % k != 0:break    
    s = ''
    for y in x:
        s+= mystring[y] #生成该组合的字符串    
    for i in mybei: #对可能的i测试
        if i > imin :break
        if test(s,i):
            if i < imin:
                break
            if i == imin:
                coutk +=1
                break

print(coutk)


发表于 2016-08-06 20:56:30 回复(1)
Kiryu_Kazuma头像 Kiryu_Kazuma
纯模拟，这样也能过 
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <functional>
#include <algorithm>
#include <stack>
#include <queue>
#include <sstream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <random>
#include <fstream>

int main()
{
    int n, K;
	std::cin >> n >> K;
	std::vector<std::string> orig_strs(n);
	for (int i = 0; i < n; i++)
		std::cin >> orig_strs[i];
	
	std::vector<int> pa;
	for (int i = 0; i < n; i++)
		pa.push_back(i);

	int ans = 0;
	do
	{
		std::string str, str_bak;
		for (int i = 0; i < n; i++)
			str += orig_strs[pa[i]];
		str_bak = str;
		int k = 0;
		for (int i = 1; i <= str.length(); i++)
		{
			std::string new_str = str.substr(i, -1) + str.substr(0, i);
			if (new_str == str_bak)
				k += 1;
		}
		if (k == K)
			ans += 1;
	} while (std::next_permutation(pa.begin(), pa.end()));

	std::cout << ans;

	return 0;
}


发表于 2022-09-11 11:59:12 回复(0)
头大的烦恼头像 头大的烦恼
此题首先注意到最多不超过8个字符串，用全排列也只有2的8次方之多，所以首先可以确定是可以穷举，然后拼接完的字符串最长长度也不超过200，可以判断真的一直左移算法的循环次数也不会太大。所以这道题我采取的方式是穷举。以下是关键步骤的解析。
1 - 穷举产生全排列：
     使用的方式是迭代，利用辅助vector<bool>判断该位置是否已使用，其次本意是想使用回溯的写的，奈何str字符串的回溯是有点麻烦，所以
就直接传形参过去了。
2 - 题目的左移要求：
    模运算就可以了，在generateK里面有具体步骤
发表于 2021-04-23 15:29:54 回复(0)
牛客0X0001号头像 牛客0X0001号 
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, K, res = 0;
	cin >> n >> K;
	vector<string> strs(n);
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> strs[i];
		v[i] = i;
	}

	do {
		string s;
		for (int i : v) s += strs[i];
		int n = s.size(), k = 1;
		vector<int> f(n, 0);
		for (int i = 1, len = 0; i < n;) {
			if (s[i] == s[len]) f[i++] = ++len;
			else if (len) len = f[len-1];
			else f[i++] = 0;
		}
        if (n % (n - f[n-1]) == 0) k = n / (n - f[n-1]);
        if (k == K) ++res;
	} while (next_permutation(v.begin(), v.end()));
	cout << res << "\n";
}

发表于 2020-12-06 18:27:25 回复(0)
etinnebezout头像 etinnebezout 
def all_permutation(l, s=[]):
    if len(l) == 0:
        return [s + l]
    else:
        r = []
        for i in range(len(l)):
            r += all_permutation(l[0:i] + l[i + 1:], s + [l[i]])
        return r


def check(s, m, k):
    if m % k == 0:
        for i in range(1, m):
            if m % i == 0:
                if s[0:i] * (m // i) == s:
                    break
        if m // i == k:
            return True
        else:
            return False
    else:
        return False


n, k = [int(ele) for ele in input().split(' ')]
r = []
while n > 0:
    r.append(input())
    n -= 1

r2 = all_permutation(r)
m = len(''.join(r))
ans = 0
for ele in r2:
    if check(''.join(ele), m, k):
        ans += 1
print(ans)

发表于 2019-09-12 14:35:03 回复(1)
😌2106头像 😌2106 
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner scn = new Scanner(System.in);
        
        int n = scn.nextInt();
        int k = scn.nextInt();
        List<String> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(scn.next());
        }
        List<String> all = new ArrayList<>();
        backtrack(list, new ArrayList<String>(), all);
        int ret = 0;
        for(String str: all){
            //System.out.println(str);
            int c = getWeight(str);
            //System.out.println(" "+c);
            if(c==k)ret++;
        }
        System.out.println(ret);
    }
    
    public static int getWeight(String s) {
        int weight = 0;
        int len = s.length();
        for(int i=0;i<s.length();i++){
            if(s.substring(0, i).equals(s.substring(len - i, len)) && s.substring(0, len-i).equals(s.substring(i, len))){
                weight++;
            }
        }
        return weight;
    }
    
    public static void backtrack(List<String> list, List<String> tempList, List<String> all){
        for(int i=0;i<list.size();i++){
            String s = list.get(i);
            tempList.add(s);
            List<String> copy = new ArrayList<>(list);
            copy.remove(i);
            backtrack(copy, tempList, all);
            tempList.remove(tempList.size()-1);
        }
        if(list.size()==0){
            StringBuilder sb = new StringBuilder();
            for(String str: tempList){
                sb.append(str);
            }
            all.add(sb.toString());
        }
    }
}

发表于 2019-02-23 16:08:02 回复(0)
Mr.tai头像 Mr.tai
显示超时，60%，如何改进。。 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> get_allstr(vector<string> input)
{
    int n=input.size();
    int index[n];
    for(int i=0;i<n;i++)
        index[i]=i;
    vector<string> allstr;
    do
    {
        string newstr;
        for(int i=0;i<n;i++)
            newstr+=input[index[i]];
        allstr.push_back(newstr);
    }while(next_permutation(index,index+n));
    return allstr;
}
int get_k(string str)
{
    int k=0;
    string str_left_move=str;
    for(int i=1;i<=str.size();i++)
    {
        str_left_move=str_left_move.substr(1)+str_left_move[0];
        if(str==str_left_move)
            k++;
    }
    return k;
}
int main()
{
    int n,K;cin>>n>>K;
    vector<string> input(n);
    for(int i=0;i<n;i++)
        cin>>input[i];
    vector<string> allstr=get_allstr(input);
    int count=0;
    for(int i=0;i<allstr.size();i++)
    {
        int k=get_k(allstr[i]);
        if(k==K)
            count++;
    }
    cout<<count<<endl;
    return 0;
}

发表于 2018-10-08 16:54:58 回复(0)
小乌头像 小乌

为什么看大家的代码中求排列的时候  没有去除重复的序列
这个会有影响吧
发表于 2017-03-28 19:37:39 回复(0)
momom头像 momom 

	
	

		importjava.util.ArrayList;
	


	

		importjava.util.Scanner;
	


	

		 
	


	

		publicclassMain {
	


	

		 
	


	

		    staticArrayList<String> list =newArrayList<>();
	


	

		    publicstaticvoidmain(String[] args) {
	


	

		        Scanner scan =newScanner(System.in);
	


	

		        while(scan.hasNext()){
	


	

		            intn = scan.nextInt();//<=8
	


	

		            intk = scan.nextInt();//<=200，权值
	


	

		            String[] strs =newString[n];
	


	

		            for(inti=0;i<n;i++){
	


	

		                strs[i] = scan.next();//size<=20
	


	

		            }          
	


	

		            perm(strs,0, strs.length);
	


	

		            intcount =0;//权值为K的字符串数量
	


	

		            for(inti=0;i<list.size();i++){
	


	

		                if(getK(list.get(i))==k){
	


	

		                    count++;
	


	

		                }
	


	

		            }
	


	

		            System.out.println(count);
	


	

		            list.clear();
	


	

		        }
	


	

		    }
	


	

		     
	


	

		    //获取权值
	


	

		    privatestaticintgetK(String s){
	


	

		        String news = s+s;
	


	

		        intcount =0;
	


	

		        for(inti=1;i<=s.length();i++){
	


	

		            if(news.substring(i, i+s.length()).equals(s)){
	


	

		                count++;
	


	

		            }
	


	

		        }
	


	

		        returncount;
	


	

		    }
	


	

		 
	


	

		    privatestaticvoidperm(String[] strs,intstart,intend){
	


	

		        String s ="";
	


	

		        if(start==end){//一个字符串全排列
	


	

		            for(inti=0;i<strs.length;i++){
	


	

		                s+=strs[i];
	


	

		            }
	


	

		            list.add(s);
	


	

		        }else{//多个字符串全排列
	


	

		            for(inti=start;i<end;i++){
	


	

		                String str = strs[start];
	


	

		                strs[start] = strs[i];
	


	

		                strs[i] = str;
	


	

		                perm(strs,start+1,end);
	


	

		                strs[i] = strs[start];
	


	

		                strs[start] = str;
	


	

		            }
	


	

		        }
	


	

		    }
	


	

		}

发表于 2016-11-23 13:30:20 回复(0)
Java
Gdeer头像 Gdeer 
// 复杂度太高了？没过。。不过应该是对的
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Gdeer on 2016-9-8.
 */
public class Main3 {

    private static ArrayList<String> list = new ArrayList<>();
    private static ArrayList<Integer> resultList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n,k;

        while (scanner.hasNext()){
            list = new ArrayList<>();
            resultList = new ArrayList<>();
            n = scanner.nextInt();
            k = scanner.nextInt();

            for (int i = 0; i < n; i++) {
                String str = scanner.next();
                list.add(str);
            }

            int[] indexs = new int[list.size()];
            for (int i = 0; i < indexs.length; i++) {
                indexs[i] = i;
            }
            arrange(indexs, 0);

            int m = 0;
            for (int i : resultList) {
                if (i == k){
                    m++;
                }
            }
            System.out.println(m);
        }
    }

    private static void arrange(int[] array, int a) {
        int n = array.length;
        if (a == n - 1) {
            String s = createStr(array, list);
            resultList.add(getCount(s));
        } else {
            for (int i = 0; i < n - a; i++) {
                swap(array, a, a + i);
                arrange(array, a + 1);
                swap(array, a, a + i);
            }
        }
    }

    private static String createStr(int[] array, List list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            sb.append(list.get(array[i]));
        }
        return sb.toString();
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int getCount(String str) {
        int count = 1;
        for (int i = 0; i < str.length(); i++) {
            StringBuilder sb = new StringBuilder();
            String subStr = str.substring(0, i + 1);
            for (int j = 0; j < str.length() / subStr.length(); j++) {
                sb.append(subStr);
            }
            if (sb.toString().equals(str)) {
                count = str.length() / subStr.length();
                break;
            }
        }
        return count;
    }
}

编辑于 2016-09-08 17:54:13 回复(0)
charles_x头像 charles_x 
// 首先对问题进行划分
// 两个基本模块：生成全排列，字符串权重计算
// 生成全排列：递归
// 字符串权重：等价于寻找最小循环子串


#include <iostream>
#include <string>
#include <vector>

using namespace std;
int n, K;
int count = 0;

// 计算字符串权重
void isKWeight(vector<string> strs, vector<int> &vi) {
    string s;
    for (int i = 0; i < vi.size(); ++i) s += strs[vi[i]];
    string tmps(s);
    int lc = 1;

    // 计算字符串权重等价于寻找最小循环字符串
    for (int i = 0; i < s.size() / 2; ++i) {
        tmps = tmps.substr(1) + tmps[0];
        if (tmps == s) {
            // 根据最小循环字符串计算权重
            lc = s.size() / (i + 1);
            break;
        }
    }
    if (lc == K) ++count;
}

// 生成全排列
void permutations(vector<string> strs, vector<int> &vi, int start, int end) {
    if (start == end) {
        isKWeight(strs, vi);
    } else {
        for (int i = start; i <= end; ++i) {
            // 交换元素，使每一个元素都有放在第一位的机会
            swap(vi[start], vi[i]);
            // 递归调用
            permutations(vi, start + 1, end);
            // 恢复原始的list，不影响下次递归调用
            swap(vi[start], vi[i]);
        }
    }
}

int main() {
    cin >> n >> K;
    count = 0;
    vector<string> ss(n);
    vector<int> vi(n);
    for (int i = 0; i < n; ++i) {
        cin >> ss[i];
        vi[i] = i;
    }
    permutations(ss, vi, 0, n - 1);
    cout << count << endl;
}

发表于 2016-08-29 18:31:12 回复(0)
terminator12头像 terminator12 
//java写的，思路参考上面的，把算移位权重 直接用字符串切分比较，算是优化了，就没有超时，AC了 import java.util.*;

public class Main {

	static List<String> list = new ArrayList<String>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			int k = scan.nextInt();
			String[] strs = new String[n];
			int count = 0;
			for(int i=0; i<n; i++){
				strs[i] = scan.next();
			}
			arrange(strs, 0, n);
			for(int i=0; i<list.size(); i++){
				if(weight(list.get(i)) == k)
					count ++;
			}
			System.out.println(count);
		}
	}
	public static void arrange(String[] arr, int start, int len){
		if(start == len - 1){
			String temp = "";
			for(int i=0; i<arr.length; i++)
				temp += arr[i];
			list.add(temp);
		}else {
			for(int i=start; i<len; i++){
				swap(arr,start,i);
				arrange(arr,start + 1, len);
				swap(arr,start,i);
			}
		}
	}
	public static void swap(String[] arr, int x, int y){
		String temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
	public static int weight(String str){
		int ans = 0;
        int len = str.length();
		for(int i=1; i<=str.length(); i++){
			if(str.substring(0,i).equals(str.substring(len-i,len)) && str.substring(0,len-i).equals(str.substring(i,len)))
				ans ++;
		}
		return ans;
	}
}


发表于 2016-08-24 12:42:34 回复(3)
liuzhan头像 liuzhan
kmp算法可以很快求出字符串的循环节，这个题串很短，所以暴力枚举也可以过啦
发表于 2016-08-20 20:35:48 回复(0)
救赎之道就在其中头像 救赎之道就在其中
有用java通过的吗？我的超时了，醉了，思路也一样啊
发表于 2016-08-16 21:25:59 回复(0)
小刀初试头像 小刀初试
题目意思理解有误，权值并不是偏移长度，居然是所有左移的个数，也就是所有与原串相同的 左移 方案个数。全排列可以使用stl中的next_permutation. 

#include <bits/stdc++.h>
using namespace std;
int getk(string &str){
	int k=1;
	string tmp=str;
	for(int i=0;i<str.length()/2;i++){
		tmp=tmp.substr(1)+tmp[0];
		if(tmp==str){
			k=str.length()/(i+1);
            break;
        }
    }
    return k;
}
int main(){
    int n,k,p;
    string str;
    for(vector<string> vs;cin>>n>>k;){               
        vector<int> ids(n,0);
        for(int i=0;i<n;ids[i]=i,++i);
        for(++n;--n;cin>>str,vs.push_back(str));
        do{
            stringstream istr;
            for(int i=0;i<ids.size();istr<<vs[ids[i++]]);
            istr>>str;
            if(getk(str)==k) ++n;
        }while(next_permutation(ids.begin(),ids.end()));
        cout<<n<<endl;
    }
    return 0;
}

发表于 2016-08-08 17:56:38 回复(0)
提交观点

问题信息

C++工程师 2017 字符串 模拟 运维工程师 前端工程师 算法工程师 PHP工程师 字节跳动 Java工程师
来自：字节跳动2017客户端...
难度：
23条回答 16739浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号