2013
12-30

# UVa OJ 732 – Anagrams by Stack (堆栈字迷)

Time limit: 3.000 seconds

## Background背景

How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert “TROT” to “TORT”:

[
i i i i o o o o
i o i i o o i o
]

where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second.

## Input输入

The input will consist of several lines of input. The first line of each pair of input lines is to be considered as a source word (which does not include the end-of-line character). The second line (again, not including the end-of-line character) of each pair is a target word.

## Output输出

For each input pair, your program should produce a sorted list of valid sequences of i and o which produce the target word from the source word. Each list should be delimited by

[
]

and the sequences should be printed in “dictionary order”. Within each sequence, each i and o is followed by a single space and each sequence is terminated by a new line.

## Process处理

A stack is a data storage and retrieval structure permitting two operations:

• Push – to insert an item and
压入——向栈中插入一项
• Pop – to retrieve the most recently pushed item
弹出——取出最后插入的一项

We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the word FOO is input, then the sequence:

• i i o i o o is valid, but
i i o i o o是有效的，但
• i i o is not (it’s too short),
i i o是无效的，（没有完成操作）
• neither is
i i o o o i (there’s an illegal pop of an empty stack)

i i o o o i同样无效（执行了非法的从空栈弹出的操作）

Valid sequences yield rearrangements of the letters in an input word. For example, the input word FOO and the sequence i i o i o o produce the anagram OOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first.

bahama
bahama
long
short
eric
rice

## Sample Output输出示例

[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

## Solution解答

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//深度遍例所有可能的进出栈序列，进栈视为左子树，出栈视为右子树
void GenAnagram(vector<char> &Src, vector<char> &Dest,
vector<char> &Order, vector<char> &Stack) {
//如果字符串不为空，则执行进栈操作，相当于遍例左子树
if (!Src.empty()) {
//在操作序列中加入i
Order.push_back('i');
//进栈并保存现场
Stack.push_back(Src.back());
Src.pop_back();
//以当前状态遍例下一个动作
GenAnagram(Src, Dest, Order, Stack);
//恢复现场
Src.push_back(Stack.back());
Stack.pop_back();
Order.pop_back();
}
//如果栈不为空则执行弹栈操作，当栈顶和目标串相应字符相等时才继续
if (!Stack.empty() && Stack.back() == Dest[Stack.size() + Src.size() - 1]) {
//在操作序列中加入o
Order.push_back('o');
//弹栈并保存现场
char cTemp = Stack.back();
Stack.pop_back();
//以当前状态遍例下一个动作
GenAnagram(Src, Dest, Order, Stack);
//恢复现场
Stack.push_back(cTemp);
Order.pop_back();
}
//如果原字符串已空，且栈也为同，则说明所有字符都已出栈
if (Src.empty() && Stack.empty()) {
//输出进出栈操作序列
vector<char>::iterator i = Order.begin();
for (; i != Order.end() - 1; ++i ) {
cout << *i << ' ';
}
cout << *i << endl;
}
}
//主函数
int main(void) {
//循环处理输入的每一对字符串
for (string str1, str2; cin >> str1 >> str2; cout << ']' << endl) {
cout << '[' << endl;
//当两字符串长度相等且不为空时才运算
if (str1.length() == str2.length() && !str1.empty()) {
//建立原串、目标串、字符栈和结果数组
vector<char> Src(str1.rbegin(), str1.rend());
vector<char> Dest(str2.rbegin(), str2.rend());
vector<char> Order, Stack;
//执行深度遍例，输出所有结果
GenAnagram(Src, Dest, Order, Stack);
}
}
return 0;
}

1. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

3. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

4. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

5. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}