对了！^.^ ^.^ ^.^ ^.^ ^.^ ^.^ ^.^ ^.^ ^.^ ^.^！
23333333333333333333333333~
下面有解析：
[20分做法] 看完这题，第一想法当然是无脑暴力啦...直接枚举x,y,z,看是否满足条件即可。算法复杂度为 O(N^3)O(N^3) 。[代码就算了] 这样就可得20分了。当然，如果你想用更高级的算法不开long long也是可以的[不是了]。
[40分做法] 可以直接枚举x，z的值，通过条件(1)求出y。再看是否满足条件。算法复杂度为 O(N^2)O(N^2) 。
[40~50分做法] 仍然是枚举x,z的值，但可以先分析x+z=2*y的奇偶性，因为xyz是整数，因此2y是2的倍数，因此x,z必然都为偶数或奇数，因此可以分奇偶性进行枚举，此时这个三元组即可不考虑y值的大小，即为当(i%2==1)枚举前面奇数序列相同的颜色进行算分数即可，算法复杂度为 O(N^2/2)O(N^2/2) 。
[100分做法] 通过上面的观察我们可以发现倒回去算前面的分数可能比较浪费时间，因此，我们采用数学的方法来优化此题(放心，很简单的)。
懒得打了，自己看代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
using namespace std;
long long n,m,num[100005],cont[2][100005],cl;
long long sum1[3][100005],sum2[3][100005];
long long ans;
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
for(int i=1;i<=n;i++)
{
scanf("%lld",&cl);
if(i%2==1)
{
ans=(ans+sum1[0][cl]%10007+i*sum1[1][cl]%10007+num[i]*sum1[2][cl]%10007+cont[0][cl]*i*num[i]%10007)%10007;
sum1[0][cl]=(sum1[0][cl]+num[i]*i)%10007;
sum1[1][cl]=(sum1[1][cl]+num[i])%10007;
sum1[2][cl]=(sum1[2][cl]+i)%10007;
cont[0][cl]++;
}
else
{
ans=(ans+sum2[0][cl]%10007+i*sum2[1][cl]%10007+num[i]*sum2[2][cl]%10007+cont[1][cl]*i*num[i]%10007)%10007;
sum2[0][cl]=(sum2[0][cl]+num[i]*i)%10007;
sum2[1][cl]=(sum2[1][cl]+num[i])%10007;
sum2[2][cl]=(sum2[2][cl]+i)%10007;
cont[1][cl]++;
}
}
printf("%lld",ans%10007);
}
[呵呵]
共 1 条回复
棒棒的！