电脑c++编程试题

夏日酷爽水题大赛 ——Edited By Wayne Ho （请选手务必仔细阅读本页） 【题目概况】 中文题目名称 雷雷扔粉笔头 地精部落 程序 联络员 英文题目名称 Chalk Goblin Program Contact 可执行文件名 Chalk.exe Goblin.exe Program.exe Contact.exe 输入文件名 Chalk.in Goblin.in Program.in Contact.in 输出文件名 Chalk.out Goblin.out Program.out Contact.out 建议时限 1秒 1秒 1秒 1秒 运行内存 64MB 64MB 64MB 64MB 测试点数目 10 10 10 10 每个测试点分值 10 10 10 10 附加样例文件 有 有 有 有 题目类型 传统 传统 传统 传统 【注意事项】 1、 文件名（程序名和输入输出文件名）不区分大小写。 2、 C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、 评测时采用谢老师的机子，时限为标程运行时间的1.5~2倍。 【前言】 RT，初次见面，题目灰常和谐，欢迎虐题！ 1. 雷雷扔粉笔头 (chalk.pas/c/cpp) 【问题描述】     雷雷老师一生气就会拿粉笔头扔(读作leng)XX中学实验班的学生。学生1~n排成一排，雷雷老师可以扔(leng)任意个学生，但是相邻的两个学生不能都被扔(leng)，否则这两个同学会群起而攻Mr.雷。请问在满足相邻的两个学生不能都被扔(leng)的前提下，一共有多少种扔(leng)粉笔头的方法！！ 【输入】 n(n为整数，保证0<=n<=91) 【输出】     输出一行，为方法总数。 【输入输出样例】 chalk.in chalk.out 2 3 【样例解释】 可以都不扔，也可以扔1号或2号，一共3种方法。 2. 地精部落 (goblin.pas/c/cpp) 【问题描述】 传说很久以前，大地上居住着一种神秘的生物：地精。    地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度Hi，其中Hi是1到N之间的正整数。    如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。    类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。    地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。    地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮流担当瞭望工作，以确保在第一时间得知外敌的入侵。    地精们希望这N段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。    现在你希望知道，长度为N的可能有地精居住的山脉有多少种。两座山脉A和B不同当且仅当存在一个i，使得Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。【输入】 仅含一行，两个正整数N, P。 【输出】     输出一个整数，示你所求的答案对P取余之后的结果。 【输出输出样例】 goblin.in goblin.out 4 7 3 【样例说明】   共有10种可能的山脉，它们是： 1324 1423 2143 2314 2413  3142 3241 3412 4132 4231  其中加下划线的数位表示可以设立瞭望台的山峰，其他表示可以设立酒馆的山谷。 【数据规模和约定】 对于20%的数据，满足N≤10； 对于40%的数据，满足N≤18； 对于70%的数据，满足N≤550；   对于100%的数据，满足3≤N≤4200，P≤10^9。 3. 程序 (program.pas/c/cpp) 【问题描述】 Alice在学习编程，首先她创建一个放N个整数的数组，初始化为0，然后不停地调用以下过程：    Alice一共调用过程K次，参数分别是X1,X2。。。，Xk。然后有Q次提问，每次提问给定L和R(L<=R)，表示左右边界，你需要输出第L个元素到第R个元素的和，即seq[L]+seq[L+1]+seq[L+2]+…+seq[R]。   请你帮助Alice。  【输入】 输入第一行包含两个整数，N(1<=N<=10^6)和K(1<=K<=10^6)，表示数组的大小和调用过程的次数。 第二行包含K个整数：X1,X2…,Xk，表示参数(1<=Xi) 接下来一行包含一个整数Q(1<=Q<=10^6)，表示询问次数。   接下来Q行每行包含两个整数Li和Ri（0<=Li<=Ri） 【输出】 　 输出Q行，每行一个整数，第i行表示seq[Li] + seq[Li+1] + seq[Li+2] + ... + seq[Ri]。 【输出输出样例1】 program.in program.out 10 4 1 1 2 1 3 0 9 2 6 7 7 35 18 3 【输出输出样例2】 program.in program.out 11 3 3 7 10 3 0 10 2 6 7 7 8 2 1 【输出输出样例3】 program.in program.out 1000000 6 12 3 21 436 2 19 2 12 16124 692 29021 16422 28874 【样例解释】   样例1，调用了4次，参数分别是1，1，2，1，此后数组变成{4, 3, 4, 3, 4, 3, 4, 3, 4, 3}，第2个到第6个的和为4+3+4+3+4 = 18。  4. 联络员 (contact.pas/c/cpp) 【问题描述】 Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。 目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。 【输入】     第一行n，m表示Tyvj一共有n个管理员，有m个通信渠道    第二行到m+1行，每行四个非负整数，p,u,v,w 当p=1时，表示这个通信渠道为必选通信渠道；当p=2时，表示这个通信渠道为选择性通信渠道；u,v,w表示本条信息描述的是u，v管理员之间的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示费用。  【输出】     一行一个整数，为最小通信费用。 【输出输出样例】 Contact.in Contact.out 5 6 1 1 2 1 1 2 3 1 1 3 4 1 1 4 1 1 2 2 5 10 2 2 5 5 9 【样例解释】 1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通2和5号管理员，选择费用为5的渠道，所以总的费用为9  【注意】 U,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠道  【数据范围】 对于30%的数据，n<=10 m<=100 对于50%的数据, n<=200 m<=1000    对于100%的数据，n<=2000 m<=10000