e417: 乘法~乘法~加法~

e417: 乘法~乘法~加法~

題目連結：e417: 乘法~乘法~加法~

題意：

給你N個數字X1~Xn，求出X1X2+X1X3+X1X4+......+XN-2XN-1+XN-2XN+XN-1XN

解法：

乘法公式：

(X1+X2+X3+......+XN-1+XN )^2

=(X1^2+X2^2+X3^2+......+XN-1^2+XN^2) + 2(X1X2+X1X3+X1X4+......+XN-2XN-1+XN-2XN+XN-1XN)

移項可得：

所求=(X1X2+X1X3+X1X4+......+XN-2XN-1+XN-2XN+XN-1XN )= [(X1+X2+X3+......+XN-1+XN )^2 +(X1^2+X2^2+X3^2+......+XN-1^2+XN^2) ]/2

即可在O(N)內完成(暴力解是O(N^2))

time:58ms

memory used:1.1MB

code:

1. #include<unistd.h>
2. #include<ios>
3. using namespace std;
4. char buf[1<<20],*p1=buf,*p2=buf;
5. inline int gc(){
6. return p1==p2&&(p2=(p1=buf)+read(STDIN_FILENO,buf,1<<20),p1==p2)?EOF:*p1++;
7. }
8. inline void pc(char c) {
9.     constexpr size_t buf_size = 1 << 20;
10.     static char buf[buf_size];
11.     static char *ptr = buf;
12.     if (ptr >= buf + buf_size || c == EOF) write(STDOUT_FILENO,buf, ptr - buf), ptr = buf;
13.     if (c != EOF) *ptr++ = c;
14. }
15. inline void print(long long x) {
16. if(x==0){pc('0');return;}
17. static int stk[20];
18. int *ptr;
19. ptr=&stk[0];
20. while(x){*ptr=x%10;x/=10;ptr++;}
21. ptr--;
22. while(ptr>=(&stk[0])){pc(*ptr+'0');ptr--;}
23. pc('\n');
24. }
25. template<typename T>
26. inline bool rit(T &x){
27.     char c;
28.     for(x=0,c=gc();c<'-';c=gc())if(c==EOF)return false;
29.     for(;c>='0';x=x*10+c-'0',c=gc());
30.     return true;
31. }
32. int main(){
33.     int n,a;
34.     while(rit(n)){
35.         long long sum1=0,sum2=0;
36.         for(int i=0;i<n;i++){
37.             rit(a);
38.             sum1+=a;
39.             sum2+=(a*a);
40.         }
41.         print((sum1*sum1-sum2)>>1);
42.     }
43.     pc(EOF);
44. }

本人的分享到此結束

若有更好的想法或建議,請在留言區留言喔