题解归档 - cf2239B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2239B
• 本地来源：problems/cf2239B/idea.md
• 题目链接：https://codeforces.com/contest/2239/problem/B
• 原始标题：cf2239B - Decidophobia

思路

cf2239B - Decidophobia

pattern

Optimization objective linearization on binary decisions; circular prefix sums.

claim

Let y_i be 1 if person i receives a gift. For every visible unordered pair {i,j}, the combined contribution of the two people is

(y_i-y_j)(a_i-a_j).

With s_i=2y_i-1, this becomes

1/2 * (s_i-s_j)(a_i-a_j).

After summing over all visible pairs, the objective is

1/2 * sum_i s_i * C_i,

where

C_i = sum_{j visible from i} (a_i-a_j) = 2*d*a_i - sum_visible a_j.

Each s_i is now independent, so choose s_i=sign(C_i) and the maximum is

1/2 * sum_i |C_i|.

necessary

The original score is exactly the sum of pair contributions above; no interaction term remains after changing variables.

sufficient

Choosing each sign independently to match C_i reaches the upper bound of the linear expression, so the formula is attainable.

brute/check

For small n, enumerate all 2^n gift subsets and compare with 1/2*sum |C_i|. The submitted code was stress-checked against this brute force on random small circles.

edge

d < n/2 means the clockwise and counter-clockwise visible sets are disjoint. Use 64-bit for coefficients and 128-bit accumulation/printing. Equal weights can produce C_i=0; either choice is fine.

代码

来源：problems/cf2239B/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5;
ll s[maxn+5],pre[maxn*3+5];
char ch[100];
void print128(__int128 x){
    ll slsl,i,j,k;
    if(x==0){
        puts("0");
        return;
    }
    slsl=0;
    while(x>0){
        ch[++slsl]=char('0'+x%10);
        x/=10;
    }
    for(i=slsl;i>=1;i--) printf("%c",ch[i]);
}
int main(){
    ll t,n,d,i,j,k,cur,zc,zc2;
    __int128 ans;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&d);
        for(i=1;i<=n;i++) scanf("%lld",&s[i]);
        for(i=1;i<=3*n;i++) pre[i]=pre[i-1]+s[(i-1)%n+1];
        ans=0;
        for(i=1;i<=n;i++){
            cur=i+n;
            zc=(pre[cur-1]-pre[cur-d-1])+(pre[cur+d]-pre[cur]);
            zc2=2*d*s[i]-zc;
            if(zc2<0) zc2=-zc2;
            ans+=zc2;
        }
        print128(ans/2);
        printf("\n");
    }
    return 0;
}