题解：P6340 [COCI 2007/2008 #2] KEMIJA / [SNOW] - 12

fish_love_cat · 2026-01-24 02:27:33 · 题解

和另一条鱼手动 duel 到的。

完败嘟嘟嘟。

事实上本题不考虑无解。

注意到 i 和 i+3 一定有差分关系，于是可以递推。

然后当 n 不是 3 的倍数时，我们只要知道一个就可以通过递推来确定全部。

不妨设 a_1=0。

显然之后如果 a_1\gets a_1+k，那么每一个都会有 a_i\gets a_i+k。

对于最开始的限制是必须得满足的，所以我们算出 k 的值来满足第一个限制。

之后的限制如果不满足就会和现在所满足的限制矛盾，无解，所以我们不用管后面的情况。

考虑 n 是 3 的倍数。

此时模 3 不同余的点相互独立，不妨钦定 a_1=a_2=a_3=0。

一样递推，考虑最后如何适配限制。

显然加在这三个数哪里都是等效果，所以把要增加的东西全部算出来以后压在 a_1 上就好。

同样的这里因为满足已有限制状态被完全固定下来了，只要有解那么这个构造肯定是对的。

做完了。

#include<bits/stdc++.h>
using namespace std;
int a[10005];
bool vis[10005];
int ans[10005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    if(n%3==0){
        vis[0]=vis[1]=vis[2]=1;
        for(int i=0;i<n;i+=3,i%=n){
            if(vis[(i+3)%n])break;
            vis[(i+3)%n]=1;
            ans[(i+3)%n]=ans[i]+a[(i+1)%n]-a[i];
        }
        for(int i=1;i<n;i+=3,i%=n){
            if(vis[(i+3)%n])break;
            vis[(i+3)%n]=1;
            ans[(i+3)%n]=ans[i]+a[(i+1)%n]-a[i];
        }
        for(int i=2;i<n;i+=3,i%=n){
            if(vis[(i+3)%n])break;
            vis[(i+3)%n]=1;
            ans[(i+3)%n]=ans[i]+a[(i+1)%n]-a[i];
        }
        int qwq=(a[0]-(ans[0]+ans[1]+ans[2]));
        ans[n]=ans[0];
        for(int i=1;i<=n;i++)cout<<ans[i]+qwq*(i%3==1)<<'\n';
        return 0;
    }
    vis[0]=1;
    for(int i=0;i<n;i+=3,i%=n){
        if(vis[(i+3)%n])break;
        vis[(i+3)%n]=1;
        ans[(i+3)%n]=ans[i]+a[(i+1)%n]-a[i];
    }
    int qwq=(a[0]-(ans[0]+ans[1]+ans[2]))/3;
    ans[n]=ans[0];
    for(int i=1;i<=n;i++)cout<<ans[i]+qwq<<'\n';
    return 0;
}
// 有只手啪一声放上爱丽洁的肩膀。
// 她吓了一跳抬头，眼前是一位魔女。

//「不可以喔，你要好好付钱才对。」