ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

CF1477A Nezzar and Board 题解

posted on 2021-01-29 01:30:44 | under 题解 |

说实话这个E比D简单多了,结果呢我光顾着想D了,然后C读入忘开long long连罚五发,本来打算上CM,最后反而下了13分。还是太菜了/kk

我们看到这个奇妙系数,推了推发现没什么简单结论,就知道接下来应该打个表。

打了三元的(我这边只能bfs两层,三层就输出爆了)之后,你发现三个数前面的系数和总是$1$。归纳法证明,$x,y$前面系数和都是$1$,那么$2x-y$前面系数和还是$1$,所以任意方案操作出来的数中,所有数前面的系数和都是$1$。

接下来我们考虑调整法逼近正确方案。首先让第一个数系数为$1$,接下来给每个数调整系数,同时相反地调整第一个数的系数。根据前面的结论我们知道这样调完之后第一个数的系数也是对的。然后你发现每次给$a_i$增加$1$的系数,会给最后操作出来的数加上$a_i-a_1$,所以我们拿所有的$a_i-a_1$出来取个$\gcd$,设为$g$,然后看$a_1$和$k$膜$g$是不是同余就好了。

这个题给我们的启示大概是,数学题不能硬想,该打表就打表。另外要记得,有些题是可以先考虑正确方案的性质,然后再反推出正确方案的存在性判定或者构造方法的。

打表代码 :

#include<stdio.h>
#include<vector>
#include<map>
using std::vector;
using std::map;

struct Node
{
    int a,b,c;
    inline bool operator < (Node x) const
    {
        return a==x.a?b==x.b?c<x.c:b<x.b:a<x.a;
    }
};

Node operator + (Node x,Node y)
{
    return {x.a*2-y.a,x.b*2-y.b,x.c*2-y.c};
}

vector<Node> v;
map<Node,bool> mp;

int main()
{
    v.push_back({0,1,0}),v.push_back({1,0,0}),v.push_back({0,0,1});
    int T=2;
    while(T--)
    {
        int t=v.size();
        for(int i=0;i<t;i++)
            for(int j=0;j<t;j++)
                if(!mp[v[i]+v[j]]) v.push_back(v[i]+v[j]),mp[v[i]+v[j]]=1;
    }
    for(int i=0;i<v.size();i++)
        printf("%d %d %d\n",v[i].a,v[i].b,v[i].c);
    return 0;
}

代码 :

#include<stdio.h>

int n;
long long k,a,b,g;

inline long long gcd(long long a,long long b)
{
    if(!b) return a;
    return gcd(b,a%b);
}

inline long long abs(long long x){ return x<0?-x:x; }

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%I64d%I64d",&n,&k,&a);
        g=0;
        for(int i=2;i<=n;i++)
            scanf("%I64d",&b),g=gcd(g,abs(b-a));
        printf((k-a)%g==0?"YES\n":"NO\n");
    }
    return 0;
}