首页 > 代码库 > HDU4891_The Great Pan_字符串水题

HDU4891_The Great Pan_字符串水题

2024-07-15 00:05:46   211人阅读

2014多校第五题，当时题面上的10^5写成105，我们大家都wa了几发，改正后我和一血就差几秒…不能忍

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4891

The Great Pan

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 966    Accepted Submission(s): 339
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 than 105.
 
Sample Input
9I‘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?}1Case $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
44doge6
 
Author
Fudan University
 
Source
2014 Multi-University Training Contest 3
 
Recommend
We have carefully selected several similar problems for you:  4896 4895 4894 4893 4892

 

大意是说acm有时题意不清，给出一段题，n行中，有一些{A|B|C|D}和一些$biu biu biu$，其中ABCD是4种题意，$ $之间的空格数目不明，本来是连续的5个空格就有6种可能性（0,1,2,3,4,5)，求这一段题的可能性数。

其实就是数{}的竖线、数$$中的连续空格，一个个字符处理就行，特别水，我都怕。

代码：

 1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 using namespace std; 9 #define ll __int6410 #define RE  freopen("1.in","r",stdin)11 const ll dogenum=100000;12 int main() {13     //RE;14     ll n,i,j,k,ans,cnt,koha;15     char c,s[22222];16     ll flag;17     while(scanf("%lld",&n)!=EOF) {18         do {19             scanf("%c",&c);20         } while(c!=‘\n‘);21         flag=0;22         ans=1;23         for(i=0; i<n; i++) {24             //cout<<‘[‘<<i<<‘]‘<<endl;25             if(ans==-1) {26                 gets(s);27                 continue;28             }29             while(scanf("%c",&c)!=EOF && c!=‘\n‘) {30                 if(flag==0) {31                     if(c==‘{‘) flag=1,cnt=1;32                     else if(c==‘$‘) flag=2,koha=0;33                 } else if(flag==1) {34                     if(c==‘|‘) cnt++;35                     else if(c==‘}‘) {36                         if(cnt>dogenum) {37                             ans=-1;38                             gets(s);39                             break;40                         } else ans*=cnt;41                         if(ans>dogenum) {42                             ans=-1;43                             gets(s);44                             break;45                         }46                         flag=0;47                     }48                 } else if(flag==2) {49                     if(c==‘ ‘) koha++;50                     else {51                         if(c==‘$‘) flag=0;52                         if(koha>0) {53                             if(koha+1>dogenum) {54                                 ans=-1;55                                 gets(s);56                                 break;57                             }58                             ans*=koha+1;59                             // cout<<‘(‘<<ans<<‘)‘;60                             if(ans>dogenum) {61                                 ans=-1;62                                 gets(s);63                                 break;64                             }65                             koha=0;66                         }67                     }68                 }69             }70         }71         if(ans==-1) printf("doge\n");72         else printf("%lld\n",ans);73     }74     return 0;75 }
View Code

 


联系
我们