ioi2012中国信息学国家集训队命题答辩试题册.pdf

IOI 2012 中国信息学国家集训队 命题答辩试题册 教练: 胡伟栋、唐文斌 中国计算机学会 2012 年5 月 答辩顺序 答辩顺序 姓名 所在学校 试题名称 1 李超 浙江省杭州学军中学 拆弹计划 2 徐捷 浙江省绍兴市第一中学 字符串游戏 3 梁盾 湖南省长沙市长郡中学 字符串加密 4 艾雨青 湖南省长沙市雅礼中学 近似平均数 5 刘洪轩 天津市南开中学 电子对撞机 6 顾昱洲 江苏省南京师范大学附属中学 JZPLCM 7 沈添笑 湖南省长沙市雅礼中学 生日蜡烛 8 卓亮 福建省福州第一中学 Flare 9 王钦石 黑龙江省哈尔滨市第三中学校 能量棒 10 陈立杰 浙江省杭州外国语学校 Color 11 伍一鸣 湖南省长沙市雅礼中学 Binomial 12 钟沛林 湖南省长沙市雅礼中学 可见区域 IOI2012 国家集训队冬令营命题答辩试题册 拆弹计划 拆弹计划 命题人: 李超 【资源限制】 时间限制：3 秒 内存限制：512MB 【关键字】 序的应用，分治，线段树 【问题描述】 A 国和B 国是两个超级大国，长期处于冷战状态。 A 国在B 国中设有N 个情报站，编号为 1,2,3,„„,N ，第i 个情报站的坐 标是(X , Y ) 。 i i 但是，A 国的工作人员发现，每个情报站里都被埋上了炸弹！ 这些炸弹非常的特殊，必须同时拆除且仅拆除其中的三个炸弹，才能使所有 炸弹都不爆炸。 拆除炸弹的总代价由两部分组成，第一部分为情报站之间联络的代价，第二 部分为拆除炸弹所需要的代价。其中，联络的代价为要拆除炸弹的三个情报站的 坐标的曼哈顿距离和，在第i 个情报站拆除炸弹的代价为Z 。 i 现在 A 国的指挥部门找到了你，他想要知道，使所有炸弹都不爆炸的最小 花费代价是多少。 【输入格式】 输入的第一行包含一个整数N 。接下来N 行，第i+1 行有三个整数X , Y , Z ， i i i 表示第i 个情报站的坐标与拆除炸弹的代价。 【输出格式】