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

更新时间:2023-07-28 06:05:14 阅读：评论：0

信息学奥林匹克联赛（NOIP2011）八校联军复赛模拟二

提高组第二试

2011年10月7日 8：30-11：30

（请选手务必仔细阅读本页内容）

一、题目概况

中文题目名称	文件列表	编译优化	收费站
英文题目名称	file	compile	cost
可执行文件名	file	compile	cost
鬼哭狼嚎输入文件名	file.in	compile.in	cost.in
输出文件名	file.out	compile.out	cost.out
每个测试点时限	1秒	1秒	1秒
测试点数目	10	20	10
每个测试点分值猛烈刺入	10	5	10
附加样例文件	有	有	有
结果比较方式	全文比较过滤行末空格及文末回车	全文比较过滤行末空格及文末回车	全文比较过滤行末空格及文末回车
题目类型	传统	传统	传统

二、提交源程序文件名

对于pascal语言	file.pas	compile.pas	cost.pas
对于C语言	file.c	compile.c	cost.c
对于C++语言	file.cpp	compile.cpp	cost.cpp

三、编译命令（不包含任何优化开关）

查看防火墙状态

对于pascal语言	fpc file.pas	fpc compile.pas	fpc cost.pas
对于C语言	gcc –o file file.c -lm	gcc –o compile compile.c -lm	gcc –o cost cost.c -lm
对于C++语言	g++ -o file file.cpp -lm	g++ -o compile compile.cpp -lm	g++ -o cost 微信心情说说短句 cost.cpp -lm

四、运行内存限制

内存上限	256M	256M	256M

五、注意事项数学小论文五年级

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 //空文件夹

|----vb

生成的列表格式有如下要求:

1.属于同一层的文件或文件夹位于相同的缩进处，相邻两层文件间差距5个字符；

2.每个文件夹或文件前有4个'-'(根目录除外)，文件夹下方属于文件夹的部分有'|'；

节水知识3.属于统一文件夹下的文件或子文件夹按字典序排列；

【文件输入】

第一行一个整数n（n<=50），表示总共的文件数目；

接下来n行，每行描述一个文件的路径，路径以'/'作为文件分隔符；

所有文件（及文件夹）名均由小写字母和英文点组成；

所有输入的根目录都是一样的，文件名长度不超过10个字符，每个文件夹下不超过15个文件，不超过5层。

【文件输出】

输出符合要求的文件列表

【样例输入输出】

file.in	file.out
5 mydoc/ mydoc/dd/libexec.a mydoc/stdio.h mydoc/abcd/zzz/game.cpp mydoc/abcd/new	mydoc \|----abcd \| \|---- \| \|----new \| \|----zzz \| \| \|----game.cpp \|----dd \| \|----libexec.a \|----stdio.h

【数据范围】

对于30%的数据,根目录下只有文件，没有文件夹

【注意】此题有special judge，全文比较过滤行末空格及文末回车。

【题目考点】字符串处理，trie树+递归

【题目分析】

本题可以用trie树或者模拟trie树解决。可以选择以单个字母作为节点，在每一个文件夹结尾处做标记，但输出时非常难处理。

第二种以文件名即字符串为节点，从根目录往下查找，若当前父节点中能够找到st，则将父节点中st的编号作为新的父节点继续查找，若没有则新建一个节点，保存下st，以新建节点为父节点继续查找。

输出时从根目录递归搜索，先处理“| ”及“|----”，在对当前父节点的子节点排序，递归进行。

#include<iostream>

using namespace std;

struct trie{

bool end;

int c[28];

void clear(){memt(c,0,sizeof(c));end=0;}

}tr[600001];

int n,ct=0;

bool xxxxx=0;

int get(char x){if(x>='a'&&x<='z')return x-'a';el if(x=='.')return 26;el return 27;}

char getout(int x){if(x>=0&&x<=25)return x+'a';el return '.';}

void t(string s)

{ int sl=s.length();

int rt=0;

for(int i=0;i<sl;i++)

{ if(s[i]=='/'&&!tr[rt].end)tr[rt].end=1;

int k=get(s[i]);

中药合欢花图片 if(!tr[rt].c[k])

{ ct++;

tr[rt].c[k]=ct;

tr[ct].clear();

rt=ct;

}

el rt=tr[rt].c[k];

}

tr[rt].end=1;

}

void out(int rt,int ce,string x)

{ bool bj=0,k=tr[rt].end;

if(k){

if(xxxxx)

{ for(int j=1;j<ce;j++)cout<<"| ";

cout<<"|----";

}

cout<<x<<endl;

if(!xxxxx)xxxxx=1;

}

for(int i=0;i<=26;i++)

if(tr[rt].c[i])

{ string s=x;

s+=getout(i);

out(tr[rt].c[i],ce,s);

}

if(tr[rt].c[27])

out(tr[rt].c[27],ce+k,"");

}

int main()

{ int i;

string s;

cin>>n;

tr[0].clear();

捡拾幸福作文 for(i=1;i<=n;i++)

{ cin>>s;

t(s);

}

out(0,0,"");

//system("pau");

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.in	compile.out
7 3 1 2 3 4 5 6 7	15

【样例输入输出2】

compile.in	compile.out
7 4 1 2 3 4 5 6 7	Error!

【数据规模】

对于全部数据：m<=n；-1000<=Ai<=1000

N的大小对于不同数据有所不同：

数据编号	N的大小	数据编号	N的大小
1	40	11	2013
2	45	12	5000
3	50	13	10000
4	55	14	49999
5	200	15	111111
6	200	16	148888
7	1000	17	188888
8	2010	18	199999
9	2011	19	199999
10	2012	20	200000