题目大意：一个人一张张发牌，如果这张牌与这张牌前面的一张或者前面的第三张（后面称之为一位置和三位置）的点数或花式相同，则将这张牌移动到与之对应的位置（优先三位置，也就是说如果一位置与三位置都有以上的性质则移动到三位置之上），移动之后若仍以上的性质，则继续操作，直到已发的所有牌都无法移动之后再继续发牌，（如果一个位置被移空，则删除此位置！）
解题思路：用数组模拟链表，每发一张牌就匹配三位置，如果匹配就移动，否则再看一位置是否满足，如果满足就移动，移动之后，再继续之前的操作，直到所有的都不能移动！如果都不满足，则继续发牌！如此反复直到所有牌都发完！最后只剩下几叠移不动的牌，依次输出每叠的数量。最开始的数是总叠数，如果是1则输出“1 pile remaining: ”其他则输出“6 piles remaining: ”！
解题代码：
//Author: Freetion
//file: 127 - "Accordian" Patience #include <iostream>
#include <math.h>
#include <string.h>
#include <stdio.h>
using namespace std; struct node
{
string pile[];
int num;
}pat[];
bool noth[]; int main()
{
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
string tm;
while (cin >> tm && tm[] != '#')
{
memset (noth, false, sizeof (noth));
int i = ;
pat[i].pile[] = "";
pat[i].pile[] += tm;
pat[i++].num = ;
for ( ; i < ; i ++)
{
pat[i].num = ;
cin >> pat[i].pile[pat[i].num++];
}
/* for (i = 0; i < 52; i ++)
cout << pat[i].pile[0] << " ";
for (i = 0; i < 52; i ++)
cout << pat[i].num << " ";
*/
int total = ;
for (i = ; i < ; i ++)
{
int bf = , cm = i - ;
while (bf < && cm >= )
{
if (noth[cm --])
continue;
bf ++;
}
if (bf == && !noth[i])
{
node& cmp_1 = pat[i];
node& cmp_2 = pat[cm+];
if ( cmp_1.pile[cmp_1.num-][] == cmp_2.pile[cmp_2.num-][] )
{
cmp_2.pile[cmp_2.num] = "";
cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
if (cmp_1.num <= )
{
noth[i] = true;
total --;
}
i = cm;
continue;
}
else if ( cmp_1.pile[cmp_1.num-][] == cmp_2.pile[cmp_2.num-][] )
{
cmp_2.pile[cmp_2.num] = "";
cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
if (cmp_1.num <= )
{
noth[i] = true;
total --;
}
i = cm;
continue;
}
}
bf = , cm = i - ;
while (bf < && cm >= )
{
if (noth[cm --])
continue;
bf ++;
}
if (bf == && !noth[i])
{
node& cmp_1 = pat[i];
node& cmp_2 = pat[cm+];
if ( cmp_1.pile[cmp_1.num-][] == cmp_2.pile[cmp_2.num-][] )
{
cmp_2.pile[cmp_2.num] = "";
cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
if (cmp_1.num <= )
{
noth[i] = true;
total --;
}
i = cm;
continue;
}
else if ( cmp_1.pile[cmp_1.num-][] == cmp_2.pile[cmp_2.num-][] )
{
cmp_2.pile[cmp_2.num] = "";
cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
if (cmp_1.num <= )
{
noth[i] = true;
total --;
}
i = cm;
continue;
}
}
}
if (total > )
printf ("%d piles remaining:", total);
else printf ("%d pile remaining:", total);
for (i = ; i < ; i ++)
{
if (!noth[i])
printf (" %d", pat[i].num);
}
puts("");
}
return ;
}
开始时我用得字符数组，而不是字符串，但是用字符数组时，运行到此条语句时cmp_2.pile[cmp_2.num ++] 当cmp_2.num == 50时，自加就变成了25529。直到现在也没弄明白为什么！如果哪位大神路过此地又恰巧知道其中原理时请告知！谢谢。。。
题目大意：提供一个大牛的博客http://www.cnblogs.com/devymex/archive/2010/08/04/1792128.html
解题思路：模拟操作就是了！
解题代码：
//Author :Freetion
//file :101 - The Blocks Problem #include <stdio.h>
#include <string.h> struct node
{
int top;
int up[];
}pos[]; int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
int n;
char in[][];
int p1, on1, p2, on2, ope;
int num1, num2;
while (scanf ("%d", &n) == )
{
for (int i = ; i < n; i ++)
{
pos[i].top = ;
pos[i].up[pos[i].top ++] = i;
}
while (scanf("%s", in[]) == )
{
if (in[][] == 'q')
break;
scanf ("%d %s %d", &num1, in[], &num2);
p1 = p2 = -;
for (int i = ; i < n; i ++)
{
for (int j = ; j < pos[i].top; j ++)
{
if (num1 == pos[i].up[j])
p1 = i, on1 = j;
if (num2 == pos[i].up[j])
p2 = i, on2 = j;
if (p1 != - && p2 != -)
break;
}
if (p1 != - && p2 != -)
break;
}
if (p1 == p2)
continue;
if (in[][] == 'm')
ope = ;
else ope = ;
if (in[][] == 'v')
ope ++;
if (ope == )
{
for (int i = on1+; i < pos[p1].top; i ++)
{
node& A = pos[pos[p1].up[i]];
A.up[A.top ++] = pos[p1].up[i];
}
pos[p1].top = on1+;
for (int i = on2+; i < pos[p2].top; i ++)
{
node& A = pos[pos[p2].up[i]];
A.up[A.top ++] = pos[p2].up[i];
}
pos[p2].top = on2 +;
pos[p2].up[pos[p2].top ++] = pos[p1].up[--pos[p1].top];
}
else if (ope == )
{
for (int i = on1+; i < pos[p1].top; i ++)
{
node& A = pos[pos[p1].up[i]];
A.up[A.top ++] = pos[p1].up[i];
}
pos[p1].top = on1+;
pos[p2].up[pos[p2].top ++] = pos[p1].up[--pos[p1].top];
}
else if (ope == )
{
for (int i = on2+; i < pos[p2].top; i ++)
{
node& A = pos[pos[p2].up[i]];
A.up[A.top ++] = pos[p2].up[i];
}
pos[p2].top = on2 +;
for (int i = on1; i < pos[p1].top; i ++)
{
pos[p2].up[pos[p2].top ++] = pos[p1].up[i];
}
pos[p1].top = on1;
}
else if (ope == )
{
for (int i = on1; i < pos[p1].top; i ++)
{
pos[p2].up[pos[p2].top ++] = pos[p1].up[i];
}
pos[p1].top = on1;
}
}
for (int i = ; i < n; i ++)
{
printf ("%d:", i);
for (int j = ; j < pos[i].top; j ++)
printf (" %d", pos[i].up[j]);
printf ("\n");
}
}
return ;
}
题目大意：给你一个n个数组成的环，再给出一个顺时钟数的数k，一个逆时钟数的数m。要你从开始的位置同时朝顺时钟和逆时钟两个方向数，将顺时钟数到的第k个数和逆时钟数到的第m个数同时从环中剔除，然后继续数直到环上没有数了。如果数到的是同一个数，则只剔除这一个数。
解题思路：直接操作，水题！ps：样例中三角型代表的是空格。
解题代码：
//Author :Freetion
//file :133 - The Dole Queue #include <stdio.h>
#include <string.h>
using namespace std;
int pp[];
int k, m;
bool jug[]; int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
int k, m, n;
while (~scanf ("%d%d%d", &n, &k, &m) && (k+m+n))
{
memset(jug, true, sizeof (jug));
int shu = ;
int ni = n;
int total = n;
int num;
while (total)
{
num = ;
while (num < k)
{
if (shu > n)
shu -= n;
if (jug[shu++])
num ++;
}
shu --;
num = ;
while (num < m)
{
if (ni <= )
ni += n;
if (jug[ni --])
num ++;
}
ni ++;
if (ni == shu)
{
printf ("%3d", ni);
jug[ni] = false;
total --;
}
else
{
printf ("%3d%3d", shu, ni);
jug[ni] = jug[shu] = false;
total -= ;
}
if (total)
printf (",");
}
printf ("\n");
}
}
题目大意：给出一堆龟壳，我们要将它们按照另一种顺序排好，而每次操作都只能移动一个龟壳，并且只能将其放在这一堆的最上面。问使用最少的移动次数时依次移动龟壳的顺序。
解题思路：
解题代码：
//Author :Freetion
//file :10152 - ShellSort #include <iostream>
#include <stdio.h>
#include <string>
#include <map>
using namespace std; const int max_n = ; string str1[max_n], str2[max_n]; int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
int n, T;
scanf ("%d", &T);
while (T --)
{
scanf ("%d", &n);
getchar();
for (int i = n-; i >= ; i --)
{
getline(cin, str1[i]);
}
for (int i = n-; i >= ; i --)
{
getline(cin, str2[i]);
}
int j = ;
for (int i = ; i < n; i ++)
{
if (str1[i] == str2[j])
j ++;
}
for (; j < n; j ++)
cout << str2[j] << endl;
printf ("\n");
}
return ;
}
解题思路：将 左括号 入栈，如果碰上 右括号 则看是否与前一个左括号匹配，如果匹配则左括号匹配出栈，直到最后看栈是否空，空则Yes，否则No。
解题代码：
//Author :Freetion
//file :uva-673 Parentheses Balance #include <stdio.h>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
string str;
char mat(const char s)
{
if (s == ']')
return '[';
if (s == ')')
return '(';
return ;
} bool jug()
{
stack <char> st;
st.push('');
int len = str.size();
for (int i = ; i < len; i ++)
{
if (st.top() != mat(str[i]))
st.push(str[i]);
else st.pop();
}
return st.size() == ;
} int main()
{
int n;
scanf ("%d", &n);
getchar();
while (n --)
{
getline(cin, str);
if (str.size() == || jug())
printf ("Yes\n");
else printf ("No\n");
}
return ;
}
442 - Matrix Chain Multiplication
题目意思是让我们求矩阵相乘的总次数，另外括号是里面限定了只有两个矩阵！
解题思路：可以利用上题括号匹配，将先算的矩阵找出来，然后判断是否可以相乘，可以则计算次数，不可以则退出循环。
解题代码：
//Author :Freetion
//file :442 - Matrix Chain Multiplication #include <stdio.h>
#include <string.h>
#include <stack>
#include <iostream>
using namespace std; struct node
{
int x, y;
}Matrix[]; int main ()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
int n;
char s[];
char mul[];
while (~scanf ("%d", &n))
{
for (int i = ; i < n; i ++)
{
scanf ("%s", s);
scanf ("%d%d", &Matrix[s[]-'A'].x, &Matrix[s[]-'A'].y);
}
while (~scanf ("%s", mul))
{
int len = strlen(mul);
node temp[];
int top = ;
int ans = ;
bool falg = ;
for (int i = ; i < len; i ++)
{
if (mul[i] >= 'A' && mul[i] <= 'Z')
temp[top ++] = Matrix[mul[i]- 'A'];
else if (mul[i] == ')' && top > )
{
if (temp[top-].y != temp[top-].x)
{ falg = ; break; }
ans += temp[top-].y * temp[top-].x * temp[top-].y;
temp[top-].y = temp[top-].y;
top --;
}
}
if (falg)
printf ("%d\n", ans);
else
printf ("error\n");
}
}
}
11111 - Generalized Matrioshkas
此题与673相似，只是将左括号换成了负数，右括号换成了与之互为相反数的正数。当然依旧需要左右括号匹配，与此同时，这一级数的括号所用的数字，要比下一级括号所用的数字之和要大！
解题代码：
//Author :Freetion
//file :11111 - Generalized Matrioshkas #include <stdio.h>
#include <string>
#include <sstream>
#include <iostream>
#include <stack>
using namespace std; struct node
{
node(const int &a, const int &b):cap(a), left(b) {}
int cap, left;
}; int main ()
{
freopen ("data.in", "r", stdin);
freopen ("data.out", "w", stdout);
string line;
while (getline(cin, line))
{
stack <node> ope;
istringstream ss(line);
int t;
bool judge = false;
while (ss >> t)
{
if (t < )
{
if(ope.empty())
ope.push(node(-t, -t));
else
{
ope.top().left += t;
if (ope.top().left <= )
{ judge = ; break; }
else
ope.push(node(-t, -t));
}
}
else
{
if (ope.empty() || ope.top().cap != t)
{ judge = ; break; }
else
ope.pop();
}
}
if (judge || !ope.empty())
printf (":-( Try again.\n");
else printf (":-) Matrioshka!\n");
}
return ;
}
这题我也是百度思路的，所以直接贴代码：
//Author :Freetion
//file :11234 - Expressions
//´ËÊǺÃÌ⣡ #include <stdio.h>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
using namespace std; struct node
{
char ope;
node *left;
node *right;
node (char s, node *l, node *r)
{
ope = s;
left = l;
right = r;
}
node (char s)
{
ope = s;
left = NULL;
right = NULL;
}
}; int main()
{
string str;
int T;
scanf ("%d", &T);
getchar();
while (T--)
{
stack <node *> ans;
cin >> str;
int len = str.length();
for (int i = ; i < len; i ++)
{
if (islower(str[i]))
{
node *new_node = new node(str[i]);
ans.push(new_node);
}
else
{
node *a = ans.top();
ans.pop();
node *b = ans.top();
ans.pop();
node *new_node = new node(str[i], b, a);
ans.push(new_node);
}
}
node *root = ans.top();
ans.pop();
queue <node *> p;
p.push(root);
while (!p.empty())
{
node *q = p.front();
p.pop();
if (q -> left != NULL)
p.push(q -> left);
if (q -> right != NULL)
p.push(q -> right);
ans.push(q);
}
while (!ans.empty())
{
printf ("%c", ans.top()->ope);
ans.pop();
}
cout << endl;
}
return ;
}
题目大意：这题不难但是题意好难搞清楚（当然这是对我来说），看看能否说的清楚：给你一个初始队列，这个队列不同于一般的队列，它由多个队列组成一个大队列，然后依次输入操作，ENQUEUE n，代表将数n加入队列，如果在哪个队列里有与n相等的元素则加入该队列之后，如果没有则加入到最后那个队列之后，也就是输入的第一个队列。DEQUEUE 代表删除操作，删除操作是这样的，是按照队列来进行操作的，按队列先进先出的规则，也就是说哪个队列先加入元素，则先输出哪个队列里的元素。输出元素的规则就是先进先出，哪个元素先加入这个队列，则先输出哪个元素， 直到把加入该队列的元素都输出之后，再输出次优先的队列中的元素。每次只删除一个元素！（应该差不多了）
解题思路：运用队列来做！
解题代码：
#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <map>
using namespace std; int main()
{
int n, k, T = ;
while (~scanf ("%d", &n), n)
{
map <int, int> num;
queue <int> que[];
queue <int> que_num;
printf ("Scenario #%d\n", T++);
for (int i = ; i < n; i ++)
{
scanf ("%d", &k);
for (int j = ; j < k; j ++)
{
int x;
scanf ("%d", &x);
num[x] = i;
}
}
string str;
while (cin >> str && str[] != 'S')
{
if (str[] == 'E')
{
int x;
scanf ("%d", &x);
// cout << num[x] << endl;
if (que[num[x]].empty())
que_num.push(num[x]);
que[num[x]].push(x);
// cout << que_num.size() << endl;
}
else
{
int t = que_num.front();
printf ("%d\n", que[t].front());
que[t].pop();
if (que[t].empty())
que_num.pop();
}
}
printf ("\n");
}
}
水题一道
解题代码：
//Author :Freetion
//file :10050 - Hartals #include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int max_n = ;
bool ba[max_n]; int main()
{
int T;
int n, p;
scanf ("%d", &T);
while (T--)
{
scanf ("%d%d", &n, &p);
memset(ba, false, sizeof (ba));
for (int i = ; i < p; i ++)
{
int h;
scanf ("%d", &h);
for (int j = h; j <= n; j += h)
{
int wek = (j+)%;
if (wek != && wek != )
ba[j] = true;
}
}
int ans = ;
for (int i = ; i <= n; i ++)
if (ba[i])
ans ++;
printf ("%d\n", ans);
}
return ;
}