hdu 6794 Tokitsukaze and Multiple 前缀和思想+思维

题意：

t组输入，给你一个长度为n的数组，你每次可以从数组中找到a[i]和a[i+1],然后用a[i]+a[i+1]这个新元素来覆盖掉a[i]和a[i+1]的位置（1<=i<n），从而数组长度也减去1

你可以进行任意次这样的操作，输出最后的数组中有多少数，是p的倍数

题解：

给你一个a数组的前缀和数组w，我们保证a[i]>=1,前缀和w[i]都被p取余过

假设i<j，那么如果w[i]和w[j]相等，那也就是说（a[i+1]+a[i+2]+...+a[j]）%p == 0,也就是说这一段是p的倍数

那么我们就可以依靠这一点去做题

我们先判断一下v[i]%p==0的点，然后依次这些点把原数组分割，分别对每一段进行上面这样的判断

代码：

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <vector>

#include <map>

#include <queue>

#include <stack>

#include <set>

#include <ctime>

#include <cstring>

#include <cstdlib>

#include <math.h>

#include<map>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 5;

ll v[maxn];

map<ll,ll>r;

int main()

{

    ll t;

    scanf("%lld",&t);

    while(t--)

    {

        ll n,p;

        r.clear();

        scanf("%lld%lld",&n,&p);

//        ll vis[p+5];

//        memset(vis,0,sizeof(vis));

        for(ll i=1; i<=n; ++i)

            scanf("%lld",&v[i]),v[i]%=p;

        ll sum=0,mod=0;

        r[0]=1;

        for(ll i=1; i<=n; ++i)

        {

            if(v[i]==0)

            {

                mod=0;

                r.clear();

                sum++;

                r[0]=1;

            }

            else

            {

                mod=(mod+v[i])%p;

                r[mod]++;

                if(r[mod]>=2)

                {

                    mod=0;

                    sum++;

                    r.clear();

                }

                r[0]=1;

            }

        }

        printf("%lld\n",sum);

    }

    return 0;

}

巴特西

hdu 6794 Tokitsukaze and Multiple 前缀和思想+思维

最新文章

热门文章