内容发布更新时间 : 2024/5/5 19:12:35星期一 下面是文章的全部内容请认真阅读。
冲刺NOIP 2010模拟试题与解析（二）
试题
题目名称 提交程序名 输入文件名 输出文件名 空间限制 时间限制 各题测试点数 各测试点分值 符文之语 最接近神的人 古代人的难题 宝物筛选 chars chars.in chars.out 50MB 1s 10 10 sophist sophist.in puzzle puzzle.in treasure treasure.in treasure.out 50MB 1s 10 10 sophist. out puzzle.out 50MB 1s 10 10 50MB 1s 10 10
故事背景：
传说中珠穆朗玛峰下有座古代人修建的神庙，神庙的地下室里有古代王室的遗产，但数千年来从未有人到达过?? 探险者小FF一直梦想成为世界上最富有的人和最杰出的探险家并被永载史册。在证明了这个洞确实存在后，小FF做好了充分的准备，来到了神庙。
试题一：符文之语（chars.pas/c/cpp） 【题目描述】
当小FF来到神庙时，神庙已经破败不堪了。但神庙的中央有一个光亮如新的石台。小FF走进石台，发现石台上有一个数串，而数串的上方刻着一串古老的符文之语。精通古符文之语的小FF不费吹灰之力就读懂了文章的意思，其大意是：对于石台上的一串数字，你可以在适当的位置加入乘号（设加了k个，当然也可不加，即分成k+1个部分），设这k+1个部分的乘积（如果k=0，则乘积即为原数串的值）对m的余数（即mod m）为x;现求x能达到的最小值及该情况下k的最小值，以及x能达到的最大值及该情况下的k的最小值(可以存在x的最小值与最大值相同的情况)。小FF还知道，如果他找到了正确的答案，那么就可以通往神庙的下层了。但这个问题似乎不太好解决，小FF就找到了你，并答应找到财宝以后和你二八分（当然你拿二??）。
【输入格式】
第一行为数串，且数串中不存在0； 第二行为m。
【输出格式】
四个数，分别为x的最小值和该情况下的k，以及x的最大值和该情况下的k，相邻两个数之间用以个空格隔开。
【输入样例】
4421 22
【输出样例】
0 1 21 0
【数据范围】
对于30%的数据：2≤字符串的长度L≤50。
对于100%的数据：2≤字符串的长度L≤1000；2≤m≤50。
试题二：最接近神的人（sophist/pas/c/cpp）
【题目描述】
破解了符文之语，小FF开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小FF猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门?? 仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。 而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。
小FF发现门上同样有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小FF不会??只好又找到了你，并答应事成之后与你三七分??
【输入格式】
第一行为一个整数n，表示序列长度
第二行为n个整数，表示序列中每个元素。
【输出格式】
一个整数ans，即最少操作次数。
【输入样例】
4
2 8 0 3
【输出样例】
3
样例说明：开始序列为2 8 0 3，目标序列为0 2 3 8，可进行三次操作的目标序列： 1. Swap(8,0)：2 0 8 3 2. Swap (2,0)：0 2 8 3
3. Swap (8,3)：0 2 3 8
【数据范围】
对于30%的数据1≤n≤104。 对于100%的数据 1≤n≤5*105。
试题三：古代人的难题（puzzle.pas/c/cpp） 【题目描述】
门打开了，里面果然是个很大的厅堂。但可惜厅堂内除了中央的一张羊皮纸和一支精致的石笔，周围几具骷髅外什么也没有。难得这就是王室是遗产？小FF不信，他仔细阅读了羊皮纸上的内容后发现，里面书写的古代人一直没能解出的难题，解除这道题目的人只要将答案用石笔写到这张羊皮纸上就能到达王室的宝藏室了。而当小FF拿起石笔后，刚刚打开的巨石门突然关上了。这是小FF意识到原来那几具骷髅是在他之前到这里的冒险者，恐怕是因为没能破解这道题而困死在这里了。小FF越想越害怕，急忙联系到了你，为了能保命，他甚至愿意和你五五分??看来你不得不再次帮他了。羊皮纸上的问题如下：已知x，y为整数，且满足以下两个条件：
1． x，y∈[1?k]，且x，y，k∈Z 2． (x^2-xy-y^2)^2=1
给你一个整数k，求一组满足上述条件的x，y并且使得x^2+y^2的值最大。
当小FF得到答案后，用石笔将答案书写在羊皮纸上，那么就能到达王室的遗产所在地了。
【输入格式】
一个整数k
【输出格式】
输出文件仅一行，两个整数；两个整数分别表示x和y。x，y之间用一个空格隔开。
【输入样例】
1995
【输出样例】
1597 987
【数据范围】
对于30%的数据：2≤k≤104 对于100%的数据：2≤k≤1018
试题四：宝物筛选(Treasure.pas/c/cpp) 【题目描述】
终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝