第三届河南省大学生程序设计竞赛题型简要分析

所有的题目 时间限制： 1秒

概览：

题数	类型
1	线段树；区间树
2	动态规划；枚举
3	图论
4	图论
5	动态规划
6	模拟
7	贪心；（树形）动态规划
8	线段树

【试题一】 房间安排

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=168

类型：线段树；区间树

解法：普通的做法时间复杂度为O(n) ，每次需要遍历区间内所有的数，但用线段树可以做到O(log n)。普通的做法是统计每天占用的房间总数，最大值即解。

【试题二】素 数

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=169

类型：动态规划；枚举

解法：动态规划，求出X前的第一个素数以及其后的第一个素数，取其较近者。枚举（牺牲内存，换取时间），先离线求出范围内的所有素数（168个），存储起来，再找出离X最近且较大的那个素数即可。

【试题三】 网络的可靠性

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=170

类型：图论

解法：在给出图的基础上求出闭合环，边数与原始边数差值即解。

【试题四】 虚拟城市之旅

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=247

类型：图论

解法：求出由源点能到达的强连通分量，然后搜索求最优解。

【试题五】聪明的“KK”

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=171

类型：动态规划

解法：类似“TheTriangle”（http://acm.nyist.net/JudgeOnline/problem.php?pid=18），这个题利用数塔，数塔的思想就是从下往上来进行运算，不断的更新数组，最终求出最大和。有些细节要注意，当KK走倒最后一列是只能向下走，当KK走到最后一行时，只能向右走。

【试题六】 AMAZING AUCTION

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=251

http://acm.zju.edu.cn/na_public/showProblem.do?problemCode=2613

类型：模拟

解法：先剔除无效竞价，再取最低竞价，为了保证先入为主，在求最小值的过程中应该使用条件min > p[i]而非min>= p[i].

【试题七】 BUYING FEED

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=248

http://202.120.106.94/onlinejudge/problemshow.php?pro_id=440（条件不同）

类型：贪心；（树形）动态规划

解法：贪心，求出每个商店（每一点）每买一磅食物需要的价钱，价钱中包括从这点运到终点需要的运费。

DP，转移方程（条件不同）

DP[I][J]=MIN{DP[I-1][K]+K*K*(D[I]-D[I-1])+(J-K)*C[I]}J-F[I]<=K<=J

根据题目数据给的范围，500(I的范围)*10000(J的范围)*500(K的范围)肯定要超时。

于是用单调队列优化。

关于单调队列：队头的元素肯定是最小的（最大的）

取元素操作：从队头取出元素，直到该元素在要求的范围内（本题即为J-F[I]<=K<=J）

插入元素操作：若队尾元素比插入的元素要大，则删除。直到比待插入的元素小为止，然后再插入元素。

另外通过本题明确了队列的用法，头指针指向第一个元素，尾指针指向最后一个元素的后一位。若头尾指针相等则队列为空。

【试题八】 ROOM ASSIGNATION

练习处：http://acm.nyist.net/JudgeOnline/problem.php?pid=250

类型：线段树

题意：题目的意思很简单，问你有没有连续的n的房间，如果有，就输出以那个房间开始（最小的）。如果没有就输出0；还有一种情况：客人要退房间，然后退掉n——n+len-1这些房间。

给出M(M<= 50000)组操作，每组操作的形式如下：

1 D: 询问是否有长度为D的连续区间，如果存在输出最左边的，否则输出0，并且将这块连续的区间占据。

2 X D:将从X开始的连续D块空间释放掉。

解法：线段树染色问题，和ZJU2301 Color the Ball类似，也是寻找最长连续区间。记录左右端点的连续情况。

赛题见：http://download.csdn.net/download/wujun8/4218470