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

梦里梦外; 2022-08-21 13:59 156阅读 0赞

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

概览：

** **

**【试题一】          房间安排**

练习处：[http://acm.nyist.net/JudgeOnline/problem.php?pid=168][http_acm.nyist.net_JudgeOnline_problem.php_pid_168]

类型：[线段树][Link 1]；区间树

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

**【试题二】         素 数**

练习处：[http://acm.nyist.net/JudgeOnline/problem.php?pid=169][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_170]

类型：图论

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

【**试题四**】 **         虚拟城市之旅  **

练习处：[http://acm.nyist.net/JudgeOnline/problem.php?pid=247][http_acm.nyist.net_JudgeOnline_problem.php_pid_247]

类型：图论

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

**【试题五】         聪明的“KK”**

练习处：[http://acm.nyist.net/JudgeOnline/problem.php?pid=171][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.nyist.net_JudgeOnline_problem.php_pid_251]

[http://acm.zju.edu.cn/na\_public/showProblem.do?problemCode=2613][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_acm.nyist.net_JudgeOnline_problem.php_pid_248]

[http://202.120.106.94/onlinejudge/problemshow.php?pro\_id=440][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][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][http_download.csdn.net_download_wujun8_4218470]

[http_acm.nyist.net_JudgeOnline_problem.php_pid_168]: http://acm.nyist.net/JudgeOnline/problem.php?pid=168
[Link 1]: http://blog.chinaunix.net/uid-20656730-id-1588759.html
[http_acm.nyist.net_JudgeOnline_problem.php_pid_169]: http://acm.nyist.net/JudgeOnline/problem.php?pid=169
[http_acm.nyist.net_JudgeOnline_problem.php_pid_170]: http://acm.nyist.net/JudgeOnline/problem.php?pid=170
[http_acm.nyist.net_JudgeOnline_problem.php_pid_247]: http://acm.nyist.net/JudgeOnline/problem.php?pid=247
[http_acm.nyist.net_JudgeOnline_problem.php_pid_171]: http://acm.nyist.net/JudgeOnline/problem.php?pid=171
[http_acm.nyist.net_JudgeOnline_problem.php_pid_251]: http://acm.nyist.net/JudgeOnline/problem.php?pid=251
[http_acm.zju.edu.cn_na_public_showProblem.do_problemCode_2613]: http://acm.zju.edu.cn/na_public/showProblem.do?problemCode=2613
[http_acm.nyist.net_JudgeOnline_problem.php_pid_248]: http://acm.nyist.net/JudgeOnline/problem.php?pid=248
[http_202.120.106.94_onlinejudge_problemshow.php_pro_id_440]: http://202.120.106.94/onlinejudge/problemshow.php?pro_id=440
[http_acm.nyist.net_JudgeOnline_problem.php_pid_250]: http://acm.nyist.net/JudgeOnline/problem.php?pid=250
[http_download.csdn.net_download_wujun8_4218470]: http://download.csdn.net/download/wujun8/4218470