小学生程序设计复赛练习题

Qǐng bāngzhù Gabiluso lái jìsuàn zuìdī shùmù dì bāshì zhàn, tā bìxū xiāohuǐ, wánchéng tā de shǐmìng.

字典 - 查看字典详细内容

【输入】

第一行一个整数N,表示小明共有N个整数。

第二行N个整数,第i个数a[i],表示第i个整数。

【输出】

一个整数,表示满足条件的四元组取法,最终结果对1000000007取模。

【输出输出样例1】 game.in game.out 4 3 1 3 1 4

【数据范围】

对于20%的数据1<=n<=50。 对于40%的数据1<=n<=200。 对于60%的数据1<=n<=2000。

对于100%的数据1<=n<=100000,1<=a[i]<=1000000000。 其中有50%的数据不同的a[i]的个数<=10(相同的a[i]很多),另外50%的数据不同的a[i]的个数>=n/10(不同的a[i]很多)哦。

第5题 乐乐的得分

问题描述:

“六一”儿童节到了,乐乐参加了学校组织的诗歌朗颂比赛,这个比赛有n个评委,各参赛者朗颂完后,每个评委会马上打出一个分数,而参赛者的得分是指这n个分数里去掉一个最高分和一个最低分后的(n-2)个数的平均分。现在乐乐想知道自己的得分是多少。 输入格式:

第一行是一个整数n(3≤n≤20000)。

第二行是n个100以内的正整数,每个整数之间用一个空格隔开。 输出格式:

输出文件只有一个数,表示乐乐的分数,得数保留小数点后一位数字。 输入样例: 10

95 90 88 92 94 98 98 93 93 91 输出样例: 93.3

5

第6题 乐乐的数字

问题描述:

乐乐最近喜欢研究回文数,假设一个数从左到右读跟从右到左读的结果是一样的,那么我们说这个数是一个回文数。 如果一个数在十进制下是回文的,我们说这个数是一重回文数,如果一个数在十进制和二进制下是回文的,我们说这个数是二重回文数,如果一个数在三种进制下是回文的,我们说这个数是三重回文数??。现在我们用数字0..9,字母‘A’..‘Z’分别代表数字0..35(即10用A表示,11用B表示,??,35用Z表示),任意给出一个10进制数,乐乐想知道它在2至36进制里是多少重的回文数。 输入格式:

输入文件只有一个10进制的整数n(2≤n≤2000000000)。 输出格式:

第一行为一个整数m,表示n在2至36进制里有m种是回文的; 接下来是m行,从小到大输出n在哪些进制下是回文的。 输入样例: 50 输出样例: 3 7 9 24 样例解释:

50对应的7进制数为101,9进制数为55,24进制数为22。

第7题 乐乐的礼物

问题描述:

圣诞节到了,乐乐所在的班准备搞一个圣诞晚会,晚会的其中一个环节是全班同学互送礼物。已知每个同学都准备了一些钱来送礼物,而这些钱将会被平均分给那些将收到他的礼物的人。有些人准备了较多的钱,有些人准备了较少的钱。现在乐乐想知道晚会结束后哪些同学收到的礼物的总价值最大(包含无法送出的钱)。

6

输入格式:

第1行一个整数n,表示乐乐所在的班的人数(2≤n≤100);

第2至n+1行(n行),按班里的学号顺序给出每个同学的姓名。(姓名只包含大写或小写字母,姓名的长度不超过10个字母);

第n+2至2*n+2行(n行),按学号顺序给出每个同学送礼物的信息:第一个是整数m(0≤m≤5000),表示该同学准备用来送礼的钱;第二个是整数k(0≤k≤20),表示该同学准备把钱平均分给k个好朋友(给每个朋友的钱都是整数,并尽量全部用完,剩下无办法再分的钱自己保留);接着是k个姓名,姓名之间用一个空格分开,表示要分给哪k个朋友。 输出格式:

输出文件有n行,按最后的钱数从大到小的顺序输出每个同学的姓名和钱数。如果钱数相同的按学号顺序从小到大输出。 输入样例: 5 Dave laura owen vick amr

200 3 laura owen vick 500 1 Dave 150 2 vick laura 600 1 amr 0 0 输出样例: amr 600 Dave 502 laura 141 vick 141 owen 66 样例解释:

Dave的200元分给了3人,每人66元,剩下2元,还收到了2号给他的500元,因此他最后有502元。

laura的500元给了同学,收到1号给他的66元和3号给他的75元,他最后有141元。

owen的150元给了2人,每人75元,收到1号给他的66元,他最后有66元。 vick的600元给了同学,收到1号给他的66元和3号给他的75元,他最后有141元。 amr没钱给人,收到5号给他的600元,他最后有600元。

7

第8题 乐乐的工作

问题描述:

乐乐非常喜欢现在这份工作,因为公司只要求员工把每天的工作完成,不要求固定的上班时间。假如乐乐的同事有的从300时刻(以秒为单位),一直工作到3000时刻(我们认为从300时刻工作到3000时刻所工作的时间为3000-300=2700秒,即结束的那个时刻是没有工作的);有的从700时刻开始,在5200时刻结束;有的从6500时刻开始,到8100时刻结束。那么期间最长的至少有一个人在工作的连续时间是4900秒(从300时刻到5200时刻),而最长的无人工作的连续时间为1300时刻(从5200时刻到6500时刻)。

现在乐乐想知道从最早有人开始工作的时间至最后一个人离开的时间里,公司里最长至少有一人在工作的时间段和最长的无人工作的时间段。

输入格式:

第一行一个整数n(1≤n≤5000);

接着有n行,每行有两个用空格分开的正整数Ai和Bi(0≤Ai

一行,两个整数,即题目所要求的两个答案。 输入输出样例: 3 输入 300 3000 700 5200 6500 8100 输出 4900 1300 10 1 样例1 2 10 20 21 30 样例2 【问题分析】

有n个人,每个人从时刻i开始工作,到时刻j结束,从最早开始的人开始的时刻算起,至少有一个人工作的连续时间段的最大值,和一个人也不工作的时间段的最大值。

【样例解释】

样例一:最长至少有一个人工作的连续时间段的最大值即从300到5200,一个人也不工作的时间段的最大值即从5200 到6500。

【算法分析】

从数据看,bi<=1000000,n<=5000,如果标记每个时刻是否有人工作,最坏情况时间复杂度O(n*10^6),超的一塌糊涂。预计60分。(这个数据有点水,原题是时刻小于maxlongint)。

仔细思考不难发现,如果n[i]开始的时间小于等于n[j]结束的时间,那么n[i]会和n[j]相重合一部分就可以更新前者的结束时间。如果再按照开始时间排序,那么这就是一个单调上升的序列。一旦n[i]开始时间大于n[j]结束时间,那么这段空隙一定是无人工作的,前面那一段时间必定是一直有人工作的。

但要注意一点比如: 10 50

8

20 30 40 50

虽然第一个到的是50,但第二个只有30<40,这个时候就要与目前能达到的最大时间做比较。或者你更新最前面一个的时间,一直于最前面一个的结束时间做比较。

那么就有了一个算法,先排序,再模拟。 时间复杂度O(n log(n)+n)

9

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4