ACM第四次比赛题目及标准程序（STL模板类）

题目描述

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.

魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.

输入

输出

样例输入

1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0

样例输出

11

[cpp] view plain copy

 


#include <stdio.h>    
#include <string.h>    
#include <queue>    
using namespace std;    
const int N = 55;    
    
int map[N][N][N];    
int vis[N][N][N];    
int tx[] = {1,-1,0,0,0,0};    
int ty[] = {0,0,1,-1,0,0};    
int tz[] = {0,0,0,0,1,-1};    
int a,b,c,t,ans;    
    
struct Node    
{    
    int x,y,z,step;    
};    
    
int abs(int x)//绝对值    
{    
    return x<0?-x:x;    
}    
    
int check(int i,int j,int k)//判断是否可行    
{    
    if(i<0 || j<0 || k<0 || i>=a || j>=b || k>=c || map[i][j][k])    
    return 0;    
    return 1;    
}    
    
int bfs(int x,int y,int z)    
{    
    int i;    
    queue<Node> Q;    
    Node p,q;    
    p.x = x;    
    p.y = y;    
    p.z = z;    
    p.step = 0;    
    vis[x][y][z] = 1;    
    Q.push(p);    
    while(!Q.empty())    
    {    
        p = Q.front();    
        Q.pop();    
        if(p.x == a-1 && p.y == b-1 && p.z==c-1 && p.step<=t)    
        return p.step;    
        for(i = 0;i<6;i++)    
        {    
            q = p;    
            q.x+=tx[i];    
            q.y+=ty[i];    
            q.z+=tz[i];    
            if(!vis[q.x][q.y][q.z] && check(q.x,q.y,q.z))    
            {    
                q.step++;    
                vis[q.x][q.y][q.z] = 1;    
                if(abs(q.x-a+1)+abs(q.y-b+1)+abs(q.z-c+1)+q.step>t)//由于行走只能朝6个固定方向，这里是对剩下时间里能否走到出口进行预判，如果走最短路径依然不能再规定时间内到达出口，明显是不行的,当然不加这个判断也能AC，只是比较消耗时间    
                continue;    
                Q.push(q);    
            }    
        }    
    }    
    return -1;    
}    
    
int main()    
{    
    int cas;    
    scanf("%d",&cas);    
    while(cas--)    
    {    
        int i,j,k;    
        scanf("%d%d%d%d",&a,&b,&c,&t);    
        memset(map,0,sizeof(map));    
        memset(vis,0,sizeof(vis));    
        for(i = 0;i<a;i++)    
        for(j = 0;j<b;j++)    
        for(k = 0;k<c;k++)    
        scanf("%d",&map[i][j][k]);    
        ans = bfs(0,0,0);    
        printf("%d\n",ans);    
    }    
    
    return 0;    
}    



题目 B: 表达式求值

时间限制: 3 Sec  内存限制: 6 MB


题目描述

实现输入一个表达式求出它的值的计算器，比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）


输入
第一行输入一个整数n，共有n组测试数据（n<10)。 每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。 数据保证除数不会为0

输出
每组都输出该组运算式的运算结果，输出结果保留两位小数。

样例输入
2
1.000+2/4=
((1+2)*5+1)/4=

样例输出

1.50
4.00




[html] 
view plain 
copy







#include <stdio.h>    


#include <stdlib.h>    


#include <string.h>    


#include <math.h>    


#include <stack>    


using namespace std;    


stack<char> osta;//定义一个char类型的字符栈    


stack<double> dsta;//定义一个double类型的数据栈    


int main()    


{    


    int T;    


    scanf("%d",&T);    


    while(T--)    


    {    


        char s[1030];    


        scanf("%s",&s[1]);//从下标1开始读入    


        int len=strlen(&s[1]);    


        s[0]='(';s[len]=')';//把读入的表达式左端用“（”括起来，右端的等号换成“）”    


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


        {    


            if(s[i]=='(')    


                osta.push(s[i]);//是左括号则压入字符栈中    


            else if(s[i]>='0'&&s[i]<='9')    


            {    


                int b,K=0;    


                double v=0;    


                while(s[i]>='0'&&s[i]<='9'||s[i]=='.')    


                {    


                    if(s[i]=='.')//判断是否是小数点    


                    {    


                        b=i;//记录小数点的位置    


                        K=1;//标记    


                    }    


                    else    


                        v=v*10+s[i]-'0';    


                    i++;    


                }    


                i--;    


                if(K==1)    


                    dsta.push(v/pow(10,i-b));    


                else    


                    dsta.push(v);    


            }    


            else if(s[i]=='+'||s[i]=='-')    


            {    


                while(osta.top()!='(')//判断栈顶元素，同下    


                {    


                    double a=dsta.top();dsta.pop();    


                    double b=dsta.top();dsta.pop();    


                    double c;    


                    switch(osta.top())    


                    {    


                        case '+':c=b+a;break;    


                        case '-':c=b-a;break;    


                        case '*':c=b*a;break;    


                        case '/':c=b/a;break;     


                    }    


                    dsta.push(c);    


                    osta.pop();    


                }    


                osta.push(s[i]);    


            }    


            else if(s[i]=='*'||s[i]=='/')    


            {    


                if(osta.top()=='*')    


                {    


                    double a=dsta.top();dsta.pop();    


                    double b=dsta.top();dsta.pop();    


                    dsta.push(b*a);    


                    osta.pop();    


                }    


                else if(osta.top()=='/')    


                {    


                    double a=dsta.top();dsta.pop();    


                    double b=dsta.top();dsta.pop();    


                    dsta.push(b/a);    


                    osta.pop();    


                }    


                osta.push(s[i]);    


            }    


            else if(s[i]==')')    


            {    


                while(osta.top()!='(')    


                {    


                    double a=dsta.top();dsta.pop();    


                    double b=dsta.top();dsta.pop();    


                    double c;    


                    switch(osta.top())    


                    {    


                        case '+':c=b+a;break;    


                        case '-':c=b-a;break;    


                        case '*':c=b*a;break;    


                        case '/':c=b/a;break;    


                    }    


                    dsta.push(c);    


                    osta.pop();    


                }    


                osta.pop();    


            }    


        }    


        printf("%.2lf\n",dsta.top());    


        dsta.pop();//弹出最后数据，以免影响下一次运算    


    }    


    return 0;    


}    










题目 C：Train



时间限制: 1 Sec  内存限制: 33 MB





题目描述


As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the
 world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway
 before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway
 in an order O1, your task is to determine whether the trains can get out in an order O2.







输入


The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input
 is terminated by the end of file. More details in the Sample Input.







输出


The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting
 into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.





样例输入

3 123 321
3 123 312

样例输出

Yes.
in
in
in
out
out
out
FINISH
No.
FINISH



[html] 
view plain 
copy







#include<iostream>    


#include<stack>    


#define max 100    


using namespace std;    


int main()    


{    


    stack<char>s;    


    int n,i,j,k,result[max];//n为列车个数， result数组用来表示结果，1表示进栈。0表示出    


    char str1[max],str2[max];//序列1和序列2    


    while(cin>>n>>str1>>str2)    


    {    


        j=0,i=0,k=1;    


        s.push(str1[0]);//为防止栈空，压一个进去    


        result[0]=1;//记录进来了一个。    


        while(i<n&&j<n)    


        {    


            if(s.size()&&s.top()==str2[j])    


            {//如果栈顶元素与序列2当前的元素相等，str2向后移一位 ，然后把str1放在栈里边的元素弹出来。    


                j++;    


                s.pop();    


                result[k++]=0;    


            }    


            else    


            {//栈顶元素跟str2当前的元素不一样的时候就把str1中的元素再压栈。    


                /**   


                 *  i == n-1 的时候也已经全部压栈过一次了 当 i == n的时候就说明不匹配   


                 */    


                if(i==n)    


                    break;    


                s.push(str1[++i]);    


                result[k++]=1;    


            }    


        }    


        if(i==n)    


        {//如果I==N表示栈顶元素不等于序列2当前元素，且序列1中元素都已经入过栈，判断不能得到序列2一样的答案。    


            cout<<"No."<<endl;    


        }    


        else    


        {//输出进出栈方式    


            cout<<"Yes."<<endl;    


            for(i=0; i<k; i++)    


                if(result[i])    


                    cout<<"in"<<endl;    


                else    


                    cout<<"out"<<endl;    


        }    


        cout<<"FINISH"<<endl;    


    }    


    return 0;    


}    






题目 D:
 情报分析
时间限制: 1 Sec  内存限制: 12 MB




题目描述



“八一三”淞沪抗战爆发后，*几次准备去上海前线视察和指挥作战。但都因为宁沪之间的铁路和公路遭到了敌军的严密封锁，狂轰滥炸，一直未能成行。 特科组织，其主要任务是保卫的安全，了解和掌握敌方的动向。经过一段时间的监听，谍报组获取了敌方若干份密报，经过分析，发现密文中频繁出现一些单词，情报人员试图从单词出现的次数中，推出敌军的行动计划。 请你编程，快速统计出频率高的前十个单词。





输入


密文是由英语单词（小写字母）组成，有若干段。单词之间由一个或多个空格分开，自然段之后可以用一个“，”或“。”表示结束。整个内容的单词数量不超过10000，不同的单词个数不超过500.






输出


输出占10行，每行一个单词及出现的次数，中间一个空格。要求按频率降序输出，出现次数相同的单词，按字典序输出。






样例输入

shooting is at shanghai station. shooting must 
be carried out. shooting shooting. 
shanghai station must be surrounded, at least a team of one hundred soldiers to fight. twenty five soldiers shooting in the north, twenty five soldiers shooting in the south, twenty five soldiers shooting in the east, twenty five soldiers shooting in the west. 

样例输出

shooting 8 
soldiers 5 
five 4 
in 4 
the 4 
twenty 4 
at 2 
be 2 
must 2 
shanghai 2 



[html] 
view plain 
copy







#include <algorithm>    


#include <iostream>    


#include <string>    


#include <map>    


#include<cstring>   


#include <cstdio>    


  


using namespace std;    


struct node//定义结构体存放各个单词的情况    


{    


    char str[100];    


    int count;    


}word[1000];    


int N=0;    


int cmp(node w1,node w2)    


{    


    if(w1.count!=w2.count)//比较出现数目的多少，大者在前，小者在后    


        return w1.count>w2.count;    


    else//如果出现数目相等，按照字典序排序    


    {    


        int a=strcmp(w1.str,w2.str);    


        if(a>0)    


            return 0;    


        else    


            return 1;    


    }    


}    


int main()    


{    


    map <string,int> m;//定义map来接收并记录输入的数据    


    map <string,int>::iterator it;//定义迭代器    


    char str[100];    


    while(scanf("%s",str)!=EOF)    


    {    


        int len=strlen(str);    


        if(str[len-1]==','||str[len-1]=='.')//如果末尾字符是','或'.'，将其清除    


            str[len-1]='\0';    


        string s=str;    


        m[s]++;//将此单词出现的次数++    


    }    


    for(it=m.begin(); it!=m.end(); it++)    


    {    


        string s=(*it).first;    


        int count=(*it).second;    


        strcpy(word[N].str,s.c_str());    


        word[N++].count=count;//将map中存放的数据放入结构体中    


    }    


    sort(word,word+N,cmp);//将结构体排序    


    for(int i=0; i<10; i++)//输出前10个元素    


    {    


        printf("%s %d\n",word[i].str,word[i].count);    


    }    


    return 0;    


}  




题目E: Information Sharing
时间限制: 3 Sec  内存限制: 65 MB




题目描述



There is going to be a test in the kindergarten. Since the kids would cry if they get a low score in the test, the teacher has already told every kid some information about the test in advance. But the kids are not satisfied with
 the information teacher gave. They want to get more. On the testing day, some kids arrived to the classroom early enough, and then shared his/her information with another. kids are honest, if A shares with B, B can get all the information A knows, so does
 A. At first the classroom is empty. As time pass by, a kid would arrive, or share information with other. However, the teacher hides somewhere, watching everything. She wants to know how much information some kid has gotten.





输入


There are multiple cases. The first line of each case contains an integer n, indicating there is n actions. The following n actions contain 3 types. 1: "arrive Name m a1 a2 ..am", means the kid called
 Name arrives at the classroom. He has m information, their id is a1 a2 ...am. 2: "share Name1 Name2", means that the kids called Name1 and Name2 share their information. (The sharing state will keep on, that means, if A share with B, later B share with C,
 A can also get all C's information via B. One kid may share with himself, but it doesn't mean anything.) 3: "check Name", means teacher wants to know the number of information kid called Name has got. n is less than 100000, and is positive. The information
 id is among [0,1000000]. Each Name has at most 15 characters. There would appears at most 1000 distinct information. Each kid carry no more than 10 information when arriving(10 is included).






输出


For every "check" statement, output a single number. If there's no check statement, don't output anything.






样例输入

8
arrive FatSheep 3 4 7 5
arrive riversouther 2 4 1
share FatSheep riversouther
check FatSheep
arrive delta 2 10 4
check delta
share delta FatSheep
check riversouther


样例输出

4
2
5

提示



check 1: FatSheep has 1 4 5 7, having all the information. So answer is 4.

check 2: delta has only 4 10 , doesn't have 1 5 7. So answer is 2

check 3: riversouther has 1 4 5 7 10, having all the information. So answer is 5





[cpp] 
view plain 
copy







#include <stdio.h>    


#include <set>    


#include <map>    


#include <string.h>    


#include <string>    


    


using namespace std;    


int fa[100005];    


set <int>   s[100005];    


map <string,int>   m;    


    


int main(){    


    int n,countn;    


    int i,j,q;    


    char command[20],str2[20],str3[20];    


    


    while(scanf("%d",&n) != EOF){    


        for(i = 0;i < 100005;i++){    


            fa[i] = i;    


            s[i].clear();    


        }    


        m.clear();    


        countn = 0;    


        while(n--){    


            scanf("%s",command);    


            if(command[0] == 'a'){    


                scanf("%s",str2);    


                m[str2] = countn;    


                scanf("%d",&q);    


                while(q--){    


                    int tem;    


                    scanf("%d",&tem);    


                    s[countn].insert(tem);    


                }    


                countn++;    


            }    


            else if(command[0] == 'c'){    


                scanf("%s",str2);    


                int p = m[str2];    


                while(fa[p] != p)    


                    p = fa[p];    


                m[str2] = p;    


                printf("%d\n",s[p].size());//集合的大小，即是所求的答案    


            }    


            else{    


                scanf("%s%s",str2,str3);    


                int p2 = m[str2];    


                int p3 = m[str3];    


                while(fa[p2] != p2)    


                    p2 = fa[p2];    


                while(fa[p3] != p3)    


                    p3 = fa[p3];    


                if(p2 == p3)    //这一个地方很重要，如果这两个是同一个集合,    


                    continue;   //就不要再进行下面的操作，否则会出错    


                while(!s[p2].empty()){    


                    int tem = *s[p2].begin();    


                    s[p3].insert(tem);    


                    //如果集合中已经存在tem，则这个插入操作是无效的    


                    //就是利用这条性质来求集合的并集    


                    s[p2].erase(tem);    


                }    


                m[str2] = p3;    


                m[str3] = p3;    


                fa[p2] = p3;    


            }    


        }    


    }    


}   







题目 F: The Intervals



时间限制: 2 Sec  内存限制: 65
 MB





题目描述



Cantor, the famous mathematician, was working on a problem about intervals. Let's start from a line segment of unit length. Remove its middle 1/3. Now remove the middle 1/3's from the remaining two segments. Now remove the middle
 1/3's from the remaining four segments. Now remove the middle 1/3's from the remaining eight segments. Now remove ... well, you get the idea. If you could continue this procedure through infinitely many steps, what would you have left? Now he assigns the following
 task to you. (He asked me to pass his assignment to you last night.) Given two arrays of numbers {A(n)} and {B(m)}. For each B(i) in {B(m)}, find 2 numbers a and b from {A(n)}, such that B(i) is in [a,b) and b-a<=|b'-a'| for all a' and b' from {A(n)} such
 that [a',b') contains B(i).





输入


There are several test cases. In each test case, the first line gives n and m. The second line contains n numbers, which are the elements of {A(n)}. The third line contains m nubmers, which are the elements of {B(m)}.






输出


For each B(i) in {B(m)}, output a line containing the interval [a,b). If there is no such interval, output "no such interval" instead. Print a blank line after each test case.






样例输入

3 3
10 20 30
15 25 35


样例输出

[10,20)
[20,30)
no such interval






[cpp] 
view plain 
copy







#include<iostream>    


using namespace std;    


#include<algorithm>    


    


int n,m;    


    


int find(int *a,int x)    


{    


    if(x<a[0] || a[n-1]<=x)return -1;    


    return  lower_bound(a,a+n,x)-a;    


}    


    


int main()    


{    


    int a[10001];    


    while(cin>>n>>m)    


    {    


        int i,j;    


        for(i=0;i<n;i++)    


            cin>>a[i];    


        sort(a,a+n);    


        for(i=0;i<m;i++)    


        {    


            int b;    


            cin>>b;    


            j=find(a,b);    


            if(a[j]!=b)j=j-1;    


            if(j>=0)    


            cout<<"["<<a[j]<<","<<a[j+1]<<")"<<endl;    


            else    


                cout<<"no such interval\n";    


        }    


         


    }    


    return 0;    


}    




题目G: 懒省事的小名
时间限制: 1 Sec  内存限制: 12 MB




题目描述



小名总结了一个英语近义词的词典（很厚哦，有多厚，你猜），词典实在太厚了，你需要帮助他写一个程序，输入一个单词，输出它的近义词





输入



第一行输入近义词的个数N和小名要查询的行数M

接下来N行为近义词对

M行单词，根据单词，输出它的近义词





输出


输出近义词，每个近义词占一行






样例输入

2 2
abc	cba
aaa	bbb
abc
aaa

样例输出

cba
bbb





[html] 
view plain 
copy







#include<iostream>  


#include<map>  


#include<cstring>  


#include<string>  


#include<algorithm>  


using namespace std;  


int main()  


{  


    int N, M;  


    string a, b,c;  


    map<string, string> mp;  


    while(scanf("%d%d",&N,&M)!=EOF){  


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


        {  


            cin>>a>>b;  


            mp[a] = b;  


        }  


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


        {  


            cin>>c;  


            map<string,string>::iterator it;  


            for(it=mp.begin();it!=mp.end();it++)  


            {  


                if(it->first == c)   


                {  


                    cout<<it->second<<endl;  


                    break;  


                }else if(it->second == c){  


                    cout<<it->first<<endl;  


                    break;  


                }                             


            }  


        }  


          


          


    }  


      


 }