信息学奥赛绍兴县柯桥中学60周年校庆赛试题.pdf

绍兴县柯桥中学绍兴县柯桥中学 60606060 周年校庆试题周年校庆试题 第一题 第一题 气场气场 AuraAuraAuraAura 背景背景 BackgroundBackgroundBackgroundBackground 此题是柯桥中学 60 周年校庆欢乐赛第一题 描述描述 DescriptionDescriptionDescriptionDescription zj 终于等啊等 终于等到了校庆表演 在表演中 zj 大显身手 使台下女生尖叫连连 下台后 zj 从女生的眼中看到了无限的期待 他不禁对此做了一份研究 他发现 台下的学 生坐成一个 n m 的方阵 而从台上下来的自己的拥有一个 n l 的气场 气场覆盖到女生后 会对 zj 有一个倾心值 但他又发现一个非常奇葩的性质 当且仅当某女生的倾心值为素数 时 这个女生会迷恋 zj 由于刚刚单身的 zj 想让更多的 MM 迷恋自己 以此来打击前女友 所以 他请你帮忙找出最好的位置 使迷恋自己的 MM 最多 输入格式输入格式 InputInputInputInput FormatFormatFormatFormat 输入文件第一行有三个正整数 n m l l m 100 n 100 含义如题中所述 第 2 行到第 N 1 行 每行 M 个数 保证每个数小于 maxlongint 输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat 仅有一行 包含一个整数 表示 zj 坐在从左往右数第几个时 迷恋自己的 MM 最多 假 设有多个位置符合条件 输出最小的一个 因为 zj 是演出人员 所以只会坐在第一排 样例输入样例输入 SampleSampleSampleSample InputInputInputInput 2 3 1 2 5 8 1 3 4 样例输出样例输出 SampleSampleSampleSample OutputOutputOutputOutput 2 时间限制时间限制 TimeTimeTimeTime LimitationLimitationLimitationLimitation 1s 注释注释 HintHintHintHint 20 的数据 n 1 100 的数据 l L m 100 n 100 第二题 幸运数第二题 幸运数 luckyluckyluckylucky 背景背景 BackgroundBackgroundBackgroundBackground 目睹 Zj 神犇的气场覆盖若干 MM 并使之为其倾心后 奶牛 Hyc 感到了莫大的压力 因 为他自己是单身 趁着校庆愉快的气氛 奶牛 Hyc 决定向爱慕已久的 MM Zxl 表白 经 过 N 久的酝酿后 奶牛 Hyc 发现一个问题 表白里不可避免的出现了数字 比如 爱你 xx 年 可是 描述描述 DescriptionDescriptionDescriptionDescription Zxl 非常喜欢数字 8 和 3 因此 所有有 8 和 3 组成的数字 Zxl 都认为是幸运的 比如 8833 3 888 但 88733 就不是幸运数了 因为 Zxl 不喜欢 7 她只喜欢 8 和 3 Zxl 看到类似 88733 这样的非幸运数字就会很不开心 这次表白也就失败了 为了让表白尽可能成功 奶 牛 Hyc 决定把一些不幸运的数写成一些幸运数的和 当然为了不把事情搞的麻烦 拆分的 个数越少越好 个数相同时字典序越小越好 可是奶牛实力太差 只好请你帮忙 概括 给定一个表白中出现的数 N 将其分解为一些幸运数的和 要求所用数字最少 如果有多组解要求字典序最小 无解则输出 No solution 对于字典序的解释 对于数列 a 1 n b 1 n 我们寻找第一位子 i 使得 a i b i 如果 a i b i 则a字 典序小 否则 b i 字典序小 输入格式输入格式 InputInputInputInput FormatFormatFormatFormat 一行 一个整数 N 输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat 一行 N 的幸运分解 两个数之间用空格隔开 样例输入样例输入 SampleSampleSampleSample InputInputInputInput 11 样例输出样例输出 SampleSampleSampleSample OutputOutputOutputOutput 3 8 时间限制时间限制 TimeTimeTimeTime LimitationLimitationLimitationLimitation 1s 注释注释 HintHintHintHint 对于 20 的数据 n 100 对于 50 的数据 n 100000 对于 100 的数据 n 1000000000 第三题 逆序对第三题 逆序对 pairpairpairpair 背景背景 BackgroundBackgroundBackgroundBackground 柯桥中学 60 周年校庆欢乐赛第 3 题 描述描述 DescriptionDescriptionDescriptionDescription 问题概括 n 个元素的排序一共有 n 个 询问排列中逆序对个数为 m 个的排列有多少 个 输入格式输入格式 InputInputInputInput FormatFormatFormatFormat 输入文件仅一行有两个正整数 n m 输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat 仅有一行 即满足要求的排列的个数 样例输入样例输入 SampleSampleSampleSample InputInputInputInput 3 2 样例输出样例输出 SampleSampleSampleSample OutputOutputOutputOutput 2 时间限制时间限制 TimeTimeTimeTime LimitationLimitationLimitationLimitation 1s 注释注释 HintHintHintHint 对于 20 的数据 n 10 对于 40 的数据 n 20 对于 100 的数据 1 n 50m n 1 n 2 第四题 叠爱心第四题 叠爱心 lovelovelovelove 背景背景 BackgroundBackgroundBackgroundBackground 在柯中热烈的校庆闭幕式上 校长张老大首先做了简短而深刻的讲话 按照此进程 很 快就可以放学回家了 然而 不幸降临了 书记 92 同志上台开始了他那代表性的冗长而无 味的讲话 下面 我讲 3 句话 在 92 同志的 狂轰滥炸下 同学们纷纷感到昏昏欲睡 LZT 坐在台下 对这种浪费生命的行为感到无比 地愤慨 于是他环视全场 突然眼前一亮 心中萌发出一个对他的人生具有重大意义的念 头 描述描述 DescriptionDescriptionDescriptionDescription 台下的童鞋们坐成一个 m 行 n 列的方阵 由于平时太过不遵守纪律 LZT 非常悲剧地 被学部的副校长大人安排在了方阵的左上角 1 1 而他所倾心的乖女孩 FYT 童鞋 则被安 排在方阵的右下角 m n LZT 终于体味到了 溯洄从之 道阻且长 的感觉 于是 他决 定利用这一段差点被 92 同志荒废的时间来叠爱心向 FYT 童鞋表达爱慕之情 由于 LZT 和 FYT 他们两个之间人海茫茫 LZT 叠的爱心不得不通过方阵中的童鞋们传 递给女孩 FYT 而每个童鞋只能给相邻的同学传递爱心 LZT 很快就叠好了无数的爱心 但他突然想到了一个非常严峻的问题 虽然两个童鞋间爱心的传递是双向的 但由于两个童 鞋间的友好程度不同 他们之间能够传递的爱心数量是有限的 这样 LZT 所叠的爱心就 不能源源不断地送给 FYT 了 LZT 由于这个无法避免的事实瞬时从亢奋状态跌落 而此时 FYT 已经收到了传递出的第一颗爱心 于是她想知道 她最终能够收到多少颗 LZT 叠的爱 心 由于 LZT 实在太弱了 而且还沉浸在不能用无限的爱心来表达深沉的爱意的巨大悲伤 中不可自拔 所以他暂时无法计算出 FYT 想知道的问题答案 他举目四望 却发现最强的 zyc 神犇坐在方阵的右上角而无法联系到 由于这个问题关系到 LZT 后半生的幸福 他只能 求助于你 希望尽快得到 FYT 想要的这个答案 这样就可以得到 FYT 的倾心 事成之后 作为酬谢 LZT 会付给你 10 100000 mod 10 的 RMB 输入格式输入格式 InputInputInputInput FormatFormatFormatFormat 第一行两个整数 m n 接下来 m 行 每行有 n 1 个非负整数 第 i 1 行的第 j 个数表示坐在 i j 与 i j 1 位置的 同学之间能传递爱心的最大数量 再接下来 m 1 行 每行有 n 个非负整数 第 i m 1 行的第 j 个数表示坐在 i j 与 i 1 j 位置的同学之间能传递爱心的最大数量 输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat 仅有一行 表示 FYT 最多能收到的爱心数量 样例输入样例输入 SampleSampleSampleSample InputInputInputInput 2 2 2 4 3