提高组试题.docx

《提高组试题.docx》由会员分享，可在线阅读，更多相关《提高组试题.docx（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、提高组试题NOIP提高组模拟试题2017.07BYXYX小X的质数prime【题目背景】小X是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的情感。小X以为，质数是一切自然数起源的地方。【题目描绘】在小X的认知里，质数是除了本身和1以外，没有其他因数的数字。但由于小X对质数的热爱超乎寻常，所以小X同样喜欢那些固然不是质数，但却是由两个质数相乘得来的数。于是，我们定义，一个数是小X喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。而如今，小X想要知道，在L到R之间，有多少数是他喜欢的数呢？【输入格式】从文件prime.in中读取数据。第一行输入一个正整数Q，表示询问的组数。接下来Q

2、行，包含两个正整数L和R，保证LR。【输出格式】输出Q行，每行一个整数，表示小X喜欢的数的个数。【样例1输入】116【样例1输出】5【样例1解释】6以内的质数有2、3、5，而4=2*2,6=2*3，因而，2,3,4,5,6都是小X喜欢的数，而1不是。【样例2】见下发文件prime2.in，prime2.ans【样例3】见下发文件prime3.in，prime3.ans小X的密室room【题目背景】小X正困在一个密室里，他希望尽快逃出密室。【题目描绘】密室中有N个房间，初始时，小X在1号房间，而出口在N号房间。密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间X到房

3、间Y的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙。幸运的是，钥匙在打开传送门的封印后，并不会消失。然而，通过密室的传送门需要消耗大量的时间，因而，小X希望通过尽可能少的传送门到达出口，你能告诉小X这个数值吗？另外，小X有可能不能逃出这个密室，假如是这样，请输出“NoSolution。【输入格式】从文件room.in中读取数据。第一行三个整数N、M、K，分别表示房间的数量、传送门的数量以及钥匙的种类数。接下来N行，每行K个0或1，若第i个数为1，则表示该房间内有第i种钥匙，若第i个数为0，则表示该房间内没有第i种钥匙。接下来M行，每行先读入两个整数X，Y，表示该传送门是建立在X号房

4、间，通向Y号房间的，再读入K个0或1，若第i个数为1，则表示通过该传送门需要i种钥匙，若第i个数为0，则表示通过该传送门不需要第i种钥匙。【输出格式】输出一行一个“NoSolution，或一个整数，表示最少通过的传送门数。【样例1输入】332100100131112102311【样例1输出】2【样例2】见下发文件room2.in,room2.ans【样例3】见下发文件room3.in,room3.ans【样例4】见下发文件room4.in,room4.ans小X的fo光light【题目背景】小X是远近出名的学fo，平日里最喜欢做的事就是蒸发学水。【题目描绘】小X所在的城市X城是一个含有N个节点

5、的无向图，同时，由于X国是一个发展中国家，为了节约城市建设的经费，X国首相在建造X城时只建造N1条边，使得城市的各个地点能够互相到达。小X计划蒸发Q天的学水，每一天会有一名学水从A地走到B地，并在沿途各个地点留下一个水塘。此后，小X会从C地走到B地，并用fo光蒸发沿途的水塘。由于X城是一个学fo横行的城市，学水留下的水塘即便没有被小X蒸发，也会在第二天之前被其他学fo蒸发殆尽。如今，小X想要知道，他每一天能够蒸发多少水塘呢？【输入格式】从文件light.in中读取数据。第一行三个整数N、Q、NUM，分别表示X城地点的个数，小X蒸发学水的天数，以及测试点编号。注意，测试点编号是为了让选手们更方便

6、的获得部分分，你可能不需要用到这则信息，在下发的样例中，测试点编号的含义是该样例知足某一测试点限制。接下来N1行，每行两个整数X、Y，表示X地与Y地之间有一条边。接下来Q行，每行三个整数A、B、C，表示一天中，有一名学水从A地走到B地，而小X会从C地走到B地。【输出格式】输出Q行，每行一个整数，表示小X能够蒸发的水塘数。【样例1输入】3311223123113313【样例1输出】113【样例2】见下发文件light2.in,light2.ans【样例3】见下发文件light3.in,light3.ans【样例4】见下发文件light4.in,light4.ans【数据范围及子任务】特殊性质1：第i条边连接第i和第i+1个地点。