前缀和算法差分算法（4）——习题简述（1）

1.4 习题思路简述

本节将给出以下题的题解：

1. P3131 Subsequences Summing to Sevens S、
2. P1719 最大加权矩形
3. P2879 Tallest Cow S
4. P1314 聪明的质监员

在这里建议每道题都认真思考，习题题解只是简单表明一下思路，不会和例题一样具体

1.4.1P3131 Subsequences Summing to Sevens S

题意简述

有n nn个编号各不相同的奶牛（我们最熟悉的Farmer John和他的天天排成一排nz有点不正常的奶牛们）排成一排，要求找到最长的区间[ l , r ] [l,r][l,r]，使∑ i = l r i d [ i ] \sum_{i=l}^r id[i]∑i=lr​id[i]的值为7 77的倍数

算法分析

值为7 77的倍数，也就意味着区间和是7 77的倍数，同余的性质不是显而易见的吗？：
a % n + b % n = ( a + b ) % n a\%n+b\%n=(a+b)\%na%n+b%n=(a+b)%n，其中%符号就是取模的意思，那么，要判断∑ i = l r i d [ i ] \sum_{i=l}^r id[i]∑i=lr​id[i]是否是7 77的倍数，只需要判断p r e [ l − 1 ] % 7 pre[l-1]\%7pre[l−1]%7是否等于p r e [ r ] % 7 pre[r]\%7pre[r]%7即可。

既然如此，我们不妨每走一步，都对7 77取模，接下来找到每个余数第一次和最后一次出现的位置，计算区间长度，选择最长的即可。

此处尤其注意：0 00是个特殊的余数，0 00不用管什么时候第一次出现，只需要找到最后一次出现的位置即可（想一想，为什么）。

上面的内容已经足够详尽了，应该足以写出代码了。

代码位置：1\problems\P3131.cpp

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=1;i<=n;i++)#define_rep(i,a,b)for(inti=a;i<=b;i++)#defineendl'\n'constintmaxn=5e4+10;inta[maxn],pre[maxn];intfst[7],lst[7];// 第一次和最后一次出现索引对应数的位置（first，last）intmain(){// 初始化数组memset