hdoj 5818 5821

hdoj 5818 5821

今天多校的A题和K题，明天有时间再放F题。

Problem Description

A stack is a data structure in which all insertions and deletions of entries are made at one end, called the "top" of the stack. The last entry which is inserted is the first one that will be removed. In another word, the operations perform in a Last-In-First-Out (LIFO) manner. A mergeable stack is a stack with "merge" operation. There are three kinds of operation as follows: - push A x: insert x into stack A - pop A: remove the top element of stack A - merge A B: merge stack A and B After an operation "merge A B", stack A will obtain all elements that A and B contained before, and B will become empty. The elements in the new stack are rearranged according to the time when they were pushed, just like repeating their "push" operations in one stack. See the sample input/output for further explanation. Given two mergeable stacks A and B, implement operations mentioned above.

Input

N(0

Output

For each case, print a line "Case #t:", where t is the case number (starting from 1). For each "pop" operation, output the element that is popped, in a single line.

Sample Input

4 push A 1 push A 2 pop A pop A 9 push A 0 push A 1 push B 3 pop A push A 2 merge A B pop A pop A pop A 9 push A 0 push A 1 push B 3 pop A push A 2 merge B A pop B pop B pop B 0

Sample Output

Case #1: 2 1 Case #2: 1 2 3 0 Case #3: 1 2 3 0

A题的题意是给出两个等长数列，并给出m个操作，每个操作可以对A数列所指定的范围进行数字打乱重新排序，并且范围的顺序按操作的顺序来（也就是样例3跟样例4的差别），然后问A能不能在经过这些操作后变成B数列。

我一开始的思路是对每次操作，对范围内的两个数列的数进行排序，然后最后比较...这个思路是错的..因为B数列也变是违反规定的，这种投机取巧经不起推敲。

后来看学姐的代码才知道，排序的不是数列的数，而是数列里每个数出现的位置，先对B记录每个数出现的位置，然后每次操作，对A的那个范围里的所有的数在B里的位置进行排序，这样就不用干扰B数列了。

代码如下：

#include#include#include#includeusing namespace std;#define N 2010int a[N],b[N],vis[N][N],cnt[N];int main(){ int i,j,n,m,T,x,y; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(i=0;i

Problem Description

A stack is a data structure in which all insertions and deletions of entries are made at one end, called the "top" of the stack. The last entry which is inserted is the first one that will be removed. In another word, the operations perform in a Last-In-First-Out (LIFO) manner. A mergeable stack is a stack with "merge" operation. There are three kinds of operation as follows: - push A x: insert x into stack A - pop A: remove the top element of stack A - merge A B: merge stack A and B After an operation "merge A B", stack A will obtain all elements that A and B contained before, and B will become empty. The elements in the new stack are rearranged according to the time when they were pushed, just like repeating their "push" operations in one stack. See the sample input/output for further explanation. Given two mergeable stacks A and B, implement operations mentioned above.

Input

N(0

Output

For each case, print a line "Case #t:", where t is the case number (starting from 1). For each "pop" operation, output the element that is popped, in a single line.

Sample Input

4 push A 1 push A 2 pop A pop A 9 push A 0 push A 1 push B 3 pop A push A 2 merge A B pop A pop A pop A 9 push A 0 push A 1 push B 3 pop A push A 2 merge B A pop B pop B pop B 0

Sample Output

Case #1: 2 1 Case #2: 1 2 3 0 Case #3: 1 2 3 0

F题题意简单，给一个只有（和）的字符串，是否能更换任意两个位置的括号使这个字符串的所有括号都能匹配。

用栈来做，数组来存没有匹配到的括号，先匹配完所有可以匹配的括号，剩下的处理。

不过要注意：‘（）‘  这种情况不行，因为必须要更换一次。

还有‘））（（’是可以通过更换匹配的到的，特判写一下就能过了。

#include#include#include#include#includeusing namespace std;#define N 100010stacka;char s[N],k[N];int main(){ int i,j,n,cnt,res,T,l,r; char x; scanf("%d",&T); while(T--) { scanf("%d",&n); l=0,r=0; for(i=1;i<=n;i++){ cin>>x; k[i]=x; if(x==')') r++; else l++; a.push(x); } if(n%2!=0||l!=r) { printf("No\n"); continue; } if(n==2&&k[1]=='('&&k[2]==')'){ printf("No\n");continue;} cnt=n/2,res=0; for(i=1;i<=n;i++){ x=a-(); a.pop(); s[++res]=x; if(x=='('&&s[res-1]==')'){ cnt--; res-=2; } } if(cnt-1==0||cnt==0){ printf("Yes\n"); continue;} if(s[4]==')'&&s[3]==')'&&s[2]=='('&&s[1]=='(') printf("Yes\n"); else printf("No\n"); }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。