2022年NOI导刊冲刺NOIP模拟试题 .pdf

《2022年NOI导刊冲刺NOIP模拟试题 .pdf》由会员分享，可在线阅读，更多相关《2022年NOI导刊冲刺NOIP模拟试题 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、冲刺 NOIP2011 模拟试题（十二）1单词分类（word.c/cpp）问题描述 Oliver 为了学好英语决定苦背单词，但很快他发现要直接记住杂乱无章的单词非常困难，他决定对单词进行分类。两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。例如“AABAC”，它和“CBAAA”就可以归为一类，而和“AAABB”就不是一类。现在 Oliver 有 N 个单词，所有单词均由大写字母组成，每个单词的长度不超过100。你要告诉Oliver这些单词会被分成几类。输入格式 输入文件的第一行为单词个数N，以下 N 行每行为一个单词。输出格式 输出文件仅包含一个数，表示这N 个单词分成的类数

2、。样例输入 3 AABAC CBAAA AAABB 样例输出 2 数据范围 对于 70%的数据满足N 100。对于 100%的数据满足N10000。2.过河问题（river.c/cpp）问题描述 有一个大晴天，Oliver 与同学们一共N 人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。船太小了，一次只能乘坐两人。每个人都有一个渡河时间T，船划到对岸的时间等于船上渡河时间较长的人所用时间。现在已知N 个人的渡河时间T，Oliver 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。注意，只有船在东岸（西岸）的人才能坐上船划到对岸。输入格式 输入文件第一行为人数N，以

3、下有 N 行，每行一个数。第 i+1 行的数为第i 个人的渡河时间。输出格式 输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。样例输入 4 6 7 10 15 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -样例输出 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，没有比这个更优的方案。数据范围 对于

4、 40%的数据满足N 8。对于 100%的数据满足N100000。3集合分组（device.c/cpp）问题描述 现有 K 个整数集合，第i 个集合有Sumi 个元素。集合中的数都为正数，且不大于N。现有定义集合A 与集合 B 相似；1B 与 A 相似；2将 A 集合删去一个元素，或更改一个元素的值之后A 集合与 B 集合相等。现要将 K 个集合分成至多 M组（M N），使得每一组内的集合互不相似。要求你给出一种合法的方案。如果无解请输出“impossible”。输入格式 输入文件第一行有三个数N，K，M，意义如题目所述。接下来有K 行，每行第一数Sum 表示序列长度。之后Sum 个数为些集合

5、的元素。输出格式 输出文件有K 个数，表示每个集合（按输入顺序）被分到的组的编号（1 M）。样例输入 8 20 12 5 1 3 5 6 4 5 1 3 5 6 3 4 5 6 3 3 4 5 6 3 4 4 4 6 5 8 4 7 7 7 7 3 7 7 7 2 2 2 3 2 2 7 3 1 2 3 3 1 2 4 10 1 2 3 4 5 6 7 8 7 6 10 8 7 6 5 4 3 2 1 2 1 20 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 7 5 4 6 4 6 4 5 6 4 6 4 6 6 6 6 6 6 6 6 3 6 6 6 1 1

6、1 2 样例输出 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -2 1 9 1 6 2 4 5 3 7 8 5 4 8 7 9 1 1 2 3 数据范围 对于 30%的数据满足N 10，M2，K10。对于 100%的数据满足N100，M100，K50000，Sum100。4最短路（path.c/cpp）问题描述 给定一个包含N 个点，M 条边的无向图，每条边的边权均为1。再给定 K 个三元组（A，B，C），表示从 A 点走到 B 点后不能往C 点走。注意三元组是有序的，如可以从 B 点走到 A 点再走到C。现在你要在K 个三元组的限制下，找出1 号点到 N 号点的最短

7、路径，并输出任意一条合法路径，会有 Check 检查你的输出。输入格式 输入文件第一行有三个数N，M，K，意义如题目所述。接下来 M 行每行两个数A，B，表示 A，B 间有一条边。再下面 K 行，每行三个数（A，B，C）描述一个三元组。输出格式 输出文件共两行数，第一行一个数S 表示最短路径长度。第二行 S+1 个数，表示从1 到 N 所经过的节点。样例输入 4 4 2 1 2 2 3 3 4 1 3 1 2 3 1 3 4 样例输出 4 1 3 2 3 4 数据范围 对于 40%的数据满足N 10，M20，K5。对于 100%的数据满足N3000，M20000，K100000。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -