网站品牌形象设计怎么做,做摄影和后期的兼职网站,中山做展示型网站,网站要怎么做才能让360收录传送 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format:%lld 题目描述 输入描述: 第一行一个整数n. 第二行n个整数ai. 输出描述: 一个整数表示上述求和式的答案. 示例1 输入 5
1 2 3 4 5输出…传送 时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format:%lld 题目描述 输入描述: 第一行一个整数n. 第二行n个整数ai. 输出描述: 一个整数表示上述求和式的答案. 示例1 输入 5
1 2 3 4 5输出
33备注: 1≤n≤1e5 0≤ai≤1e8
题解 根据题意就能打出最简单的暴力方法 for(int i1;in;i) for(int j1;jn;j) suma[i]a[j]; 复杂度On肯定超时这题也不可能这么水。
---------------------------------此处为做题时错误想法 我一开始这么想的a[i]a[j] a[j]a[i]所以j循环时从i1开始就行因为这个是对称的sum算完再*2最后再加上对角线上的i j的情况结果还是超时捂脸 (以下为正解) 啥性质111其余情况都为0 当12是我们可以转化成二进制运算011101 其实就是对应列运算 0 1 1 1 —— 0 1 我们看样例 1 -0 0 1 2 -0 1 0 3 -0 1 1 4 -1 0 0 5 -1 0 1 看第一列 0 0 0 1 1 因为0任何都是0所以看1第四五行有1 那运算时第四行第四行1第四行第五行1接着第五行再分别与第五行和第四行运算也是两个1最后加起来一共四个1.其实就是这一列1的数量的平方。你试试最后一列是不是也是这样 其实这个就是模仿暴力方法的第二个for循环i与每个j运算 那这样算例题结果就是 1 -0 0 1 2 -0 1 0 3 -0 1 1 4 -1 0 0 5 -1 0 1 结果-4 4 9 这个449就可以理解成有4个100,4个010,9个001因为咱们是用二进制运算要转换成十进制 100对应的就是4 22 010对应的就是2 21 001对应的就是1 20 二进制转换成十进制时要乘以对应位置2的n次方就是4 * 22 4 * 21 9 * 2033 33就是最后结果各位想明白了吗 代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll n;
ll a[10004];
ll w;
ll maxn;
int max(ll a,ll b)
{return ab?a:b;
}
int main()
{cinn;for(int i1;in;i){int ant0;cinw;while(w){ant;if(w1)a[ant];//求出每列1的数量 w1;}maxnmax(ant,maxn);//确定一共有多少列 }ll sum0;for(int i1;imaxn;i)sum(a[i]*a[i])(i-1);coutsum;return 0;
}
