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

绍兴县柯桥中学绍兴县柯桥中学 60606060 周年校庆试题周年校庆试题 题目题目气场气场 AuraAuraAuraAura幸运数幸运数 luckyluckyluckylucky逆序对逆序对 pairpairpairpair叠爱心叠爱心 lovelovelovelove 输入文件输入文件Aura inAura inAura inAura inLucky inLucky inLucky inLucky inpair inpair inpair inpair inlove inlove inlove inlove in 输出文件输出文件Aura outAura outAura outAura outLucky outLucky outLucky outLucky outpair outpair outpair outpair outlove outlove outlove outlove out 时间限制见题目时间限制见题目 空间限制均为空间限制均为 128MB128MB128MB128MB 第一题 第一题 气场气场 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 InputInpu