hdu 6140 思维

题解：这道题中的数能组成的数构成了一个连续区间.

一开始只有 a1 的时候能够构成 [-1, 1][−1,1] 中的所有整数.

如果一堆数能够构成 [-a, b][−a,b] 中的所有整数, 这时候来了一个数 x. 如果 x 只能取正值的话, 如果有 x<b 那么就能够构成 [-a, b+x][−a,b+x] 的所有整数.

如果 x 只能取负值, 如果有 x<|a| 那么就能构成 [-a-x, b][−a−x,b] 的所有整数.

如果 x 可正可负, 如果有 x<min(|a|,b) 那么就能构成 [-a-x, b+x][−a−x,b+x] 中的所有整数.

然后题目中那个奇怪的不等式就保证了上面的"如果有"的条件.

比赛的时候就想到了可正可负的情况，然后一直卡，弱的一批/

ac代码：

#include <cstdio>

#include <iostream>

#include <cstring>

#include <string>

using namespace std;

int a[];

int flag[];

int main()

{

    int  t;

    scanf("%d",&t);

    while(t--)

    {

        int n,k;

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

        for(int i=;i<=n;i++) scanf("%d",&a[i]);

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

        {

            string s;

            cin>>s;

            if(s[]=='N') flag[i]=;

            else if(s[]=='L') flag[i]=;

            else flag[i]=-;

        }

        int l=-;

        int r=;

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

        {

            if(flag[i]==)

            {

                l-=a[i];

                r+=a[i];

            }

            else if(flag[i]==) r+=a[i];

            else l-=a[i];

        }

        if(k>=l && k<=r) cout<<"yes"<<endl;

        else cout<<"no"<<endl;

    }

    return ;

}

巴特西

hdu 6140 思维

最新文章

热门文章