CodeForces 639C Bear and Polynomials

Bear and Polynomials

题解：

如果改变一个其中的一个数，那么需要知道的是，前面的数都可以进到当前位来，如果过不来的话，那么就会因为前面有数导致无法变成0。

所以我们将前面的数不断向高位转移，找到第一个不能往上进位的位置, p。

现在只有在0 <= i <= p 的时候才有解。

然后我们从高位到地位转移系数。

然后到0 <= i <= p的地方再check合法性。

注意的是，如果当前系数的绝对值 > 2e9, 那么就是不会再出现合法情况了，因为不可能再变成0了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 2e5 + ;

int a[N];

int n, k;

int solve(){

    LL tv = , p = n;

    int ret = ;

    for(int i = ; i <= n; ++i){

        tv = tv /  + a[i];

        if(tv&){

            p = i;

            break;

        }

    }

    LL val = ;

    for(int i = n; i > p; --i){

        val = val *  + a[i];

        if(abs(val) > INF) {

            return ret;

        }

    }

    val = val *  + tv;

    if(abs(val) > INF) {return ret;}

    for(int i = p; i >= ; --i){

        if(abs(val - a[i]) <= k){

            if(i == n && val == a[i]) ;

            else {

                ++ret;

            }

        }

        val <<= ;

        if(abs(val) > INF) {return ret;}

    }

    return ret;

}

int main(){

    scanf("%d%d", &n, &k);

    for(int i = ; i <= n; ++i)

        scanf("%d", &a[i]);

    printf("%d\n", solve());

    return ;

}

巴特西

CodeForces 639C Bear and Polynomials

最新文章

热门文章