10.7模拟赛题目分析(二试)NEW

1、信息学奥林匹克联赛（NOIP2011 ）八校联军复赛模拟二提高组第二试2011 年 10 月 7 日 8： 30-11： 30（请选手务必仔细阅读本页内容）、题目概况中文题目名称文件列表编译优化收费站英文题目名称filecompilecost可执行文件名filecompilecost输入文件名file.incompile.incost.in输出文件名file.outcompile.outcost.out每个测试点时限1秒1秒1秒测试点数目102010每个测试点分值10510附加样例文件有有有结果比较方式全文比较过滤行末空 格及文末回车全文比较过滤行末空 格及文末回车全文比较过滤行末空 格及文末

2、回车题目类型传统传统传统、提交源程序文件名对于pascal语言file.pascompile.pascost.pas对于C语言file.ccompile.ccost.c对于C+语言file.cppcompile.cppcost.cpp三、编译命令（不包含任何优化开关）对于pascal语言fpc file.pasfpc compile.pasfpc cost.pas对于C语言gcc filegcc compilegcc -o costfile.c -lmcompile.c -lmcost.c -lm对于C+语言g+ -o file file.cpp -lmg+ -o compile compil

3、e.cpp -lmg+ -o cost cost.cpp -lm四、运行内存限制内存上限256M256M256M五、注意事项1、文件名（程序名和输入输出文件名）必须使用小写。2、 C/C+中函数main（）的返回值类型必须是 int,程序正常结束时的返回值必须是0。3、 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存1G，上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。1.文件列表(file pas/c/c+)【问题描述】BSOI在线评测机被不明身份的人入侵了！系统中大量的数据遭到恶意破坏，数据文件残缺不全。现在，老师正在尽力抢救数据文件。为了检查数据文件是否完整，老师

4、打印出了 所有文件的列表，但数据文件太多，老师眼睛都要看花了。所以，为了方便老师检查，需要 你写个程序处理一下文件列表，转换成下面这样统一的格式：（后面为注释）data| prob/data/data文件夹，根目录下面的文件夹|-a.in /prob下面的文件|a.out|-qq/data下面的文件夹|-new/qq下面的文件夹| -ok.txt /new下面的文件|-old/空文件夹| xxx.rmvb生成的列表格式有如下要求1. 属于同一层的文件或文件夹位于相同的缩进处，相邻两层文件间差距5个字符；2. 每个文件夹或文件前有 4个-（根目录除外），文件夹下方属于文件夹的部分有T;3. 属于

5、统一文件夹下的文件或子文件夹按字典序排列；【文件输入】第一行一个整数n （ n=50），表示总共的文件数目；接下来n行，每行描述一个文件的路径，路径以7作为文件分隔符；所有文件（及文件夹）名均由小写字母和英文点组成；所有输入的根目录都是一样的，文件名长度不超过10个字符，每个文件夹下不超过15个文件，不超过5层。【文件输出】输出符合要求的文件列表【样例输入输出】file.infile.out5mydocmydoc/abcd/abc.txt| abcdmydoc/dd/libexec.a|abc.txtmydoc/stdio.h| |newmydoc/abcd/zzz/game.cpp|-_-z

6、zzmydoc/abcd/new| | |game.cpp| -dd|libexec.a| -stdio.h【数据范围】对于30%的数据，根目录下只有文件，没有文件夹【注意】 此题有special judge,全文比较过滤行末空格及文末回车。 【题目考点】字符串处理，trie树+递归【题目分析】本题可以用trie树或者模拟trie树解决。可以选择以单个字母作为节点，在每一个文件 夹结尾处做标记，但输出时非常难处理。第二种以文件名即字符串为节点，从根目录往下查找，若当前父节点中能够找到 st,则将父节点中st的编号作为新的父节点继续查找，若没有则新建一个节点，保存下st，以新建节点为父节点继续查

7、找。输出时从根目录递归搜索，先处理“|”及“卜-”，在对当前父节点的子节点排序，递归进行。#in cludeusing n amespace std;struct triebool end;int c28;void clear()memset(c,0,sizeof(c);e nd=0;tr600001;int n, ct=0;boolxxxxx=0;int get(char x)if(x=a&x=0&x=25)return x+a;else retur n .;void set(stri ng s) int sl=s .len gth();int rt=0;for(i nt i=0;isl;i

8、+)if(si=/& !trrt.e nd)trrt.e nd=1;int k=get(si);if(!trrt.ck)ct+;trrt.ck=ct;trct.clear();rt=ct;else rt=trrt.ck;trrt.e nd=1;void out(i nt rt,i nt ce,stri ng x) bool bj=O,k=trrt.e nd;if(k)if(xxxxx) for(i nt j=1;jce;j+)cout|;cout|;coutxe ndl; if(!xxxxx)xxxxx=1;for(i nt i=0;i=26;i+) if(trrt.ci)stri ng s=

9、x;s+=getout(i); out(trrt.ci,ce,s);if(trrt.c27) out(trrt.c27,ce+k,);int mai n() int i;stri ng s;cinn;trO.clear();for(i=1;i s; set(s);out(0,0,);system(pause); return 0;2.编译优化(compile .pas/c/cpp)【问题描述】众所周知，衡量一个编译器是否优秀的标准，除了它的编译速度和正确性以外，编译出的代码的质量也很重要。最近，作为XCC系列编译器作者的 Dr. X发明了一种跨时代的优化算法：“ NanGe不等式优化”。一个程

10、序可以看成是由若干个连续的函数构成的，NanGe不等式算法能针对某一个函数进行优化，得到一个优化效果值,不同的函数的效果值可能是不同的。但这个算法还有一个很大的Bug :该算法不能同时优化相邻的两个函数，否则就会直接Compile Error，值得注意的是，一个程序的第一个函数和最后一个函数也算是相邻的。现在给你一个程序从头到尾每个函数的优化效果值，Dr. X想用NanGe不等式对该程序的M个函数进行优化，他该怎么选择才能使总的优化效果值最大 (前提是不能出现错误)？ 如果错误不能避免，请输出“ Error! ”【输入文件】输入文件的第一行包含两个正整数n、m。第二行为n个整数Aj。【输出文件

11、】输出文件仅一个整数，表示最后对该程序进行优化后的最大效果值。如果无解输出 Error!,不包含引号。【样例输入输出1】compile.incompile.out7 3151 2 3 4 5 6 7【样例输入输出2】compile.incompile.out7 4Error!1 2 3 4 5 6 7【数据规模】对于全部数据：m=n; -1000=Ai using namespace std; int n,m;int L200001,R200001;int d200001,pos200001,a200001;void up(int x) int i=x;while(i1 &adiadi/2)s

12、wap(di,di/2);swap(posdi,posdi/2);i/=2; void down(int x) int i=x,j;while(i*2adi*2+1)j=i*2;else j=i*2+1;if(adiadj)return;swap(di,dj); swap(posdi,posdj); i=j；int main() int i,j;cinnm;if(n/2vm)coutvvError!;return 0; for(i=1;iv=n;i+) cinai; di=i;posi=i;up(i); Li=i-1;Ri=i+1; L1=n;Rn=1; int ans=0;while(m-)

13、 int x=d1; ans+=ax; ax=aL x +aR 凶-a x; aL x =-1111;down(posL 凶); aR 凶=-1111;down(posR 凶); down(1);LN=LL 凶; Rx=RRx; RL x=x; LR凶=x;coutvvans;system(pause);return 0;3.过路费(cost pas/c/c+【问题描述】在某个遥远的国家里，有 n个城市。编号为1,2,3,n这个国家的政府修建了 m条双 向道路，每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为2, B到C长度为3

14、,那么开车从A经过B到C需要上交的过路费为 3。佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据老板的起止城市， 提供给他从开始城市到达目的城市，最少需要上交多少过路费。【输入文件】第一行是两个整数 n和m，分别表示城市的个数以及道路的条数。接下来m行，每行包含三个整数a，b，w (1a bn Ow* 10A9，表示a与b之间有一条长度为w的道路。接着有一行为一个整数 q，表示佳佳发出的询问个数。再接下来q行，每一行包含两个

15、整数 S, T ( KS,TW,nSMT),表示开始城市S和目的 城市T。【输出文件】输出文件共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。【样例输入输出】cost.incost.out4 5201 2 10201 3 201 4 1002 4 303 4 1021 44 1【数据范围】对于 30%的数据，满足 K n 1O0O1W me 1000, K qw 100对于 50%的数据，满足 1w n w 1000 1w mW 1000, 1w qw 1000；对于 100%的数据，满足 1w n w 100001 w mW 10000, 1w

16、 qw 10000【题目大意】 给定一个无向图。求任何一个点对(s,t)所有路径中最大边最小的那条路径，并求出此时的最大边。询问非常多，要求快速计算。【思路点拨】一般多询问的问题要么是具有比较短的时间内可以在线获得答案，要么是用很多时间来处理然后用极短的时间来获得答案。那我们先来想下在线算法。【一般做法】求最大边最小？二分！设最大边为w，把=w的所有边重新构图，如果s,t连通，则w是一种符合的最大边。二分这个最大边。我们可以求出该最大边的最小值。复杂度 O(Q*(|V|+|E|)*log(|E|)可以过50%的数据；【一个定理】定理：图G的(s,t)之间的最小最大边，一定是其在最小生成树中(s

17、,t)的路径上的最大边。证明：反证法，设(s,t)之间的最小最大边权值为 mi nW。1. 假设最小生成树中(s,t)的路径上的最大边 maxWminW。则跟maxW是最小生成树的 边矛盾，因为在添加 maxW之前minW已经添加了。【方法1】转成LCA+RMQ于是我们可以先构造出这个图的一棵最小生成树。然后问他就转为求树上任意两点的最大边权LCA+RMQ【算法】求二叉树上任意两点的最短路径上的边权最大值【问题】给出一棵树，每条边有一边权。对于任意给定的两点，求此两点的最短路径上边权的最大值。对于下图：蓝圈中任意一点与红圈中任意一点的路径上的最大边必定是&根据这个现象，可以把上述的树重建成如下

18、图所示。新图的叶子结点为原图的所有结点，内部结点为原图的边权，建边顺序为从小到大。如图所示：新图的红色编号为原图的结点编号，蓝色编号为原图的边。 这样，问题就转换为求新图中，任意两个叶子节点的最小公共祖先问题了。【分析时间复杂度】：对于一棵树，n个结点，m条边，n=m-1。1、 对所有的边进行排序：O(mlgm)；2、 建图采用并查集维护集合，并查集当前集合的根结点时间复杂度平均为0(1)，建图一共要建立n+m个点，所以时间复杂度为0(n+m);3、 查询任意两个结点的最近公共祖先，采用RMQ处理，预处理的时间复杂度为0(n+m),回答时间复杂度为0(1)；所以，总的时间复杂度0(nlogn)

19、。#include#include#includeconst int maxn=11000,maxm=110000,logn=30;struct edgeint u,v,c; emaxm;int E=1,n,q,m,i,x,y,famaxn,lamaxnlogn,Maxmaxnlogn;int pointmaxm*2,nextmaxm*2,lenmaxm*2,firmaxn,dmaxn;bool fmaxn;int CMP(const void *a,const void *b)return (edge*)a)-c-(edge*)b)-c;int get(int x)if(fa x=x)ret

20、urn x;return fax=get(fa x);void add(int u,int v,int c)pointE=v;nextE=firu;lenE=c;firu=E+;int maxi(int a,int b)return ab?a:b;void dfs(int x,int fa,int w,int deep)d x=deep;f 凶=1;la 凶O=fa;Max x 0=lenw;for(int i=1;lala xi-1i-1;i+)lax i=lala xi-1i-1;Max 凶i=maxi(Max 凶i-1,Maxla xi-1i-1);for(int k=fir 凶;k;k

21、=nextk) if(!fpointk)dfs(pointk,x,k,deep+1);int ask(int x,int y)int ans=O,i;if(dxdy)int tmp=x;x=y;y=tmp; for(i=logn-1;i=0;i-)if(layi &dlayi=d 凶) ans=maxi(ans,Maxyi);y=layi; if(dlayi=d x )break;if(x=y)return ans;for(i=logn-1;i=0;i-)if(layi &la 凶i &(layi!=la x i) ans=maxi(ans,Maxyi);y=layi; ans=maxi(an

22、s,Max xi);x=la 凶i;ans=maxi(ans,maxi(Maxy0,Max 凶0);return ans;int main()freopen(cost.in,r,stdin); freopen(cost.out,w,stdout); scanf(%d%d,&n,&m);for(i=1;iv=m;i+)scanf(,%d%d%d, &ei.u, &ei.v，& ei.c); for(i=1;iv=n;i+)fai=i;qsort(e+1,m,sizeof(edge),CMP); for(i=1;iv=m;i+)int p=get(ei.u),q=get(ei.v); if(p!=

23、q)fap=q;add(ei.u,ei.v,ei.c);add(ei.v,ei.u,ei.c); memset(f,0,sizeof(f);dfs(1,0,0,1);scanf(%d,&q); for(i=1;iv=q;i+)scanf(%d%d, &x,&y);printf(%dn,ask(x,y); return 0;【方法2】#include#include#include#includeusing namespace std;const int MaxN=20005,MaxM=100005;struct LinkTypeint a,b,c;LinkType wMaxM,eMaxM,tM

24、axN,qMaxN,rMaxN;int heMaxM,hqMaxN,hrMaxN;int fatherMaxN,mvMaxN,markMaxN;int ansMaxN;int N,M,Q,eO=O,qO=O,rO=O;void Addq(int x,int y,int z)q0+; qqO.a=y; qqO.b=hq 凶；hq凶=q0; qqO.c=z;void Adde(int x,int y,int z)e0+; eeO.a=y; eeO.b=he x; he x=e0; eeO.c=z;void Addr(int x,int y)r0+; rrO.a=y; rr0.b=hrx; hr凶=

25、r0;void Read() int i;scanf(%d%d,&N,&M);for(i=1;iv=M;i+) scanf(%d%d%d, &wi.a，&wi.b,&wi.c); scanf(%d，& Q);for(i=1;iv=Q;i+) scanf(%d%d, &ti.a，& ti.b);Addq(ti.a,ti.b,i);Addq(ti.b,ti.a,i);void Qsort(int L,int R) int i=L,j=R,Mid=w(L+R)/2.c;while(iv=j) while(wi.cMid) i+; while(Midwj.c) j-; if(iv=j) swap(wi

26、+,wj-);if(Lvj) Qsort(L,j);if(ivR) Qsort(i,R);int Find(int x)if(fatherx=x) return x;int fa=Find(fatherx);mvx=max(mvx,mvfatherx);return fatherx=fa;void Rebuild。/求最小生成树，并建立图 int i,r1,r2;for(i=1;iv=N;i+)fatheri=i;Qsort(1,M);for(i=1;iv=M;i+)r仁Find(wi.a);r2=Find(wi.b); if(r1!=r2) fatherr2=r1;Adde(r1,r2,wi

27、.c);Adde(r2,r1,wi.c);void Tarjan(int x,int fa) int i,y,r1,r2;fatherx=x;mvx=O;for(i=he 凶;i;i=ei.b)y=ei.a;if(y=fa)continue; Tarjan(y,x); fathery=x;mvy=ei.c;mark x=1;for(i=h q x;i;i=qi.b)y=qi.a;if(marky)Addr(Find(y),qi.c);for(i=hr 凶;i;i=ri.b)r仁tri.a.a;r2=tri.a.b; Find(r1); Find(r2); ansri.a=max(mvr1,mv

28、r2);void Solve() Rebuild();Tarjan(1,0);for(int i=1;iv=Q;i+)printf(%dn,ansi); int main() freopen(cost.in,r,stdin); freopen(cost.out,w,stdout); Read();Solve(); return 0;【方法3】#in elude #in elude #i nclude using n amespace std;const int maxn = 100009+10009;struct arrint x,y,z;emax n;int depmax n,premax n22,famax n,two22, n,m,q ,vmax n;struct cmpbool opera