ZZXYY's blog

作为整个GDOI2015里面我唯一可以当场A的题目，也只好写写题解了什么的。

题目点击这里

一个组织里有N个人，要讨论M个问题，每个人对每个问题有一个意见值，并且保证每个人所有的意见值平方的和等于1，两个人的意见一致性为他们两个人每个问题的意见值的乘积的总和，整个组织的意见一致性为整个组织所有人两两的意见一致性的总和，现在要加入K个人，问加入K个人后整个组织的意见一直性最高有多少？

分析：

N个人可以抽象成N个M维的向量，而题目有正好说了每个向量的长度都是1（单位向量），那么组织一致性就是所有向量两两数量积的和了。

由于N达到了10000，所以最好用O（NM）的办法求出答案。

我们可以发现，(a+b)^2=a^2+b^2+2ab，(a+b+c)^2=a^2+b^2+c^2+2(ab+bc+ca).......，(a1+a2+...+an)^2=a1^2+a2^2+....+an^2+2(a1a2+a1a3+..+a1an+...an-1an)，所以我们只需要将所有的向量加起来平方，减去所有向量的平方（也就是1），除以2就是组织一致性了。

现在思考第二个问题，这k个人该如何加入。

当组织有N个人时，加入一个人后组织的一致性就增加了ka1+ka2+..kan，提一个k就变成了k(a1+a2+a3..+an)，是两个向量的数量积，而这两个向量的长度已经定了下来，所以我们可以通过改变k来改变两个向量的夹角变成两个向量同向，这样数量积就增加了(a1+a2+..an)的模长，第二个人加入数量积就会再增加(a1+a2...an)+1，以此类推就可以求出最终答案。