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;}