【题解】WebGoC 118869.项链

题目描述

魔法学院开设了一项魔法训练课程，学员可通过学习掌握一种魔法，能够将任意一条项链转换为另一条项链。项链由n颗各种颜色的珠子串联而成，珠子的顺序你可以自由调整，魔法效果与限制如下：

你可以施展若干次魔法，每次可以把项链中所有颜色x的珠子都变成颜色y，但作为代价，项链中所有颜色y的珠子也会变成颜色x。

现在给定一条目标项链，以及需要施展魔法的k条初始项链（所有项链长度均为n，颜色用由小到大排好序的整数表示）。对于每条初始项链，若能通过若干次魔法施展将其转换为目标项链，则画1号色的“ ✔️ ”；若无法通过任何魔法组合达成转换，则画一个0号色的“×”，所有线条线粗都是10。

画图时，请先使用moveTo命令，把画笔移动到（-300,0）。

输入格式

• 第一行，2个整数n和k。(5≤n≤100,2≤k≤7)。
• 第二行，n个以空格隔开由小到大排好序的整数ai，表示目标项链珠子的颜色。
• 接下来有k行，每行n个以空格隔开由小到大排好序的整数bi，表示需要施展魔法的每条项链珠子的初始颜色。（数据：0≤ai,bi≤100，数据：0≤ai,bi≤1×10^9）

输出格式

正确的图形。

输入/输出例子1

输入：

6 3

1 2 2 3 4 7

1 3 4 5 5 7

1 1 1 2 2 2

1 2 3 4 6 6

输出：

样例解释

项链长度为6，目标项链颜色是1 2 2 3 4 7。

• 第一串项链：把5号色变成2号色，此时项链没有2号色，1 3 4 5 5 7变为1 3 4 2 2 7，交换顺序便得到目标项链1 2 2 3 4 7
• 第二串项链：无法变成目标项链
• 第三串项链：

参考答案

int target[105]; int now[105]; int workArr[105]; int workArr2[105]; int ans[10]; void T() { p.c(1).size(10); p.rt(30).fd(60).bk(60); p.lt(60).fd(30).bk(30).rt(30); } void F() { p.c(0).size(10); p.rt(45).fd(30).bk(60); p.fd(30).lt(90); p.fd(30).bk(60).fd(30).rt(45); } int optSort(int len) { int i,j,temp; int swapFlag; for(i = 0; i < len; i = i + 1) { swapFlag = 0; for(j = 0; j < len - i - 1; j = j + 1) { if(workArr[j] > workArr[j+1]) { temp = workArr[j]; workArr[j] = workArr[j+1]; workArr[j+1] = temp; swapFlag = 1; } } if(swapFlag == 0) { break; } } return 0; } int buildTargetFreq(int len) { int i; for(i = 0; i < len; i = i + 1) { workArr[i] = target[i]; } optSort(len); int count = 0; int same = 1; for(i = 1; i < len; i = i + 1) { if(workArr[i] == workArr[i-1]) { same = same + 1; } else { workArr[count] = same; count = count + 1; same = 1; } } workArr[count] = same; count = count + 1; optSort(count); return count; } int buildTestFreq(int len) { int i; for(i = 0; i < len; i = i + 1) { workArr[i] = now[i]; } optSort(len); int count = 0; int same = 1; for(i = 1; i < len; i = i + 1) { if(workArr[i] == workArr[i-1]) { same = same + 1; } else { workArr[count] = same; count = count + 1; same = 1; } } workArr[count] = same; count = count + 1; optSort(count); return count; } int compareFreq(int lenA, int lenB) { if(lenA != lenB) { return 0; } for(int i = 0; i < lenA; i = i + 1) { if(workArr[i] != workArr2[i]) { return 0; } } return 1; } int main() { int n, k; cin >> n >> k; int i,t; for(i = 0; i < n; i = i + 1) { cin >> target[i]; } int sizeBase = buildTargetFreq(n); for(i = 0; i < sizeBase; i = i + 1) { workArr2[i] = workArr[i]; } for(t = 0; t < k; t = t + 1) { for(i = 0; i < n; i = i + 1) { cin >> now[i]; } int sizeTest = buildTestFreq(n); ans[t] = compareFreq(sizeBase, sizeTest); } p.speed(10); p.moveTo(-300, 0); for(t = 0; t < k; t = t + 1) { if(ans[t] == 1) T(); else F(); p.rt(90).up().fd(100); p.lt(90).down(); } p.hide(); return 0; } //难点：超时

题目链接：

https://v1.51goc.com/question/viewProgram/118869

（进去后要登录）