《信息学奥赛绍兴县60周年校庆赛试题》由会员分享，可在线阅读，更多相关《信息学奥赛绍兴县60周年校庆赛试题（3页珍藏版）》请在金锄头文库上搜索。
1、绍兴县柯桥中学绍兴县柯桥中学 60606060 周年校庆试题周年校庆试题第一题：第一题：气场气场 AuraAuraAuraAura 背景背景 BackgroundBackgroundBackgroundBackground 此题是柯桥中学 60 周年校庆欢乐赛第一题。描述描述 DescriptionDescriptionDescriptionDescription zj 终于等啊等，终于等到了校庆表演。在表演中，zj 大显身手，使台下女生尖叫连连。 下台后，zj 从女生的眼中看到了无限的期待。他不禁对此做了一份研究。他发现，台下的学生坐成一个 n*m 的方阵，而从台上下来的自己的拥有一个 n*
2、l 的气场。气场覆盖到女生后 会对 zj 有一个倾心值。但他又发现一个非常奇葩的性质：当且仅当某女生的倾心值为素数 时，这个女生会迷恋 zj。由于刚刚单身的 zj 想让更多的 MM 迷恋自己，以此来打击前女友。所以，他请你帮忙找出最好的位置，使迷恋自己的 MM 最多。 输入格式输入格式 InputInputInputInput FormatFormatFormatFormat 输入文件第一行有三个正整数 n,m,l(l b1.n 我们寻找第一位子 i 使得 aibi ， 如果 ai bi 则a字 典序小， 否则 bi 字典序小输入格式输入格式 InputInputInputInput Form
3、atFormatFormatFormat 一行，一个整数 N 输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat一行，N 的幸运分解，两个数之间用空格隔开。 样例输入样例输入 SampleSampleSampleSample InputInputInputInput 11样例输出样例输出 SampleSampleSampleSample OutputOutputOutputOutput 3 8 时间限制时间限制 TimeTimeTimeTime LimitationLimitationLimitationLimitation1s
4、 注释注释 HintHintHintHint 对于 20%的数据，n=100对于 50%的数据，n=100000 对于 100%的数据，n=1000000000第三题：逆序对第三题：逆序对 pairpairpairpair 背景背景 BackgroundBackgroundBackgroundBackground 柯桥中学 60 周年校庆欢乐赛第 3 题描述描述 DescriptionDescriptionDescriptionDescription 问题概括：n 个元素的排序一共有 n!个，询问排列中逆序对个数为 m 个的排列有多少 个。输入格式输入格式 InputInputInputInp
5、ut FormatFormatFormatFormat 输入文件仅一行有两个正整数 n，m 输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat仅有一行,即满足要求的排列的个数 样例输入样例输入 SampleSampleSampleSample InputInputInputInput 3 2样例输出样例输出 SampleSampleSampleSample OutputOutputOutputOutput 2 时间限制时间限制 TimeTimeTimeTime LimitationLimitationLimitationLimi
6、tation1s 注释注释 HintHintHintHint 对于 20%的数据，n=10对于 40%的数据，n=20 对于 100%的数据，1=n=50m=(n-1)*n/2第四题：叠爱心第四题：叠爱心 lovelovelovelove 背景背景 BackgroundBackgroundBackgroundBackground在柯中热烈的校庆闭幕式上，校长张老大首先做了简短而深刻的讲话，按照此进程， 很 快就可以放学回家了。然而，不幸降临了。书记 92 同志上台开始了他那代表性的冗长而无味的讲话： “下面，我讲 3 句话，#%#￥#&%#&!#￥!#￥%” 。在 92 同志的 狂轰滥炸下，同
7、学们纷纷感到昏昏欲睡。LZT 坐在台下，对这种浪费生命的行为感到无比 地愤慨。于是他环视全场，突然眼前一亮，心中萌发出一个对他的人生具有重大意义的念头 描述描述 DescriptionDescriptionDescriptionDescription 台下的童鞋们坐成一个 m 行 n 列的方阵，由于平时太过不遵守纪律，LZT 非常悲剧地被学部的副校长大人安排在了方阵的左上角(1,1)，而他所倾心的乖女孩 FYT 童鞋，则被安 排在方阵的右下角(m,n)。LZT 终于体味到了“溯洄从之，道阻且长”的感觉。于是，他决 定利用这一段差点被 92 同志荒废的时间来叠爱心向 FYT 童鞋表达爱慕之情。由
8、于 LZT 和 FYT 他们两个之间人海茫茫， LZT 叠的爱心不得不通过方阵中的童鞋们传 递给女孩 FYT，而每个童鞋只能给相邻的同学传递爱心。LZT 很快就叠好了无数的爱心， 但他突然想到了一个非常严峻的问题： 虽然两个童鞋间爱心的传递是双向的， 但由于两个童鞋间的友好程度不同，他们之间能够传递的爱心数量是有限的。这样，LZT 所叠的爱心就 不能源源不断地送给 FYT 了。LZT 由于这个无法避免的事实瞬时从亢奋状态跌落。而此时 FYT 已经收到了传递出的第一颗爱心。于是她想知道，她最终能够收到多少颗 LZT 叠的爱心。 由于 LZT 实在太弱了，而且还沉浸在不能用无限的爱心来表达深沉的爱
9、意的巨大悲伤 中不可自拔，所以他暂时无法计算出 FYT 想知道的问题答案。他举目四望，却发现最强的zyc 神犇坐在方阵的右上角而无法联系到。 由于这个问题关系到 LZT 后半生的幸福， 他只能 求助于你，希望尽快得到 FYT 想要的这个答案，这样就可以得到 FYT 的倾心。事成之后， 作为酬谢，LZT 会付给你 10100000 mod 10 的 RMB。输入格式输入格式 InputInputInputInput FormatFormatFormatFormat 第一行两个整数 m，n。 接下来 m 行，每行有 n-1 个非负整数，第 i+1 行的第 j 个数表示坐在(i,j)与(i,j+1)
10、位置的同学之间能传递爱心的最大数量。 再接下来 m-1 行，每行有 n 个非负整数，第 i+m+1 行的第 j 个数表示坐在(i,j)与(i+1,j) 位置的同学之间能传递爱心的最大数量。输输出出格式格式 OutOutOutOutputputputput FormatFormatFormatFormat 仅有一行，表示 FYT 最多能收到的爱心数量。 样例输入样例输入 SampleSampleSampleSample InputInputInputInput2 2 2 43 1 样例输出样例输出 SampleSampleSampleSample OutputOutputOutputOutput 4时间限制时间限制 TimeTimeTimeTime LimitationLimitationLimitationLimitation 2s 注释注释 HintHintHintHint对于 20%的数据，n,m=10 对于 40%的数据，n,m=200 对于 100%的数据，n,m=1000
