【题解】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

（进去后要登录）