HDU 1407 测试你是否和LTC水平一样高 枚举、二分、hash

计算方程x^2+y^2+z^2= num的一个正整数解。num为不大于10000的正整数

思路：

方法一、直接三重循环暴力 234MS

方法二、枚举x和y，对z进行二分查找。62MS

方法三、枚举x和y，对z用hash判断是否存在 15MS

方法二和方法三都是枚举x和y，但是二分查找为O(log(n))而hash为O(1）

可以看到，方法一和方法三差了十几倍！

还有就是用goto从内重循环直接跳出简洁而优雅。

方法一：直接三重循环暴力 234MS

#include
  
   
#include
   
     int res[101]; int main() { int n; for(int i=1;i<=100;i++) res[i]=i*i; while(~scanf(%d,&n)) { for(int x=1;x<=100;x++) for(int y=1;y<=100;y++) for(int z=1;z<=100;z++) if( res[x]+res[y]+res[z]==n) { printf(%d %d %d ,x,y,z); goto end; } end:; } return 0; }
   
  

方法二：枚举x和y，对z进行二分查找。62MS

#include
  
   
#include
   
     int res[101]; int search(int n) { int L=1,R=101; while(L
    
     >1; if(res[m]==n) return m; else if(res[m] < n) L=m+1; else R=m; } return -1; } int main() { int n; for(int i=1;i<=100;i++) res[i]=i*i; while(~scanf(%d,&n)) { for(int x=1;x<=100;x++) { for(int y=1;res[x]+res[y]
     
      
 
      
方法三：枚举x和y，对z用hash判断是否存在 15MS
      
 
      
#include
       
        
#include
        
          const int MAXN=10001; int res[101]; struct HASH { bool exist; int index; }hash[MAXN]; int main() { int n; for(int i=1;i<=100;i++) { res[i]=i*i; hash[ res[i] ].exist=true; hash[ res[i] ].index=i; } while(~scanf(%d,&n)) { for(int x=1;x<=100;x++) { for(int y=1;res[x]+res[y]