7月10日

sequence|sequence.in|sequence.out

题目描述：

给定一个整数K和长为N的数列{Ai}，求有多少个子串（不含空串）的和为K的倍数。（在这里子串表示{A[i]..A[j]}，i<=j）

输入格式：

共两行

第一行 两个整数N,K

第二行 N个整数表示数列{Ai}

输出格式：

一行一个整数 表示满足条件的子串的个数

样例输入：

6 3

1 2 6 3 7 4

样例输出：

7

数据范围：

20%    N<=100

对另外20%  K<=100

对所有数据  N<=500000  K<=500000

保证输入数据中所有数都能用longint保存

#include<cstdio>

#include<cstring>

#include<iostream>

#define PROC "sequence"

using namespace std;

const int MAXN = 500000+5;

int x,n,k;

int a[MAXN],rest[MAXN];

long long ans = 0;

int main()

{

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

    a[0] = 0;

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

     {

                       scanf("%d",&x);

                       int yushu = (x % k+k) %k;

                       a[i] = (yushu + a[i-1]%k+k) % k;

         }

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

          rest[a[i]]++;

         ans += rest[0];

     long long t;

         for (int i = 0;i<k;i++)

                 if (rest[i]!=0 && rest[i]!=1)

                 {

                  t = rest[i];

                  ans += (t * (t-1)/2);

                 }

         cout<<ans;

        return 0;

}

错因：

1.正解：余数 前缀和组合

做：反应较快 5分钟

改：没有注意到500000的平方会超longint

得：注意数据规模 especially 负数 和 计算过程中产生的大数据

2.未完待续

3.未完待续

s??ln?/ `??le=‘font-size:10.5pt;font-family:"Courier New";color:darkred;mso-ansi-language: FR‘>()

{

        scanf("%d",&n);

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

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

    sort(b+1,b+n+1);

    int count = 0,now = b[1];

    a[++count] = now;

    int ans = 0;

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

        {

     if (b[i]!= now) {

                       now = b[i];

                       a[++count] = now;

     }

     else ans ++;

    }

     int max = a[1];

     memset(dp, 0x3f3f,sizeof(dp));

     for (int i = 1;i<=count;i++)

     {

        dp[a[i]] = 1;

        if (a[i]>max)  max = a[i];

         }

         for (int i = 1;i<=count;i++)

          for (int j = 1;j<=max;j++)

           {

                       int cur = gcd(a[i],j);

                       if (dp[cur]>dp[j]+1) dp[cur] = dp[j] + 1;

           }

        int g = a[1];

        for (int i =2;i<=count;i++)

          g = gcd(g,a[i]);

        printf("%d",count-dp[g]+ans);

        return 0;

}

错因：

1.正解：DP： dp[i]表示使得最大公约数是i最小使用多少数。

             对于每个i枚举所有数，进行更新。

理由：1.gcd满足“交换律结合律”。

      2. 更新结果与搜索顺序无关。

做：审题：误把gcd当成了最大公因数。

改：no problem

得：缜密审题  动态思维

2.未完待续

3.未完待续