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++模拟试题_1-2
C++模拟试题_1-2_IT认证_资格考试/认证_教育专区。计算机二级考试必看题,未完待续CPP 程序设计 模拟考试 1--第 2 套试卷 1.c++系统预定了 4 个用于标准数据...
C++习题答案-2
C++习题答案-2 隐藏>> 第二章 [2_1]简述 C++的主要特点 C++语言的主要特点表现在两个方面,一是全面兼容 C,并对 C 的功能作了不少 扩充,二是增加了面向对...
c++练习题(带答案)
c++练习题(带答案)_IT认证_资格考试/认证_教育专区。一、选择题 1. C++语言属于( C )。 A) 自然语言 B) 机器语言 C)面向对象语言 D) 汇编语言 2. 下面...
c++模拟试题
模拟试题一一、单项选择题(本大题共 10 小题,每小题 2 分,共 20 分) 1...在 C++中 Fun,使用 类型的参数, 2.在 C++中,编写一个内联函数 Fun,使用 ...
c++指针类练习题及答案
c++指针类练习题及答案_工学_高等教育_教育专区。1、利用指针,编写用于交换两个整型变量值的函数。程序运行结果如下:输入:5 6 输出:6 5 #include <iostream> ...
C++习题与解析-引用
(cout); } 本程序的执行结果如下: 输出数据 书名:C 语言程序设计 作者:谭浩强 月销售量:800 输出数据 书名:C++语言程序设计 作者:李春葆 月销售量:300 题 6...
50道C++编程练习题及解答
50 道 C/C++编程练习题 1、输入 3 个数,求最大值 int main() { int a,b,c,m; cin>>a>>b>>c; m=a; if(b>m) m=b; if(c>m) m=c; ...
C++上机练习题
C++上机练习题_IT/计算机_专业资料。C++上机练习题1.有一个圆环,其中小院半径为 2.5,大圆半径为 7。编程定义一个 circle 类,含有私有变 有一个圆环, 有一个圆...
C++习题及其解答(第四版)(周霭如)全
C++习题及其解答(第四版)(周霭如)全_理学_高等教育_教育专区。除了这些,我还有C++程序设计基础(第四版)上的完整ppt课件习题1 及其解答 1.1 选择题 1.一个最...
《面向对象程序设计C++》期末试卷及标准答案集总
《面向对象程序设计 C++》期末考试试卷(A)班级: 姓名: 学号:第 18 页 分数: 题号 得分 一 二 三 四 总分 试卷说明: 本套试题共四个大题, 全部题目都答...
更多相关标签:

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

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