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

冲刺NOIP2011八校联军复赛模拟二（巴蜀中学） 提高组信息学奥林匹克联赛（NOIP2011）八校联军复赛模拟二提高组第二试2011年10月7日 8：30-11：30（请选手务必仔细阅读本页内容）一、题目概况中文题目名称文件列表编译优化收费站英文题目名称filecompilecost可执行文件名filecompilecost输入文件名file.incompile.incost.in输出文件名file.outcompile.outcost.out每个测试点时限1秒1秒1秒测试点数目102010每个测试点分值10510附加样例文件有有有结果比较方式全文比较过滤行末空格及文末回车全文比较过滤行末空格及文末回车全文比较过滤行末空格及文末回车题目类型传统传统传统二、 提交源程序文件名对于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 o file file.c -lmgcc o compile compile.c -lmgcc o cost cost.c -lm对于C+语言g+ -o filefile.cpp -lmg+ -o compile compile.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在线评测机被不明身份的人入侵了！系统中大量的数据遭到恶意破坏，数据文件残缺不全。现在，老师正在尽力抢救数据文件。为了检查数据文件是否完整，老师打印出了所有文件的列表，但数据文件太多，老师眼睛都要看花了。所以，为了方便老师检查，需要你写个程序处理一下文件列表，转换成下面这样统一的格式：(/后面为注释)data /data文件夹,根目录|-prob /data下面的文件夹| |-a.in /prob下面的文件| |-a.out|-qq /data下面的文件夹| |-new /qq下面的文件夹| | |-ok.txt /new下面的文件| |-old /空文件夹|-xxx.rmvb生成的列表格式有如下要求:1.属于同一层的文件或文件夹位于相同的缩进处，相邻两层文件间差距5个字符；2.每个文件夹或文件前有4个-(根目录除外)，文件夹下方属于文件夹的部分有|；3.属于统一文件夹下的文件或子文件夹按字典序排列；【文件输入】第一行一个整数n（n=50），表示总共的文件数目；接下来n行，每行描述一个文件的路径，路径以/作为文件分隔符；所有文件（及文件夹）名均由小写字母和英文点组成；所有输入的根目录都是一样的，文件名长度不超过10个字符，每个文件夹下不超过15个文件，不超过5层。【文件输出】输出符合要求的文件列表【样例输入输出】file.infile.out5mydoc/abcd/abc.txtmydoc/dd/libexec.amydoc/stdio.hmydoc/abcd/zzz/game.cppmydoc/abcd/newmydoc|-abcd| |-abc.txt| |-new| |-zzz| | |-game.cpp|-dd| |-libexec.a|-stdio.h【数据范围】对于30%的数据,根目录下只有文件，没有文件夹【注意】此题有special judge，全文比较过滤行末空格及文末回车。【题目考点】字符串处理，trie树+递归【题目分析】本题可以用trie树或者模拟trie树解决。可以选择以单个字母作为节点，在每一个文件夹结尾处做标记，但输出时非常难处理。第二种以文件名即字符串为节点，从根目录往下查找，若当前父节点中能够找到st，则将父节点中st的编号作为新的父节点继续查找，若没有则新建一个节点，保存下st，以新建节点为父节点继续查找。输出时从根目录递归搜索，先处理“| ”及“|-”，在对当前父节点的子节点排序，递归进行。#includeusing namespace std;struct trie bool end; int c28; void clear()memset(c,0,sizeof(c);end=0; tr600001;int n,ct=0;bool xxxxx=0;int get(char x)if(x=a&x=0&x=25)return x+a;else return .;void set(string s) int sl=s.length(); int rt=0; for(int i=0;isl;i+) if(si=/&!trrt.end)trrt.end=1; int k=get(si); if(!trrt.ck) ct+; trrt.ck=ct; trct.clear(); rt=ct; else rt=trrt.ck; trrt.end=1;void out(int rt,int ce,string x) bool bj=0,k=trrt.end; if(k) if(xxxxx) for(int j=1;jce;j+)cout| ; cout|-; coutxendl; if(!xxxxx)xxxxx=1; for(int i=0;in; tr0.clear(); for(i=1;is; set(s); out(0,0,); /system(pause); return 0;2.编译优化(compile.pas/c/cpp)【问题描述】众所周知，衡量一个编译器是否优秀的标准，除了它的编译速度和正确性以外，编译出的代码的质量也很重要。最近，作为XCC系列编译器作者的Dr. X发明了一种跨时代的优化算法：“NanGe不等式优化”。一个程序可以看成是由若干个连续的函数构成的，NanGe不等式算法能针对某一个函数进行优化，得到一个优化效果值, 不同的函数的效果值可能是不同的。但这个算法还有一个很大的Bug：该算法不能同时优化相邻的两个函数，否则就会直接Compile Error，值得注意的是，一个程序的第一个函数和最后一个函数也算是相邻的。现在给你一个程序从头到尾每个函数的优化效果值，Dr. X想用NanGe不等式对该程序的M个函数进行优化，他该怎么选择才能使总的优化效果值最大（前提是不能出现错误）？如果错误不能避免，请输出“Error!”【输入文件】输入文件的第一行包含两个正整数n、m。第二行为n个整数Ai。【输出文件】输出文件仅一个整数，表示最后对该程序进行优化后的最大效果值。如果无解输出“Error!”，不包含引号。【样例输入输出1】compile.incompile.out7 31 2 3 4 5 6 715【样例输入输出2】compile.incompile.out7 41 2 3 4 5 6 7Error!【数据规模】对于全部数据：m=n；-1000=Ai=1000N的大小对于不同数据有所不同：数据编号N的大小数据编号N的大小1401120132451250003501310000455144999952001511111162001614888871000171888888201018199999920111919999910201220200000【精炼任务】：给出由n个数组成的环，取某个数就可以得到它的分数，相邻的两个数不能同时取。问取m个数可以得到的最大分数。 对于前8个数据，我们采用搜索方法可以解决，但搜索的效率直接决定得分。我想到的优化有两点：1排序、2剪枝。（很简单，不详细说，详见程序） 特别的，如果这个环上的点是偶数个，我们可以把此题转化为带权匹配。在环上两个数之间建点，点恰好有n个，可以黑白染色构成二分图。而把数当做边。在这个图做带权匹配就是最后结果了。（由于匹配中同一个点引出的两条边是不可能同时取到的，这正好符合了相邻两个数不能同时取的性质） 符合这个算法的数据有：1、3、5、7、9、10、11（O(n4)）。如果带权匹配写的好（O(n3)外加系数小），可以再过13、15、17三个点。 我们再考虑这个题的简单版：在一个长度为n的数列中，选m个数，两个相邻的数不能同时选，要求取数的和最大。（即把原题的环改为链） 如果我们选取的数的集合叫C。C一开始是空集，每一次取数操作就会让C集合中多一个数，直到够m个数为止。而每次取数时，如果要取的这个数x左边右边都没被取，那这个数就可以直接取走，x就是取这个数带来的价值；如果这个要取的数x的左边的数y（右边完全一样，这里略）已经被取走了，那y必定要放回去，而把y左边的数z取出来以保证本次操作能让C集合多一个数，若z的左边的数w也被取了，那我们再用w左边的数代替，总之我们进行了一个类似01翻转的操作，使C集合多了一个数。而我们取这个数使C集合的总和增加的量，就是取这个数能带来的价值。我们可以证明：每次操作带来的价值，一定是单调递减的（挺显然的）。所以我们可以用贪心的方法，取够m个为止，并且保证算法是正确的。 接下来是考虑时间复杂度，暴力做是O(N2)。我们也可以用线段树（或者堆）来维护这一操作，从而达到O(NLogN)的时间复杂度。 回到原问题环。直接用这个算法是行不通的，因为在环上，左边进行的01翻转和右边进行的01翻转可能会相遇！最后就会导致两个1相邻。 我们可以想到一个略暴力的方法：枚举每一个数，不要它！把这个数剔除后所形成的链，通过刚才的算法求出不取这个数的情况下的最优值。最后一定可以得到最优值。这样时间复杂度为O(N2*LogN)。 在这个算法的基础上，稍作优化，就可以得到一个很好的算法：我们考虑两个相邻的数a和b，分三种情况：a和b都取（题目不允许）、不取a、不取b（虽然后两者有重叠，但包含了所有情况）。也就是说，我们并不需要枚举每一个数不要它，只需要针对两个相邻的数a和b，比较不要a的最优值更好还是不要b的最优值更好就可以了。最终复杂度为O(NLogN)。【题目考点】贪心+双向链表+堆优化【方法1】对于前4个数据，我们采用搜索方法可以解决，但搜索的效率直接决定得分。【方法2】动态规划，设fij0表示前i个位置选择j个种树且第i个位置没有种树,fij1表示表示前i个位置选择j个种树且第i个位置必须种树，则转化为非常简单的O(n2)动规，转台转移方程为：fij0=max(fi-1j0,fi-1j1);fij1=fij-10;【方法3】这个题标准解法是借鉴网络流中的残余流思想，用堆来维护解决。映射建大根堆，记录每一个数值在堆中的位置好方便删除操作。每回出堆顶元素后，ak=alk+ark-ak,lk和rk是k的左边节点和右边节点，即双链表思想，再将alk和ark删除，将新的ak加入堆中。#includeusing namespace std;int n,m;int L200001,R200001;int d200001,pos200001,a200001;void up(int x) int i=x; while(i1&adiadi/2) swap(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/2m)coutError!;return 0; for(i=1;iai; di=i;posi=i;up(i); Li=i-1;Ri=i+1; L1=n;Rn=1; int ans=0; while(m-) int x=d1; ans+=ax; ax=aLx+aRx-ax; aLx=-1111;down(posLx); aRx=-1111;down(posRx); down(1); Lx=LLx; Rx=RRx; RLx=x; LRx=x; coutans; /system(pause); return 0;3.过路费（cost.pas/c/c+）【问题描述】在某个遥远的国家里，有n个城市。编号为1,2,3,n。这个国家的政府修建了m条双向道路，每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为2，B到C长度为3，那么开车从A经过B到C需要上交的过路费为3。佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。【输入文件】第一行是两个整数n 和m，分别表示城市的个数以及道路的条数。 接下来m行，每行包含三个整数 a，b，w（1a，bn，0w109），表示a与b之间有一条长度为w的道路。 接着有一行为一个整数q，表示佳佳发出的询问个数。 再接下来q行，每一行包含两个整数S，T（1S,Tn，ST）, 表示开始城市S和目的城市T。 【输出文件】输出文件共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。【样例输入输出】cost.incost.out4 51 2 101 3 201 4 1002 4 303 4 1021 44 12020【数据范围】对于30%的数据，满足1 n1000，1m10000，1q100；对于50%的数据，满足1 n10000，1m10000，1q10000； 对于100%的数据，满足1 n10000，1m100000，1q10000；【题目大意】给定一个无向图。求任何一个点对(s,t)所有路径中最大边最小的那条路径，并求出此时的最大边。询问非常多，要求快速计算。【思路点拨】一般多询问的问题要么是具有比较短的时间内可以在线获得答案，要么是用很多时间来处理然后用极短的时间来获得答案。那我们先来想下在线算法。【一般做法】求最大边最小？二分！设最大边为w，把=w的所有边重新构图，如果s,t连通，则w是一种符合的最大边。二分这个最大边。我们可以求出该最大边的最小值。复杂度O(Q*(|V|+|E|)*log(|E|)可以过50%的数据；【一个定理】定理：图G的(s,t)之间的最小最大边，一定是其在最小生成树中(s,t)的路径上的最大边。证明：反证法，设(s,t)之间的最小最大边权值为minW。1.假设最小生成树中(s,t)的路径上的最大边maxWminW。则跟maxW是最小生成树的边矛盾，因为在添加maxW之前minW已经添加了。【方法1】转成LCA+RMQ于是我们可以先构造出这个图的一棵最小生成树。然后问他就转为求树上任意两点的最大边权LCA+RMQ【算法】求二叉树上任意两点的最短路径上的边权最大值【问题】给出一棵树，每条边有一边权。对于任意给定的两点，求此两点的最短路径上边权的最大值。 对于下图：蓝圈中任意一点与红圈中任意一点的路径上的最大边必定是8。 根据这个现象，可以把上述的树重建成如下图所示。新图的叶子结点为原图的所有结点，内部结点为原图的边权，建边顺序为从小到大。如图所示：新图的红色编号为原图的结点编号，蓝色编号为原图的边。这样，问题就转换为求新图中，任意两个叶子节点的最小公共祖先问题了。【分析时间复杂度】：对于一棵树，n个结点，m条边，n=m-1。1、对所有的边进行排序：O(mlgm)；2、建图采用并查集维护集合，并查集当前集合的根结点时间复杂度平均为O(1)，建图一共要建立n+m个点，所以时间复杂度为O(n+m)；3、查询任意两个结点的最近公共祖先，采用RMQ处理，预处理的时间复杂度为O(n+m)，回答时间复杂度为O(1)；所以，总的时间复杂度O(nlogn)。#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(fax=x)return x;return fax=get(fax);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) dx=deep;fx=1;lax0=fa;Maxx0=lenw; for(int i=1;lalaxi-1i-1;i+) laxi=lalaxi-1i-1; Maxxi=maxi(Maxxi-1,Maxlaxi-1i-1); for(int k=firx;k;k=nextk) if(!fpointk)dfs(pointk,x,k,deep+1);int ask(int x,int y) int ans=0,i;if(dxdy)int tmp=x;x=y;y=tmp; for(i=logn-1;i=0;i-) if(layi&dlayi=dx) ans=maxi(ans,Maxyi);y=layi; if(dlayi=dx)break; if(x=y)return ans; for(i=logn-1;i=0;i-)if(layi&laxi&(layi!=laxi) ans=maxi(ans,Maxyi);y=layi; ans=maxi(ans,Maxxi);x=laxi; ans=maxi(ans,maxi(Maxy0,Maxx0); return ans;int main() freopen(cost.in,r,stdin); freopen(cost.out,w,stdout); scanf(%d%d,&n,&m); for(i=1;i=m;i+)scanf(%d%d%d,&ei.u,&ei.v,&ei.c); for(i=1;i=n;i+)fai=i;qsort(e+1,m,sizeof(edge),CMP); for(i=1;i=m;i+) int p=get(ei.u),q=get(ei.v); if(p!=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;i=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,tMaxN,qMaxN,rMaxN;int heMaxM,hqMaxN,hrMaxN;int fatherMaxN,mvMaxN,markMaxN;int ansMaxN;int N,M,Q,e0=0,q0=0,r0=0;void Addq(int x,int y,int z) q0+; qq0.a=y; qq0.b=hqx; hqx=q0; qq0.c=z;void Adde(int x,int y,int z) e0+; ee0.a=y; ee0.b=hex; hex=e0; ee0.c=z;void Addr(int x,int y) r0+; rr0.a=y; rr0.b=hrx; hrx=r0;void Read() int i;scanf(%d%d,&N,&M);for(i=1;i=M;i+) scanf(%d%d%d,&wi.a,&wi.b,&wi.c);scanf(%d,&Q);for(i=1;i=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(i=j) while(wi.cMid) i+; while(Midwj.c) j-;if(i=j) swap(wi+,wj-);if(Lj) Qsort(L,j);if(iR) 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;i=N;i+)fatheri=i;Qsort(1,M);for(i=1;i=M;i+) r1=Find(wi.a);r2=Find(wi.b);if(r1!=r2)fatherr2=r1; Adde(r1,r2,wi.c);Adde(r2,r1,wi.c);void Tarjan(int x,int fa) int i,y,r1,r2;fatherx=x;mvx=0;for(i=hex;i;i=ei.b)y=ei.a;if(y=fa)continue;Tarjan(y,x);fathery=x;mvy=ei.c;markx=1;for(i=hqx;i;i=qi.b)y=qi.a;if(marky)Addr(Find(y),qi.c);for(i=hrx;i;i=ri.b)r1=tri.a.a;r2=tri.a.b;Find(r1); Find(r2);ansri.a=max(mvr1,mvr2);void Solve() Rebuild();Tarjan(1,0);for(int i=1;i=Q;i+)printf(%dn,ansi);int main() freopen(cost.in,r,stdin); freopen(cost.out,w,stdout);Read();Solve();return 0;【方法3】#include #include #include using