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)参考代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,d;cinnd;vectorlonglonga(n);for(inti0;in;i){cina[i];}vectorlonglongdoubled(2*n);for(inti0;i2*n;i){doubled[i]a[i%n];}vectorlonglongpref(2*n1,0);for(inti0;i2*n;i){pref[i1]pref[i]doubled[i];}longlonganswer0;for(inti0;in;i){longlongclockwisepref[id1]-pref[i1];longlongcounter_clockwisepref[in]-pref[in-d];longlongseen_sumclockwisecounter_clockwise;longlongcoefficient2LL*d*a[i]-seen_sum;if(coefficient0){answercoefficient;}}coutanswer\n;}return0;}