NOIP2010模拟题.doc

Noip2010模拟题（二）2010-11-14试题SHLQSH数石材切割睡觉赛跑源程序shlqsh.c/cpp/pasbrick.c/cpp/passleep.c/cpp/pasrun.c/cpp/pas输入文件名shlqsh.inbrick.insleep.inrun.in输出文件名shlqsh.outbrick.outsleep.outrun.out时间限制1S1S1S1S空间限制256M256M128M256MPROBLEM 1. SHLQSH数问题描述：我们把t1 , t2 (包括t1 , t2 (1=t1t2=10000000)之间的所有数的约数个数和n称为t1 , t2的shlqsh数;问题是给出数据t1 , t2后,求t1 , t2的shlqsh数；输入输入文件 shlqsh.in 仅包含一行，共有两个整数，表示t1 t2 (用空格分开)输出输出文件shlqsh.out 仅有一个整数，表示t1 , t2之间的shlqsh数。输入样例：2 6输出样例：13 样例说明：(说明部分不必输出) 2的约数有1,2 (2个)； 3的约数有1,3 (2个)； 4的约数有1,2,4 (3个)； 5的约数有1,5 (2个)； 6的约数有1,2,3,6 (4个)。所以2 6 的shlqsh数为13 【数据规模】 对于50 %的数据,保证有t1,t2=5000000 对于全部的数据,保证有t1,t2=10000000PROBLEM 2.石材切割问题描述：某人得到一块N*M个小格的矩形石材（可能是玉石），经专家分析，把这个矩形石材的每个小格都有一个价值（使用一个绝对值不大于10的整数来描述），现在将这块石材切割成两块矩形石材，注意，切割只能与该矩形边平行，也就是说不能把矩形的小格切碎，假设每块矩形石材的价值为该矩形中所有小格子价值之和。问怎样切割，才能使得这两个矩形的价值乘积最大。如下图是一种比较好的切割方式。输入格式：输入文件BRICK.IN的第一行为2个正整数N和M，表示石材被划分为N*M个格子。接下来N行，每行有M个整数，代表这个格子的价值。输出格式：输出文件BRICK.OUT只有一行，包含一个整数，为两个矩形的价值的最大乘积。输入样例输出样例3 4-1 -1 -1 -10 0 0 0-1 -1 -1 -1 16数据范围对于30%的数据，满足N,M5。对于100%的数据，满足N,M100。每个小格的伤害值的绝对值不超过10。一切数据及中间变量不超过longint范围。PROBLEM 3 睡觉 问题描述：为了提高程序解题能力，勤奋努力的QQ天天锯题到深夜，导致睡眠严重不足，可NOIP决赛就要来临了，必须要有良好的状态才行啊，因此QQ决定准备拿出一天时间，好好补补觉。他把这一天等分成了n个时间段，在每个时间段睡觉能获得精神点数不尽相同，在第i段时间能获得Vi的精神点数。由于勤奋的QQ觉得整天都睡太堕落了，他决定最多只能睡m个时间段。至于其他的时间吗.那自然是勤奋地锯题.有两点事情要特别提出注意：1.QQ不可能一上床马上睡着，他在连续一段睡觉时间的第一个时间段不能获得此时的V。也就是说如果他在i.j中的所有时间都休息了，获得的精神点数为Vi+1+.+Vj。2.所有的时间段呈环形分布，也就是说第n个时间段之后为第1个时间段。要求的自然是QQ最多能获得的精神点数之和。输入格式：第一行两个正整数n,m，意义如题所述接下来n行，每行一个非负整数Vi输出格式：一行，表示QQ最多能获得的精神点数之和输入样例：5 320314输出样例： 6样例解释：选择4、5、1三个时间段休息，在5、1时睡着，最大值为4+2=6数据范围：对于20%的数据n=20对于50%的数据n=200对于100%的数据n=5000,m=n,Vi=10000PROBLEM 4 赛跑 问题描述：Yali校运会又开始了。这次校运会设置了一个有趣的项目，就是在田径场设置了很多障碍，并且在障碍之间设置了跑道，要求同学们从第s个障碍，以最快的速度跑到第t个障碍，当然不一定每个障碍都要经过。如果把每个障碍看成一个点的话，那么这个项目就可以抽象成一个n个顶点，m条有向边的图。当然每个人都想走最短距离，QQ想，那么走最短路有多少种方案呢？QQ又想，大家都走最短距离的路线可能会非常拥挤，我干脆走只比最短距离只多1的路线算了，那么，比最短路多1的路线到底有多少种方案呢？输入格式：第一行有四个正整数n,m,s,t。 (st)接下来m行，每行3个正整数xi,yi,vi,表示有一条从xi到yi的长度为vi的有向边(xiyi)，注意，数据随机生成，可能会有重边。输出格式：一行，用空格隔开的两个数，分别表示两问的答案 mod 19940405。输入样例：5 6 4 12 3 13 2 13 1 104 5 25 2 75 2 7输出样例：2 0样例解释：最短路长度为20,4-5-2-3-1，注意到5-2有两条，因此有两种最短路走法。找不到长度为21的路径，因此第2问答案为0数据范围：vi=10000测试点 N M 其他1 =10 =100 vi为偶数2 =10 =1003 =1000 =50000 vi为偶数4 =50000 =200000