冲刺noip2011模拟试题(一).doc

冲刺NOIP2011模拟试题(一)/c//c/()【问题描述】Oliver为了学好英语决定苦背单词,但很快他发现要直接记住杂乱无章的单词非常困难,他决定对单词进行分类。两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。例如“AABAC”,它和“CBAAA”就可以归为一类,而和“AAABB”就不是一类。现在Oliver有N个单词,所有单词均由大写字母组成,每个单词的长度不超过l00。你要告诉Oliver这些单词会被分成几类。【输入格式】输入文件的第一行为单词个数N,以下N行每行为一个单词。【输出格式】输出文件仅包含一个数,表示这N个单词分成的类数。【样例输入】BAAAAAABB【样例输出】2【数据范围】对于70%的数据满足N≤100。对于100%的数据满足N≤10000。()【问题描述】在一个大晴天,Oliver与同学们一共N人出游,他们走到一条河的东岸边,想要过河到西岸。而东岸边有一条小船。船太小了,一次只能乘坐两人。每个人都有一个渡河时间T,船划到对岸的时间等于船上渡河时间较长的人所用时间。现在已知N个人的渡河时间T,Oliver想要你告诉他,他们最少要花费多少时间,才能使所有人都过河。注意,只有船在东岸(西岸)时东岸(西岸)的人才能坐上船划到对岸。【输入格式】输入文件第一行为人数N,以下有N行,每行一个数。第i+l行的数为第i个人的渡河时间。【输出格式】输出文件仅包含一个数,表示所有人都渡过河的最少渡河时间。【样例输入】4671015【样例输出】42【样例解释】初始:东岸{1,2,3,4},西岸{}第一次:东岸{3,4},西岸{1,2}时间7第二次:东岸{1,3,4},西岸{2}时间6第三次:东岸{1},西岸{2,3,4}时间15第四次:东岸{1,2},西岸{3,4}时间7第五次:东岸{},西岸{1,2,3,4}时间7所以总时间为7+6+15+7+7=42,没有比这个更优的方案。【数据范围】对于40%的数据满足N≤8。对于100%的数据满足N≤100000。()【问题描述】现有K个整数集合,第i个集合有Sumi个元素。集合中的数都为正数,且不大于N。现在定义集合A与集合B相似:。,或更改一个元素的值之后A集合与B集合相等。现要将K个集合分成至多M组(M>N),使得每一组内的集合互不相似。要求你给出一种合法的方案。如果无解请输出“impossible”。【输入格式】输入文件第一行有三个数N,K,M,意义如题目所述。接下来有K行,每行第一个数Sum表示序列长度。之后sum个数为此集合的元素。【输出格式】输出文件有K个数,表示每个集合(按输入顺序)被分到的组的编号(1~M)。【样例输入】820125135645135634