首页 > 其他 > 详细

codeforces A. k-String 题解

时间:2014-05-03 15:42:58      阅读:394      评论:0      收藏:0      [点我收藏+]

A string is called a k-string if it can be represented as k concatenated copies of some string. For example, the string "aabaabaabaab" is at the same time a 1-string, a 2-string and a 4-string, but it is not a 3-string, a 5-string, or a 6-string and so on. Obviously any string is a 1-string.

You are given a string s, consisting of lowercase English letters and a positive integer k. Your task is to reorder the letters in the string s in such a way that the resulting string is a k-string.

Input

The first input line contains integer k (1?≤?k?≤?1000). The second line contains s, all characters in s are lowercase English letters. The string length s satisfies the inequality 1?≤?|s|?≤?1000, where |s| is the length of string s.

Output

Rearrange the letters in string s in such a way that the result is a k-string. Print the result on a single output line. If there are multiple solutions, print any of them.

If the solution doesn‘t exist, print "-1" (without quotes).

Sample test(s)
input
2
aazz
output
azaz
input
3
abcabcabz
output
-1

本题有意思,是hash表的灵活运用。

思路:

1 计算好总字符数,和使用hash表A[26]记录好各个字符出现的次数

2 判断总字符是否可以被k整除,如果不可以,那么就不能分成k个子字符了

3 计算各个字符出现的次数是否能被k整除,如果不能,那么就不能分成k个子字符

4 根据字符出现的次数逐个打印

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

void KString()
{
	int k, len = 0;
	cin>>k;
	int A[26] = {0};
	char a;
	while (cin>>a)
	{
		A[a-‘a‘]++;
		len++;
	}
	if (len == 0 || len % k) 
	{
		cout<<-1;
		return;
	}

	bool ks = true;
	for (unsigned i = 0; i < 26; i++)
	{
		if (A[i] % k != 0) ks = false;
	}
	if (!ks) cout<<-1;
	else
	{
		for (int d = 0; d < k; d++)
		{
			for (unsigned i = 0; i < 26; i++)
			{
				if (A[i])
					for (unsigned j = 0; j < A[i]/k; j++)
					{
						cout<<char(i + ‘a‘);
					}
			}
		}
	}
}




codeforces A. k-String 题解,布布扣,bubuko.com

codeforces A. k-String 题解

原文:http://blog.csdn.net/kenden23/article/details/24875899

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!