组合数学-抽屉原理

文章目录

  • 抽屉原理
  • 例题
    • HDU-1205
    • POJ-2356

抽屉原理


抽屉原理又称鸽巢原理:把 n+1个物品放进 n个盒子里,那么至少有一个盒子包含两个及以上的物品。

例题

HDU-1205


HDU-1205 吃糖果

Problem Description HOHO,终于从Speakless手上赢走了所有的糖果,是Gardon吃糖果时有个特殊的癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另一种,这样;可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完?请你写个程序帮忙计算一下。 Input 第一行有一个整数T,接下来T组数据,每组数据占2行,第一行是一个整数N(0<N<=1000000),第二行是N个数,表示N种糖果的数目Mi(0<Mi<=1000000)。 Output 对于每组数据,输出一行,包含一个"Yes"或者"No"。 Sample Input 2 3 4 1 1 5 5 4 3 2 1 Sample Output No Yes

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	cin >> t;
	while (t--) {
		ll mx, x, cnt = 0;
		cin >> n >> mx;
		cnt += mx;
		for (int i = 1; i < n; i++) {
			cin >> x;
			mx = max(mx, x);
			cnt += x;
		}
		if (cnt - mx < mx - 1) cout << "No\n";
		else cout << "Yes\n";
	}
	return 0;
}

POJ-2356


POJ-2356 Find a multiple

Description The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k). Input The first line of the input contains the single number N. Each of next N lines contains one number from the given set. Output In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order. If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them. Sample Input 5 1 2 3 4 1 Sample Output 2 2 3

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100005;
int a[maxn], sum[maxn], vis[maxn];
int main() {
	int n;
	while (cin >> n) {
		memset(vis, -1, sizeof(vis));
		sum[0] = vis[0] = 0;	//余数为0时一个即可,置为非-1
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum[i] = (sum[i - 1] + a[i]) % n;
		}
		for (int i = 1; i <= n; i++) {
			if (vis[sum[i]] == -1)
				vis[sum[i]] = i;
			else {	//找到两个余数相同的
				cout << i - vis[sum[i]] << "\n";
				for (int j = vis[sum[i]] + 1; j <= i; j++)
					cout << a[j] << "\n";
				break;
			}
		}
	}
	return 0;
}

这一题的变形还有很多,都是抽屉原理,换汤不换药: POJ-3370 Halloween treats HDU-3183 A Magic Lamp HDU-5776 sum

原创不易,请勿转载本不富裕的访问量雪上加霜 ) 博主首页:https://blog.csdn.net/qq_45034708

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Maven安装配置详细教程

    你还在为导入jar包而苦恼吗?常常找不到jar包,不知道从哪导入,就算导入了可能还会依赖冲突,目录杂乱,那么maven你值得拥有。 什么是jar包?jar [...

    唔仄lo咚锵
  • 贪心-HDU3348 coins(钱币问题)

    分别给出1,5,10,50,100角面值的纸币张数,求凑出p角的最小张数和最大张数。

    唔仄lo咚锵
  • 动态规划-区间DP

    唔仄lo咚锵
  • POJ-2356 Find a multiple(DFS,抽屉原理)

    Find a multiple Time Limit: 1000MS Memory Limit: 65536K Total Submissio...

    ShenduCC
  • poj-1007-DNA Sorting

    One measure of ``unsortedness'' in a sequence is the number of pairs of entries ...

    瑾诺学长
  • 【Codeforces】1213C - Book Reading

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 3.1.2 使用绘图API绘制Contour的思路

    A week or so back I wrote about a package I ported/modified to create the Delaun...

    周星星9527
  • Twitter用户数据Profiling

    传统的数据摘要包括data exploration/data cleansing/data integration.而之后,data management和bi...

    DuncanZhou
  • 生物信息学算法之 Python 实现|Rosalind 刷题笔记:007 兔子问题和递推

    递推关系是一种用来定义序列的方法,可以通过前面的项,推导出后面的项。如斐波那契兔子问题,某月的兔子数,等于上一个月的兔子数,加上新生的兔子数;一个关键的现象是,...

    简说基因
  • Understanding a Kernel Oops!

    Understanding a kernel panic and doing the forensics to trace the bug is conside...

    jeff xie

扫码关注云+社区

领取腾讯云代金券