基础知识

栈(stack)

原则：后进先出

容量限制（由操作系统决定）：2MB


stack<int>s，定义了一个名为s的由整型数据构成的栈。

s.push(x) 将元素x入栈

s.top() 返回栈顶元素

s.pop() 将栈顶元素出栈

s.size() 返回栈的大小（元素数量）

s.empty() 返回栈是否为空

注意：使用s.top()和s.pop()时必须确保s非空，否则会发生段错误。

New Zealand 1989 - "Accordian" Patience

题目

You are to simulate the playing of games of “Accordian” patience, the rules for which are as follows:

Deal cards one by one in a row from left to right, not overlapping. Whenever the card matches its immediate neighbour on the left, or matches the third card to the left, it may be moved onto that card. Cards match if they are of the same suit or same rank. After making a move, look to see if it has made additional moves possible. Only the top card of each pile may be moved at any given time. Gaps between piles should be closed up as soon as they appear by moving all piles on the right of the gap one position to the left. Deal out the whole pack, combining cards towards the left whenever possible. The game is won if the pack is reduced to a single pile.

Situations can arise where more than one play is possible. Where two cards may be moved, you should adopt the strategy of always moving the leftmost card possible. Where a card may be moved either one position to the left or three positions to the left, move it three positions.

模拟一种纸牌游戏，其规则如下：

1.从左到右依次处理牌。当一张卡片与左边的邻牌相匹配（它们的花色或数字相同），或与左边第三相邻的卡相匹配时，它就可以移动到这些卡上。每次只能移动一个卡堆的顶部卡片。

2.满足匹配条件的牌在一次移动之后如果仍然满足匹配条件，可以继续移动，直到不匹配条件为止。

3.如果卡片移动之后留下空位，（在下一次移动之前，）需要将空位右侧的卡堆整体向左移动一个位置。

4.在一轮处理结束之后，如果有牌满足匹配条件，可以进行下一轮处理，否则游戏结束。

5.如果一张卡片可以向左移动一个或三个位置，则将其移动三个位置。

输入游戏开始时从左到右的卡牌面值(共52张)，输出游戏结束后剩余的堆数与每一堆卡片的数量（按照输入的顺序）。

分析

审题点1：对于一张牌的处理，可移动多次，直到不能移动为止。(After making a move, look to see if it has made additional moves possible.)

1种可能的情况：牌A移动完之后，另一张牌B移到牌A的左边第一邻位或第三邻位，使得牌B可以移动到牌A之上。（见图）

审题点2：每轮处理的对象不是一副牌中的每张牌，而是每个牌堆（的顶部卡片）。（Only the top card of each pile may be moved at any given time.）

审题点3：可以进行多轮处理，直到牌堆数量不再减少。（combining cards towards the left whenever possible）

推论1：在多轮处理的过程中，对于一个牌堆而言，添加新卡片的位置在其顶部，取走卡片也是在其顶部。牌堆的组织形式符合“后进先出”原则，即用栈来实现。

审题点3应作为外循环，审题点2 应作为中循环，审题点1应作为内循环。

原创代码 

#include<iostream>
#include<string>
#include<stack>
using namespace std;
const int N=52;
stack<string>p[N+10];
int i,n;//n为当前剩余的栈数
bool move(int s)//s为step（步数）的缩写
{
	if(i-s<=0) return false;
	string oldc=p[i].top();//备份
	if(oldc[0]!=p[i-s].top()[0]&&oldc[1]!=p[i-s].top()[1]) return false;	
	p[i].pop();//出栈
	p[i-s].push(oldc);i-=s;//入栈
	return true;
}
void combine() 
{
	int oldi=i;
	while(1==1)//内循环
	{
		if(move(3)) continue;
		if(!move(1)) break;
	}
	if(p[oldi].empty())//消除空位
	{
		for(int j=oldi+1;j<=n;j++)
			p[j-1]=p[j];
		n--;
	}
}
int main()
{
	string temp;
	while(cin>>temp&&temp[0]!='#')
	{
		for(i=1;i<=N;i++)
			while(!p[i].empty())
				p[i].pop();
		p[1].push(temp);
		for(i=2;i<=N;i++)
		{cin>>temp;p[i].push(temp);}
		n=N;int oldn=0;
		while(n!=oldn)//外循环 
		{
			oldn=n;
			for(i=1;i<=n;i++)//中循环 
				combine();
		}
		if(n>1) {cout<<n<<" piles remaining:";
		for(i=1;i<=n;i++) cout<<" "<<p[i].size();}
		else cout<<"1 pile remaining: "<<p[1].size();
		cout<<"\n";
	}
	return 0;
}

2019牛客暑期多校训练营（八）-G Gemstones

题目

输入一个由大写字母组成的字符串s（1≤∣s∣≤10^5），每次从中拿走一个由三个相同字母组成的串（拿走后其前后部分自动拼合），求最多可以拿走的次数。

思路1

显然，对于给定字符串，拿走的次数是唯一的，并无“最多”之说。

不妨采取从左到右的方式遍历，当最右端三个字母相同时，可进行一次拿走操作。这里我们只关心字符串的最右端（仅在一端进行加入、删除操作），符合“后入先出”的原则，可用栈来实现。

模型建立：每轮循环将最右端的字母入栈，当栈顶的三个字母相同时，则将这3个字母出栈，记为拿走一次。

代码1 

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int N=1e5+5;
char s[N];
stack<char>st;
int main()
{
    scanf("%s",s);
    int n=strlen(s),i;
    int cnt=0;char top1,top2,top3;
    for(i=0;i<n;i++)
    {
        st.push(s[i]);
        if(st.size() > 2)
        {
            top1= st.top();st.pop();
            top2= st.top();st.pop();
            top3= st.top();st.pop();
            if(top1==top2&&top3==top2) cnt++;
            else{st.push(top3);st.push(top2);st.push(top1);}
        }
    }
    printf("%d\n",cnt);
    return 0;
}

思路2

栈是本质，当然也可以模拟实现。每轮循环，最右端即为栈顶，栈的第二层和第三层不一定是当前字符的左一字符和左二字符（因为它们可能被拿走了），所以要用数组la[i]维护s[i]的上一个有效字符（底下一层）的编号。因此，第二层为s[la[i]]，第三层为s[la[la[i]]]。每次拿走后，原第四层变成第二层（在下一轮循环里），更新la[i+1]为la[la[la[i]]]。在某些轮次中可能出现栈不满3层的情况，将最底层的la记为-1，以供判断。

代码2 

#include<stdio.h>
#include<string.h>
const int N=1e5+5;
char s[N];int la[N];
int main()
{
scanf("%s",s);
    int n=strlen(s),i;
    int cnt=0;
    la[0]=-1;
    for(i=1;i<n;i++) la[i]=i-1;
    for(i=2;i<n;i++)
	{
        if(la[i]<0||la[la[i]]<0) continue;
		if(s[i]==s[la[i]]&&s[i]==s[la[la[i]]])
		{la[i+1]=la[la[la[i]]];cnt++;}
    }
    printf("%d\n",cnt);
    return 0;
}