问题 B: Tournament Chart

时间限制: 1 Sec  内存限制: 128 MB
提交: 206  解决: 52
[提交] [状态] [命题人:admin]

题目描述

In 21XX, an annual programming contest, Japan Algorithmist GrandPrix (JAG) has become one of the most popular mind sports events.

JAG is conducted as a knockout tournament. This year, N contestants will compete in JAG. A tournament chart is represented as a string. '[[a-b]-[c-d]]' is an easy example. In this case, there are 4 contestants named a, b, c, and d, and all matches are described as follows:

Match 1 is the match between a and b.
Match 2 is the match between c and d.
Match 3 is the match between [the winner of match 1] and [the winner of match 2].
More precisely, the tournament chart satisfies the following BNF:

<winner> ::= <person> | "[" <winner> "-" <winner> "]"
<person> ::= "a" | "b" | "c" | ... | "z"
You, the chairperson of JAG, are planning to announce the results of this year's JAG competition. However, you made a mistake and lost the results of all the matches. Fortunately, you found the tournament chart that was printed before all of the matches of the tournament. Of course, it does not contains results at all. Therefore, you asked every contestant for the number of wins in the tournament, and got N pieces of information in the form of "The contestant ai won vi times".

Now, your job is to determine whether all of these replies can be true.

 

输入

The input consists of a single test case in the format below.

S
a1 v1
:
aN vN
S represents the tournament chart. S satisfies the above BNF. The following N lines represent the information of the number of wins. The (i+1)-th line consists of a lowercase letter ai and a non-negative integer vi (vi≤26) separated by a space, and this means that the contestant ai won vi times. Note that N (2≤N≤26) means that the number of contestants and it can be identified by string S. You can assume that each letter ai is distinct. It is guaranteed that S contains each ai exactly once and doesn't contain any other lowercase letters.

 

输出

Print 'Yes' in one line if replies are all valid for the tournament chart. Otherwise, print 'No' in one line.

 

样例输入

复制样例数据

[[m-y]-[a-o]]
o 0
a 1
y 2
m 0

样例输出

Yes

题目大意:给出一个字符串,这个字符串由[],-,与英文字母组成,每个[]内都会有一对进行比赛,胜者将会进行与下一个括号的胜者进行对战,题目中给出每个人获胜的次数,你需要判断一下,这个次数是否正确.

题目思路:

这个题的大体思路我们可以这样想:我每次遇到 一个 ]  说明此时需要进行对战,比如说第一个 m-y,出现 ] 之后说明 m与y需要进行对战,而且因为失败的一方不能再去参站,所以此时绝对有一个获胜次数为0的人(先不用管为什么),和一个次数不为0的人,所以说这场的结果绝对是次数不为0的人获胜,然后胜利的那个人的获胜次数就要--,失败的人就淘汰掉,此时我们用数组只保存 y,然后下一次再遇到 ] 数组里就有 yao 三个字母,我们取后两个(每次都取后两个),然后重复以上过程,这样就可以保证最后那个人一定是获胜者 .

此题的坑点比较多:

1.我们判断 如果数组中后两个 没有一个是0的,那就说明 这个数不对 // 没人输的局面

2.如果全是0,也不对//没人赢的局面

3.最后的赢者的获胜次数应该为0 // 否则他多赢几次 又和谁打呢?

AC:

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+7;
const int maxn=1e6;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
int cot[30];
char str[maxn];
bool judge(int len)
{
    int s=0;
    char save[50];
    int cnt=0;
    for(int i=1;i<=len;i++)
    {
        if(str[i]==']')
        {
            s--;
            int res=-1,res1=-1;
            for(int k=cnt-1;k<=cnt;k++)
            {
                if(cot[save[k]-'a'+1]>0) res=k;
                else if(cot[save[k]-'a'+1]==0) res1=k;
            }
            if(res==-1) return false;
            if(res1==-1) return false;
            cnt--;
            save[cnt]=save[res];
            cot[save[res]-'a'+1]--;
        }
        else if(str[i]>='a'&&str[i]<='z')
            save[++cnt]=str[i];
    }
    if(cot[save[cnt]-'a'+1]>0) return false;
    return true;
}
int main()
{
    int s=0;n=0;
    scanf("%s",str+1);
    int len=strlen(str+1);
    for(int i=1;i<=len;i++)
        if(str[i]>='a'&&str[i]<='z') n++;
    for(int i=1;i<=n;i++)
    {
        char cho[3];int x;
        scanf("%s%d",cho,&x);
        cot[cho[0]-'a'+1]=x;
    }
    bool res=judge(len);
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}

比赛时没有优先看到这个题,感觉有点亏...(不过那段时间又重新了温馨了A*第k短路),也小赚...