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++复习题及答案
2. 程序中都必须包含有这样一个函数, 在每个 C++程序中都必须包含有这样一个...c++练习题(带答案) 12页 1下载券 c++复习题 28页 免费 C++复习题及答案(1...
C++试题库有答案的
C++试题库有答案的_计算机软件及应用_IT/计算机_专业资料。C++试题库 一、 选择题 1、求“abc\\12\n”字符串的长度( C ) (A) 5 (A) 6 (A) 6 (B)...
C++练习题
C++练习题一、选择题 1、下面选项中不属于面向对象程序设计特征的是( ) A、继承性 B、多态性 C、相似性 D、封装性 2、C++对 C 语言作了很多改进,即从面向...
C++测试题
C++测试题_IT认证_资格考试/认证_教育专区。C++ C++测试题一、 填空题(30 空 * 1 分) 1. 在 C++中,函数的参数有两种传递方式,它们是值传递和___。 2. ...
C++习题
C++习题_计算机软件及应用_IT/计算机_专业资料。C++程序设计习题 7,求 2 个或 3 个正整数的最大数,用带有参数的函数实现。 #include <iostream> using namespac...
c++_经典习题(附答案)
c++_经典习题(附答案)_IT/计算机_专业资料。c++_1. 关于 C++语言,下列说法不正确的是 . 语言, 语言 A. C++具有简洁、高效和接近汇编语言的特点 具有简洁、 ...
c++练习题(带答案)
c++练习题(带答案)_IT/计算机_专业资料。一、选择题 1. C++语言属于( C A) 自然语言 A)继承性 A) void C) for )。 B) 机器语言 C)面向对象语言 D)...
C++试题及答案
C++试题及答案_IT认证_资格考试/认证_教育专区。c++ C++程序设计模拟试卷(一) 一、单项选择题(本大题共20小题,每小题1分,共20分)在每小题列出的四个备选项...
C++入门经典习题集
C++入门经典习题集第一章:基本概念***(1):c++程序至少包含一个 main()函数 (2):函数的可执行部分由包含在一对花括号中的语句组成 (3):一对花括号定义了一...
C++基础习题
下列数据类型不是 C++语言基本数据类型的是___。 基本控制结构程序设计习题 26 A.字符型 答案:D B.整型 C.实型 D.数组 54. 在 C++语言中,080 是___。...
更多相关标签:

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

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