Noip2010模拟题由朱全民老师提供1

Noip2010模拟题由朱全民老师提供PROBLEM1.SHLQSH数问题描述：我们把t1,t2(包括t1,t2(1=t1t2=10000000))之间的所有数的约数个数和n称为t1,t2的shlqsh数;问题是给出数据t1,t2后,求t1,t2的shlqsh数；输入输入文件shlqsh.in仅包含一行，共有两个整数，表示t1t2(用空格分开)输出输出文件shlqsh.out仅有一个整数，表示t1,t2之间的shlqsh数。输入样例：26输出样例：13样例说明：(说明部分不必输出)2的约数有1,2(2个)；3的约数有1,3(2个)；4的约数有1,2,4(3个)；5的约数有1,5(2个)；6的约数有1,2,3,6(4个)。所以26的shlqsh数为13【数据规模】对于50%的数据,保证有t1,t2=5000000对于全部的数据,保证有t1,t2=10000000试题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空间限制256M256M128M256MPROBLEM2.石材切割问题描述：某人得到一块N*M个小格的矩形石材（可能是玉石），经专家分析，把这个矩形石材的每个小格都有一个价值（使用一个绝对值不大于10的整数来描述），现在将这块石材切割成两块矩形石材，注意，切割只能与该矩形边平行，也就是说不能把矩形的小格切碎，假设每块矩形石材的价值为该矩形中所有小格子价值之和。问怎样切割，才能使得这两个矩形的价值乘积最大。如下图是一种比较好的切割方式。输入格式：输入文件BRICK.IN的第一行为2个正整数N和M，表示石材被划分为N*M个格子。接下来N行，每行有M个整数，代表这个格子的价值。输出格式：输出文件BRICK.OUT只有一行，包含一个整数，为两个矩形的价值的最大乘积。输入样例输出样例34-1-1-1-10000-1-1-1-116数据范围对于30%的数据，满足N,M≤5。对于100%的数据，满足N,M≤100。每个小格的伤害值的绝对值不超过10。一切数据及中间变量不超过longint范围。PROBLEM3睡觉问题描述：为了提高程序解题能力，勤奋努力的QQ天天锯题到深夜，导致睡眠严重不足，可NOIP决赛就要来临了，必须要有良好的状态才行啊，因此QQ决定准备拿出一天时间，好好补补觉。他把这一天等分成了n个时间段，在每个时间段睡觉能获得精神点数不尽相同，在第i段时间能获得V[i]的精神点数。由于勤奋的QQ觉得整天都睡太堕落了，他决定最多只能睡m个时间段。至于其他的时间吗...那自然是勤奋地锯题...有两点事情要特别提出注意：1.QQ不可能一上床马上睡着，他在连续一段睡觉时间的第一个时间段不能获得此时的V。也就是说如果他在i...j中的所有时间都休息了，获得的精神点数为V[i+1]+...+V[j]。2.所有的时间段呈环形分布，也就是说第n个时间段之后为第1个时间段。要求的自然是QQ最多能获得的精神点数之和。输入格式：第一行两个正整数n,m，意义如题所述接下来n行，每行一个非负整数V[i]输出格式：一行，表示QQ最多能获得的精神点数之和输入样例：5320314输出样例：6样例解释：选择4、5、1三个时间段休息，在5、1时睡着，最大值为4+2=6数据范围：对于20%的数据n=20对于50%的数据n=200对于100%的数据n=5000,m=n,V[i]=10000PROBLEM4赛跑问题描述：Yali校运会又开始了。这次校运会设置了一个有趣的项目，就是在田径场设置了很多障碍，并且在障碍之间设置了跑道，要求同学们从第s个障碍，以最快的速度跑到第t个障碍，当然不一定每个障碍都要经过。如果把每个障碍看成一个点的话，那么这个项目就可以抽象成一个n个顶点，m条有向边的图。当然每个人都想走最短距离，QQ想，那么走最短路有多少种方案呢？QQ又想，大家都走最短距离的路线可能会非常拥挤，我干脆走只比最短距离只多1的路线算了，那么，比最短路多1的路线到底有多少种方案呢？输入格式：第一行有四个正整数n,m,s,t。(st)接下来m行，每行3个正整数x[i],y[i],v[i],表示有一条从x[i]到y[i]的长度为v[i]的有向边(x[i]y[i])，注意，数据随机生成，可能会有重边。输出格式：一行，用空格隔开的两个数，分别表示两问的答案mod19940405。输入样例：56412313213110452527527输出样例：20样例解释：最短路长度为20,4-5-2-3-1，注意到5-2有两条，因此有两种最短路走法。找不到长度为21的路径，因此第2问答案为0数据范围：v[i]=10000测试点NM其他1=10=100v[i]为偶数2=10=1003=1000=50000v[i]为偶数4=50000=200000v[i]为偶数5=50000=200000v[i]为偶数测试点NM其他6=1000=500007=1000=500008=50000=2000009=50000=20000010=50000=200001、SHLQSH数1的约数有1(1个)2的约数有1,2(2个)；3的约数有1,3(2个)；4的约数有1,2,4(3个)；5的约数有1,5(2个)；6的约数有1,2,3,6(4个)。所以6以内的shlqsh数为14所以有，fori:=1tordobeginans:=ans+rdivi;2.石材切割题目的意思就是，在一个N*M的矩阵中，要找出两个不相交的子矩阵，使得它们的乘积最大。一个很简单的想法就是枚举一条分割线把矩阵切成两个，然后对这两个矩阵求解最大子矩阵相乘，更新最优解。首先，这两个矩形只可能有如下两种切割方案。因此我们只要知道求出1个矩形的最优值即可（最优值包括最大值和最小值）。那么怎样求一个矩阵的最优值呢？为了解决这个问题，我们先看它的一维版本：最大连续和——在一个序列中，找出一个连续的子序列，使得这个序列中的元素和最大。例如，序列{4,-1,3,-2,2}的最大连续和是6。可以采用动态规划的方法求解最大连续和问题：定义状态F[I]表示以序列中第I个元素为结尾的最大连续和，状态转移方程为：F[I]=MAX{W[I],F[I-1]+W[I]}（W[I]代表第I个元素的值）。它的意义是：对于第I个元素，它面临的决策有2种：1、接在以第I-1个元素为结尾的子序列上(F[I-1]+W[I])；2、单独成为一个子序列（W[I]）。状态总数为N，转移时间为O(1)，所以它的时间复杂度是O(N)。现在的问题是如何将最大子矩阵转化成最大连续和。采用枚举左右边界的办法即可。当枚举完左右边界L和R之后，每一行从第L列到R列的元素和就可以视为一个元素，从第一行到第N行组成了一个长度为N的序列，对这个序列求解最大连续和就可以得到边界为L，R时的最大子矩阵。举个例子：2|35|2-1|02|-3-2|-19|9-10|-21|4对于上面那个矩阵，竖线表示枚举的左右边界，则构成序列{3+5,0+2,-1+9,-2+1}。对这个序列求解最大连续和即可。这样在O(N^3)的时间内解决了最大子矩阵问题（枚举O(N^2)和最大连续和O(N)）。但这样依然没有解决本题。枚举分割线需要O(N)的时间，求解最大子矩阵需要O(N^3)的时间，所以朴素算法的时间复杂度有O(N^4)，还有较大的常数，无法在时限内出解。其实枚举完分割线之后，并不需要对分割出来的两个矩阵求解最大子矩阵。设F[L,R]为以L,R为左右边界的最大子矩阵。显然可以在一开始对整个矩阵做一次最大子矩阵，预处理出这个数组。这样在枚举完分割线之后只需O(N^2)的枚举左右边界即可，时间复杂度降至O(N^3)。注意，以上说的只是找最大子矩阵，竖着枚举分割线的过程，大家还需要考虑另外三种情况。也就是我们也要去找最小子矩阵（两个很小的负数的乘积也有可能是个大正数），也要去横着枚举分割线。3睡觉(Sleep)简单的动态规划状态数组f[N][B][2]：f[i][j][0]={现在处于第i个小时，之前一共休息了j个小时，第i个小时没休息。到现在为止获得的最大点数}f[i][j][1]={现在处于第i个小时，之前一共休息了j个小时，第i个小时休息了。到现在为止获得的最大点数}转移:f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+v[i]);由于是循环数组。所以就分开两种情况：1.第1个小时没休息2.第1个小时休息了枚举一下做两次DP就行了PS:注意n=m的特殊情况4.狂飙（Run）改进Dijkstra算法。将状态扩展到二维，第一维仍然是顶点编号，第二维的长度为2，分别用于记录最短路和次短路。这样的数据有两个，dis[v][2]记录距离，count[v][2]计数。更新状态时：1）新值小于最短路径长：更新最短路径长，计数；次短路径长，计数2）新值等于最短路径长：更新最短路径计数3）新值大于最短路径长，小于次短路径长：更新次短路径长，计数4）新值等于次短路径长：更新次短路径计数朴素实现的Dijkstra只能得到一半左右的分数，使用堆优化可以使复杂度降到O((M+N)logN)，能通过所有数据。