下载文档原格式
CCF 全国信息学奥林匹克联赛（NOIP2015）复赛提高组day1（请选手务必仔细阅读本页内容）一．题目概况注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存 4G，上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、特别提醒：评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。
1．神奇的幻方(magic.cpp/c/pas)【问题描述】幻方是一种很神奇的 N*N 矩阵：它由数字 1,2,3, …… , N*N 构成，且每行、每列及两条对角线上的数字之和都相同。
当N为奇数时，我们可以通过以下方法构建一个幻方：首先将 1 写在第一行的中间。
之后，按如下方式从小到大依次填写每个数K(K= 2,3, … , N*N )：1.若 (K−1) 在第一行但不在最后一列，则将K填在最后一行，(K− 1) 所在列的右一列；2.若 (K− 1) 在最后一列但不在第一行，则将K填在第一列，(K− 1) 所在行的上一行；3.若 (K− 1) 在第一行最后一列，则将K填在 (K− 1) 的正下方；4.若 (K− 1) 既不在第一行，也不在最后一列，如果 (K− 1) 的右上方还未填数，则将K填在(K− 1)的右上方，否则将K填在 (K− 1) 的正下方现给定N，请按上述方法构造 N*N 的幻方。
【输入格式】输入文件名为 magic.in。
输入文件只有一行，包含一个整数N，即幻方的大小。
【输出格式】输出文件名为 magic.out。
输出文件包含N行，每行N个整数，即按上述方法构造出的N*N的幻方。
相邻两个整数之间用单个空格隔开。
【输入输出样例 2】见选手目录下的 magic/magic2.in 和 magic/magic2.ans。
第一题题库NOIP20071．统计数字(count.pas/c/cpp)【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。
已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
【输入】输入文件count.in包含n+1行：第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。
每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
【输入输出样例】【限制】40%的数据满足：1<=n <=100080%的数据满足：1<=n <=50000100%的数据满足：1<=n <=200000，每个数均不超过1 500 000 000（1.5*109）NOIP20081. 笨小猴(wird.pas/c/cpp)【问题描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。
但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn 是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn 是一个质数，那么笨小猴就认为这是个Lucky Word ，这样的单词很可能就是正确的答案。
【输入】输入文件word.in 只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
【输出】输出文件word.out 共两行，第一行是一个字符串，假设输入的的单词是Lucky Word ，那么输出“Lucky Word ”，否则输出“No Answer ”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn 的值，否则输出0。
全国信息学奥林匹克联赛(NOIP2014)复赛模拟题Day1长乐一中题目名称正确答案序列问题长途旅行英文名称answer sequence travel输入文件名answer.in sequence.in travel.in输出文件名answer.out sequence.out travel.out 时间限制1s1s1s空间限制256M256M256M测试点数目202010测试点分值5510是否有部分分无无无题目类型传统传统传统是否有SPJ无无无1.正确答案【题目描述】小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。
“吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。
外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。
之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。
这可让小Y与小H犯了难。
你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。
无解输出-1。
【输入格式】第一行四个整数n,m,p,q，意义如上描述。
接下来n行，每一行m个字符’N’或’Y’，表示这题这个神犇的答案。
【输出格式】仅一行，一个长度为m的字符串或是-1。
【样例输入】2220YYYY【样例输出】YY【数据范围】30%:n<=100.60%:n<=5000,m<=100.100%:1<=n<=30000,1<=m<=500.0<=p,q且p+q<=n.2.序列问题【题目描述】小H是个善于思考的学生，她正在思考一个有关序列的问题。
她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。
这两个集合要满足以下的条件：1.两个集合中的元素都为整数，且都在[1,n]里，即Si，Ti∈[1,n]。
2.对于集合S中任意一个元素x，集合T中任意一个元素y，满足x<y。
NOI’ 95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210 分钟）<1>编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1 之间的整数，且A[i]≠ A[j]（当i≠ j时）。
例如： N=6 时，有：此时，数组 A 的编码定义如下：A[0] 的编码为0；A[i] 的编码为：在A[0] ，A[1]∴上面数组 A 的编码为：A= （ 4，3， 0， 5，1， 2），， A[i-1] 中比 A[i] 的值小的个数（B= （0， 0，0，3，1， 2）i=1 ，2，， N-1 ）程序要求解决以下问题：①给出数组 A 后，求出其编码。
②给出数组 A 的编码后，求出 A 中的原数据。
<2> 灯的排列问题：设在一排上有 N 个格子（ N≤ 20），若在格子中放置有不同颜色的灯，每种灯的个数记为 N 1， N2， N k（ k 表示不同颜色灯的个数）。
放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。
例如： N=8 （格子数）R=2 （红灯数）B=3 （蓝灯数）放置的方法有：R-B 顺序R R B B BR R B B BR R B B BR R B B BR R B B BR R B B BB-R顺序B B B BBBBBBBBBBBBBBR RRRBRRRRRRRR放置的总数为12 种。
数据输入的方式为：NP1（颜色，为一个字母）P2N1（灯的数量）N2Q（结束标记， Q 本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。
<3> 设有一个四层的积木块，1～ 4 层积木块的数量依次为：5， 6，7， 8如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。
1.【问题描述】请统计某个给定范围[L,R]的所有整数中，数字N出现的次数。
【输入格式】共1行，为三个正整数L、R和N，之间用空格隔开。
(1≤L≤R≤10000)。
【输出格式】仅1行，表示数字N出现的次数。
如输入2 22 2 则输出62.用自然数1，2，3，4，5，。
构成连续数1234567891011…9899100101…从键盘输入整数m(20000m)，输出第m位数字。
样例输入输出：输入：m=15输出：23. 聪明的囚犯：传说从前有一个残暴的国王，喜欢杀戮百姓。
有一次，他抓到30个百姓并要一一杀掉。
在这30个百姓中间有一个聪明人，他站出来对国王说：“请国王打发慈悲，赦免两个人不死。
”国王问：“赦免哪两个人不死？”那个聪明人回答说：“我们30个人围成一圈，从1开始报数，凡数到5的人就拉出去杀掉，剩下的人继续从1开始报数，循环反复，直到剩下两个人为止，这两个人被赦免。
”国王一听很有意思，就同意了聪明人的建议，叫这30个百姓围成一圈，依依报数，凡数到5的就杀掉。
最后只剩下两个人没有被杀掉，而聪明人就是其中之一。
编写程序，输入N个百姓，由计算机判断一下，聪明人要站在什么位置，才能躲过这场屠杀。
如输入N=30则输出14 34. 算盘，这个古老的计算工具是我国古代的重要发明。
在算盘上，一个档相当于整数的一位，高位在左边，所以，从右向左数，各档依次表示个位、十位、百位、……，在每个档上，靠框的珠不参与计数，靠梁的珠参与计数，且梁上面的珠每个表示5，梁下面的珠每个表示1，并规定0用本档上所有的珠都靠框来表示。
根据这个规则，上面的算盘就表示拨入了一个整数123456789（其它的档，认为是0）。
算盘的初始状态是所有的珠都靠框，即所有档上都是0。
请编写程序计算一下，从初始状态拨入一个整数n（位数≤17），一共需要拨动多少个珠？样例输入：8102 样例输出：75. 现在有一个长度为N(1<=N<=1000)的并且每个数只可能是1或2或3的数列，求至少要交换多少次，才能得到一个升序的序列。
1．某监狱里有个很长的走廊，走廊中一个接一个地有N个房间。
每个房间中锁着一个犯人。
一天夜里，狱警决定玩一个无聊游戏。
第1轮中，他喝了一口威士忌，然后打开每个房间。
第2轮，他喝了一口威士忌，然后按2的倍数遍历每个房间。
第3轮，他又喝了一口威士忌，然后遍历所有3的倍数的房间。
依次类推。
在遍历中，如果房间是锁着的，则打开；否则锁上。
他这样重复N轮，最终醉酒。
这时有些囚犯看到自己房间的锁被打开了，他们立即逃跑。
对于有N个房间的走廊，最终会有多少囚犯逃脱？输入：输入数据的第一行中有一个整数，表示有多少组测试数据。
接下来的若干行每行包含一个值为5-100的整数，这是房间的数目。
输出：对应输入数据输出多行，每行一个整数，表示逃脱的囚犯数量。
样例输入：25100样例输出：210var n,num,s,m,i,k,j:integer;a:array[0..200]of boolean;begin readln(num);for i:=1 to num dobegin readln(n);fillchar(a,sizeof(a),true);for j:=1 to n dofor k:=1 to n doif k mod j=0 then a[k]:=not a[k];s:=0;for j:=1 to n doif a[j]=false then inc(s);writeln(s);end;end. 输入3 10 35 50输出3 5 7输入3 22 68 99 输出 4 8 9输入5 10 30 60 85 100 输出 3 5 7 9 10一个自然数，若它的素因数至少是两重的（相同的素因数至少个数为二个，如：24=2*2*2*3，则称该数为“漂亮数”。
若相邻的两个自然数都是“漂亮数”，就称它们为“孪生漂亮数”，例如8和9就是一对“孪生漂亮数”。
输入X,Y,编程找出[X,Y]之间的所有“孪生漂亮数”。
如输入2 25,则输出8 924 25var i,n,a,t,x,y,s:longint; f :boolean;begin readln(x,y);a:=x;repeata:=a+1;n:=a;f:=false; i:= 2 ;while n >= i do begint:=0;while n mod i = 0 do begint:=t+1;n := n div i;end;if t>=2 then f:=true;i := i+1;end;if f then beginn:=a+1;f:=false; i:= 2 ;while n >= i do begint:=0;while n mod i = 0 do begint:=t+1;n := n div i;end;if t>=2 then f:=true;i := i+1;end; end;if f then begin s:=s+1; writeln(a,’‘,a+1);end;until a=y;readln;end.输入50 120输出63 64 75 76 80 81 98 99 99 100 116 117 120 121 输入354 480 输出360 361 363 364 368 369 。
CCF 全国信息学奥林匹克联赛（NOIP2014）复赛提高组 day1（请选手务必仔细阅读本页内容）一、题目概况二、提交源程序文件名三、编译命令（不包含优化开关）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+， 2.71GHz，内存 2G，上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、特别提醒：评测在 NOI Linux 下进行。
6、为了方便评测请以自己名字的拼音为文件夹名，而且将原程序直接保存在文件夹内，不用再新建子文件夹。
1．斐波那契(pf.pas/c/cpp)【问题描述】是个斐波那契数迷。
他是如此的酷爱这个数列，因此他想知道很多关于这个数列的东西，比方说第个斐波那契数是多少啊、前项的和是多少啊如何用若干个斐波那契数的和表示一个自然数啊之类之类的。
今天他希望知道的是：第个斐波那契数的末尾一位是多少？记表示第个斐波那契数，。
【输入】输入文件名为pf.in，共行。
输入只有一个数。
【输出】输出文件名为pf.out，仅一行，即第个数的最后一位。
【输入输出样例】【数据说明】对于3的数据满足，；对于的数据满足，。
(toy.pas/c/cpp)【问题描述】一天小D去超市买回来了一个玩具，这个玩具是由n个球和一些支架组成，每一个支架连接着两个不同的球，通过支架每两个球之间的简单路径有且只有一条，如果某一个支架的两端的球全被拿走，那么这个玩具就会垮掉。
小D无聊的时候开始拿走球，问，他有多少中拿球方案，使玩具不垮。
【输入】输入文件名为toy.in。
第一行一个数n 表示球的个数接下来若干行每行两个数a，b表示有一个支架连接着球a和球b【输出】输出文件名为toy.out.一行一个数ans 表示DRJ拿球的方案数mod 109+7（可以一个球也不拿）【输入输出样例】【数据说明】30%的数据满足n<=20;50%的数据满足n<=1000100%的数据满足 n<=500000;（running.cpp/c/pas）【问题描述】某校开展了同学们喜闻乐见的阳光长跑活动。
【问题描述】请统计某个给定范围[L,R]的所有整数中，数字N出现的次数。
【输入格式】共1行，为三个正整数L、R和N，之间用空格隔开。
(1≤L≤R≤10000)。
【输出格式】仅1行，表示数字N出现的次数。
如输入2 22 2 则输出6var a,b,c,d,e,f,n:integer;beginassign(input,'two.in');reset(input);assign(output,'two.out');rewrite(output);readln(a,b,n);f:=0;d:=0;for c:=a to b dobegine:=c;repeatd:=e mod 10;e:=e div 10;if d=n then inc(f);until e=0;end;writeln(f);close(input);close(output);end.输入2 100 5输出 20 输入 1 1000 9 输出 300输入 2222 2223 2 输出 7 输入 9993 10000 2 输出 02.用自然数1，2，3，4，5，。
构成连续数1234567891011…9899100101…从键盘输入整数m(20000m)，输出第m位数字。
样例输入输出：输入：m=15输出：2①m=11②m=194③m=100007④m=199992var p,d,i,j,w,c,m:integer;beginwrite('m=');readln(m);c:=1;i:=1;while c<m do begini:=i+1;w:=1;j:=i;while j>=10 do beginj:=j div 10;w:=w+1;end;c:=c+w;end;d:=c-m+1;for j:=1 to d do beginp:=i mod 10;i:=i div 10;end;writeln(p);end.3.聪明的囚犯：传说从前有一个残暴的国王，喜欢杀戮百姓。
CCF全国信息学奥林匹克联赛（NOIP2014）复赛提高组 day11．生活大爆炸版石头剪刀布(rps.cpp/c/pas)【问题描述】石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。
如果两个人出拳一样，则不分胜负。
在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。
升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：斯波克：《星际迷航》主角之一。
蜥蜴人：《星际迷航》中的反面角色。
这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。
表一石头剪刀布升级版胜负关系乙剪刀石头布蜥蜴人斯波克甲对乙的甲结果剪刀平输赢赢输石头平输赢输布平输赢蜥蜴人平赢斯波克平现在，小A和小B尝试玩这种升级版的猜拳游戏。
已知他们的出拳都是有周期性规律的，但周期长度不一定相等。
例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”已知小A和小B一共进行N次猜拳。
每一次赢的人得1分，输的得0分；平局两人都得0分。
现请你统计N次猜拳结束之后两人的得分。
【输入】输入文件名为rps.in。
第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。
数与数之间以一个空格分隔。
第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。
其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。
数与数之间以一个空格分隔。
【输出】输出文件名为rps.out。
输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。
【输入输出样例1】rps.in rps.out10 5 66 20 1 2 3 40 3 4 2 1 0【输入输出样例2】rps.in rps.out4 49 5 50 1 2 3 41 0 32 4【数据说明】对于100%的数据，0 < N ≤ 200，0 < NA ≤ 200， 0 < NB ≤ 200。
CCF全国信息学奥林匹克联赛（NOIP2014）复赛提高组 day11．生活大爆炸版石头剪刀布(rps.cpp/c/pas)【问题描述】石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。
如果两个人出拳一样，则不分胜负。
在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。
升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：斯波克：《星际迷航》主角之一。
蜥蜴人：《星际迷航》中的反面角色。
这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。
现在，小A和小B尝试玩这种升级版的猜拳游戏。
已知他们的出拳都是有周期性规律的，但周期长度不一定相等。
例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”已知小A和小B一共进行N次猜拳。
每一次赢的人得1分，输的得0分；平局两人都得0分。
现请你统计N次猜拳结束之后两人的得分。
【输入】输入文件名为rps.in。
第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。
数与数之间以一个空格分隔。
第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。
其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。
数与数之间以一个空格分隔。
【输出】输出文件名为rps.out。
输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。
【输入输出样例2】【数据说明】对于100%的数据，0 < N ≤ 200，0 < NA ≤ 200， 0 < NB ≤ 200。
2．联合权值(link.cpp/c/pas)【问题描述】无向连通图G有n个点，n-1条边。
点从1到n依次编号，编号为i的点的权值为Wi ，每条边的长度均为1。
图上两点(u, v)的距离定义为u点到v点的最短距离。
对于图G上的点对(u, v)，若它们的距离为2，则它们之间会产生Wu×Wv的联合权值。
请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？【输入】输入文件名为link.in。
第一行包含1个整数n。
接下来n-1行，每行包含2个用空格隔开的正整数u、v，表示编号为u和编号为v的点之间有边相连。
最后1行，包含n个正整数，每两个正整数之间用一个空格隔开，其中第i个整数表示图G上编号为i的点的权值为Wi。
【输出】输出文件名为link.out。
输出共1行，包含2个整数，之间用一个空格隔开，依次为图G上联合权值的最大值和所有联合权值之和。
由于所有联合权值之和可能很大，输出它时要对10007取余。
link.in link.out20 7451 22 33 44 51 523 10【样例说明】本例输入的图如上所示，距离为2的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。
其联合权值分别为2、15、2、20、15、20。
其中最大的是20，总和为74。
【数据说明】对于30%的数据，1<≤100；对于60%的数据，1<≤2000；对于100%的数据，1<≤200,000，0<Wi ≤10,000。
3. 飞扬的小鸟（bird.cpp/c/pas)【问题描述】Flappy Bird 是一款风靡一时的休闲手机游戏。
玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。
如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。
为了简化问题，我们对游戏规则进行了简化和改编：1.游戏界面是一个长为n，高为m的二维平面，其中有k个管道（忽略管道的宽度）。
2.小鸟始终在游戏界面移动。
小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
3.小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。
如果点击屏幕，小鸟就会上升一定高度X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度Y。
小鸟位于横坐标方向不同位置时，上升的高度X和下降的高度Y可能互不相同。
4.小鸟高度等于0或者小鸟碰到管道时，游戏失败。
小鸟高度为m时，无法再上升。
现在，请你判断是否可以完成游戏。
如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
【输入】输入文件名为 bird.in。
第1行有3个整数n，m，k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；接下来的n行，每行2个用一个空格隔开的整数X和Y，依次表示在横坐标位置0~n-1上玩家点击屏幕后，小鸟在下一位置上升的高度X，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度Y。
接下来k行，每行3个整数P，L，H，每两个整数之间用一个空格隔开。
每行表示一个管道，其中P表示管道的横坐标，L表示此管道缝隙的下边沿高度为L，H表示管道缝隙上边沿的高度（输入数据保证P各不相同，但不保证按照大小顺序给出）。
【输出】输出文件名为bird.out。
共两行。
第一行，包含一个整数，如果可以成功完成游戏，则输出1，否则输出0。
第二行，包含一个整数，如果第一行为1，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。
【输入输出样例1】【输入输出样例说明】如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。
【数据围】对于30%的数据：5≤n≤10，5≤m≤10，k=0，保证存在一组最优解使得同一单位时间最多点击屏幕3次；对于50%的数据：5≤n≤20，5≤m≤10，保证存在一组最优解使得同一单位时间最多点击屏幕3次；对于70%的数据：5≤n≤1000，5≤m≤100；对于100%的数据：5≤n≤10000，5≤m≤1000，0≤k<n，0<X<m，0<Y<m，0<P<n，0≤L<H ≤m，L+1<H。
CCF全国信息学奥林匹克联赛（NOIP2014）复赛提高组 day21．无线网络发射器选址(wireless.cpp/c/pas)【问题描述】随着智能手机的日益普及，人们对无线网的需求日益增大。
某城市决定对城市的公共场所覆盖无线网。
假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值1。
东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为0,1,2…128。
东西向街道和南北向街道相交形成路口，规定编号为x的南北向街道和编号为y的东西向街道形成的路口的坐标是（x, y）。
在某些路口存在一定数量的公共场所。
由于政府财政问题，只能安装一个大型无线网络发射器。
该无线网络发射器的传播围是一个以该点为中心，边长为2*d的正方形。
传播围包括正方形边界。
例如下图是一个d = 1的无线网络发射器的覆盖围示意图。
现在政府有关部门准备安装一个传播参数为d的无线网络发射器，希望你帮助他们在城市找出合适的安装地点，使得覆盖的公共场所最多。
【输入】输入文件名为wireless.in。
第一行包含一个整数d，表示无线网络发射器的传播距离。
第二行包含一个整数n，表示有公共场所的路口数目。
接下来n行，每行给出三个整数x, y, k, 中间用一个空格隔开，分别代表路口的坐标(x, y)以及该路口公共场所的数量。
同一坐标只会给出一次。
【输出】输出文件名为wireless.out。
输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。
【输入输出样例】wireless.in wireless.out11 3024 4 106 6 20【数据说明】对于100%的数据，1 ≤ d ≤ 20，1 ≤ n ≤ 20， 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤ 1,000,000。
2．寻找道路(road.cpp/c/pas)【问题描述】在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。
注意：图G中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
【输入】输入文件名为road.in。
第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。
接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。
【输出】输出文件名为road.out。
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。
如果这样的路径不存在，输出-1。
road.in road.out3 2－11 22 11 3【输入输出样例说明】如上图所示，箭头表示有向道路，圆点表示城市。
起点1与终点3不连通，所以满足题目描述的路径不存在，故输出-1。
road.in road.out6 631 21 32 62 54 53 41 5【输入输出样例说明】如上图所示，满足条件的路径为1->3->4->5。
注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。
【数据说明】对于30%的数据，0< n ≤10，0< m ≤20；对于60%的数据，0< n ≤100，0< m ≤2000；对于100%的数据，0< n ≤10,000，0< m ≤200,000，0< x,y,s,t≤n，x≠t。
3．解方程(equation.cpp/c/pas)【问题描述】已知多项式方程：求这个方程在[1, m]的整数解（n和m均为正整数）。
【输入】输入文件名为equation.in。
输入共n+2行。
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,……,an。
【输出】输出文件名为equation.out。
第一行输出方程在[1, m]的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]的一个整数解。
【输入输出样例1】equation.in equation.out2 10 1-2 111equation.in equation.out2 10 2 -3 1 2 1 2【输入输出样例3】equation.in equation.out 2 10132【数据说明】对于30%的数据，0<n≤2，|ai|≤100，an≠0，m≤100；对于50%的数据，0<n≤100，|ai|≤10100，an≠0，m≤100；对于70%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤10000；对于100%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤1000000。
