B. Decidophobia（Codeforces Round 1105 (Div. 1)）

B. Decidophobia 题解

思路

设g_i表示第i个人是否收到礼物：

• g_i = 1：收到礼物；
• g_i = 0：没有收到礼物。

考虑一个有向关系i -> j，其中j在i的视野内。

• 如果i收到礼物、j没收到礼物，贡献是+a_i；
• 如果i没收到礼物、j收到礼物，贡献是-a_i；
• 两人状态相同，贡献是0。

这三种情况都可以统一写成：

a_i * (g_i - g_j)

所以总幸福值为：

sum_i a_i * (2d * g_i - sum_{j in view(i)} g_j)

把含有同一个g_i的项合并。由于视野关系是对称的，j在i的视野内等价于i在j的视野内，因此第i个人的选择系数为：

c_i = 2d * a_i - sum_{j in view(i)} a_j

总幸福值就变成：

sum_i c_i * g_i

每个g_i都可以独立选择：

• 如果c_i > 0，让第i个人收到礼物，答案增加c_i；
• 如果c_i <= 0，不送给第i个人更优。

因此答案是：

sum_i max(0, c_i)

剩下的问题是快速求每个人视野内2d个人的权值和。

因为是环，可以把数组复制一遍，然后用前缀和求：

• 顺时针d个人：i + 1 ... i + d
• 逆时针d个人：i + n - d ... i + n - 1

这里使用0下标。

正确性证明

对任意一对有视野关系的人i和j，从第i个人视角产生的贡献只取决于g_i和g_j。

当(g_i, g_j)分别为(1, 0)、(0, 1)、(1, 1)、(0, 0)时，a_i * (g_i - g_j)分别等于a_i、-a_i、0、0，与题目定义完全一致。

因此总贡献可以写为所有有向视野关系上的a_i * (g_i - g_j)之和。

展开后，第i个人自己收到礼物时，会从自己的2d个视野对象中得到2d * a_i的正系数；同时，如果第i个人收到礼物，会让所有能看到他的人产生负项。由于视野关系对称，能看到第i个人的人正好也是第i个人视野内的人，所以负系数为视野内所有人的权值和。

所以第i个人是否收到礼物只影响线性项c_i * g_i，其中：

c_i = 2d * a_i - sum_{j in view(i)} a_j

所有人的选择互相独立。若c_i > 0，取g_i = 1最优；若c_i <= 0，取g_i = 0不劣。因此算法得到的sum_i max(0, c_i)就是最大总幸福值。

复杂度

每个测试用例只需要构造一次长度为2n的复制数组和前缀和，并线性扫描所有人。

时间复杂度：O(n)

空间复杂度：O(n)

参考代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn,d;cin>>n>>d;vector<longlong>a(n);for(inti=0;i<n;++i){cin>>a[i];}vector<longlong>doubled(2*n);for(inti=0;i<2*n;++i){doubled[i]=a[i%n];}vector<longlong>pref(2*n+1,0);for(inti=0;i<2*n;++i){pref[i+1]=pref[i]+doubled[i];}longlonganswer=0;for(inti=0;i<n;++i){longlongclockwise=pref[i+d+1]-pref[i+1];longlongcounter_clockwise=pref[i+n]-pref[i+n-d];longlongseen_sum=clockwise+counter_clockwise;longlongcoefficient=2LL*d*a[i]-seen_sum;if(coefficient>0){answer+=coefficient;}}cout<<answer<<'\n';}return0;}