所有的题目 时间限制: 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
分享到:
相关推荐
包括图论例题、动态规划例题、综合题例题。
全国大学生英语竞赛题型,时间和分数分数分数第三方
刘征宇编写的 大学生电子设计竞赛 指南,内容有六大章:元器件介绍;单元电路讲解;单片机;系统设计方法与题型分析;竞赛常用仪器;竞赛实务。
河北省第六届大学生物理竞赛试题.pdf
包含大学生英语竞赛阅读理解题型简介,对有掌握阅读技巧有帮助。
大学英语四级新题型听力分析解析PPT课件.pptx
包含ACM经典题型及详细解析,希望能给大家带来帮助!!
全国大学生电子设计竞赛是电子信息类在校大学生的重点学科竞赛,经过历届的发展,参赛的学校和队伍以及赛题的数量与难度都在逐年递增,竞赛的题目也由以往简单的电路设计开始向系统设计演变,其中部分题目还会综合...
该资源为2012-2019年四川师范大学831C语言程序设计与数据结构考研真题,资源高清无水印哦!
河南省公务员面试新题型河南省公务员考试题型.pdf
第3章 面向对象程序设计 第4章 数组、字符串与异常处理 第5章 文件与数据流 第6章 图形用户界面设计 第7章 小应用程序 第8章 多线程程序设计 第9章 编程规范 第10章 网络程序设计 第11章 多媒体与图形学程序设计 第...
大一VB《计算机语言与程序设计》考试题型复习分析含答案.pdf
全国电子设计大赛、全国大学生智能汽车竞赛、蓝桥杯、集成电路创新创业大赛、光电设计竞赛、挑战杯、大创项目、互联网+、三创赛、计算机设计竞赛、创新创业大赛、ACM-ICPC国际大学生程序设计竞赛、全国大学生数学...
课程设计题型,预先了解题型,能让你超越别人。不要输在起跑线。
大学生心理健康考试题型.doc
新课标河南省2016中考英语第三部分中招题型研究三阅读理解话题2学生学习
新课标河南省2016中考英语第三部分中招题型研究三阅读理解C话题2学生活动
新课标河南省2016中考英语第三部分中招题型研究三阅读理解B话题4学生学习
包含程序设计题,判断题,选择题,填空题,包含有大量典型例题。足够应付考试中出现的各类题型,学到就是赚到
新课标河南省2016中考英语第三部分中招题型研究四词语运用话题3学生学习与活动