2012AHUT ACMICPC选拔赛题目评.ppt

Welcome 欢迎加入安徽工业大学ACM ICPC队伍 2012AHUT ACM ICPC选拔赛题目讲评 主讲人 王旭晨 2012 12 13 一 等比数列之和 简单题 Description问题描述已知等比数列第1 2项 求其前n项之和InputFormat输入格式输入数据有多组 每组占一行 由3个实数组成 分别表示a1 a2 nOutputFormat输出格式对于每组输入数据 输出一行Hint注释所有数据均为整形 基本思路一 定义一个sum表示和 利用循环依次求出前n项 累加放入sum中 C语言实现 includeintmain intsum 0 i ai a1 a2 n q while scanf d d d 基本思路二 通过a1和a2求出公比q 讨论q 利用等比数列求和公式 得到答案 include includeintmain inta1 a2 n intq s a i while scanf d d d C语言实现 两种不同思路给我们的启示 第一种方法简单易实现 算出每一项的值再累加 最后得到总和结果 就算你没学过等比数列求和公式都能写出这个思路 该方法使用了一个循环 所以时间复杂度为O n 第二种方法使用了数学公式 使得运算过程大大简化 不需要使用循环 直接一个表达式就能得到正确结果 时间复杂度为O 1 显然 运用公式对算法做出了很大的改进 这也告诉了我们 必须要学好数学 因为有很多这样的情况公式不是我们学过的 而是需要我们自己来推导的 你如果没法推出使问题算法简单化的公式 可能你写出的程序就要比别人多花很多时间才能得到答案或因为太占用时间而根本得不到答案 Description问题描述蜗牛在井底 井深n厘米 蜗牛每分钟上爬u厘米 接下来一分钟下掉d厘米 重复这一过程直到爬出井 求爬出井需多长时间 InputFormat输入格式下面存在多组测试数据 每一行包括3个正数分别代表n u和d 你可以认为dx 我们认为这最后一段仍然是花了一分钟 蜗牛肯定会爬出井 也就是u d 所有数据均为整数 二 顽强的蜗牛 简单题 最易理解的思路 用代码模拟整个蜗牛爬行的过程 includeintmain ints d u n t while scanf d d d 更棒的思路 推算出公式 这道题目一样可以推算出公式 你能想出来吗 if d 0 if n u 0 t n u 1 elset n u else if n u u d 0 t n u u d 2 1 elset n u u d 1 2 1 printf d n t 重点思路 先不考虑最后一次上升的阶段 Description问题描述输入3个 x y 型直角坐标 求距原点最短的点的距原点距离InputFormat输入格式输入数据有多组 每组占一行 由4个实数组成 分别表示X1 Y1 X2 Y2 X3 Y3数据之间用空格隔开输入X1 Y1 X2 Y2 X3 Y3 输入数据全部为double型 OutputFormat输出格式对于每组输入数据 输出一行 最短距离 结果保留两位小数 三 买水果 超级简单题 lf include includeintmain doublex1 y1 x2 y2 x3 y3 doubled1 d2 d3 doublemin while scanf lf lf lf lf lf lf C语言实现代码 四 WarCraft 难题 Description问题描述N元钱 购买150 200 350元三件商品 最少能剩余多少钱InputFormat输入格式第一行整数T 1 T 100 代表测试数据的数量 然后是T行测试数据 每个测试数据只包含一个正整数N 1 N 10000 代表钱数 OutputFormat输出格式每组数据一行 能剩余的最少钱数 完全背包问题 动态规划 其实没这么复杂 考虑到350正等于150 200 所以一切可以买350的钱都能买150 200代替 所以我们可以直接无视350的那件物品 先把所有钱用于买150的物品 然后只要还剩50块钱以上 就用一个200的代替150 要点1 要点2 C语言实现代码 includeintmain intt n m k scanf d 五 LookEasy 中等题 Description问题描述F 0 4 F 1 7 F 2 9 F n F n 1 F n 2 F n 3 n 1000 InputFormat输入格式输入数据有多行 每行有一个数 为nOutputFormat输出格式对于每组输入 输出一个k k为F n 5的值 这样的思路错在哪里 intf 1002 i f 0 4 f 1 7 f 2 9 for i 3 i 1000 i f i f i 1 f i 2 f i 3 while scanf d 我们知道int的范围不过2 16 1 long的范围也不过2 32 1 是个10位数 对于这样一个数列 其增长速度不可小觑 肯定会超过最大范围 怎么处理呢 得证 所以 f n 5 f n 1 5 f n 2 5 f n 3 5 5这样 是不是确保了不会超过int的界限哇 很显然吧 但我们还是来看一下过程 includeintmain intf 1005 i n f 0 4 f 1 2 f 2 4 for i 3 i 1000 i f i f i 1 f i 2 f i 3 f i f i 5 while scanf d C语言实现代码 六 飞行棋 较难题 Description问题描述起点为0 终点为n 每次能走的步数小于m 但必须至少移动一步 两人都采取最优策略 小明先走 如果小明赢 输出first 如果小明输了 输出second InputFormat输入格式第一行样例个数N 然后是N行数据 每行包含两个整数n m OutputFormat输出格式输出数据N行 每行为first 小明赢 或second 小明输 博弈论 请找必胜 输 点 n 终点 起点 0 n 1 n m n m 1 必胜点 必输点 必输点 对于小明来说 n 2m 1 必胜点 n 2 m 1 必输点 n m 1 1 长度m 1 长度m 1 对于小明来说 在n m到n 1的地方时 他都可以一次走到终点取得胜利 但是如果他处于了n m 1 的状态 他就不得不走至少一步 这时就到了对手的必胜点区 所以n m 1 是小明的必输点 而在往前 如果小明处在n 2m 1到n m 2 他都可以一次走到n m 1 处 使得对手处于必输点 从而小明可以拿到胜利 依次向前推 n k m 1 就是小明的必输点 即n m 1 0时小明输 否则小明胜 includeintmain intt n m i scanf d C语言实现代码 Description问题描述有一电梯共M层 刚开始时你在第一级 若每次只能上一层或三层 要上第M层 共有多少种方法 InputFormat输入格式第一行整数N 表示测试样例的个数 然后是N行数据 每行包含一个整数M 1 M 41 表示电梯的层数 OutputFormat输出格式每行对应一个测试样例不同走法的数量 七 3or1 中等题 递推思想的好处 到第n级前我们可能在哪里呢 如果是上1层到n的话 我们在n 1 如果是上3层到n的