Gym - 102035B Mahmoud the Thief 补题（取余的思维题）

题意：U盘有n个题目每个问题的大小是ai，Ayoub不小心把U盘落在了Mahmoud。Mahmoud按照一定的顺序bi窃取里面的文件，但是如果U盘里面的文件只剩下1个或者任意相邻的文件的大小差的绝对值能够被m整除，则U盘会停止传输。告诉Ayoub多少问题Mahmoud将窃取，直到传输停止。

条件：1 U盘里面的文件只剩下1个或者任意相邻的文件的大小差的绝对值能够被m整除，则U盘会停止传输

            2 Mahmoud按照一定的顺序bi窃取里面的文件

思路：求取所有文件大小被m整除后余数的种数，余数相同的文件之间的差必然能够被m整除。那么条件里面的条件1就转换成了：U盘里面的文件被m整除后余数种数为1，则U盘会停止传输（只有一个文件也算余数种数为1）。

代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdlib>
#include <map>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
int a[maxn],arr[maxn];
map<int,int>mp;//补题的时候这里用了数组，但是因为个数最多1e5但是大小最大1e9
int main()
{
    int n,m;
    int cnt=0;//cnt是余数种数
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(mp[a[i]%m]==0)//计算余数种数
        {
            cnt++;
        }
        mp[a[i]%m]++;//统计每个种数个数
    }
    for(int i=1;i<=n;i++)
    {
        int num;
        scanf("%d",&num);
        arr[i]=a[num];
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(cnt==1)
        {
            break;
        }
        mp[arr[i]%m]--;
        if(mp[arr[i]%m]==0)
        {
            cnt--;
        }
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}
           

总结：1 思维题，是真的没想到这个方法。

            2 对于模和取余不太敏感，没有想到模和取余的m*n（除数*n）+k（余数）形式。（想到这个方向的话，或许就能解出来了）