noip2011

第十六届noip普及组的答案 pascal语言 急求 今天回答的再加100分

我初赛78分哈，初赛算是挤进了......
一、

1-10 DAADADBDCB
11-20 DABBBAADCD

二、 1. {2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6}
2. 49种

三、1. 2_20_77_91("_"指一个空格，下同)
2. 99_101_111_
3. 120_112
4. (1) 1 (2)4

四、1. (1) tmp:=true
(2) p[j]
(3) p[r]:=i
(4)p[j]+p[k]
(5)1004

2. (1)num<=2
(2)go(LEFT_TO_RIHGT)
(3)pos[i]=LEFT
(4) time[i]+go(RIGHT_TO_LEFT)
(5)pos[i]:=LEFT
好不容易的......

求NOIP2011复赛普及组题目详解 PASCAL

第一题注意负数，注意有可能出现-0（虽然我也不确定有没有）；
第二题一个单词一个单词地读（用空格隔断），读一个比较一个；
第三题模拟，不断排序；（但我估计会超时）
第四题用分治，先寻找括号外的加号，没有的话就寻找括号外的乘号，把找到的那个地方的左右两边分别计算在合在一起。注意去括号，注意最后的递归边界。计算时住随时mod 10007（可以用数学的余数定律证明这样不会改变结果）。但着也不能过全，递归到十二万多层就崩溃了。不过至少可以过一半

noip2011 第二天第三题解题报告

二、统计单词个数

考你的基本功，和对程序的理解，尤其是细节上的优化。直接在文章中选出单词，与给定单词长度一致时才比较，函数传参数时也不要传字符串（会很慢的，具体慢多少没试）。

program stat;

var

s,p:ansistring;

i,j,first,num,len,c,k:longint;



function cmp(x:longint):boolean;

var

i:longint;

begin

for i:= 1 to c do

if s[i] p[x+i-1] then exit(false);

exit(true);

end;

begin

assign(input,'stat.in');reset(input);

assign(output,'stat.out');rewrite(output);



readln(s);readln(p);

s:=upcase(s);p:=upcase(p);

c:=length(s); len:=length(p);

i:=1; num:=0; first:=-1;

while (s[i]=' ')and (i<=len) do inc(i);

while (i<=len) do

begin

j:=i+1;

while (p[j]' ') and (j<=len) do

inc(j);

if (j-i = c) and cmp(i) then

begin

if first=-1 then first:=i;

inc(num);

end;

i:=j; while (p[i]=' ') and (i<=len) do inc(i);

end;

if first=-1 then

writeln(-1)

else writeln(num,' ',first-1);



close(input);close(output);

end.





三、瑞士轮

实践证明，如果单纯的排序r次，必然结果是超时。事实上只需一次真正意义上的排序以后，在以后的比赛中，按原顺序分成两组，获胜组和失败组，这两组依然是有序的，再把这两组归并成一组，就可以了。总时间复杂度O（N*R）。 为了方便归并，下面的数组采用了滚动数组。

program swiss_merger;





var

n,r,q,i,j,k,c,pwin,plose:longint;

s,w,t:array[1..200050] of longint;

id:array[0..1,1..200050] of longint;



procedure qsort(n,m:longint);

var

i,j,k,t:longint;



begin

i:=n;j:=m; k:= id[0,(n+m)div 2];

repeat

while (s[id[0,i]] > s[k]) or (s[id[0,i]]=s[k]) and (id[0,i]<k) do inc(i);

while (s[id[0,j]] k) do dec(j);

if i<=j then

begin

t:=id[0,i]; id[0,i]:=id[0,j];id[0,j]:=t;

inc(i); dec(j);

end;

until i>j;

if n<j then qsort(n,j);

if i<m then qsort(i,m);

end;



begin

assign(input,'swiss.in');reset(input);

assign(output,'swiss.out');rewrite(output);

readln(n,r,q);

for i:= 1 to n*2 do

begin

id[0,i]:=i;

read(s[i]);

end;

for i:= 1 to n*2 do

read(w[i]);

qsort(1,2*n);

c:=0;

for i:= 1 to r do

begin



for j:= 1 to n do

if w[id[c,j*2-1]]<w[id[c,j*2]] then

begin

inc(s[id[c,j*2]]);

k:=id[c,j*2-1]; id[c,j*2-1]:=id[c,j*2]; id[c,j*2]:=k;

end

else inc(s[id[c,j*2-1]]);

c:=1-c; pwin:=1; plose:=2;

for j:= 1 to n*2 do

if (pwin s[ id[1-c,plose] ]) or (s[id[1-c,pwin]] = s[ id[1-c,plose] ] ) and ( id[1-c,pwin]< id[1-c,plose] ) ) then

begin

id[c,j]:=id[1-c,pwin];

inc(pwin,2);

end

else

begin

id[c,j]:=id[1-c,plose];

inc(plose,2);

end;

end;

writeln(id[c,q]);

close(input);close(output);

end.

急求NOIP2009普及组试题

NOIP2009普及组复赛试题
1．多项式输出
(poly.pas/c/cpp)
【问题描述】
一元 n 次多项式可用如下的表达式表示：
1 0
1
1 f (x) a x a xn ... a x a
n
n
n = + ? + + +
? ， ≠ 0 n a
其中，
i
i a x 称为i 次项， i a 称为i 次项的系数。给出一个一元多项式各项的次数和系
数，请按照如下规定的格式要求输出该多项式：
1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为0 的项。
3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系
数为负，则多项式以“-”号开头。
4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项
系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，
其系数的绝对值为1，则无需输出1）。如果x 的指数大于1，则接下来紧跟的指数部分的形
式为“x^b”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；
如果x 的指数为0，则仅需输出系数即可。
5. 多项式中，多项式的开头、结尾不含多余的空格。
【输入】
输入文件名为 poly.in，共有2 行
第一行 1 个整数，n，表示一元多项式的次数。
第二行有 n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空
格隔开。
【输出】
输出文件 poly.out 共1 行，按题目所述格式输出多项式。
【输入输出样例 1】
poly.in poly.out
5
100 -1 1 -3 0 10
100x^5-x^4+x^3-3x^2+10
【输入输出样例2】
poly.in poly.out
3
-50 0 0 1
-50x^3+1
【数据范围】
1 ≤ n ≤ 100，多项式各次项系数的绝对值均不超过100。
全国信息学奥林匹克联赛（NOIP2009）复赛普及组
第 3 页共 6 页
2．分数线划定
(score.pas/c/cpp)
【问题描述】
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对
所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根
据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%
（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有
选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成
绩。
【输入】
输入文件名为 score.in。
第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其
中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%
向下取整后小于等于n。
第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k
（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各
不相同。
【输出】
输出文件 score.out。
第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为
进入面试的选手的实际人数。
从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手
的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的
顺序输出。
【输入输出样例】
score.in score.out
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88
88 5
1005 95
2390 95
1000 90
1001 88
3239 88
【样例说明】
m*150% = 3*150% = 4.5，向下取整后为4。保证4 个人进入面试的分数线为88，但因为88
有重分，所以所有成绩大于等于88 的选手都可以进入面试，故最终有5 个人进入面试。
全国信息学奥林匹克联赛（NOIP2009）复赛普及组
第 4 页共 6 页
3．细胞分裂
(cell.pas/c/cpp)
【问题描述】
Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实
验做准备工作：培养细胞样本。
Hanks 博士手里现在有N 种细胞，编号从1~N，一个第i 种细胞经过1 秒钟可以分裂为
Si 个同种细胞（Si 为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，
进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M 个试管，形成M 份样本，
用于实验。Hanks 博士的试管数M 很大，普通的计算机的基本数据类型无法存储这样大的
M 值，但万幸的是，M 总可以表示为m1 的m2 次方，即2
1
M = m m ，其中m1，m2 均为基本
数据类型可以存储的正整数。
注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4 个细胞，
Hanks 博士可以把它们分入2 个试管，每试管内2 个，然后开始实验。但如果培养皿中有5
个细胞，博士就无法将它们均分入2 个试管。此时，博士就只能等待一段时间，让细胞们继
续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。
为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚
好可以平均分入M 个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细
胞培养，可以使得实验的开始时间最早。
【输入】
输入文件名为 cell.in，共有三行。
第一行有一个正整数 N，代表细胞种数。
第二行有两个正整数 m1，m2，以一个空格隔开， 2
1
m m 即表示试管的总数M。
第三行有 N 个正整数，第i 个数Si 表示第i 种细胞经过1 秒钟可以分裂成同种细胞的个
数。
【输出】
输出文件 cell.out 共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的
最少时间（单位为秒）。
如果无论 Hanks 博士选择哪种细胞都不能满足要求，则输出整数-1。
【输入输出样例 1】
cell.in cell.out
1
2 1
3
-1
【输入输出样例1 说明】
经过 1 秒钟，细胞分裂成3 个，经过2 秒钟，细胞分裂成9 个，……，可以看出无论怎么分
裂，细胞的个数都是奇数，因此永远不能分入2 个试管。
全国信息学奥林匹克联赛（NOIP2009）复赛普及组
第 5 页共 6 页
【输入输出样例 2】
cell.in cell.out
2
24 1
30 12
2
【输入输出样例2 说明】
第 1 种细胞最早在3 秒后才能均分入24 个试管，而第2 种最早在2 秒后就可以均分（每
试管144/(241)=6 个）。故实验最早可以在2 秒后开始。
【数据范围】
对于 50%的数据，有2
1
m m ≤ 30000。
对于所有的数据，有1 ≤N≤ 10000，1 ≤m1 ≤ 30000，1 ≤m2 ≤ 10000，1 ≤ Si ≤ 2,000,000,000。
4．道路游戏
(game.pas/c/cpp)
【问题描述】
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有n 个机器人工厂，两个相邻机器人工厂之间由一小段
马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这n 个机器人工厂编号为
1~n，因为马路是环形的，所以第n 个机器人工厂和第1 个机器人工厂是由一段马路连接在
一起的。小新将连接机器人工厂的这n 段马路也编号为1~n，并规定第i 段马路连接第i 个
机器人工厂和第i+1 个机器人工厂（1 ≤ i ≤ n-1），第n 段马路连接第n 个机器人工厂和第1
个机器人工厂。
游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间
发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人
的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器
人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即
从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集
给小新，例如，小新在i（1 ≤ i ≤ n）号机器人工厂购买了一个机器人，这个机器人会从i 号
机器人工厂开始，顺时针在马路上行走，第一次行走会经过i 号马路，到达i+1 号机器人工
厂（如果i=n，机器人会到达第1 个机器人工厂），并将i 号马路上的所有金币收集给小新。
游戏中，环形马路上不能同时存在2 个或者2 个以上的机器人，并且每个机器人最多能
够在环形马路上行走p 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走
次数可以为1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小
新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次
数。
以下是游戏的一些补充说明：
1. 游戏从小新第一次购买机器人开始计时。
2. 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
3. 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买
完机器人并且设定机器人行走次数之后机器人才能行走。
4. 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器
人的花费不一定相同。
5. 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过
程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，
游戏结束后，收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人
需要的花费，请你告诉小新，经过m 个单位时间后，扣除购买机器人的花费，小新最多能
收集到多少金币。
【输入】
输入文件名为 game.in。
第一行 3 个正整数，n，m，p，意义如题目所述。
接下来的 n 行，每行有m 个正整数，每两个整数之间用一个空格隔开，其中第i 行描
述了i 号马路上每个单位时间内出现的金币数量（1 ≤ 金币数量≤ 100），即第i 行的第j
（1 ≤ j ≤m）个数表示第j 个单位时间内i 号马路上出现的金币数量。
最后一行，有 n 个整数，每两个整数之间用一个空格隔开，其中第i 个数表示在i 号机
器人工厂购买机器人需要花费的金币数量（1 ≤ 金币数量≤ 100）。
【输出】
输出文件 game.out 共一行，包含1 个整数，表示在m 个单位时间内，扣除购买机器人
花费的金币之后，小新最多能收集到多少金币。
【输入输出样例】
game.in game.out
2 3 2
1 2 3
2 3 4
1 2
5
【数据范围】
对于 40%的数据，2 ≤ n ≤ 40，1 ≤m≤ 40。
对于 90%的数据，2 ≤ n ≤ 200，1 ≤m≤ 200。
对于 100%的数据，2 ≤ n ≤ 1000，1 ≤m≤ 1000，1 ≤ p ≤m

快要参加noip2010了，希望有经验的大牛们介绍下经验，感激不尽

你好，我是今年NOI铜牌，NOIP2009一等奖。
以下是我个人的经验方法，希望能对你起到一定帮助：

前30分钟把题通读两遍，第一遍理解题意，第二遍归纳出初步的算法模型。
如果一时间看不出算法，切记不要深究，以免耽误过多时间，可以先在草稿纸上用数学语言简写下题目大意。

读完后如果对部分题目的模型很熟悉，可以先着手解决。
但一定要是十拿九稳的题目才能这么做，不然写到一半发现错了，删掉再改就得不偿失了。

接下来再仔细思考题目解法，一般思考时间不超过20分钟。
20分钟内还想不出AC算法，最好转而拿取大部分得分。
累计时间超过半小时，就只能骗分了，不然会影响到做其他题的时间。

在对待题目的策略上，前两题一般比较容易，要争取AC。在强省要争取AC第三题，或是拿到大部分得分。第四题以骗分策略为主。
如果实在做不来，交一个只输出0的程序都可以，切忌完全放弃。

在时间分配上我个人认为理想的划分是这样的：
0h0m~0h30m 读题
0h30m~1h15m 前两题
1h15m~2h15m 后两题
2h15m~3h00m 检查、对拍

这里要说的是，留下充足的时间做检查是十分必要的。
因为NOIP的重要性是不言而喻的，能拿得分一定要拿稳。
可以多写几组小数据测试程序，最好是具有特殊性的，比如验证DP的边界等等。
然后就是生成极限数据，测试程序是否会超时。
如果时间还比较充裕，可以再写一个朴素但保证正确的程序，和要提交的程序反复对拍。

总而言之，就是仔细读题、谨慎思考、反复检查、注意卡时和部分分的获取。
预祝你获得一等奖，并顺利进入理想的大学。

急求noip2011提高组初赛答案

单选就算了吧太多了~~~
答案：A

二、不定项选择题（共10题，每题1.5分，共15分。每题有一个或多个正确选项。多选或少选均不得分。）
（这部分较难得分，我错了很多题）
1. 如果根节点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（ ）。
A. 10
B. 11
C. 12
D. 2011
答案：CD
2. 在布尔逻辑中，逻辑“或”的性质有（ ）。（原题ABCD选项里的或是个类似V的表示或的符号，为了该文档流通方便我都改成了“V”）
A. 交换律：PVq=qVp
B. 结合律：P V（Q V R）=（P V Q）V R
C. 幂等律：P V P = P
D. 有界率：P V 1 = 1 （1表示逻辑真）
答案：ABCD
3. 一个正整数在十六进制下有100位，则它在二进制下可能有（ ）位。
A. 399
B. 400
C. 401
D. 404
答案：AB
4. 汇编语言（ ）。
A. 是一种与硬件无关的程序设计语言
B. 在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试
C. 可以直接访问寄存器、内存单元、I/O端口
D. 随着高级语言的诞生，如今已完全被淘汰，不再使用
答案：BC
5. 现有一段文言文，要通过二进制哈弗曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（ ）。
A. 1
B. 2
C. 3
D. 4
答案：BC
6. 生物特征识别是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（ ）。




A. 指静脉验证
B. 步态验证
C. ATM机密码验证
D. 声音验证
答案：ABD
7. 对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少3.
A. 7
B. 5
C. 3
D. 6
答案：CD
8. 计算机中的数值信息分为整数和实数（浮点数）。实属之所以能表示很大或者很小的数是由于使用了（ ）。
A. 阶码
B. 补码
C. 反码
D. 较长的位数
答案：A
9. 对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离d【B】初始时赋值为8，在算法的执行过程中还会出现的值有（ ）。
（原试题右图，为照顾手机党我字述边集（(a,b,c)代表a到b有条长c的边）：(S,A,2)，(S,B,8)，(S,D,3)，(A,B,5)，(B,C,1)，(B,D,3)，(C,D,1)
A. 3
B. 7
C. 6
D. 5
答案：BCD
10. 为计算机网络中进行数据交换而建立的规则、标准或约定的**称为（原题写的是“成为”）网络协议。下列英文缩写中，（ ）是网络协议。
A. HTTP
B. TCP/IP
C. FTP
D. WWW
答案：ABC
三、问题求解（共2题，每题5分，共计10分）
1.平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶点的平面图至多有____条边。
（图我就不画了，比较简单，是一个口画一条对角线，然后没有对角线的那2个点从口外面连了一条曲线）
答案：9
2.定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”，可以将A移到B之前，变成字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”，最少需要____次操作。
答案：4
四、阅读程序写结果（共4题，每题8分，共计32分）
1.
const
SIZE=100;
var
n,i,sum,x:integer;
A:array[1..SIZE]of integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
read(x);
inc(a[x]);




end;

i:=0;
sum:=0;
while sum<(n div 2 + 1) do
begin
inc(i);
sum:=sum+a[i];
end;
writeln(i);
end.
输入：
11
4 5 6 6 4 3 3 2 3 2 1
输出：__________
答案：3
2. 啊
var
n:ineger;
procedure f2(x,y:integer);
forward;
procedure f1(x,y:integer);
begin
if x<n then
f2(y,x+y);
end;
procedure f2(x,y:integer);
begin
write(x,’ ‘);
f1(y,x+y);
end;
begin
readln(n);
f1(0,1);
end.
输入：30
输出：__________

答案：1 2 5 13 34
3. 啊
const
v = 100;
var
visited:array[1..v]of boolean;
e:array[1..v,1..v]of integer;
n,m,ans,i,j,a,b,c:integer;

procedure dfs(x,len:integer);
var
i:integer;
begin
visited[x] := true;
if len > ans then
ans:=len;
for i:=1 to n do
if (not visited(i)) and(e[x,i] -1) then
dfs(I,len+e[x,i]);
visited[x] := false;
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
e[i][j] := -1;
for i:=1 to m do
begin
readln(a,b,c);
e[a][b]:=c;
e[b][a]:=c;
end;
for i:=1 to n do
visited[i]:=false;
ans:=0;
for i:=1 to n do
dfs(i,0);
writeln(ans);
end.
输入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
输出：______
答案：150
4. 啊
const
SIZE = 10000;
LENGTH = 10;
var
sum : longint;
n,m,I,j : integer;
a:array[1..SIZE , 1..LENGTH]of integer;
function h(u , v :integer):integer;
var
ans,i : integer;
begin
ans:=0;
for i:=1 to n do
if a[u][i] a[v][i] then
inc(ans);
h := ans;
end;
begin
readln(n);
fillchar(a,sizeof (a),0);
m:=1;
repeat
i := 1;
while (i <=n) and (a[m][i] =1 ) do
inc(i);
if i>n then
break;
a[m][i]:=1;
for j:=i + 1 to n do
a[m][j] := a[m-1][j];
until false;
sum := 0;
for i := 1 to m do
for j := 1 to m do
sum := sum + h(i,j);
writeln(sum);
end.
输入：7
输出：______
答案：57344




五、完善程序（第一题，每空2分，第二题，每空3分，共计28分）
1.（大整数开方）输入一个正整数n（1<=n<10^100）,试用二分法计算它的平方根的整数部分。
const
SIZE=200;
type
hugeint = record
len : integer;
num : array[1..SIZE] of integer;
end;
//len表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推（这个注释不是我带鱼灰写的，是原试题带有的）
var
s : string;
i : integer;
target, left, middle, right : hugeint;
function times(a, b : hugeint) : hugeint;
var
i, j : integer;
ans : hugeint;
begin
fillchar(ans,sizeof(ans),0);
for i:=1 to a.len do
for j:=1 to b.len do
① :=ans.num[i + j - 1] + a.num[i] * b.num[j];
for i:=1 to a.len+b.len do
begin
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;
②
if ans.num[a.len + b.len] > 0
then ans.len := a.len + b.len
else ans.len := a.len + b.len - 1;
end;
times := ans;
end;
function add(a,b : hugeint) : hugeint;
var
i : integer;
ans: hugeint;
begin
fillchar(ans.num,sizeof(ans.num),0);
if a.len>b.len
then ans.len := a.len
else ans.len := b.len;
for i := 1 to ans.len do
begin
ans.num[i]:=③；
ans.num[i+1] := ans.num[i+1] + ans.num[i] div 10;
ans.num[i] := ans.num[i] mod 10;
end;
if ans.num[ans.len + 1]>0
then inc(ans.len);
add := ans;
end;
function average(a,b: hugeint) : hugeint;
var
i : integer;
ans : hugeint;
begin
ans := add(a,b);
for i:= ans.len downto 2 do
begin
ans.num[i-1] := ans.num[i-1] + (④) *10;
ans.num[i]:=ans.num[i] div 2;
end;
ans.num[1]:=ans.num[1] div 2;
if ans.num[ans.len] = 0
then dec(ans.len);
average := ans;
end;
function plustwo(a : hugeint) : hugeint;
var
i : integer;
ans : hugeint;
begin
ans := a;
ans.num[1] := ans.num[1] + 2;
i:=1;
while (i = 10) do
begin
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;
ans.num[i] := ans.num[i] mod 10;
inc(i);
end;
if ans.num[ans.len + 1] > 0
then ⑤；
plustwo := ans;
end;
function over(a , b: hugeint) : boolean;
var
i: integer;
begin
if (⑥) then




begin
over := false;
exit;
end;
if a.len > b.len then
begin
over := true;
exit;
end;
for i := a.len downto 1 do
begin
if a.num[i] < b.num[i] then
begin
over := false;
exit;
end;
if a.num[i] > b.num[i] then
begin
over := true;
exit;
end;
end;
over := false;
end;
begin
readln(s);
fillchar(target.num,sizeof(target.num),0);
target.len := length(s);
for i := 1 to target.len do
target.num[i] := ord(s[target.len - i +1]) - ⑦;
fillchar(left.num,sizeof(left,num),0);
left.len:=1;
left.num[1]:=1;
right:=target;
repeat
middle:=average(left,right);
if over(⑧)
then right := middle
else left := middle;
until over(plustwo(left),right);
for i:= left.len downto 1 do
write(left.num[i]);
writeln;
end.

答案：
① ans.num[i+j-1]
② ans.num[i]:=ans.num[i] mod 10
③ ans.num[i]+a.num[i]+b.num[i]
④ ans.num[i] mod 2
⑤ inc(ans.len)
⑥ a.len<b.len
⑦ ord(‘0’)
⑧ times(middle,middle),target
2.（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父结点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵树对应的笛卡尔树。现输入序列的规模n（1<=n<100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶节点的深度为d。
const
SIZE = 100;
INFINITY = 1000000;
var
n , maxDeep, num , i : integer;
a : array[1..SIZE] of integer;
procedure solve(left , right , deep : integer);
var
i,j,min: integer;
begin
if deep>maxDeep then
begin
maxDeep :=deep;
num := 1;
end
else if deep=maxDeep then
① ;

min := INFINITY;
for i := left to right do
if min > a[i] then
begin
min := a[i];
②;
end;
if left < j then
③;
if j<right then
④;
end;
begin
readln(n);
for i := 1 to n do
read(a[i]);
maxDeep:=0;
solve( 1, n, 1);
writeln(maxDeep, ‘ ‘, num);
end.
答案：
① inc(num)
② j:=i
③ solve(left,j-1,deep+1)
④ solve(j+1,right,deep+1)

关于noip的复赛问题

算法竞赛对文件名有着严格的规定，包括程序名和输入输出文件名，不要使用绝对路径或者相对路径。你的这个题目规定程序名是cross，那么程序的源代码就要存为cross.c，输入文件为cross.in，输出文件名为cross.out,一般来说的话都是这样要求的。比赛的时候代码手册上面应该也会有说明和DEMO的。文件输入输出有两种方法：方法一：使用文件重定向#define LOCAL#include#define INF 1000000000int main(){#ifdef LOCAL freopen("cross.in", "r", stdin); freopen("cross.out", "w", stdout);#endif int x, n = 0, min = INF, max = -INF, s = 0; while(scanf("%d", &x) == 1) { s += x; if(x max) max = x;/* printf("x = %d, min = %d, max = %d\n", x, min, max);*/ n++; } printf("%d %d %.3lf\n", min, max, (double)s/n); return 0;}这种写法的好处就是如果OJ要求使用标准输入输出的话 直接把#define LOCAL删除就可以了。但是有的时候比赛禁止使用重定向的话就需要用fopen了。方法二：fopen版#include#define INF 1000000000int main(){ FILE *fin, *fout; fin = fopen("cross.in", "rb"); fout = fopen("cross.out", "wb"); int x, n = 0, min = INF, max = -INF, s = 0; while(fscanf(fin, "%d", &x) == 1) { s += x; if(x max) max = x; n++; } fprintf(fout, "%d %d %.3lf\n", min, max, (double)s/n); fclose(fin); fclose(fout); return 0;}全部为本人手打，希望可以采纳。本人ACM弱鸡，祝你在NOIP上面取得好成绩哟！！！

瑞士轮 NOIP2011 试题

　　解法：快排明显过不了，用着种XX排+快排

　　var
　　a,b,c:array[0..200000,1..3] of longint;
　　i,n,r,q,j:longint;
　　procedure kp(r,l:longint);
　　var
　　i,j,k1,k2:longint;
　　begin
　　i:=r;
　　j:=l;
　　k1:=a[(i+j) shr 1,1];
　　k2:=a[(i+j) shr 1,3];
　　while i<=j do begin
　　while (a[i,1]>k1) or (a[i,1]=k1) and (a[i,3]<k2) do inc(i);
　　while (a[j,1]k2) do dec(j);
　　if i<=j then begin
　　a[0]:=a[i];
　　a[i]:=a[j];
　　a[j]:=a[0];
　　inc(i);
　　dec(j);
　　end;
　　end;
　　if i<l then kp(i,l);
　　if r<j then kp(r,j);
　　end;
　　procedure ys;
　　var
　　t,k,j:longint;
　　begin
　　i:=1;
　　j:=1;
　　t:=0;
　　while (i<n) or (j<n) do begin
　　if i>n then begin
　　for k:=j to n do begin
　　inc(t);
　　a[t]:=c[k];
　　end;
　　exit;
　　end;
　　if j>n then begin
　　for k:=i to n do begin
　　inc(t);
　　a[t]:=b[k];
　　end;
　　exit;
　　end;
　　if (b[i,1]c[j,3]) then begin
　　inc(t);
　　a[t]:=c[j];
　　inc(j);
　　end else begin
　　inc(t);
　　a[t]:=b[i];
　　inc(i);
　　end;
　　end;
　　end;
　　begin
　　readln(n,r,q);
　　for i:=1 to n*2 do begin
　　read(a[i,1]);
　　a[i,3]:=i;
　　end;
　　for i:=1 to 2*n do read(a[i,2]);
　　kp(1,2*n);
　　for j:=1 to r do begin
　　for i:=1 to n do if a[i*2,2]>a[i*2-1,2] then begin
　　inc(a[i*2,1]);
　　b[i]:=a[i*2];
　　c[i]:=a[i*2-1];
　　end else begin
　　inc(a[i*2-1,1]);
　　b[i]:=a[i*2-1];
　　c[i]:=a[i*2];
　　end;
　　ys;
　　end;
　　writeln(a[q,3]);
　　end.

NOIP2011瑞士轮

type re=record
s:longint;
w:longint;
num:longint;
end;
var n,n1,r,q,i,j,x,y,p,c:longint;
t:re;
f:array[0..1,0..1000000]of re;
procedure qsort(l,r:longint);
var i,j:longint;
w:re;
begin
i:=l;
j:=r;
w:=f[1,(l+r)div 2];
while(i<=j)do
begin
while( (f[1,i].s>w.s) or ((f[1,i].s=w.s) and (f[1,i].num<w.num) ) )do
inc(i);
while( (f[1,j].sw.num) ) )do
dec(j);
if i<=j then begin
t:=f[1,i];
f[1,i]:=f[1,j];
f[1,j]:=t;
inc(i);
dec(j);
end;
end;
if i<r then
qsort(i,r);
if j>l then
qsort(l,j);
end;
begin
readln(n,r,q);
n1:=n;
n:=n*2;
for i:=1 to n do read(f[1,i].s);
for i:=1 to n do
begin
read(f[1,i].w);
f[1,i].num:=i;
end;
c:=1;
qsort(1,n);
for p:=1 to r do
begin
for i:=1 to n1 do
begin
if f[c,i*2-1].w<f[c,i*2].w then
begin
inc(f[c,i*2].s);
t:=f[c,i*2-1];
f[c,i*2-1]:=f[c,i*2];
f[c,i*2]:=t;
end
else
inc(f[c,i*2-1].s);
end;
x:=1;
y:=2;
for i:=1 to n do
begin
if (xf[c,y].s) or
((f[c,x].s=f[c,y].s)and(f[c,x].num<f[c,y].num))) then
begin
f[1-c,i]:=f[c,x];
inc(x,2);
end
else
begin
f[1-c,i]:=f[c,y];
inc(y,2);
end;
end;
c:=1-c;
end;
writeln(f[c,q].num);
end.