Wannafly挑战赛27 A-灰魔法师(思维)

题目链接：https://www.nowcoder.com/acm/contest/215/A

       这道题暴力肯定是过不了的，然后就有一种很巧妙地方法，因为数据范围只有1e5，两个数相加最大也只有2e5，然后2e5的数据中，完全平方数的个数其实只有几百个，所以我们可以将2e5范围内的完全平方数先打个表存起来，然后对于输入的n个数，我们只需要记录它出现的个数，然后我们去枚举1-100000中的数。

       对于接下来的操作，分为两种情况，一种是2 2 2，对于有3个2的情况，它符合条件的个数为3(就是3*(3-1)/2)，另一种情况是1 1 3 3，这样的话符合情况的个数就是2(因为不能重复)，这种情况的解就是pre[1] * pre[3] / 2。所以我们只需要对于这两种情况讨论就行了。

       还有一个小坑点就是在第二种情况的时候，我们要先把所有的第二种情况算出来以后再除以2，不然会有精度损失(详细看呆码)，还有改用ll的地方记得用ll。

       有一点不太明白不知道为啥我的num不能从0开始，这一点wa了n发...很巧妙的一道题...

AC代码：

#include <bits/stdc++.h>
#define maxn 100000
#define ll long long
using namespace std;
int pre[maxn],a[maxn];
int n,num;
  
int main()
{
  scanf("%d",&n);
  num = 1;    // 不知道为啥不能从0开始...
  for(int i=1;i*i<=200000;i++){
    a[num++] = i * i;
  }
  memset(pre,0,sizeof(pre));
  for(int i=0;i<n;i++){
    int x;
    scanf("%d",&x);
    pre[x] ++;
  }
  ll sum = 0,sum1 = 0;
  for(int i=1;i<=num;i++){
    for(int j=1;j<=maxn;j++){
      if(pre[j] == 0) continue;
      int ans = a[i] - j;
      if(ans > maxn) continue;
      if(ans <= 0) break;
      if(pre[ans]){
        if(ans == j) sum1 += ((ll)pre[j] * (ll)(pre[j] - 1)) / 2;
        else sum += (ll)pre[ans] * (ll)pre[j];    // 这里不要除以2，会有精度损失
      }
    }
  }
  printf("%lld\n",sum1 + sum / 2);
  return 0;
}