总时间限制: 1000ms 内存限制: 65536kB描述输入一行单词序列，相邻单词之间由1个或多个空格间隔，请按照字母顺序输出这些单词（即按照字符串中字母的ASCII码排序，区分大小写，当首字母相同时，比较第2个字母，依次类推），要求重复的单词只输出一次。输入一行单词序列，最少1个单词，最多100个单词，每个单词长度不超过50，单词之间用至少1个空格间隔。输出按字母顺序输出这些单词，重复的单词只输出一次。样例输入She  wants  to go to Peking University to study  Chinese样例输出ChinesePekingSheUniversitygostudytowants

#include <iostream>#include <stdio.h>#include <cstring>#include <algorithm>using namespace std;char s[101][51]={0};int work(char* a,char *b){    int i = 0;    for( i=0;a[i]!=‘\0‘&&b[i]!=‘\0‘;i++)    {        if(a[i]<b[i])            return 1;        else if(a[i]>b[i])            return -1;    }    if(a[i]==‘\0‘&&b[i]==‘\0‘)        return 0;    else if(a[i]==‘\0‘)        return 1;    else        return -1;}int main(){    char c;    cin.get(c);    int i = 0;    while(1)    {        while(c==‘ ‘)            cin.get(c);        if(c==‘\n‘)            break;        cin.putback(c);        cin>>s[i++];        for(int j = i-1; j >=1; j-- )        {            if(work(s[j],s[j-1])>0)            {                char a[100];                strcpy(a,s[j]);                strcpy(s[j],s[j-1]);                strcpy(s[j-1],a);            }        }        cin.get(c);    }    for(int j = 0; j < i; j++)    {        if(work(s[j],s[j-1])==0&&j>0)        {            continue;        }        cout<<s[j]<<endl;    }    return 0;}

总时间限制: 1000ms 内存限制: 65536kB描述    2014年巴西世界杯（2014 FIFA World Cup）开踢啦！为了方便球迷观看比赛，里约街道上很多路口都放置了的直播大屏幕，但是人群散去后总会在这些路口留下一堆垃圾。为此巴西政府决定动用一种最新发明——“垃圾炸弹”。这种“炸弹”利用最先进的量子物理技术，爆炸后产生的冲击波可以完全清除波及范围内的所有垃圾，并且不会产生任何其他不良影响。炸弹爆炸后冲击波是以正方形方式扩散的，炸弹威力（扩散距离）以d给出，表示可以传播d条街道。    例如下图是一个d=1的“垃圾炸弹”爆炸后的波及范围。    假设里约热内卢市的布局为严格的1025*1025的网格状，由于财政问题市政府只买得起一枚“垃圾炸弹”，希望你帮他们找到合适的投放地点，使得一次清除的垃圾总量最多（假设垃圾数量可以用一个非负整数表示，并且除设置大屏幕的路口以外的地点没有垃圾）。输入输入第一行是整数T (1 <= T <= 10)，表明有T组测试数据。对于每一组测试数据，第一行给出“炸弹”威力d(1 <= d <= 50)。第二行给出一个数组n(1 <= n <= 20)表示设置了大屏幕(有垃圾)的路口数目。接下来n行每行给出三个数字x, y, i, 分别代表路口的坐标(x, y)以及垃圾数量i. 点坐标(x, y)保证是有效的（区间在0到1024之间），同一坐标只会给出一次。输出对于每组测试数据，输出能清理垃圾最多的投放点数目，以及能够清除的垃圾总量。样例输入1124 4 106 6 20样例输出1 30

#include <iostream>#include <stdio.h>#include <cstring>#include <algorithm>using namespace std;int n,d;int x[21],y[21],w[21];const int MIN = 0;const int MAX = 1000000;int mw = 0,coun = 0;void work(){    for(int i = 0; i <= 1024; i ++)    {        for(int j = 0; j <=1024; j ++)        {            int tem = 0;            for(int k = 0; k <n; k++)            {                if(x[k]<=i+d&&x[k]>=i-d&&y[k]<=j+d&&y[k]>=j-d)                    tem+=w[k];            }            if(tem>mw)            {                mw = tem;                coun = 1;            }            else if(tem == mw)                coun++;        }    }}int main(){    int t;    cin>>t;    while(t--)    {        memset(x,0,sizeof(x));        memset(y,0,sizeof(y));        memset(w,0,sizeof(w));        cin>>d;        cin>>n;        mw = 0;        coun = 0;        int minx = MAX,miny = MAX,maxx = MIN,maxy = MIN;         for(int i = 0; i < n; i ++)        {            cin>>x[i]>>y[i]>>w[i];            //if(minx>x[i])        }        work();        cout<<coun<<‘ ‘<<mw<<endl;    }    return 0;}

总时间限制: 1000ms 内存限制: 65536kB描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。输入第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。输出对输入的每组数据M和N，用一行输出相应的K。样例输入17 3样例输出8来源lwx@POJ

#include <iostream>#include <stdio.h>#include <cstring>#include <algorithm>using namespace std;int n,m;int s[11][11]={0};int work(int a,int b){    if(a<0)        return 0;    if(b==1)        return 1;    if(a==1||a==0)        return 1;        if(s[a][b]!=0)        return s[a][b];    s[a][b]=work(a,b-1)+work(a-b,b);    return s[a][b];}int main(){    int t;    cin>>t;    while(t--)    {        cin>>m>>n;        memset(s,0,sizeof(s));        cout<<work(m,n)<<endl;    }    return 0;}

总时间限制: 1000ms 内存限制: 65536kB描述There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can‘t move on red tiles, he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above. 输入The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. ‘.‘ - a black tile ‘#‘ - a red tile ‘@‘ - a man on a black tile(appears exactly once in a data set) The end of the input is indicated by a line consisting of two zeros. 输出For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).样例输入6 9....#......#..............................#@...#.#..#.11 9.#..........#.#######..#.#.....#..#.#.###.#..#.#..@#.#..#.#####.#..#.......#..#########............11 6..#..#..#....#..#..#....#..#..###..#..#..#@...#..#..#....#..#..#..7 7..#.#....#.#..###.###...@...###.###..#.#....#.#..0 0样例输出4559613来源Japan 2004 Domestic

#include <iostream>#include <stdio.h>#include <cstring>#include <algorithm>using namespace std;int n,m;char a[21][21]={0};int x,y;int coun = 0;int f[21][21]={0};void work(int i,int j){    if(f[i][j]!=‘#‘)    {        f[i][j] = 1;        coun++;    }    if(a[i-1][j]!=‘#‘&&f[i-1][j]==0&&i>0)        work(i-1,j);    if(a[i+1][j]!=‘#‘&&f[i+1][j]==0&&i<m-1)        work(i+1,j);    if(a[i][j-1]!=‘#‘&&f[i][j-1]==0&&j>0)        work(i,j-1);    if(a[i][j+1]!=‘#‘&&f[i][j+1]==0&&j<n-1)        work(i,j+1);}int main(){    while(cin>>n>>m)    {        if(n ==0 && m==0)            break;        coun = 0;        memset(a,0,sizeof(a));        memset(f,0,sizeof(f));        for(int i = 0; i < m; i ++)        {            cin.get();            for(int j = 0; j <n;j++)            {                cin.get(a[i][j]);                if(a[i][j] == ‘@‘)                {                    x = i;                    y = j;                }            }        }        /*for(int i = 0; i <m; i ++)        {            for(int j = 0; j <n;j++)            {                cout<<a[i][j];            }            cout<<endl;        }*/        work(x,y);        cout<<coun<<endl;    }    return 0;}

总时间限制: 200ms 内存限制: 65536kB描述将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。输入标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。 (0 < N <= 50, 0 < K <= N)输出对于每组测试数据，输出以下三行数据:第一行: N划分成K个正整数之和的划分数目第二行: N划分成若干个不同正整数之和的划分数目第三行: N划分成若干个奇正整数之和的划分数目样例输入5 2样例输出233提示第一行: 4+1, 3+2,第二行: 5，4+1，3+2第三行: 5，1+1+3， 1+1+1+1+1+1

#include <iostream>#include <stdio.h>#include <cstring>#include <algorithm>using namespace std;int a[51][51][51]={0};int k,n;int m[51][51][51]={0};int work(int p,int q,int b){    if(a[p][q][b]!=0)        return a[p][q][b];    if(q == 1 && p>=b)        return 1;    if(p/q<b)        return 0;    a[p][q][b] = 0;    for(int i = b; i <=p;i++)    {        int tem = work(p-i,q-1,i);        a[p][q][b] += tem;        if(tem == 0)            break;    }    return a[p][q][b];}int s[51][51][51]={0};int work1(int p,int q,int b){    if(s[p][q][b]!=0)        return s[p][q][b];    if(q == 1 && p>=b)        return 1;    if(p/q<b)        return 0;    s[p][q][b] = 0;    for(int i = b; i <=p;i++)    {        int tem = work1(p-i,q-1,i+1);        s[p][q][b] += tem;        if(tem == 0)            break;    }    return s[p][q][b];}int func(int p,int q,int b){    if(m[p][q][b]!=0)        return m[p][q][b];    if(q == 1 && p>=b && p%2!=0)        return 1;    else if(q==1 && p %2 == 0)        return 0;    if(p/q<b)        return 0;    m[p][q][b] = 0;    for(int i = b; i <=p;i+=2)    {        int tem = func(p-i,q-1,i);        m[p][q][b] += tem;        if(tem == 0)            break;    }    return m[p][q][b];}int main(){    while(cin>>n>>k)    {        memset(a,0,sizeof(a));        cout<<work(n,k,1)<<endl;        int tem = 0;        for(int i = 1; i <=n; i ++)        {            tem += work1(n,i,1);        }        cout<<tem<<endl;        tem = 0;        for(int i = 1; i <= n; i ++)        {            tem += func(n,i,1);        }        cout<<tem<<endl;    }    return 0;}

总时间限制: 1000ms 内存限制: 65535kB描述“红楼飞雪，一时英杰……”耳边传来了那熟悉的歌声。而这，只怕是我最后一次听到这个声音了。想当年，我们曾经怀着豪情壮志，许下心愿，走过静园，走过一体，走过未名湖畔的每个角落。想当年，我们也曾慷慨高歌，瞻仰民主与科学，瞻仰博雅塔顶，那百年之前的遗韵。没错，我爱北大，我爱这个校园。然而，从当我们穿上学位服的那一刻起，这个校园，就再也不属于我。它只属于往事，属于我的回忆。没错，这，是我在北大的最后一日。此时，此景，此生，此世，将刻骨难忘。再也没有了图书馆自习的各种纷纭，再也没有了运动场上的挥汗如雨，有的，只是心中永远的不舍，与牵挂。夜，已深。人，却不愿离去。天边有一颗流星划过，是那般静，宁谧。忍不住不回头，我的眼边，有泪光，划过。这时候，突然有一位路人甲从你身旁出现，问你：从XX到XX怎么走？索性，就让我再爱你一次。因为，北大永远在你心中。北大的地图，永远在你的心中。轻手挥扬，不带走一分云彩。输入输入分为三个部分。第一个部分有P+1行，第一行为一个整数P，之后的P行表示北大的地点。第二个部分有Q+1行，第一行为一个整数Q，之后的Q行每行分别为两个字符串与一个整数，表示这两点有直线的道路，并显示二者之间的矩离（单位为米）。第三个部分有R+1行，第一行为一个整数R，之后的R行每行为两个字符串，表示需要求的路线。p < 30,Q < 50,R < 20输出输出有R行，分别表示每个路线最短的走法。其中两个点之间，用->(矩离)->相隔样例输入6XueYiShiTangCanYinZhongXinXueWuShiTangXueYiXiaoBaiFangBaiNianJiangTangGongHangQuKuanJi6XueYiShiTang CanYinZhongXin 80XueWuShiTang CanYinZhongXin 40XueYiShiTang XueYiXiaoBaiFang 35XueYiXiaoBaiFang XueWuShiTang 85CanYinZhongXin GongHangQuKuanJi 60GongHangQuKuanJi BaiNianJiangTang 351XueYiXiaoBaiFang BaiNianJiangTang样例输出XueYiXiaoBaiFang->(35)->XueYiShiTang->(80)->CanYinZhongXin->(60)->GongHangQuKuanJi->(35)->BaiNianJiangTang

#include <iostream>#include <stdio.h>#include <cstring>#include <algorithm>using namespace std;int n,p,q;char s[31][50]={0};int d[31][31]={0},f[31]={0},pre[31]={0},dis[31]={0};const int MAX = 1000000;int so,des;void prin(int i){    if(i==so)    {        cout<<s[i];        return ;    }    prin(pre[i]);    cout<<"->("<<d[pre[i]][i]<<")->"<<s[i];    return ;}int main(){    cin>>n;    for(int i = 0; i < n; i++)    {        cin>>s[i];    }    for(int i = 0; i < n; i ++)    {        for(int j = 0; j < n; j++)        {            d[i][j]=MAX;            if(i == j)                d[i][j]=  0;        }    }    cin>>p;    for(int i = 0; i < p; i ++)    {        char a[50],b[50];        int w;        cin>>a>>b>>w;        int x,y;        for(int j = 0; j < n ; j++)        {            if(strcmp(a,s[j])==0)                x = j;            if(strcmp(b,s[j])==0)                y = j;        }        d[x][y] = w;        d[y][x] = w;    }    cin>>q;    for(int i =0; i <q; i++ )    {        char a[50],b[50];        cin>>a>>b;        int x,y;        for(int j = 0; j < n ; j++)        {            if(strcmp(a,s[j])==0)                x = j;            if(strcmp(b,s[j])==0)                y = j;        }        so = x;        des = y;        memset(f,0,sizeof(f));        memset(pre,0,sizeof(pre));        for(int j = 0; j < n; j++ )        {            dis[j] = d[x][j];            if(d[x][j] == 0)                dis[j] = MAX;            else                pre[j] = x;                    }        dis[x] = 0;        f[x] = 1;        while(1)        {            int m = MAX,inde = 0;            for(int j = 0; j < n; j ++)            {                if(dis[j]<m&&f[j] == 0)                {                    m = dis[j];                    inde = j;                }            }            f[inde] = 1;            for(int j = 0; j < n; j ++)            {                if(d[inde][j]+dis[inde] < dis[j])                {                    dis[j] = d[inde][j]+dis[inde];                    pre[j] = inde;                }            }            if(inde == y)                break;        }        prin(des);        cout<<endl;    }    /*char a[50],b[50];    cin>>a>>b;    cout<<strcmp(a,b)<<endl;*/    return 0;}

总时间限制: 1000ms 内存限制: 65535kB描述众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：   +  / a   *    /     b c现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。输入输入分为三个部分。第一部分为一行，即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。第二部分为一个整数n(n < 10)，表示中缀表达式的变量数。第三部分有n行，每行格式为C　x，C为变量的字符，x为该变量的值。输出输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（\）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，\出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。样例输入a+b*c3a 2b 7c 5样例输出abc*+   +  /  a   *    /     b c37

总时间限制: 2000ms 内存限制: 65536kB描述Farmer John‘s cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ‘s distance queries as quickly as possible!输入* Line 1: Two space-separated integers: N and M* Lines 2..1+M: Each line contains four space-separated entities, F1, F2, L, and D that describe a road. F1 and F2 are numbers of two farms connected by a road, L is its length, and D is a character that is either ‘N‘, ‘E‘, ‘S‘, or ‘W‘ giving the direction of the road from F1 to F2* Line 2+M: A single integer, K. 1 <= K <= 10,000* Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms.(1 <= M < 40,000)输出* Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance.样例输入7 61 6 13 E6 3 9 E3 5 7 S4 1 3 N2 4 20 W4 7 2 S31 61 42 6样例输出13336提示Farms 2 and 6 are 20+3+13=36 apart.#Navigation Nightmare Description#Farmer John‘s pastoral neighborhood has N farms (2 <= N <= 40,000), usually numbered/labeled 1..N. A series of M (1 <= M < 40,000) vertical and horizontal roads each of varying lengths (1 <= length <= 1000) connect the farms. A map of these farms might look something like the illustration below in which farms are labeled F1..F7 for clarity and lengths between connected farms are shown as (n):           F1 --- (13) ---- F6 --- (9) ----- F3            |                                 |           (3)                                |            |                                (7)           F4 --- (20) -------- F2            |            |                                 |           (2)                               F5            |            F7 Being an ASCII diagram, it is not precisely to scale, of course.Each farm can connect directly to at most four other farms via roads that lead exactly north, south, east, and/or west. Moreover, farms are only located at the endpoints of roads, and some farm can be found at every endpoint of every road. No two roads cross, and precisely one path(sequence of roads) links every pair of farms.FJ lost his paper copy of the farm map and he wants to reconstruct it from backup information on his computer. This data contains lines like the following, one for every road:There is a road of length 10 running north from Farm #23 to Farm #17There is a road of length 7 running east from Farm #1 to Farm #17...As FJ is retrieving this data, he is occasionally interrupted by questions such as the following that he receives from his navigationally-challenged neighbor, farmer Bob:What is the Manhattan distance between farms #1 and #23?FJ answers Bob, when he can (sometimes he doesn‘t yet have enough data yet). In the example above, the answer would be 17, since Bob wants to know the "Manhattan" distance between the pair of farms.The Manhattan distance between two points (x1,y1) and (x2,y2) is just |x1-x2| + |y1-y2| (which is the distance a taxicab in a large city must travel over city streets in a perfect grid to connect two x,y points).When Bob asks about a particular pair of farms, FJ might not yet have enough information to deduce the distance between them; in this case, FJ apologizes profusely and replies with "-1".来源USACO 2004 February