选数 - 题目 - Daimayuan Online Judge
原本我的思路是:大致题意就是从n个数中选取若干数,使得它们的和mod n等于0
任意选取,无关顺序,是可以跳着选的,也就是对于每一个数,有两种选择,选与不选,于是我想用01背包,但是似乎不太行,于是就不知道怎么做了
这题考察的是前缀和以及抽屉原理
前置知识:抽屉原理
另外,需要知道的是模运算
(a+b)%m=(a%m+b%m)%m,
(a+b)%n=0==>(a%n+b%n)%n=0
那么先求出%n后的前缀和再%n,sum[0]到sum[n]取值范围在0到n-1,根据抽屉原理,n+1个数共n种取值,说明至少有两个sum值相等,sum[l]=sum[r],故[l+1,r]的和为0,那么答案就是从l+1开始输出直到r,也就是说必定至少有连续的一段数的和满足要求,或者sum[i]直接就等于0,那么就从1输出到i
mp.count()统计map中 key为k的元素的个数,对于map,返回值为1(存在)和0(不存在)
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N = 100010;
int n;
int a[N];
int sum[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + a[i] % n) % n;
int l, r;
map<int,int>mp;
for (int i = 0; i <= n; i++) {
if (!mp.count(sum[i])) mp[sum[i]] = i;//如果该sum值第一次出现了,那么就记录它的下标
else {
//如果该sum值第二次出现,那么直接记录两次出现的下标,并退出循环
l = mp[sum[i]] + 1;
r = i;
break;
}
}
cout << r - l + 1 << endl;
for (int i = l; i <= r; i++) cout << i << " ";
return 0;
}