{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n在欧老师小时候总是被要求做这样一种作业,即物品分类。例如,给我们物品名称{豹子、草泥马、番薯、大象、狼桃、扁豆、葡萄、火龙果、芒果},我们可以将这些物品分为三类,分别是{豹子、草泥马、大象}、{番薯、狼桃、扁豆}和{葡萄、火龙果、芒果}。我们可以用一个映射序列{a,a,b,a,b,b,c,c,c}来表示这种分类,这意味着豹子、草泥马、大象属于a组,番薯、狼桃、扁豆属于b组,葡萄、火龙果、芒果属于c组。但是代表组的字母没有意义,字母只是用来表示不同的组。所以{a,b,c}和{d,e,g}是相同的,而{a,a},{a,b}是不同的。\n \u003ccenter\u003e\n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/dfca6131b1122267192a0a5e2f258ea9?v\u003d1631263412\"\u003e\n \u003c/center\u003e\n \u003cbr\u003e\n 学生完成后提交给老师他们的绘图顺序,然后老师会给他们打分。教师通过计算学生的映射序列和答案序列之间的最大相似性来给他们作业打分。相似性的求法为:\n\u003cbr\u003e\n\u003cbr\u003e\nsimilarity(P,Q)\u003dtotal(Pi\u003d\u003dQi)/Len\n\u003cbr\u003e\nLen\u003dLength(P)\u003dLength(Q),i\u003d1,2,...,Len\n\u003cbr\u003e\n其中,total(Pi\u003d\u003dQi)表示相应位置中相等序列的总数。最大相似性是指P与Q的所有等价序列之间的最大相似性,其中P是答案,并且是固定的。现在给出学生提交的答案和老师的答案,求最大相似性。\n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入包含多个测试样例。第一行是样例总数T (T \u0026lt; 15),然后输入T个测试样例。每一个样例以三个数字n (0 \u0026lt; n \u0026lt; 10000), k (0 \u0026lt; k \u0026lt; 27), m (0 \u0026lt; m \u0026lt; 30)开始,这三个数字是物品的数量、所要分的组和学生的总数。下一行由n个字母组成,每个字母的范围为[A…Z],分别表示不同的组。可以假设序列中不同字母的数量正好是k。这个字母序列代表答案。以下是m行,每行包含n个字母,每个字母也在[A…Z]范围内,代表m个学生的答案序列。您可以假设每个序列中不同字母的数量不超过k。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,输出m行,每行是一个浮点数(小数点后四舍五入到4位)。您应该按照序列输入的顺序输出m个答案。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2\n10 3 3\nA A B A B B C C C C\nF F E F E E D D D D\nX X X Y Y Y Y Z Z Z\nS T R S T R S T R S\n3 2 2\nA B A\nC D C\nF F E\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1.0000\n0.7000\n0.5000\n1.0000\n0.6667\u003c/pre\u003e"}}]}