ARC145D 题解

yxzyy-x\neq z-y 这个东西转化成 2yx+z2y\neq x+z

先不管总和的限制,考虑三进制(为啥会想到这个啊),如果一个集合里面所有数字的三进制表示都没有 22(好像都没有 00 或者都没有 11 是一样的),那么这个集合一定合法,证明是显然的。

然后调整总和,记当前总和是 sumsum,如果 nmsumn\mid m-sum 那么我们就可以直接偏移,但是不一定可以整除。

方法是先把最后一位都设成 00,然后根据余数把若干个调整成 11,这样就好起来了。

主要还是这个三进制的套路感觉比较神奇。

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,m,a[10001],cnt,sum;
inline bool check(int x)
{
    while(x)
    {
        if(x%3==2)
            return 0;
        x/=3;
    }
    return 1;
}
signed main()
{
    cin>>n>>m;
    for(int i=0;cnt<n;++i)
        if(check(i))
            sum+=(a[++cnt]=3*i);
    int p=(m%n+n)%n;
    for(int i=1;sum%n!=p;++i)
    {
        ++a[i];
        ++sum;
    }
    int d=(m-sum)/n;
    for(int i=1;i<=n;++i)
        cout<<a[i]+d<<" ";
    cout<<'\n';
    return 0;
}

怄火。挥手。转圈。街舞。跳跳。献吻。跳绳。激动。发抖。磕头。爱情。飞吻。左太极。右太极。回头。