解题分析

$1$.频率统计：遍历所有单词，统计每个字符出现的总次数。例如，在样例输入$1$中，"$h$"和"$i$"各出现$1$次，"$o$"和"$k$"各出现$1$次。

$2$.字符排序：将字符按频率降序排序，频率相同的按字符升序排列。这样可以确保高频率字符优先分配，且在频率相同时选择字典序较小的字符。

$3$.按键分配：将排序后的字符序列分成$12$段，每个按键分配的字符数可以不同，高频率字符应该尽量分配到前面的按键，且在每个按键的字符串中靠前

$4$.切割点确定：确定$11$个切割点，使得这$11$个点之后的字符作为下一个按键的开始字符。

解题思路

这个问题需要我们将一个连续的字符序列（标签带）切割成$12$段，分配给手机键盘的$12$个按键，使得输入词典中所有单词的平均按键次数最少。关键在于：

$1$.字符频率统计：首先需要统计词典中每个字符的出现频率，高频字符应该分配在按键序列的前面位置，以减少按键次数。

$2$.最优切割策略：将字符按频率降序排序，然后按频率高低依次分配到$12$个按键上。高频率字符应该尽量放在按键字符串的前面位置。

$3$.字典序处理：当存在多个最优解时，选择字典序最小的切割方案。

实现步骤

$1$.输入处理：读取测试用例数量$t$，对于每个测试用例：读取单词数量$M$，读取$M$个单词，统计每个字符的出现频率。

$2$.字符处理：创建包含所有可能字符的集合（$a-z, +, *, /, ?$），统计每个字符的总出现次数，过滤掉频率为$0$的字符。

$3$.排序字符：按频率降序排序，频率相同的按字符升序排列

$4$.确定切割点：将排序后的字符序列均匀分配到$12$个按键，计算$11$个切割点位置，确保切割后的分配方案使平均按键次数最少。

$5$.输出结果：提取$11$个切割点的字符，按字典序选择最优解，输出结果字符串。

代码实现

#include <iostream> 
#include <cstring> 
#include <cstdio> 
using namespace std;
 
const int N = 32;
 
char alph[] = " abcdefghijklmnopqrstuvwxyz+*/?";
int flect[140];
int num[N];
int s[N][N];
int dp[N][N];
int ans[N];
 
void init()
{ 
	for (int i = 1; i <= 30; i++)
		flect[(int) alph[i]] = i;
} 
char str[N];
 
int main()
{ 
	//freopen("in.txt", "r", stdin);
	init();
	int n, T, i, j, k;
 
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		memset(num, 0, sizeof(num));
		for (i = 0; i < n; i++)
		{
			scanf("%s", str);
			for (j = 0; str[j]; j++)
				num[flect[(int)str[j]]]++;
		}
		//dp
		memset(dp, 0x3f, sizeof(dp));
		int sum = 0;
		for (i = 1; i <= 19; i++)
		{
			sum += num[i] * i;
			dp[1][i] = sum;
			s[1][i] = 1;
		}
		for (i = 2; i <= 12; i++)
			for (j = i; j <= 30; j++)
			{
				for (k = i; k <= j; k++)
				{
					sum = 0;
					for (int h = k; h <= j; h++)
						sum += num[h] *(h - k + 1);
					if (dp[i - 1][k - 1] + sum < dp[i][j])
					{
						dp[i][j] = dp[i - 1][k - 1] + sum;
						s[i][j] = k;
					}
				}
			}
			int cnt = 0;
			int now = 30;
			for (i = 12; i > 1; i--)
			{
				ans[cnt++] = s[i][now];
				now = s[i][now] - 1;
			}
			for (i = cnt - 1; i >= 0; i--)
				printf("%c", alph[ans[i]]);
			printf("\n");
	}
	
}