提高1班2011一组控江中学王

1、控江中学 王建德小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早

2、进入内存的那个单词，腾出单元来，存放新单词。 假设一篇英语文章的长度为 N个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。 【输入】 输入文件名为 translate.in，输入文件共 2 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数 M和 N，代表内存容量和文章的长度。 第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。【输出】 输出文件 translate.out 共1行，包含一个整数，为软件需要查词典的次数。 【数据范围】 对于

3、 10%的数据有 M=1，N5。00%的数据有 0M100，0N1000。 思维方向 内存采用什么样的存储结构，可使得存储的单词数不超过 M-1时，新近的单词存储在最晚进入内存的单词后；否则替代最早进入内存的单词。 显然，“先进先出”的队列满足这一要求。模拟算法建立一个队列queue每读入一个数x，先查看队列中是否已经存在。在队列不存在x的情况下，若队列长度m，则x入队；否则x替换队首元素。时间复杂度:查找一次的复杂度为O(m)，故总复杂度为O(m*n)var n,m,ans:longint; /* 内存容量、文章长度和软件需要查词典的次数*/ s:array 1.100000 of long

4、int;队列i,j,p,q,c:longint; assign(input,translate.in);reset(input); /*输入输出文件初始化*/assign(output,translate.out);rewrite(output);readln(m,n);/* 读内存容量和文章的长度*/ans0; p1;q0;/* 查词典的次数和队列的首尾指针初始化*/for i1 to n do read(c);/*读第i个数*/ jp;hfalse; /* 检查队列中是否存在该数*/ while( j=q )and(csj)do inc(j); if j0的情况下分析四种情况X10时右走1

5、步：fi+1,x1-1,x2,x3=max fi+1,x1-1,x2,x3，fi,x1,x2,x3+vi+1X20时右走2步：fi+2,x1,x2-1,x3=max fi+2,x1,x2-1,x3，fi,x1,x2,x3+vi+2X30时右走3步：fi+3,x1,x2,x3-1=max fi+3,x1,x2,x3-1，fi,x1,x2,x3+vi+3X40时右走4步：fi+4,x1,x2,x3=max fi+4,x1,x2,x3，fi,x1,x2,x3+vi+4 由于递腿推过程中fi+1,x1-1,x2,x3、 fi+2,x1,x2-1,x3、 fi+3,x1,x2,x3-1、 fi+3,x1

6、,x2,x3-1已经求出，因此方程成立。显然，最后fn，0，0，0即为问题解。时间复杂度：由于每种卡片数量不超过40张、数字4的卡片数直接推出，故状态量O(403)。而状态转移O(1)，可得出总复杂度为O(403)var v:array 1.1000 of longint;/*vi为第i格的分数*/ x:array 1.4 of longint;/*数字i的卡片数为xi*/ f:array 1.360,0.42,0.42,0.42 of longint;/到达i格、数字1、2、3尚剩卡片数为x1,x2,x2时的最多得分为fi,x1,x2,x3*/ n,m，i,temp,x1,x2,x3,x4:

7、longint;/* 棋盘格子数为n,爬行卡片数为m，数字1、2、3、4尚剩的卡片数为x1、x2、x3、x4*/ assign(input,tortoise.in);reset(input);/*输入输出文件初始化*/ assign(output,tortoise.out);rewrite(output); readln(n,m); /* 读棋盘格子数和爬行卡片数*/ for i1 to n do read(vi); /* 读每格子分数*/ for i1 to m do read(temp); inc(xtemp) ;/*读每张爬行卡片上的数字，统计每个数字的卡片数*/ fillchar(f,

8、sizeof(f),0); f1,x1,x2,x3v1;/*设置第1格出发时的得分*/for i1 to n do /*从左而右递推每一格*/ for x10 to x1 do /*枚举数字1、2、3尚剩的卡片数*/ for x20 to x2 do for x30 to x3 do if fi,x1,x2,x30 /*若已经求出到达格子i、数字1、2、3尚剩x1、x2、x3时的最大分数*/ then x4x4-(i-1-(x1-x1)*1-(x2-x2)*2-(x3-x3)*3) div 4;/*计算数字4尚剩的卡片数*/ if (x10) and (fi+1,x1-1,x2,x30) an

9、d (fi+2,x1,x2-1,x30) and (fi+3,x1,x2,x3-10) and (fi+4,x1,x2,x3fi,x1,x2,x3+vi+4) /*花1张数字4的卡片到达i+4格子的得分高*/ then fi+4,x1,x2,x3fi,x1,x2,x3+vi+4; ;/*then*/ writeln(fn,0,0,0);/*输出用完m张卡片后到达格子n的最高得分*/close(input);close(output);/*关闭输入输出文件*/.S城现有两座监狱，一共关押着 N名罪犯，编号分别为 1N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时

10、可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。 每年年末，*局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换*局长。 在详细考察了 N 名罪犯间的矛盾关系后，*局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两

11、个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M行每行为三个正整数 aj，bj，cj，表示 aj号和 bj号罪犯之间存在仇恨，其怨气值为 cj。数据保证1aj bj N ，0cj 1,000,000,000，且每对罪犯组合只出现一次。 【输出】输出文件 prison.out 共1 行，为 Z 市长看到的那个冲突事件的影响力。如果

12、本年内监狱中未发生任何冲突事件，请输出 0。 【数据范围】对于 30%的数据有 N15；对于 70%的数据有 N2000，M50000；对于 100%的数据有 N20000，M100000。思维方向1、能否在同所监狱的最大怨气值不超过c的前提下，将所有罪犯分配在两所监狱。定义图的顶点为罪犯，所有怨气值大于c的罪犯对之间连边，边权为怨气值（连边的两个罪犯不在同一监狱）。如果该图是一个二分图，则顶点集合X和Y的罪犯各分配一个监狱，每个监狱的最大怨气值为c。2、顶点（罪犯）数的上限为2000，边权（怨气值）的数据类型为4个字节的longint，因此不能采用图的相邻矩阵，只能采用指针类型的邻接表存储二

13、分图，采用边表存储原图。3、按照怨气值递增的顺序排序罪犯对。通过二分搜索的办法寻找同一监狱中罪犯对间最小的最大怨气值：算法：二分+判定 1、给定一个边权值的顺序值ans，通过二分图判断同一监狱中罪犯对的最大怨气值是否不超过ans按照边权递增的顺序排序边集e定义图的顶点为罪犯，存在仇恨的罪犯之间连边，边权为怨气值。将边eansem加入新图中，即这些边的权值不小于第ans大的权值采用dfs或者bfs判定新图是否为一个二分图。若是，则表示新图中任何边(x,y)的端点x和y不能在同一个集合中，同一集合（同一监狱）中罪犯的最大怨气值为eans-1的边权2、枚举边权的大小顺序ans,再通过判定新图是否为二

14、分图来判断能否把罪犯分成两个集合，使得同一集合内罪犯的怨气值不超过第ans大。由于ans是满足单调性的，如果ans可行，则最小的最大怨气值在其左区间，否则最小的最大怨气值在其右区间。所以可以通过二分法来枚举ans。 时间复杂度：二分复杂度为O(log(maxci),约为30，判定复杂度为O(m)，故总复杂度为O(log(maxci)*m)。(二分复杂度可以通过离散化进一步降为O(log(n),总复杂度降为O(log(n)*m)数据结构Type rectype=record/*存在仇恨的罪犯序号为x、y，怨气值为c*/ x,y,c:longint; end; plink=point;/*单链表的

15、指针类型*/ point=record x:longint; next:plink; end;var t:array 1.50000 of plink;/*二分图的邻接表*/ c:array1.50000 of longint;/*顶点i的集合标志，ci= */ e:array 0.200000 of rectype;/*边表，存储存在仇恨的罪犯序列*/ n,m:longint; /* 罪犯数为n，存在仇恨的罪犯对数为m*/ h:boolean; /*二分图标志*/按照怨气指递增的顺序排列存在仇恨的罪犯对序列eproc sort(l,r:longint);var i,j,v:longint;

16、temp:rectype; il;jr; ve(l+r) div 2.c; repeat while ei.cv do dec(j); if ij; if lj then sort(l,j); if ir then sort(i,r); ;/* sort */proc init;/* 输入信息，按照怨气值递增的顺序排列存在仇恨的罪犯对序列*/var i:longint; readln(n,m);/*读罪犯数和存在仇恨的罪犯对数*/ for i1 to m do readln(ei.x,ei.y,ei.c);/*读每一对存在仇恨的罪犯序号和怨气值*/ e0.c0;/*虚拟第0对罪犯的怨气值为0*

17、/ sort(0,m); /*按照怨气值递增的顺序排列存在仇恨的罪犯对序列e*/ ;/* init */proc pro(d,r:longint); /*从r集合中的顶点d出发，判别二分图*/var u:plink; if h=false then exit;/*若当前图非二分图，则回溯*/ if cd=r then exit;/*若顶点d已属于集合r，则回溯*/ if cd=-r then hfalse;exit ;/*若顶点d已属于集合-r，则说明同一集合内的顶点间出现边，返回失败信息*/ cdr;utd;/*顶点d设r集合标志，并继续递归下去*/ while unil do pro(u.

18、x,-r); uu.next; ;/* pro */判别第min对罪犯的怨气值是否在同一集合中最大func check(min:longint):boolean; var i:longint; u:plink; for i1 to n do tinil;/*新图初始化为空*/ for imin to m do /*将大于等于第min对罪犯的怨气值的罪犯对间连边，构造新图*/ new(u); u.xei.y; u.nexttei.x; tei.xu; new(u); u.xei.x;u.nexttei.y; tei.yu; ;/*for*/htrue; /*二分图标志初始化*/fillchar(

19、c,sizeof(c),0);/*顶点的集合标志初始化*/for i1 to n do/*从每个未确定集合的顶点出发，判断当前图是否二分图*/ if ci=0 then pro(i,1); if h=false then break ;/*若当前图非二分图，则失败退出*/ checkh;/*返回二分图标志*/;/* check */计算和输出冲突事件影响力的最小值proc work;var p,q,ans:longint; p1;qm; while p0，则说明有ans个干旱区必定不能有水利设施，输出失败信息，否则说明第1行的m个点，通过“从高往低”的规则能够到达第n行的m个点。3、此时有一个

20、结论：第1行的任何一个点，能到达的第n排的点是连续的*（证明在之后给出），可使用类似记忆化搜索的方式计算第1行每个点到达第n行的区间。设 Lj表示第1行第j列的点通过“从高往低”规则能扩展到的第n行的最左侧的点为Lj（第n行第1,2,.Lj-1列的点不能扩展到）。同理有Rj设顶行的ck点原来可达底行的区间为I，j，现计算出ck可达底行的点i和点j，且ii，j j。由于Ck可达第n行的区间是连续的，因此Ck可达底行的区间调整为I，j，即LCK=i，RCK=j。4、问题就转化为给定m条线段Li，Ri，问用最少几条线段能覆盖1,m，这是经典的DP（贪心）设fi为覆盖n,1n,i的最少线段数。显然f0

21、=0 有左而右递推n行的每一列i(1im)； 在覆盖i+1列的所有线段中，计算右端点的最大值R= ; 调整i+1,R区间的f值：fk=max fi+1,fk i+1kR最后得出的fm即为问题解。时间复杂度：O(n*m)。 结论：任何一个点，能到达的第n排的点集是连续的。证明：A点能到达的点集在图中用灰色区域表示（不包括D点）。假设A点能到达的第n排的点不连续，其中点D无法到达，由于第一排的m个点能够通过“从高往低”的规则到达第n排所有点，故必定存在点B，A点不能到达，它能到达点D。此时，B点到达D点的路径必定和A点能到达的点相交,设为C点，那么此时A点可以通过ACD来到达D，与假设矛盾。数据结

22、构const /*i方向上的水平增量为txi，垂直增量为tyi*/ tx:array 1.4 of longint=(0,0,1,-1); ty:array 1.4 of longint=(1,-1,0,0);var n,m,sum,x:longint;/*矩形规模为n*m；第n行中sum个城市有水利设施；线段数为x*/ s:array 1.2000000 of record /*队列(存储坐标)或线段序列(第1行中点i到达第n排的区间为si.x,si.y)*/ x,y:longint; end; hash:array 0.1000,0.1000 of boolean; /*(i,j)的搜索标

23、志为hashi,j*/ e:array 1.1000,0.1000 of longint; /*第1行中提供给(n,i)水源的蓄水厂数为ei,0，其中第j个蓄水厂的列位置为ei,j*/ h:array 0.1000,0.1000 of longint; /*(i,j)的海拔高度为hi,j*/ p,q:array1.1000 of longint;/*第i条线段为pi,qi*/ f:array 0.1000 of longint;/*覆盖n,1n,i的最少线段数为fi*/proc init; /*输入矩形规模和矩形中每座城市的海拔高度 */var i,j:longint; fillchar(h,

24、sizeof(h),0); readln(n,m); /*输入矩形规模和矩形中每座城市的海拔高度 */ for i1 to n do for j1 to m do read(hi,j); ;/* init */proc pro(c:longint); /*计算(1,c)可以提供给第n行中哪些城市水源*/var p,q,i,ux,uy,ox,oy:longint; fillchar(hash,sizeof(hash),0); p1;q1;/*队列的首尾指针初始化*/ s1.x1;s1.yc; hash1,ctrue;/*(1,c)进入队列，并标记*/ while p=hux,uy ) or(ha

25、shox,oy) then continue; hashox,oytrue; inc(q);sq.xox;sq.yoy ;/*for*/ inc(p);/*出队*/ ;/*while*/ ;/* pro */p和q序列以p为关键字递增排序proc sort(l,r:longint); /*所有线段按照左端点递增的顺序排序*/var i,j,v,temp:longint; il;jr; vp(l+r) div 2; repeat while piv do dec(j); if ij; if lj then sort(l,j); if ir then sort(i,r); ;/* sort */计算和输出第1行最少建造的蓄水厂数proc run; var i,j,k,max:longint; fillchar(s,sizeof(s),0); for i1 to m do si.xmaxlongint;si.y0;/*for*/ for i1 to m do /*搜索第n行的每一列*/ for j1 to ei,0 do /*搜索第1行中供给(n,i)水源的所有蓄水厂*/ if isei,j.y then sei,j.yi ;/*for*/ x0;/*线段数初始化*/ for i1 to m do/*若(1,i)能