首页 > 代码库 > HDU 4891 简单模拟
HDU 4891 简单模拟
The Great Pan
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1035 Accepted Submission(s): 355
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.
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.
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 than 105.
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
题目意思：
初始化ans=1,然后给出行数为n的字符串，若字符串中{}里有n个|，那么ans*=(n+1)，在$$中每遇见一个长度为n的连续空格数，ans*=(n+1)。
若ans>10^5 输出doge 否则输出ans
思路：
典型纸老虎题目，光这题干就能把人吓死，（我英语不好，用各种在线翻译才看懂= =），模拟一下就行了 。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 7 char a[1000005]; 8 int n; 9 main()10 {11 __int64 flag1, flag2, ans;12 int MAXH=100000, i, j, k;13 __int64 num1, num2;14 int len, flag3;15 while(scanf("%d",&n)==1){16 ans=1;17 flag3=0;18 num1=num2=0;19 flag1=flag2=0;20 getchar();21 22 while(n--){23 gets(a);24 len=strlen(a);25 for(i=0;i<len;i++){26 if(a[i]==‘{‘){27 flag1=1;28 }29 else if(a[i]==‘}‘){30 flag1=0;31 ans*=(num1+1);32 num1=0;33 }34 else if(a[i]==‘$‘&&flag2==0){35 flag2=1;36 }37 else if(a[i]==‘$‘&&flag2==1){38 flag2=0;39 }40 else if(a[i]==‘|‘&&flag1){41 num1++;42 }43 else if(a[i]==‘ ‘&&flag2){44 num2++;45 }46 else {47 num2=0;48 }49 if(a[i]==‘ ‘&&a[i+1]!=‘ ‘&&flag2){50 ans*=(num2+1);51 num2=0;52 }53 if(ans>MAXH) flag3=1; //这一步去了就会wa，因为在过程中ans可能超出long long 范围 54 }55 }56 if(ans>MAXH||flag3) printf("doge\n");57 else printf("%I64d\n",ans);58 }59 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。