【ccJUNE14】Forgot Password

描述 Description

Chef changed the password of his laptop a few days ago, but he can’t remember it today. Luckily, he wrote the encrypted password on a piece of paper, along with the rules for decryption.

The encrypted password is a string S consists of ASCII printable characters except space (ASCII 33 - 126, in decimal notation, the same below). Read here for more details: ASCII printable characters.

Each rule contains a pair of characters ci, pi, denoting that every character ci appears in the encrypted password should be replaced with pi. Notice that it is not allowed to do multiple replacements on a single position, see example case 1 for clarification.

After all the character replacements, the string is guaranteed to be a decimal number. The shortest notation of this number is the real password. To get the shortest notation, we should delete all the unnecessary leading and trailing zeros. If the number contains only non-zero decimal part, the integral part should be omitted (the shortest notation of “0.5” is “.5”). If the number contains zero decimal part, the decimal point should be omitted as well (the shortest notation of “5.00” is “5”).

Please help Chef to find the real password.

输入格式 InputFormat

The first line of the input contains an interger T denoting the number of test cases.
The description of T test cases follows.
The first line of each test case contains a single interger N, denoting the number of rules.
Each of the next N lines contains two space-separated characters ci and pi,
denoting a rule.
The next line contains a string S, denoting the encrypted password.

输出格式 OutputFormat

For each test case, output a single line containing the real password.

样例输入 SampleInput

4
2
5 3
3 1
5
0
01800.00
0
0.00100
3
x 0
d 3
# .
0xd21#dd098x

样例输出 SampleOutput

3
1800
.001
321.33098

数据范围和注释 Hint

1 ≤ T ≤ 1000
0 ≤ N ≤ 94
All characters in S and ci may be any ASCII printable character except space. (ASCII 33 - 126)
All ci in a single test case are distinct.
pi is a digit (“0” - “9”) or a decimal point “.” (ASCII 46).
The total length of S in a single input file will not exceed 106.

CodeChef FORGETPW

代码 Code

算是细节题吧, 竟然还会 TLE…. 学了好多 C 字符串的处理方法。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char a[127];
char s[1000005];
int i,j,t,n,m,l,r,k,z,y,x;
char c,ch;
bool exist; 
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d\n",&n);
        for (i=33;i<=126;i++) a[i]=i;
        exist=false;
        for (i=1;i<=n;i++)
        {
            scanf("%c %c\n",&c,&ch);
            a[c]=ch;
        }
        m=0;
        memset(s,0,sizeof(s)/sizeof(char));
        ch=getchar();
        while (ch<33 || ch>126) ch=getchar();
        while (ch>=33 && ch<=126)
        {
            if (m>0 || a[ch]!='0') s[m++]=a[ch];
            if (s[m-1]=='.') exist=true;
            ch=getchar();
        }
        m--;
        while (exist && s[m]=='0' && m>=0) s[m]='\0',m--;
        while (s[m]=='.' && m>=0) s[m]='\0',m--;
        if (m<0) printf("0\n");
        else printf("%s\n",s);
    }
    return 0;
}