链接:https://ac.nowcoder.com/acm/contest/908/I

题意:

Baby bear and his good friends are very fond of mushrooms. On this day, they go to 402 mushroom field together. Kuangyeye, the owner of the mushroom field, is very happy to see the children. He is going to give the children some mushrooms, so he takes them to a warehouse.

In the warehouse, there are N baskets in a row, numbered from 1 to N, with some mushrooms in each basket. Baby bear and his friends can take several baskets of mushrooms, but Kuangyeye has several requirements:

·Kuangyeye likes to be neat and tidy. He asks the children to take away only the consecutively numbered baskets when they take the mushrooms. This means that if the children choose the 4th, 5th and 6th baskets of mushrooms, they can't choose the 9th basket unless they also choose the 7th and 8th baskets.

·Kuangyeye likes all of them, so he asks each child to get the same number of mushrooms. This means that the total number of mushrooms the children take away must be P = k * M, where k is an integer and M is the total number of children.

·Kuangyeye made a record of the number of mushrooms in each basket. He asks the children not to put some mushrooms in other baskets or throw them away. This means that when the children take a basket of mushrooms, they must take away all the mushrooms in the basket.

Now given the number of mushrooms in a row of N baskets, please answer:

1. The maximum number of mushrooms that baby bear and his friends can take away.

2. The maximum number of baskets that baby bear and his friends can take away.

Please note that the answers to questions 1 and 2 May not come from the same situation!!!

思路:

用一个二维数组记录原数组的前缀和数组modm的值。

如果sum[j]%m == sum[i]%m 则(sum[j]-sum[i])%m == 0说明j-(i-1)篮子里的蘑菇是m的倍数。(sum为前缀和数组)

找到%m的每个余数去最左和最右的两个位置。%m为0时只用取最右的。

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MAXN = 2e6 + 10;
const int MOD = 1e9 + 7;
int n, m, k, t; LL fsum[MAXN];
int Po[MAXN][2]; int main()
{
memset(Po, -1, sizeof(Po));
scanf("%d%d", &n ,&m);
LL sum = 0;
for (int i = 1;i <= n;i++)
{
scanf("%lld", &fsum[i]);
fsum[i] += fsum[i-1];
}
for (int i = 1;i <= n;i++)
{
int lef = fsum[i] % m;
if (lef == 0)
{
Po[lef][0] = i;
continue;
}
if (Po[lef][0] == -1)
Po[lef][0] = i;
else
Po[lef][1] = i;
}
LL res1 = 0;
int res2 = 0;
for (int i = 1;i <= m;i++)
{
if (Po[i][1] == -1)
continue;
res1 = max(res1, fsum[Po[i][1]]-fsum[Po[i][0]]);
res2 = max(res2, Po[i][1]-Po[i][0]);
}
if (Po[0][0] != -1)
{
res1 = max(res1, fsum[Po[0][0]]);
res2 = max(res2, Po[0][0]);
} printf("%lld %d", res1, res2); return 0;
}

  

最新文章

  1. dom解析和sax解析的区别及优缺点
  2. nginx基本配置和参数说明
  3. docker-registry使用笔记
  4. 问题Initial SessionFactory creation failed.org.hibernate.HibernateException: /hibernate.cfg.xml not found解决方法
  5. JStorm注意事项
  6. linux 搭建jenkins+创建maven工程JOB
  7. PDB文件:每个开发人员都必须知道的
  8. NSDate的运算
  9. 让EDIUS中素材小距离精确移动的教程
  10. Flash Builder4.6破解方案(亲测有效)(转)
  11. SQL Server 查看identity值的几种方法。
  12. 从头开始-06.C语言中预处理指令
  13. vijos1009:扩展欧几里得算法
  14. Android在一个APP中通过包名或类名启动另一个APP
  15. jQuery手风琴菜单!!!!
  16. Unicode字符集,各个语言的区间
  17. python数据存储技巧
  18. esayui扩展验证方法
  19. Jeecg
  20. 20155219付颖卓《网络对抗》EXP7网络欺诈技术防范

热门文章

  1. npm使用淘宝镜像安装包
  2. BZOJ 1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居:队列 + multiset + 并查集【曼哈顿距离变形】
  3. 中文标准web字体
  4. mybatis传递多个参数值(转)
  5. CodeForces - 697F:Legen... (AC自动机+矩阵)
  6. Linq 支持动态字查询集合, 也就是说根据传入的值进行查询。
  7. Nuget-QRCode:jquery-qrcode
  8. maven学习八 关于maven的version
  9. leetcode Word Break-单词划分
  10. 安装时后的idea,项目不能运行,pom.xml文件不能下载到本地仓库,maven配置是正确的