林厚从信息学奥赛课课通第7单元第9课哈希表课件

0 01 12 23 34 45 56 67 78 89 9101011111212 54 4318 4660 75 90H练习练习1 1：整数集合：整数集合(sumsets,1s,256MB)(sumsets,1s,256MB)问题描述：问题描述：给定一个整数集合给定一个整数集合s s，请你寻找一个最大的，请你寻找一个最大的d d，使得，使得a+b+c=da+b+c=d，并且并且a a、b b、c c、d d都是集合中的元素。都是集合中的元素。输入格式：输入格式：若干集合若干集合s s。对于每个集合对于每个集合s s的第的第1 1行包含行包含1 1个整数个整数n,1=n=1000n,1=n=1000，表示集，表示集合中元素的个数。随后有合中元素的个数。随后有n n行，每一行一个整数，表示集合行，每一行一个整数，表示集合s s中的元素，每个整数的范围是中的元素，每个整数的范围是 536870912,536870911.536870912,536870911.输入的最后一行包含一个输入的最后一行包含一个0 0。输出格式：输出格式：对于每个集合对于每个集合s s，输出一行一个整数，输出一行一个整数d d，或者，或者“No SolutionNo Solution”表示无解。表示无解。输入样例：输入样例：5 52 23 35 57 712125 52 216166464256256102410240 0输出样例：输出样例：1212No SolutionNo Solution练习练习2 2：生日：生日(birthday,1s,256MB)(birthday,1s,256MB)问题描述：问题描述：多多今天很高兴，因为他的好朋友苹果要过生日了。由多多今天很高兴，因为他的好朋友苹果要过生日了。由于今天多多得到了两张价值不菲的于今天多多得到了两张价值不菲的SHOPSHOP购物券，所以他决定买购物券，所以他决定买N N件礼物送给苹果。件礼物送给苹果。一个下午过去了，多多选好了一个下午过去了，多多选好了N N件礼物，并且它们的价件礼物，并且它们的价格之和恰好为两张购物券的面额这和。当多多被自己的聪明所折格之和恰好为两张购物券的面额这和。当多多被自己的聪明所折服，高兴地去结账时，他突然发现服，高兴地去结账时，他突然发现SHOPSHOP对购物券的使用有非常严对购物券的使用有非常严格的规定：一次只允许使用一张，不找零，不与现金混用。多多格的规定：一次只允许使用一张，不找零，不与现金混用。多多身上根本没有现金，并且他不愿意放弃挑选好的礼物。这就意味身上根本没有现金，并且他不愿意放弃挑选好的礼物。这就意味着，他只能通过这两张购物券结账，而且每一张购物券所购买的着，他只能通过这两张购物券结账，而且每一张购物券所购买的物品总价格，必须精确地等于这张购物券的面额。物品总价格，必须精确地等于这张购物券的面额。怎样才能顺利地买回这怎样才能顺利地买回这N N件礼物送给苹果呢？本题的任务件礼物送给苹果呢？本题的任务就是帮助多多确定是否存在一个购买方案。已知其中一张购物券就是帮助多多确定是否存在一个购买方案。已知其中一张购物券的面额以及所有商品的价格，只需要确定能否找到一种方案使得的面额以及所有商品的价格，只需要确定能否找到一种方案使得选出来的物品的价格总和正好是这张购物券的面额即可。选出来的物品的价格总和正好是这张购物券的面额即可。输入格式：输入格式：有多组测试数据。每组数据的第一行为两个整数有多组测试数据。每组数据的第一行为两个整数N N和和M M，分别表示多，分别表示多多一共挑选了多一共挑选了N N个物品送给苹果以及多多的一张购物券的面额为个物品送给苹果以及多多的一张购物券的面额为M M。接下来。接下来的一行有的一行有N N个用空格隔开的正整数，第个用空格隔开的正整数，第i i个数表示第个数表示第i i个物品的价格。个物品的价格。输出格式：输出格式：包含若干行，每行一个单词包含若干行，每行一个单词“YESYES”或者或者“NONO”，分别代表存在一，分别代表存在一个购买方案或不存在一个购买方案。个购买方案或不存在一个购买方案。输入样例：输入样例：10 200010 20001000 100 200 300 400 500 700 600 900 8001000 100 200 300 400 500 700 600 900 80010 229010 22901000 100 200 300 400 500 700 600 900 8001000 100 200 300 400 500 700 600 900 800输出样例：输出样例：YESYESNONO数据规模：数据规模：对于对于30%30%的数据，所有的的数据，所有的N=20.N=20.对于对于100%100%的数据，所有的的数据，所有的N=40N=40，并且，并且M M和物品的总价值不超过和物品的总价值不超过2 231311 1，测试，测试组数不超过组数不超过1010组，不少于组，不少于5 5组。组。