NOIP模拟试题2.pdf

1 NOIPNOIPNOIPNOIP 模拟试题模拟试题模拟试题模拟试题 题目 题目名称上学路线遗址 拼写检查 最轻的天平郁闷的记者 文件名routeruin Spell mobilerank 测试点数510 10 1410 分值100100 100 140100 时限lS1S 1s 1S1S 1 1 上学路线 上学路线 route route paspas c c cpp cpp 题目描述 你所在城市的街道好像一个棋盘 有 a 条南北方向的街道和 b 条东西方向的 街道 南北方向的 a 条街道从西到东依次编号为 l 到 a 而东西方向的 b 条街道 从南到北依次编号为 l 到 b 南北方向的街道 i 和东西方向的街道 j 的交点记为 i j 你住在 1 1 处 而学校在 a b 处 你骑自行车去上学 自行车只能沿着 街道走 而且为了缩短时间只允许沿着向东和北的方向行驶 现在有 N 个交叉路口在施工 X1 Yl X2 Y2 Xn Yn 这些路口是 不能通车的 问你上学一共有多少走法 输入格式 第一行包含两个整数 a 和 b 并且满足 1 a b 16 第二行包含一个整数 N 表示有 N 个路口在维修 1 N 40 接下来 N 行 每行两个整数 X i Y i 描述路口的位置 输出格式 输出一个整数表示从 1 1 到 a b 的行车路线总数 样例输入输出 Route inRoute out 5 4 3 22 23 42 5 样例数据解释 2 JOI High School 5 4 1 1 Taro s Home 2 2 遗址 遗址 ruin ruin paspas c c cpp cpp 题目描述 很久很久以前有一座寺庙 从上往下看寺庙的形状正好是一个正方形 由 4 个角上竖立的圆柱搭建而成 现在圆柱都倒塌了 只在地上留下圆形的痕迹 可 是现在地上有很多这样的痕迹 专家说一定是最大的那个 写一个程序 给出圆柱的坐标 找出由 4 个圆柱构成的最大的正方形 因为 这就是寺庙的位置 要求计算出最大的面积 注意正方形的边不一定平行于坐标 轴 例如右上图有 l0 根柱子 其中 4 2 5 2 5 3 4 3 可以形成 一个正方形 1 1 4 O 5 3 2 4 也可以 后者是其中最大的 面 积为 l0 输入格式 第一行包含一个 N 1 N 3 0 0 0 表示柱子的数量 接下来 N 行 每行有两个空格隔开的整数表示柱子的坐标 坐标值在 0 到 5000 之间 柱子的位置互不相同 输出格式 如果存在正方形 输出最大的面积 否则输出 0 3 样例输入输出 Ruin inRuin out 10 9 4 4 3 1 1 4 2 2 4 5 8 4 0 5 3 0 5 5 2 10 数据范围 30 满足 1 N 100 60 满足 1 N 500 4 3 3 拼写检查 拼写检查 spellspell 问题描述 路人乙的上司非常的 NC NC 的上司分配了路人乙一个非常 NC 的任务 那就是写一 个拼写检查程序 这样上司就可以避免一些非常 NC 的拼写错误 路人乙的上司指出了以下 几种情况算是拼写错误 1 句子的第一个字母用了小写 2 不是单词的第一个字母用了大写 一个单词是字母的序列 不包含其他任何字符 或行尾结束符 用句号 问号或叹号表示句子的结束 输入 输入为文字包含大小写字母 A Z a z 标点符号 空格 文字长度不超过 10000 输出 输出文字中错误的数量 样例输入 This sentence iz correkt It Has No mista Kes et oll But there are two BIG mistakes in this one and here is one more 样例输出 3 4 4 最轻的天平 最轻的天平 mobile mobile paspas c c cpp cpp 题目描述 天平的两边有时不一定只能挂物品 还可以继续挂着另一个天平 现在给你 一些天平的情况和它们之间的连接关系 要求使得所有天平都能平衡所需物品的 总重量最轻 一个天平平衡当且仅当 左端点的重量 左端点到支点的距离 右端 点的重量 右端点到支点的距离 注意题目中的输入保证这些天平构成一个整 体 输入格式 第一行包含一个 N N 100 表示天平的数量 天平编号为 l 到 N 接下来 包含 N 行描述天平的情况 每行 4 个整数 P Q R B P 和 Q 表示横杆上支点到 左边的长度与到右边的距离的比例为 P Q R 表示左边悬挂的情况 如果 R 0 说明悬挂的是物品 否则表示左边悬挂的是天平 R B 表示右边的悬挂情况 如 果 B O 表示右边悬挂的是物品 否则右边悬挂着天平 B 对于所有的输入 保证 W L 2 31 其中 w 为最轻的天平重量 而 L 为输入 中描述左右比例时出现的最大值 输出格式 输出一个整数表示使得所有天平都平衡所需最轻的物品总重量 5 5 5 郁闷的记者 郁闷的记者 rank rank papa s s c c cpp cpp 题目描述 你是一个体育报社的记者 你接受到一个艰难的任务 有 N 支足球队参加足 球比赛 现在给你一些比赛的结果 需要你给出各支球队的排名 从 1 到 N 以下是给你的一些信息 1 没有平局 2 不同的球队排名不能相同 3 对于所有满足 l a b n 第 a 名的球队一定可以打败第 b 名的球队 给你部分比赛结果 要求给出排名 并且判断是否存在另一种排名方法满足 给你的比赛结果 6 输入格式 第一行输入 N 1 N 5000 表示球队的数量 编号为 l 到 N 第二行输入 M 1 M 100 000 表示给出的比赛场数 接下来 M 行 每行两个整数 X i Y i 表示 X i 能打败 Y i 输出格式 输出包含 N 1 行 前 N 行描述球队的排名 第 i 个数表示第 i 名的球队 第 N 1 行包含一个整数 如果为 0 表示不存在其他的排名方法 如果为 1 表