分类目录归档:ACM

ACM/ICPC

HDOJ2127:Polish notation——表达式转换

Problem Description
Reverse Polish notation (RPN) is a method for representing expressions in which the operator symbol is placed after the arguments being operated on.
Polish notation, in which the operator comes before the operands, was invented in the 1920s by the Polish mathematician Jan Lucasiewicz.
In the late 1950s, Australian philosopher and computer scientist Charles L. Hamblin suggested placing the operator after the operands and hence created reverse polish notation.

RPN has the property that brackets are not required to represent the order of evaluation or grouping of the terms.
RPN expressions are simply evaluated from left to right and this greatly simplifies the computation of the expression within computer programs.
As an example, the arithmetic expression (3+4)*5 can be expressed in RPN as 3 4 + 5 *.

Reverse Polish notation, also known as postfix notation, contrasts with the infix notation of standard arithmetic expressions in which the operator symbol appears between the operands. So Polish notation just as prefix notation.

Now, give you a string of standard arithmetic expressions, please tell me the Polish notation and the value of expressions.

Input
There’re have multi-case. Every case put in one line, the expressions just contain some positive integers(all less than 100, the number of integers less than 20), bi-operand operators(only have 3 kinds : +,-,*) and some brackets'(‘,’)’.
you can assume the expressions was valid.

Output
Each case output the Polish notation in first line, and the result of expressions was output in second line.
all of the answers are no any spaces and blank line.the answer will be not exceed the 64-signed integer.

Sample Input
1+2-3*(4-5)
1+2*(3-4)-5*6

Sample Output
Case 1:
– + 1 2 * 3 – 4 5
6
Case 2:
– + 1 * 2 – 3 4 * 5 6
-31

题目考察表达式的转换将中缀表达式转换成前置表达式(波兰式),并计算出结果。可以直接套模板……需要注意表达式中空格的位置;字符串需要用__int64存贮。

关于前置表达式和后置表达式的转换方法可以参考这篇博文:波兰式、逆波兰式与表达式求值

参考代码:

#include 
#include 
#include 
using namespace std;

char stack[500];                    
int top;                        //栈顶指针       
char output[500], input[500];        
int outLen;

int priority(char op)           //定义运算符优先级     
{
    if (op=='+' || op=='-')
        return 1;
    if (op=='*' || op=='/')
        return 2;
    else
        return 0;
}

bool isOperator(char op)                
{
    return (op=='+' || op=='-' || op=='*' || op=='/');
}

void Polish(char *s,int len)            
{
    memset(output,'\0',sizeof output);    
    outLen = 0;
    for (int i=len-1; i >= 0; --i)        
    {
        if (isdigit(s[i]))                
        {
            output[outLen++] = s[i];    
            while (i-1 >= 0 && isdigit(s[i-1]))
            {
                output[outLen++] = s[i-1];
                --i;
            }
            output[outLen++] = ' ';        
        }
        if (s[i]==')')                    
        {
            ++top;
            stack[top] = s[i];
        }
        while (isOperator(s[i]))        
        {                                                
            if (top==0 || stack[top]==')' || priority(s[i]) >= priority(stack[top])) 
            {
                ++top;
                stack[top] = s[i];
                break;
            }
            else
            {
                output[outLen++] = stack[top];
                output[outLen++] = ' ';
                --top;
            }
        }
        if (s[i]=='(')                    
        {
            while (stack[top]!=')')
            {
                output[outLen++] = stack[top];
                output[outLen++] = ' ';
                --top;
            }
            --top;    
        }
    }
    while (top!=0)                        
    {
        output[outLen++] = stack[top];
        output[outLen++] = ' ';
        --top;
    }
}

char DstBuf[200];
char* OP(char* op1,char* op2,char op)
{
    __int64 res = 0;
    if (op=='+')
        res = _atoi64(op1) + _atoi64(op2);
    else if (op=='-')
        res = _atoi64(op1) - _atoi64(op2);
    else if (op=='*')
        res = _atoi64(op1) * _atoi64(op2);
    else if (op=='/')
        res = _atoi64(op1) / _atoi64(op2);
    _i64toa(res,DstBuf,10);
    return DstBuf;
}

char cSt1[200][80], cSt2[200][80];
__int64 calc(char *s)                
{
    int top1=0, top2=0, i;
    for (i=0; s[i]; ++i)
    {
        if (s[i] && s[i] != ' ')
        {
            ++top1;
            sscanf(s+i,"%s",cSt1[top1]);        
            while (s[i] && s[i] != ' ')
                ++i;
        }
    }
    while (top1 != 0)    
    {
        if (!isdigit(cSt1[top1][0]))    
        {
            OP(cSt2[top2], cSt2[top2-1], cSt1[top1][0]);
            memcpy(cSt2[top2-1],DstBuf,sizeof DstBuf);
            --top2;                    
            --top1;                        
        }
        else
        {
            ++top2;                        
            memcpy(cSt2[top2],cSt1[top1],sizeof cSt1[top1]);
            --top1;                        
        }
    }
    return _atoi64(cSt2[1]);
}
int main()
{
    int T = 1;
    while (gets(input))
    {
        Polish(input, strlen(input));
        reverse(output,output+outLen-1);
        output[outLen-1] = '\0';
        printf("Case %d:\n%s\n",T++,output);
        printf("%I64d\n",calc(output));//注意要__int64
    }
    return 0;
}

HDOJ1042:N!–大数

Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

Input
One N in one line, process to the end of file.

Output
For each N, output N! in one line.

Sample Input
1
2
3

Sample Output
1
2
6

要求计算10000以内的阶乘,典型的大数问题.这里用的是 五位一存的方法. 关于X位一存的解释可以看这篇文章. 注意特殊情况(0,1)下的处理.

#include 
#include 
#define MOD 100000
int main()
{
    int a[8000];    
    int i,k,n,t,la;
    while(~scanf("%d",&n))
    {
        if(n==0||n==1) {printf("1\n");continue;}

        a[0] = 1; 
        la = 1;
        t = 0;
        for(k=2; k 0)   
            {    
                a[la++] = t;
                t = 0; 
            } 
        }
        printf("%d",a[la-1]);
        for(i=la-2; i>=0; i--)
            printf("%05d",a[i]);
        printf("\n");
    }
    return 0;
}

HDOJ1052:Tian Ji — The Horse Racing–简单贪心

Here is a famous story in Chinese history.

“That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others.”

“Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser.”

“Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian’s. As a result, each time the king takes six hundred silver dollars from Tian.”

“Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match.”

“It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king’s regular, and his super beat the king’s plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?”

Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian’s horses on one side, and the king’s horses on the other. Whenever one of Tian’s horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching…

However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses — a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.

In this problem, you are asked to write a program to solve this special case of matching problem.

Input
The input consists of up to 50 test cases. Each case starts with a positive integer n (n 田忌最快的马比齐王最快的快–直接跑赢;

  • 田忌最快的马比齐王最快的慢–用田忌最慢的马去跟齐王的马跑;
  • 田忌最快的马跟齐王最快的一样快–再比较田忌最慢的马是否比齐王的最慢的马快,如果是就直接跑赢,如果不是就用田忌最慢的马去跟齐王最快的马跑.
  • 放上代码:

    #include
    #include
    #include
    int cmp(const void*a ,const void*b)
    {
    	return *(int *)b-*(int *)a;
    }
    int main()
    {
    	int i,n;
    	int tian,king;
    	int fa,fb,la,lb;
    	while(~scanf("%d",&n)&&n!=0)
    	{
    		int a[1001]={0},b[1001]={0};
    		getchar();
    		tian=king=0;
    		for(i=0;ib[fb])
    			{
    				tian++;
    				fa++;
    				fb++;
    			}
    			else if(a[la]>b[lb])
    			{
    				tian++;
    				la--;
    				lb--;
    			}
    			else if(a[la]b[fb])
    			tian++;
    		else if(a[fa]
    					

    HDOJ5131:Song Jiang’s rank list

    Problem Description
    《Shui Hu Zhuan》,also 《Water Margin》was written by Shi Nai’an — an writer of Yuan and Ming dynasty. 《Shui Hu Zhuan》is one of the Four Great Classical Novels of Chinese literature. It tells a story about 108 outlaws. They came from different backgrounds (including scholars, fishermen, imperial drill instructors etc.), and all of them eventually came to occupy Mout Liang(or Liangshan Marsh) and elected Song Jiang as their leader.

    In order to encourage his military officers, Song Jiang always made a rank list after every battle. In the rank list, all 108 outlaws were ranked by the number of enemies he/she killed in the battle. The more enemies one killed, one’s rank is higher. If two outlaws killed the same number of enemies, the one whose name is smaller in alphabet order had higher rank. Now please help Song Jiang to make the rank list and answer some queries based on the rank list.

    Input
    There are no more than 20 test cases.

    For each test case:

    The first line is an integer N (0<n&<200), indicating that there are N outlaws.

    Then N lines follow. Each line contains a string S and an integer K(0<k<300), meaning an outlaw’s name and the number of enemies he/she had killed. A name consists only letters, and its length is between 1 and 50(inclusive). Every name is unique.

    The next line is an integer M (0<m<200) ,indicating that there are M queries.

    Then M queries follow. Each query is a line containing an outlaw’s name.
    The input ends with n = 0

    Output
    For each test case, print the rank list first. For this part in the output ,each line contains an outlaw’s name and the number of enemies he killed.

    Then, for each name in the query of the input, print the outlaw’s rank. Each outlaw had a major rank and a minor rank. One’s major rank is one plus the number of outlaws who killed more enemies than him/her did.One’s minor rank is one plus the number of outlaws who killed the same number of enemies as he/she did but whose name is smaller in alphabet order than his/hers. For each query, if the minor rank is 1, then print the major rank only. Or else Print the major rank, blank , and then the minor rank. It’s guaranteed that each query has an answer for it.

    Sample Input
    5
    WuSong 12
    LuZhishen 12
    SongJiang 13
    LuJunyi 1
    HuaRong 15
    5
    WuSong
    LuJunyi
    LuZhishen
    HuaRong
    SongJiang
    0

    Sample Output
    HuaRong 15
    SongJiang 13
    LuZhishen 12
    WuSong 12
    LuJunyi 1
    3 2
    5
    3
    1
    2

    简单排序,直接上代码:

    #include
    #include
    #include
    #include
    using namespace std;
    #define N 205
    
    struct hero_t{
        string s;
        int i, n;
    } heros[N];
    
    struct node_t {
        int mmin, mmax;
        node_t() {}
        node_t(int a, int b) {
            mmin = a; mmax = b;
        }
    } node;
    
    //struct heros[N];
    
    bool comp(hero_t a, hero_t b) {
        if (a.n == b.n)
            return a.s  b.n;
    }
    
    int main() {
        int n, m;
        int i, j, k, id = 0;
        string s;
        node_t nd;
    
        while (cin>>n && n) {
            for (i=0; i>heros[i].s>>heros[i].n;
            }
    
            sort(heros, heros+n, comp);
            for (i=0; i tb;
            i = 0;
            while (i  1) {
                    for (k=0; k>m;
            while (m--) {
                cin >>s;
                nd = tb[s];
                if (nd.mmin == 1)
                    cout 
    					

    HDOJ1232:畅通工程——并查集简单应用

    Problem Description
    某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

    Input
    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( #include #include int father[1001]; int FindGF(int a)//找祖父节点 { while (father[a] != a) a = father[a]; return a; } void Branch(int a, int b)//合并不同的祖父节点 { int fx, fy; fx = FindGF(a); fy = FindGF(b); if (fx != fy) father[fx] = fy; } int main() { int n, m, i, x, y, ans; while (scanf(“%d”, &n) && n != 0) { for (i = 1; i

    汇编语言数组练习题两则

    题目一:在数组中查找某数,查到则返回下标,查不到则返回-1
    data段提供如下:

    area array, data, readwrite
    src    dcd 2,4,3,8,14,1,5
    length equ 6*4
    num    equ 3
    dst    dcd -1,-1,-1,-1,-1,-1,-1
    

    参考解答:

    area search, code, readonly
           entry
    start  mov r5, #num
           ldr r1, =src
           add r6, r1, #length
           ldr r3, =dst
           mov r4, #0
    
    loop   ldr r2, [r1]
           cmp r2, r5
           BEQ output
    inner  add r4, r4, #1
           add r1, r1, #4
           cmp r1, r6
           BLE loop
           B stop
    
    output str r4, [r3]
           add r3, r3, #4
           B inner
    
    Stop    MOV r0,#0x18
        LDR r1,=0x20026
        SWI 0x123456
    
    end
    
    

    题目二:数组匹配,给两个各自无重复数据的数组,查找里面匹配到的数据,把数据保存到另一个数组里。
    data段如下:

    area array, data, readwrite
    src    dcd 2,4,6,8,10,12,14
    len    equ 6*4
    dst    dcd 1,2,3,4,5,6,7,8
    length equ 7*4
    array  dcd 0,0,0,0,0,0,0
    
    

    参考解答:

    area match, code, readonly
           entry
    start  ldr r1, =src
           add r5, r1, #len
           ldr r2, =dst
           add r6, r2, #length
           ldr r7, =array
    
    inner  ldr r3, [r1]
           ldr r4, [r2]
           cmp r3, r4
           BEQ output
           add r2, r2, #4
           cmp r2, r6
           BLE inner
    outer  add r1, r1, #4
           ldr r2, =dst
           cmp r1, r5
           BLE inner
           B stop
    
    output str r3, [r7]
           add r7, r7, #4
           B outer
    
    Stop    MOV r0,#0x18
        LDR r1,=0x20026
        SWI 0x123456
    
    

    HDOJ3926:Hand in hand——并查集、同构图应用

    Problem Description
    In order to get rid of Conan, Kaitou KID disguises himself as a teacher in the kindergarten. He knows kids love games and works out a new game called “hand in hand”.

    Initially kids run on the playground randomly. When Kid says “stop”, kids catch others’ hands immediately. One hand can catch any other hand randomly. It’s weird to have more than two hands get together so one hand grabs at most one other hand. After kids stop moving they form a graph.

    Everybody takes a look at the graph and repeat the above steps again to form another graph. Now Kid has a question for his kids: “Are the two graph isomorphism?”

    Input
    The first line contains a single positive integer T( T D_Double同学的。
    首先考虑到每个节点的度数最多只能是2(每人两只手)。最终这些学生可能会被分成多组,每组是一个环形圆圈,或者是一条链。

    题目要判断两个已经连好的图是否是”同构图”,。这里所谓的同构图是指两个图组成的不同的圆圈,链条,他们各个所对应的数量都是相等的。

    那么我们只需要用并查集把连这的都合并起来,如果发现有环,就进行标识。然后把两个图的并查集按照每颗树的节点个数大小排序,如果个数相同,那么有环的都放在前面。 然后,只要一一比较两个已排序的数组,只要发现有一个是不同的,就不是同构图。

    代码:

    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    const int maxN = 10001;
    
    int n, m, n2, m2;
    int father[maxN], PT[maxN], isCircle[maxN];
    //memset(0, isCircle, sizeof(isCircle));
    struct node
    {
        int num, isCircle;
        friend bool operator b.num;
            return a.isCircle>b.isCircle;
        }
    }an[maxN], bn[maxN];
    
    int findset(int x)
    {
        if (x == father[x]) return x;
        return father[x] = findset(father[x]);
    }
    void Union(int x, int y)
    {
        x = findset(x); y = findset(y);
        if (x == y)
        {
            isCircle[x] = 1;
            return;
        }
        if (PT[x]>PT[y])
        {
            father[y] = x;
            PT[x] += PT[y];
        }
        else
        {
            father[x] = y;
            PT[y] += PT[x];
        }
    }
    
    int main()
    {
        int t, ncase = 1;
        scanf("%d", &t);
        while (t--)
        {
            scanf("%d%d", &n, &m);
            memset(isCircle, 0, sizeof(isCircle));
            for (int i = 1; i 
    

    参考了一部分代码。心急火燎的赶去看谷歌IO了~