9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

C++ 练习题



10 月 5 日解题报告
seat 题目大意:在网格图中选取 n 个小正方形,问最多有多少条公共边。 首先这个题的数据规模是如此之大,而输入文件又是如此之小。 因此果断用数学方法解决。 其实打表也是一种数学方法,输入只有一个数,这不明摆着打表么。手算+ 打表即可得到 20 分。各种乱搞?不保险。O(1) 但是在手算的过程中,我们很可能发现一些规律。 比如说:如果某方案中同一行有不连续的多个小正方形,一定存在一种方案 保证各行正方形个数不变的情况下使每行小正方形都连续,而且不比此方案差。 证明:某一行行内产生的公共边最多为行内小正方形个数-1,它与相邻行产 生的公共边最多为两行小正方形个数的较小值。 再比如:使每行的连续小正方形都从某一纵坐标开始排列,可达到最优。 再比如:对齐后,从小正方形较多的行中拿出最后一个调整到较少的行一定 不差。 于是我们就推出:最优解一定出现在正方形摆成 a 行*b 列(最后一行可以少 c 个,0<=c<b)时。 对于每个 b,存在唯一 a,枚举 b 可得到 40 分。O(n) 但是 b 一定要从 1 枚举到 n 吗? 对于每一个(a,b,c)满足 a>b,显然满足 a>c,则存在(b,a,c)与之答案相等。 所以只要枚举 a<=b 即可。60 分到手。O(sqrt(n)) 要想得到 100 分就得稍微推一下式子了。 对于(a,b,c)满足 a*b-c=n,ans=(a-1)*b+a*(b-1)-2*c=2*(a*b-c)-(a+b)=2*n-(a+b) 让 a+b 最小化即可。相信大家就算没有推出来也能想到这个结论。 那么,枚举 a 在 sqrt(n)上下就能 AC 了。O(1) 事实上,打表也可以做到 O(1)。 让我们从 n=0 开始。 n=0 ans=0 0*0=0,0*1=0 n=1 ans=0 1*1=1 n=2 ans=1 1*2=2 n=3 ans=2 n=4 ans=4 2*2=4 n=5 ans=5 n=6 ans=7 2*3=6 n=7 ans=8 n=8 ans=10 n=9 ans=12 3*3=9 n=10 ans=13 发现没? ans=n*2-(i 的个数)-(j 的个数),其中 i,j 为非负整数且满足 i*i<n,j*(j+1)<n。 divide 题目大意:将一棵 n 个节点的树分为 k 块,要求权值最大一块的权值最小。

最大值最小,一看就是二分。 然后,好像这题可以贪心的样子。 自下向上的,关于每个节点,将其儿子从小到大合并到自身,直到不能再合 并,将其作为该节点的权值。 (在这里合并的儿子应尽量多,因为到上一层,无 论这里合并多少儿子都只需一次就能全部切掉) 所以就是二分贪心了。O(n*logh) 至于那些小数据,特殊数据之类的,就不讲了。 visit 题目大意:n 个正整数的序列,增加总计不超过 m 后,相邻两项相减绝对值 之和的最小值。 题目背景:去年教师节的时候?? 其实根本没有雕塑这回事!一切为出题服务。 搜索的话 O(n*m^n)肯定是正确的,能拿到 10 分。但是一点也不优美。 注意到题目中给出 hi 的范围,考虑动态规划。 (本来这道题是可以加一或减一总计 m 次,那样的话只有动态规划了) F[i][j][k]代表前 i 个雕塑的高度被增加了 j,且第 i 个雕塑的高度为 k 时最小 不满度。三次方的状态,一次方的转移。40 分刚刚好。O(n*m*h^2) 之前我们用的方法都是与电脑的运算密切相关的“笨办法” 。让我们回归人 类思维吧。 要是你,你该怎么办? 一眼看去,发现有一个雕塑比两边都低。这也太不和谐了,赶紧搬砖垫到下 面。每垫一块砖可以让不满度减少 2(如果在两端则是 1) 。 仔细观看,发现有 k 个连续的雕塑高度相等,且比两边都低。每垫 k 块砖可 以让不满度减少 2(1)。 这样的操作最多有 n-1 个。按效率排序然后从小往大取。效率相等的操作, 应先做中间再做两边(先整后零) 。O(n*logn) 什么?不知道怎么取出操作?用链表存高度和连续个数,取出的操作要记录 最大改变高度、连续个数和是否在两端。 有人说这些操作是有先后顺序的。但是在现实中靠后的操作肯定没有必须在 之前做的操作要优,因为操作越靠后,k 越大。 话说??100%的数据居然有 10^6 这么变态!这可如何是好吖。 用两个数组 a[i]和 b[i]分别记录在两端和不在两端的操作, 用下标表示连续个 数,数组中存储高度之和。O(n) 有的同学如果某些细节处理的不太好,会 WA。 拿第一组数据做个示范。 8 6 4 3 3 2 4 2 3 1 (1)将 4 上移不超过 1,每花费 1,不满度减少 2。 (2)将 6 上移不超过 1,每花费 1,不满度减少 2。 (3)将 8 上移不超过 2,每花费 1,不满度减少 1。 (4)将 2~4 上移不超过 1,每花费 3,不满度减少 2。 (必须先完成 1) (5)将 6~8 上移不超过 1,每花费 3,不满度减少 1。 (必须先完成 2 和 3) 以上是我们将操作排序后的结果。 如果直接做(1)(2)(3)操作,答案是 3。

如果选取(1)(2)(4)操作和(3)的一半,答案是 2。 我们看到,某些情况下,不做减少 1 的操作会获得一个减少 2 的机会。 那么,在做减少 2 的操作时,如果还有剩余操作空间但 m 不足以支持,应该 看一下上一次减少 1 的操作中 k 是多少。 (减少 1 的操作永远不会必须在减少 2 的操作之前) 特判即可。 其余情况,使用前文的方法都可以解决。毕竟是一个贪心,特殊情况不会太 多。 最后,说一下为什么 O(n*logn)和 O(n)的用时会差不多,甚至到了卡不掉的 地步。 (其实我家里的电脑慢,是可以卡掉的) 快排常数小是一个原因。 取出操作已经有一定的顺序是另一个原因。 就是这样。 北京市第八十中学 陈瑞麟 2012 年 10 月 5 日



更多相关文章:
C++练习题及答案
C++练习题及答案_工学_高等教育_教育专区。C++考试必备 一、单选题 1.下列描述中,表达错误的是()。 A、公有继承的基类中的 Public 成员在派生类中仍是 ...
C++练习题2015年下(读程序练习题)
C++练习题2015年下(读程序练习题)_IT认证_资格考试/认证_教育专区。一、 读程序题目 1. 本题考核指针与字符串,指向字符串的指针,意味着指针变量中 存放字符串...
c++练习题
c++练习题_工学_高等教育_教育专区。1.8习题 一、选择 1.下面对派生类的描述中,错误的是( ) A.一个派生类可以作为另外一个派生类的基类 B.派生类至少有一...
C++试题及答案
C++试题及答案_IT认证_资格考试/认证_教育专区。c++ C++程序设计模拟试卷(一) 一、单项选择题(本大题共20小题,每小题1分,共20分)在每小题列出的四个备选项...
C++编程练习题大全(带答案)
C++编程练习题大全(带答案)_从业资格考试_资格考试/认证_教育专区。C++编译试题大全 一、简单问题: 5. 编程计算: 1!+2!+3!+…+20!,并将结果输出.输出格式...
C++练习题
C++练习题_工学_高等教育_教育专区。老师给的练习题,带答案~1 绪论例题 2:输入一名学生的成绩,判断该成绩的等级。 如>=60 的,显示“合格” ,<60 的显示“...
高级C++练习题2013
面向对象程序设计练习题 一.概念题 1. 定义形式如下的类,C++编译器自动为该类产生的四个缺省函数是什么?写出其原型。 class MyClass { public: void SetX(int...
C++练习题
C++练习题_计算机硬件及网络_IT/计算机_专业资料。C++练习题课后题:5-5 5-6 5-7 5-9 5-11 5-12 5-13 5-14 5.4: #include<iostream> #include<iomanip...
C++经典编程练习题
C++经典编程练习题_IT认证_资格考试/认证_教育专区。C++经典练习,适合入门。。。C++经典编程例题(1) 1、(已验证!)计算铁路运费。已知从甲地到乙地,每张票托运行...
C++练习题(附答案)
C++练习题(附答案)_电脑基础知识_IT/计算机_专业资料。都是我们班的复习题5.9 (11)下列关于 C++函数的叙述中,正确的是 A)每个函数至少要具有一个参数 B)每个...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图