首页 > 代码库 > HDU--4891--The Great Pan--暴力搜索

HDU--4891--The Great Pan--暴力搜索

2024-09-26 18:06:02   214人阅读

The Great Pan

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 827    Accepted Submission(s): 292


Problem Description
As a programming contest addict, Waybl is always happy to take part in various competitive programming contests. One day, he was competing at a regional contest of Inventing Crappy Problems Contest(ICPC). He tried really hard to solve a "geometry" task without success.

After the contest, he found that the problem statement is ambiguous! He immediately complained to jury. But problem setter, the Great Pan, told him "There are only four possibilities, why don‘t you just try all of them and get Accepted?

".

Waybl was really shocked. It is the first time he learned that enumerating problem statement is as useful as trying to solve some ternary search problem by enumerating a subset of possible angle!

Three years later, while chatting with Ceybl, Waybl was told that some problem "setters" (yeah, other than the Great Pan) could even change the whole problem 30 minutes before the contest end! He was again shocked.

Now, for a given problem statement, Waybl wants to know how many ways there are to understand it.

A problem statement contains only newlines and printable ASCII characters (32 ≤ their ASCII code ≤ 127) except ‘{‘, ‘}‘, ‘|‘ and ‘$‘.

Waybl has already marked all ambiguity in the following two formats:

1.{A|B|C|D|...} indicates this part could be understand as A or B or C or D or ....
2.$blah blah$ indicates this part is printed in proportional fonts, it is impossible to determine how many space characters there are.

Note that A, B, C, D won‘t be duplicate, but could be empty. (indicate evil problem setters addedclarified it later.)

Also note that N consecutive spaces lead to N+1 different ways of understanding, not 2N ways.

It is impossible to escape from "$$" and "{}" markups even with newlines. There won‘t be nested markups, i.e. something like "${A|B}$" or "{$A$|B}" or "{{A|B}|C}" is prohibited. All markups will be properly matched.

 

Input
Input contains several test cases, please process till EOF.
For each test case, the first line contains an integer n, indicating the line count of this statement. Next n lines is the problem statement.
1 ≤ n ≤ 1000, size of the input file will not exceed 1024KB.
 

Output
For each test case print the number of ways to understand this statement, or "doge" if your answer is more than105.
 

Sample Input
9
I‘ll shoot the magic arrow several
 times on the ground, and of course
 the arrow will leave some holes
 on the ground. When you connect
 three holes with three line segments,
 you may get a triangle.
{|It is hole! Common sense!|
No Response, Read Problem
 Statement|don‘t you know what a triangle is?}
1
Case $1: = >$
5
$/*This is my code printed in
 proportional font, isn‘t it cool?*/
printf("Definitely it is cooooooool %d\n",4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 
* 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4);$
2
$Two  space$ and {blue|
red} color!
 

Sample Output
4
4
doge
6
 
题意：假设是｛｝，求当中的 “ | ” 的个数，然后加一乘到总和里面。假设是 $ $ 。求当中空格，连续的n个空格有n+1种方式。$ $ 中的空格段之间的计算也是直接相乘，然后乘到总和里面

体验过什么叫WA到死么？-.-！不罗嗦了。注意的就是当中的方式总量是会超过int范围的。所以要及时推断出来。另一个。也就是把我卡了半天的，就是推断文件大小，每次输入最大文件是1024KB，一个字符是1B，所以每次输入的字符串长度都是百万++的   T.T 所果断开了500W的才过


代码太简单，所以不凝视了


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str[5000000];
int main (void)
{
    int n,i,j,k,l;
    __int64 num,s;
    while(~scanf("%d%*c",&n))
    {
        num=1;
        k=0;
        s=0;
        while(n--&&gets(str))
        {
            l=strlen(str);
            if(num>100000)continue;
            for(i=0;i<l;i++)
            {
                if(str[i]==‘$‘||str[i]==‘{‘||str[i]==‘}‘)
                {
                    if(k!=0)
                    {
                        if(num*(s+1)>100000)
                        {
                            num=100001;
                            break;
                        }
                        num*=s+1;
                        s=0;
                        k=0;
                    }
                    else if(str[i]==‘$‘)k=1;
                    else k=2;
                }else if(k==1)
                {
                    if(str[i]==‘ ‘)
                    {
                        s++;
                        if(s>=100000)
                        {
                            num=100001;
                            break;
                        }
                    }
                    else
                    {
                        if(num*(s+1)>100000)
                        {
                            num=100001;
                            break;
                        }
                        num*=s+1;
                        s=0;
                    }
                }else if(k==2)
                {
                    if(str[i]==‘|‘)
                    {
                        s++;
                        if(s>=100000)
                        {
                            num=100001;
                            break;
                        }
                    }
                }
            }
        }
        if(num>100000)puts("doge");
        else printf("%I64d\n",num);
    }
    return 0;
}

HDU--4891--The Great Pan--暴力搜索


联系
我们