冲刺NOIP模拟试题与解析提高组

1、冲刺NOIP 模拟试题与解析（ 十一 ）学校： 河南省焦作一中 出题人：刘晓刚NOI导刊 2011 年 9 月 第 7 期题目一览题目多米诺骨牌超车最小奖励文件名dominoovertakingminaw输入文件.in.in.in输出文件.out.out.out题目类型传统传统传统测试数目101010时间限制1s1s1s内存限制128m128m128m【多米诺骨牌 DOMINO】【题目描述】Jzabc对多米诺骨牌有很大的兴趣，然而他的骨牌比较特别，只有黑的和白的。他觉得如果存在连续三个骨牌是同种颜色的，那这个骨牌排列就是不美观的。现在他有N个骨牌要排列，他想知道不美观的排列的个数。他想请你帮忙

2、进行统计不美观排列的个数。【输入格式】只有一个正整数，即要排列的骨牌的个数。【输出格式】一个数，即不美观的排列的个数。【输入样例】4【输出样例】6解释：有6中不美观的排列。【数据规模】对于20%的数据，满足N<=60对于50%的数据，满足N<=600对于100%的数据，满足N<=20000对于%的数据，满足。【超车 OVERTAKING】【题目描述】Jzabc对赛车也很感兴趣，在参观车展是，想到这样一个问题，在某时刻，他看到n辆车（总是匀速行驶）在同一直线上，且处于一个无限长的直道上，而且n辆车有严格的先后之分，。他通过特殊的器材测出了每辆车的速度，那么问题出现了，如果有车A

3、和车B，A在B的后面，且A的速度快于B的，那么经过一段时间后，A一定会超过B，我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0 ，没有两辆车的坐标相同。【输入格式】第一行，一个数N，表示车辆总数。以下n行为N辆车的信息；第二行至第N+1行，每行有两个正整数X、Y，X和Y之间有一个空格，其中X为车的坐标，Y为车的速度。0<=X,Y<=1000000000【输出格式】一行，超车总数【输入样例】25 62 8【输出样例】1【数据规模】对于20%的数据，满足N<=300对于50%的数据，满足N<=3000对于100%的数据，满足N<=300000

4、对于%的数据，满足。【最小奖励 MINAW】【题目描述】Jzabc更是一个狂热的“驴友”，这次他想去一个诡异的地方。这个地方有n个村庄，编号为1到n。此刻他在1号村，他想到n号村。这n个村子之间有m条单向道路。通过某些道路时，可能需要花费一些钱作为“买路钱”，可是通过一些道路时不仅不用交钱反而会得到某些奖励。当然两个村庄之间可能有多条直接相连的道路，但是每条道路只能通过一次。这些村庄有这样的特性，从任何一个村庄出发，沿着任一条路径走都不会回到出发点。找到一条路径从1号到n号，他需要计算一共得到多少奖励，一共交了多少过路钱。如果奖励的钱数大于交的过路钱数，那么称这样一套路径可以得到奖励，反之如果

5、前者小于后者，那么这样的路径需要花费，如果二者相等，那么Jzabc不会选择。不会出现所有的路径两者都相等，现在请你帮忙找到一条路径，使得到的奖励最小（为什么不是奖励最大？或花费最少？花费最大？），并输出最小奖励。如果找不到一条路径使其得到奖励，那么就找一条路径使其得到的花费最大（为何不是最小花费？），并输出最大花费。【输入格式】第一行，两个用空格隔开的正整数n和m；以下m行，每行三个正整数x,y,w，描述一条路的信息，中间用空格隔开，其中x表示道路的起点，y表示终点；若w为负，则是通过磁条道路交的买路钱数目，若w为正，则表示这条路奖励的钱数；w不为零，且其绝对值不大于10。【输出格式】一个整数

6、，若有最小奖励则输出，否则输出最大花费；【输入样例】3 41 2 22 3 -12 3 31 3 -1【输出样例】1【输入样例】3 41 2 22 3 -32 3 -51 3 -2【输出样例】3【数据规模】对于20%的数据，满足n<=20, m<=200对于50%的数据，满足n<=50, m<=2000对于100%的数据，满足n<=100, m<=20000对于%的数据，满足。【多米诺骨牌】【题目大意或抽象出的数理模型】【解法或分析】递推我们不妨计算一下美观的情况（问题转化，寻求解题突破口）用fI表示。我们默认已经推到第I个，那么前I个都是满足题意的，在第I

7、的位置上放置一个与第I-1相同颜色的骨牌，则情况数为FI-2，否则为FI-1，然后FI=FI-1+FI-2；再求出所有情况用排列组合的思想，每一位都可以是白的和黑的，所以美观与否的总的排列数目为ans=2n，最后的ans=ans-FI，即得到所求。因为数据量很大，需要使用高精度，还需要用到高精度的优化（万进制优化）。【参考程序】（在FP中编辑、编译之后再复制过来）【出题目的】【分析二】【一句话题意】求所有n位二进制中存在连续3位相同的个数。【考察知识点】动态规划/递推/高精度【思路】考虑美观的情况，设fi为i个骨牌的排列中完美排列的数量。若在第i个位置上放与i-1个骨牌颜色相同的骨牌，则情况数

8、为fi-2，否则为fi-1，那么fi:=fi-1+fi-2。由二进制的数量可得，此时不完美排列个数即为gi:=2n-fi。由于数量巨大，n=20000时答案位数已经达到了6000+，因此必须用万进制的高精度。附：这里给出一个我一开始遇到题目的思考过程。首先没发现明显的规律，于是用枚举程序打表n=1.10的情况，得到的数据如下。i12345678910gi0026163886188402846gi/200138194394201423gi/2-gi-1-1123581321gi/2-gi-1明显是斐波那契数列，因此我顺推，光荣地超时了2个数据。【提交过程】50分(给我们的题目中n范围说明是100

9、00)=>AC【时间复杂度】O(n*length)【代码】/uses sysutils;Const    ProgramName='domino'Type    num=record        leng:longint;        data:array0.7000of integer;   

10、0;end;Var    fin,fout:text;    i,j,k,n,m,l,r,s,x,y:longint;    f1,f2:num;    a1,a2,a3,t:num;    time:real; Procedure Pin;var    i,j,k:longint;begin    read

11、ln(fin,n);end;  Function add(x,y:num):num;var    i,j,k:longint;begin    fillchar(add,sizeof(add),0);    if x.leng>y.leng then        add.leng:=x.leng    else 

12、0;      add.leng:=y.leng;    for i:=1 to add.leng do        add.datai:=x.datai+y.datai;    for i:=1 to add.leng do        if add.datai>=10000 then&

13、#160;           begin                add.datai+1:=add.datai+1+add.datai div 10000;              

14、;  add.datai:=add.datai mod 10000;            end;    while add.dataadd.leng+1<>0 do        inc(add.leng);end;  Procedure print(x:num);var  

15、0; i,j,k:longint;    st:string;begin    str(x.datax.leng,st);    write(fout,st);    for i:=x.leng-1 downto 1 do        begin        

16、60;   str(x.datai,st);            for j:=1 to 4-length(st) do                st:='0'+st;        &

17、#160;   write(fout,st);        end;    writeln(fout);end;  Procedure Main;var    i,j,k:longint;begin    if n<=2 then        begin

18、60;           writeln(fout,0);            exit;        end;    if n=3 then        beg

19、in            writeln(fout,2);            exit;        end;    if n=4 then       

20、0;begin            writeln(fout,6);            exit;        end;    a1.leng:=1;    a1.data1:=1; 

21、;   a2.leng:=1;    a2.data1:=1;    f1.leng:=1;    f1.data1:=6;    for i:=5 to n do        begin           

22、0;a3:=add(a1,a2);            t:=add(f1,a3);            f2:=add(t,t);            a1:=a2;     

23、60;      a2:=a3;            f1:=f2;        end;    print(f2);end;  Procedure Pout;var    i,j,k:longint;beginend; &#

24、160;begin    assign(fin,ProgramName+'.in');    assign(fout,ProgramName+'.out');    reset(fin);    rewrite(fout);   / time:=now;    pin;    main; 

25、;   pout;   / writeln(fout,(now-time)*86400000:8:8);    close(fin);    close(fout);end.【超车】【题目大意或抽象出的数理模型】题目就是求逆序对的数目问题（简化或抽象或问题转化为较熟悉或交易解决的，寻求解题突破口）【解法或分析】考察：题意分析+归并排序或树状数组首先按照位置从小到大排列整个信息，再根据速度求逆序对的个数（详见代码），求逆序对的个数可以用归并排序或树状数组实现

26、。参考程序给出的是归并排序法求逆序对数，具体方法如下：。我们用数组Alohi存放当前子数列，用D（LO,HI）记录该子数列中的多有逆序对，整个归并排序需要三步：分：令mid=(lo+hi) div 2，将整个数列A分成元素个数尽量相等的两部分。左数列ALO.MID和右数列AMID+1.HI，两字子数列已经按照由小到大的顺序排序，继续划分，直到LO=HI；治：若逆序对的两个数分别取自子数列ALO.MID 和AMID+1.HI的话，则将该逆序对存入F(LO,MID,HI).合：显然ALO.HI中的逆序对数D(LO,HI)=其子数列ALO.MID中的逆序对数D(LO,MID)+其子数列AMOD+1.

27、HI中的逆序对数D（MID+1，HI）+当前数理新得逆序对数F(LO,MID,HI)即D(LO,HI)= D(LO,MID)+ D（MID+1，HI）+ F(LO,MID,HI)【参考程序】（在FP中编辑、编译之后再复制过来）【出题目的】【分析二】【一句话题意】给定一些坐标为ai的点，这些点有属性vi，求(ai<aj)and(vi>vj)的对数。【考察知识点】逆序对/归并排序【思路】非常明显，这就是求逆序对。只需先将坐标数组从小到大排序一遍即可，然后再用归并排序的merge来求逆序对。【提交过程】一次AC【时间复杂度】O(nlogn)【代码】/uses sysutils;Const

28、    ProgramName='minaw'Var    fin,fout:text;    i,j,k,n,m,l,r,s,t,x,y:longint;    a:array0.110,0.20010,0.2 of integer;    d,b:array0.110 of longint;    v:array0.110of boole

29、an;    m1,m2:longint; Procedure Pin;var    i,j,k:longint;begin    readln(fin,n,m);    for i:=1 to m do        begin          

30、  readln(fin,j,k,t);            inc(aj,0,0);            aj,aj,0,0,1:=k;            aj,aj,0,0,2:=t;  

31、      end;end;  Procedure SPFA(kind:longint);var    i,j,k:longint;    ok:boolean;begin    fillchar(v,sizeof(v),false);    fillchar(b,sizeof(b),0);    for i:=1 t

32、o n do        di:=10000000;    d1:=0;    l:=0;    r:=1;    b1:=1;    v1:=true;    while l<>r do      

33、60; begin            l:=(l+1) mod n;            x:=bl;            vx:=true;      

34、0;     for i:=1 to ax,0,0 do                begin                    if kind=-1 then  

35、;                      ok:=(dax,i,1>dx+ax,i,2)and(dx+ax,i,2>0)                    el

36、se                        ok:=(dax,i,1>dx+ax,i,2);                    if ok t

37、hen                        begin                        

38、0;   dax,i,1:=dx+ax,i,2;                            if not vax,i,1 then            &#

39、160;                   begin                             

40、60;      r:=(r+1)mod n;                                    br:=ax,i,1;   &#

41、160;                                vax,i,1:=true;               

42、                 end;                        end;       

43、0;        end;        end;end;  Procedure Main;var    i,j,k:longint;begin    spfa(-1);    if dn=10000000 then       

44、; begin            spfa(1);            writeln(fout,abs(dn);        end    else      

45、  begin            writeln(fout,dn);        end;end;  Procedure Pout;var    i,j,k:longint;beginend;  begin    assign(fin,ProgramNa

46、me+'.in');    assign(fout,ProgramName+'.out');    reset(fin);    rewrite(fout);    /time:=now;    pin;    main;    pout;    

47、/writeln(fout,(now-time)*86400000:8:8);    close(fin);    close(fout);end.【最小奖励】【题目大意或抽象出的数理模型】图论、拓扑排序【解法或分析】有向图，没有回路，并且要遍历整个图，非常容易想到使用拓扑排序的思想。对图进行拓扑排序，我们知道到达一个点获得的奖励或花费可以由其父节点递推，所以按照拓扑排序的顺序进行递推即可。但是题目不仅仅考察到此为止，其中的细节很多，必须要全面考虑或细心，所以更多的加入了代码实现能力的考察，增加了试题的解决复杂度。

48、也可以不进行拓扑排序，因为数据较小，直接用深搜DFS也可以，不过必须进行判重（很重要），同时辅以搜索优化，这也是考察了细节或是分析是否全面，或者是考察对题意的理解或者分析角度的选择，以及解决问题的思维广度如何！很明显考察了对题目的分析和思路的设计，也就是写代码之前的工作！。简单的暴搜而没有任何优化，也只能过部分点。对于此题的优化很有很多，100个点，20000条边，会有很多的重边，可以进行判重；由于手工做的数据，所以数据包中的数据较弱，因此很多思路或算法都可以AC。解题者不妨自己将数据加强，然后以此题为基本框架，做些拓展，一次来强化训练和进行深入的分析、思考。【参考程序】（在FP中编辑、编译之

49、后再复制过来）【出题目的】考察基本算法是否掌握准确、熟练，以及是否全面的分析或理解题目中的信息（尤其是隐含信息），细节是否能够发现和正确的处理好，这些都可以归为基础范围，而和学习的深度和难度没有直接关系！考察了思维或者思路的广度，以及是否有主动的变通意识，是否能跳出原有对题目的理解，重新从零开始读题、分析寻找新的解题点，关键是这样的意识有没有？！【分析二】【一句话题意】给定一有向含负权图，找一条1.n的路径，使其权值和大于0且最接近0；若没有，则找一条最小权值路。【考察知识点】最短路/SPFA【思路】按照题目描述模拟即可，只需注意SPFA时松弛操作的条件，进行两次SPFA。【提交过程】WA(以

50、为要求第K短路+二分)=>AC【时间复杂度】O(ne)【代码】/uses sysutils;Const    ProgramName='overtaking'Var    fin,fout:text;    i,j,k,n,m,l,r,s,t,x,y:longint;    a,b:array0.500100,1.2of longint;    ans:int64; 

51、;   t1,t2,t3:longint; Procedure Pin;var    i,j,k:longint;begin    readln(fin,n);    for i:=1 to n do        read(fin,ai,1,ai,2);    readln(fin);end;  

52、Procedure swap(x,y:longint);var    t:longint;begin    a0:=ax;    ax:=ay;    ay:=a0;end;  Function merge(l,t,r:longint):int64;var    i,j,k,w:longint;    p:int64;begin 

53、;   i:=l;    j:=t+1;    p:=0;    w:=l-1;    while (i<=t)and(j<=r) do        if ai,2<=aj,2 then          &#

54、160; begin                inc(w);                bw:=ai;             &

55、#160;  inc(i);            end        else            begin            

56、    inc(w);                bw:=aj;                p:=p+int64(t-i+1);        

57、0;       inc(j);            end;    while i<=t do        begin            inc(w);&

58、#160;           bw:=ai;            inc(i);        end;    while j<=r do        beg

59、in            inc(w);            bw:=aj;            inc(j);        end; 

60、60;  merge:=p;    for i:=l to r do        ai:=bi;end;  Function mergesort(l,r:longint):int64;var    t:longint;    p1,p2,p3:int64;begin    mergesort:=0; 

61、60;  if l<r then        begin            t:=(l+r)shr 1;            p1:=mergesort(l,t);       

62、;     p2:=mergesort(t+1,r);            p3:=merge(l,t,r);            t1:=p1;            t2:=p2;            t3:=p3;            mergesort:=p1+p