【题解】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 31 2 2 3 4 71 3 4 5 5 71 1 1 2 2 21 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第二串项链无法变成目标项链第三串项链第一步把2号色变成7号色项链没有7号色1 2 3 4 6 6变为1 7 3 4 6 6第二步把6号色变成2号色此时项链没有2号色1 7 3 4 6 6变为1 7 3 4 2 2交换顺序便得到目标项链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[j1]) { temp workArr[j]; workArr[j] workArr[j1]; workArr[j1] 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进去后要登录