游戏通关了,把暑假没有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;
}
运行截图:
师兄的数据: