POJ 3370 Halloween treats

题目传送门:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3370


鸽笼原理的标准应用,查看鸽笼原理的资料请看这里:
传送门:http://www.wutianqi.com/?p=1267


解体报告:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Author: Tanky Woo
// POJ 3370
#include <iostream>
using namespace std;
 
int ans[100001];
int use[100001];
 
int main()
{
	int c, n, i, j;
	while(scanf("%d %d", &c, &n) && (c+n))
	{
		memset(ans, 0, (n+1)*sizeof(ans[0]));
		for(i=0; i<c; ++i)
			use[i] = -1;
		int k=0;
		int flag=0;
		for(i=1; i<=n; ++i)
			scanf("%d", &ans[i]);
		use[0] = 0;
		for(i=1; i<=n; ++i)
		{
			k = (k+ans[i])%c;
			if(use[k] != -1)
			{
				flag = 1;
				break;
			}
			use[k] = i;
		}
		if(!flag)
			puts("no sweets");
		else
		{
			printf("%d", use[k]+1);
			for(j=use[k]+2; j<=i; ++j)
				printf(" %d", j);
			printf("\n");
		}
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《POJ 3370 Halloween treats》有578个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注