建立一个网站的技术解决方案,小公司网站用什么服务器划算,湖南seo推广系统,中国字体设计网站五个物品分给四个人#xff0c;保证每个人都能够分得物品#xff0c;那么一定有一个人会分得两个物品。
这就是我们所说的抽屉原理。
抽屉原理的一般含义为#xff1a;“如果每个抽屉代表一个集合#xff0c;每一个苹果就可以代表一个元素#xff0c;假如有n#xff0b…五个物品分给四个人保证每个人都能够分得物品那么一定有一个人会分得两个物品。
这就是我们所说的抽屉原理。
抽屉原理的一般含义为“如果每个抽屉代表一个集合每一个苹果就可以代表一个元素假如有n1或多于n1个元素放到n个集合中去其中必定至少有一个集合里有两个元素。” 抽屉原理有时也被称为鸽巢原理“如果有五个鸽子笼养鸽人养了6只鸽子那么当鸽子飞回笼中后至少有一个笼子中装有2只鸽子”。它是组合数学中一个重要的原理。 原理1把多于n个的物体放到n个抽屉里则至少有一个抽屉里的东西不少于两件。 [证明]反证法如果每个抽屉至多只能放进一个物体那么物体的总数至多是n而不是题设的nk(k≥1)这不可能。 原理2把多于mn(m乘以n)个的物体放到n个抽屉里则至少有一个抽屉里有不少于m1的物体。 [证明]反证法若每个抽屉至多放进m个物体那么n个抽屉至多放进mn个物体与题设不符故不可能。 原理3把无穷多件物体放入n个抽屉则至少有一个抽屉里 有无穷个物体。 示例
1Find a multiple 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. 输入包含n个自然即正整数数n10000。每个数字都不超过15000。这些数字并不一定不同因此可能会发生两个或更多个数字相等的情况。你的任务是选择几个给定的数1少数n这样对于n所选数的和是倍数即对于某个自然数kn*k所选数的和。 输入 输入的第一行包含单个数字n。接下来的n行中的每一行都包含给定集合中的一个数字。 输出 如果程序确定找不到目标数字集则应将单个数字0打印到输出中。否则它应该以任意顺序打印第一行中所选号码的号码后跟所选号码本身每行单独一行。 如果有多个具有所需属性的数字集则应仅将其中一个最好是您最喜欢的打印到输出。 Sample Input 5 1 2 3 4 1 Sample Output 2 2 3 题意
给定一个n接下来输入n个数对于这n个数我们选择从i到j的区间(i和j在1-n范围内)满足区间内的所有数字的和是n的倍数如果存在的话就输出区间内下标每个数字占一行。
题解
令sum【i】为前i项和则sun【i】%n的结果在【1n-1】之间有sum[i]%n有n个结果由抽屉原理可知必有两个余数相同即sum【j]%nsum[i]%n,则此两项sum【】相减的结果必为n的倍数,下标为j1~i的数为所求结果。 #includecstdio
#includeiostream
#includealgorithm
#includecstring
#includestring
#includemap
#includevector
#includecmath
using namespace std;
const int maxn1e4100;
int n,a;
int num[maxn],mod[maxn];
int main()
{cinn;for(int i1;in;i){scanf(%d,a);num[i]num[i-1]a;}//首先是求前缀和for(int i1;in;i){if(num[i]%n0){printf(%d\n,i);for(int j1;ji;j){printf(%d\n,num[j]-num[j-1]);}break;}else if(mod[num[i]%n]!0){int jmod[num[i]%n];printf(%d\n,i-j);for(j;ji;j){printf(%d\n,num[j]-num[j-1]);}break;}//如果说上面的情况都没有存在的话mod[num[i]%n]i;}return 0;
}
2Halloween treats Every year there is the same problem at Halloween: Each neighbour is only willing to give a certain total number of sweets on that day, no matter how many children call on him, so it may happen that a child will get nothing if it is too late. To avoid conflicts, the children have decided they will put all sweets together and then divide them evenly among themselves. From last years experience of Halloween they know how many sweets they get from each neighbour. Since they care more about justice than about the number of sweets they get, they want to select a subset of the neighbours to visit, so that in sharing every child receives the same number of sweets. They will not be satisfied if they have any sweets left which cannot be divided. Your job is to help the children and present a solution. Input The input contains several test cases. The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000), the number of children and the number of neighbours, respectively. The next line contains n space separated integers a1 , ... , an (1 ≤ ai ≤ 100000 ), where ai represents the number of sweets the children get if they visit neighbour i. The last test case is followed by two zeros. Output For each test case output one line with the indices of the neighbours the children should select (here, index i corresponds to neighbour i who gives a total number of ai sweets). If there is no solution where each child gets at least one sweet print no sweets instead. Note that if there are several solutions where each child gets at least one sweet, you may print any of them. 每年万圣节都有同样的问题每个邻居只愿意在那天给一定数量的糖果不管有多少孩子来找他所以如果太晚了孩子可能什么也得不到。为了避免冲突孩子们决定把所有的糖果放在一起然后平均分配给他们自己。从去年万圣节的经历中他们知道每个邻居能给他们多少糖果。因为他们更关心的是公平而不是他们得到的糖果的数量所以他们想选择一个子集的邻居来拜访这样在分享时每个孩子都能得到同样数量的糖果。他们若有不能分的糖就不满足。 你的工作是帮助孩子们并提出解决方案。 输入 输入包含几个测试用例。 每个测试用例的第一行分别包含两个整数c和n1≤c≤n≤100000、子代数和邻居数。下一行包含n空格分隔整数a1…an1≤ai≤100000其中ai表示孩子访问邻居i时得到的糖果数量。 最后一个测试用例后面跟着两个零。 输出 对于每个测试用例输出一行其中包含孩子们应该选择的邻居的索引这里索引i对应于给出ai糖果总数的邻居i。如果没有解决办法每个孩子至少得到一个甜点打印“没有糖果”。注意如果有几个解决方案每个孩子至少得到一个甜点你可以打印其中任何一个。 Sample Input 4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0 Sample Output 3 5
2 3 4 题意
万圣节有c个小孩n家居民i居民家有 ai 颗糖果问小孩们要去哪几家要糖果才能使他们能够平分要到的糖果有多种情况可以输出任意一种。
题解
输入xy分别代表人数和邻居的数量输入y个数代表每个邻居所拥有的的糖的数量对前缀和进行取余操作记录取余后的数字对应的下标以及这个数出现的次数如果说出现两次就说明当前区间内的数据的和是x的倍数输出区间对应的下标如果说在进行取余操作的过程中出现0直接从最开始的下标输出如果说所有的数据输入完毕还没有输出的话就输出“no sweets”。
#includealgorithm
#includeiostream
#includestring.h
#includecstdio
#includecstring
#define ll long long
using namespace std;
const int maxn1e5100;
int a[maxn];
int indexxx[maxn];
int main()
{int x,y;while(~scanf(%d%d,x,y)){if(xy0) break;memset(indexxx,0,sizeof(indexxx));memset(a,0,sizeof(a));long long sum0;int num;bool flagtrue;for(int i1; iy; i){scanf(%d,num);if(flag){sumnum;sum%x;a[sum];if(a[sum]2){for(int jindexxx[sum]1;ji;j){printf(%d ,j);}printf(\n);flagfalse;}indexxx[sum]i;if(sum0){for(int j1; ji; j){printf(%d ,j);}printf(\n);flagfalse;}}}if(flag)printf(no sweets\n);}return 0;
}
