GDOI2015DAY2第四题题解

  • 内容
  • 评论
  • 相关

作为整个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,以此类推就可以求出最终答案。

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据