游戏通关了，把暑假没有AC的pokemon再看了一遍。
能过师兄的数据，但仍不能AC
思路二：
总体思路：记录两两互质所有状况，记录权重，用权重判断数据的取舍。
（1）引入权重的概念，两重循环遍历数据，判断两两互质的数量。并将权重记录下来。
如：7 6 5 4 3 2 1中，7与其他任何一个数都互质，所以他的权重是6，而6与4 3 2 都不互质，所以权重为3.
（2）记录7 6 5 4 3 2 1互质的情况，如果7与6互质，就判定为1，并记录，否则判定为0。（好像是状态压缩的概念，但我没学过状态压缩）
（3）排序权重，将权重高的排在前面，权重低的排在后面，避免因为逻辑问题反而把权重高的舍弃了。（比如，a权重为7，b权重为6，c权重为6, d权重为8，如果先判断a，把b，c舍弃了，如果b,c和d是互质的，b,c被舍弃后d权重会下降变成6，c就会被舍弃。）
（4）如果两个数不互质，就通过权重比较舍弃数据
代码如下：
#include<iostream>
using namespace std;
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
void niubi(int n, long long a[20][20])
{
long long i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (a[i][0] != 0 && a[j][0] != 0)
{
if (gcd(a[i][0], a[j][0]) == 1)//判断两个数是否互质，如果互质
{
a[i+1][j+1] = 1;
}
else
{
a[i+1][j+1] = 0;
}
}
}
}
}
int main()
{
int T;
int n;
int i, j,k;
int sum;
long long temp;
long long a[20][20] = {0};
long long dp[20] = {0};
int ins[20];
//用二维数组记录，第一个维度代表着输入的数据，第二个维度代表数据互质状况，第二个维度末尾的一位代表着权重，
//互质为1，不互质为0，数据加起来的总和即为权重
cin >> T;
while (T--)
{
cin >> n;
sum = 0;
memset(a, 0, sizeof(a));
for (j = 0; j < n; j++)
{
cin >> a[j][0];//在第0位输入对应的数据
a[0][j] = a[j][0];
}
for (j = 0; j <= n; j++)
ins[j] = j;//初始化对应坐标
niubi(n, a);
for (i = 1; i <= n; i++)//计算权重
for (j = 1; j <= n; j++)
{
a[j][n + 1] += a[i][j];
dp[j] = a[j][n + 1];
}
for (i = 1; i <= n; i++)//给权重坐标排序
{
for (j = 1; j <= n; j++)
{
if (dp[i] > dp[j])
{
temp = dp[i];
dp[i] = dp[j];
dp[j] = temp;
temp = ins[j];
ins[j] = ins[i];
ins[i] = temp;
}
}
}
/*for (i = 1; i <= n; i++)
cout <<"\t"<< a[0][i-1];
cout << endl;*/
/*for (i = 1; i <=n+1; i++)
{
cout<< a[i-1][0] <<'\t';
for (j = 1; j <=n; j++)
cout << a[j][i] << '\t';
cout << endl;
}*/
//在此之前要将权重高的排个序
/*for (j = 0; j <= n; j++)
cout << ins[j] << '\t';
cout << endl<<endl;*/
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
//cout << a[ins[i]][j] << '\t';
if (a[ins[i]][j] == 0 && ins[i] != j&&a[ins[i]][n+1]!=0)
{
for (k = 1; k <= n + 1;k++) a[j][k]=0;
}
//cout << a[ins[i]][n + 1] << a[j][n+1] << endl << endl;
}
//cout << endl;
}
/*cout << endl;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
cout << a[ins[i]][j] << '\t';
}
cout << endl;
}*/
for (j = 1; j <=n; j++)
if (a[j][n+1] != 0) sum++;
cout << sum << endl;
}
return 0;
}
运行截图：
image.png
师兄的数据:
image.png
