CF1028E Restore Array 构造

时间：2021-11-25 18:10:23

正解:构造

解题报告:

传送门!

是的灵巧还在写构造,,,不知道484我做题太慢的缘故我感觉我做了好久的构造了然而一半的题目都没做完QAQ

要哭出来了QAQ

然后说下这题的解法,开始花了这——么的时间也没有get,,,然后听psj又讲了遍才发现是我傻逼了,,,

这题的解法趴,大概是这样的

首先对于这种取余的,一般来说看到之后第一反应就要想到商=0或者商=1,这样比较好做

那这道题中是商=1,也就是说我们只要Ai=Ai+1+Bi

再加上这题是个环

看到环你难道没有断环为链的冲动嘛

所以就找一个i,然后一路按照我们刚才求的式子推过去就好了

那剩下的唯一一个问题就是,我们怎么保证推一圈推回来之后A依然是合法的呢

思考怎么样会是合法的鸭

只要保证Ai%Ai+1=Bi就成

显然从上面求的那个式子可以发现A是单调增的了

那就结果会是Ai+1是max然后Ai是min,那就Ai=Bi了

所以我们只要找一个地方断开,断开的值A就=B就好了

另外一个鸭,如果要合法就还要保证余数<=除数是趴

那我们怎么保证余数<=除数啊!

现在我们已经知道Ai=Bi并且Ai是min了

那只要Bi是max就成立辣!

好了那就做完了!只是剩几个细节交代一下

1)  如果Bi的前一个Bi-1也是max怎么办,那样就会导致余数=除数就非法了嘛

那我们就改一下变成i-1=i,好辣

那如果再往前推一个,就继续往前走

那如果Bi全部相等呢

那就不成立了嘛,比较显然?(唯一一个例外就是,B全部=0那就只要A全部相等就好辣!

2)  还有一个是,不想写了回家写咕咕咕

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

const ll N=;

ll n,a[N],b[N],stp,nw;

inline ll read()

{

    char ch=getchar();ll x=;bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

int main()

{

    n=read();rp(i,,n){b[i]=read();if(b[i-]<b[i] && i!= && b[i]!=)stp=i;}if(b[n]<b[] && b[]!=)stp=;nw=stp-;a[stp]=b[stp];

    if(!stp)

    {

        if(b[]==){printf("YES\n");rp(i,,n)printf("1 ");}

        else printf("NO\n");

        return ;

    }

    while(nw!=stp)

    {if(nw<)nw=n,a[nw]=a[]+b[nw];else a[nw]=a[nw+]+b[nw];--nw;}

    printf("YES\n");rp(i,,n)printf("%lld ",a[i]);

    return ;

}

这儿是WA在了第五个点的代码QwQ

相关文章