目 录
组A01 字串数（简单排列组合） 1
组B01 放苹果（多重集合的组合） 2
组B02 有趣的排列（排列组合） 3
组B03 旅游路线（不相邻的排列） 4
组B04 序列（Catalan数） 5
组B05 洗牌问题（置换群） 6
算A01 植树活动（蛮力法） 7
算A02 密码（蛮力法） 8
算A03 数制转换（栈） 9
算A04 愚人节的礼物（栈） 10
注：组表示本题属于组合数学，算表示本题属于算法设计技术，A表示简单，B表示稍难。
组A01 字串数（简单排列组合）
【问题描述】
一个A和两个B一共可以组成三种字符串:"ABB","BAB","BBA".
给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串.
【数据输入】每组测试数据分两行,第一行为n(1<=n<=26),表示不同字母的个数,第二行为n个数A1,A2,...,An(1<=Ai<=12),表示每种字母的个数.测试数据以n=0为结束.
【数据输出】对于每一组测试数据,输出一个m,表示一共有多少种字符串.
【样例输入】
2
1 2
3
2 2 2
0
【样例输出】
3
90
组B01 放苹果（多重集合的组合）
【问题描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
【要求】
【数据输入】第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
【数据输出】对输入的每组数据M和N，用一行输出相应的K。
【样例输入】
1
7 3
【样例输出】
8
组B02 有趣的排列（排列组合）
【问题描述】
大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。
任务描述： 给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。
【数据输入】第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。
【数据输出】对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。
【样例输入】
3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
【样例输出】
3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 鸡年吉祥
10
组B03 旅游路线（不相邻的排列）
【问题描述】
假如长江沿岸有n个城市，每个城市依次标号（上游到下游次序编）为1，2，3…, n-3, n-2, n-1, n。alg想从长江上游出发，游玩这些城市。其中alg的旅游路线选取原则为：
1.至少要游玩一个城市。
2.不会游玩相邻的两个城市。即相邻的两个城市不会出现在algoo的旅游路线中。例如：当游玩过城市n-k后，就不会考虑在城市n-k+1停下。
现在你的任务是：如果有n个城市，帮助algoo计算有多少种路线可以选择。
【数据输入】多组测试数据。每组测试数据一行，为一个数n（1<=n<=100），表示城市的个数。
【数据输出】对每组测试数据，输出algoo总共有多少种路线选择。
【样例输入】
3
4
5
【样例输出】
4
7
12
Hint
数据会好大^_^
当n=4时，有如下几种路线。
1
2
3
4
1--> 3
1--> 4
2--> 4 （1，3城市都不玩，游玩过城市2后再到城市4）
共7种路线。
组B04 序列（Catalan数）
【问题描述】
一个序列{Ai, i=0,1,2,…,3*N}由3*N+1 项组成，每一项要么为1，要么为-2。
定义部分和S(K)=A0+A1+…+AK，求所有满足性质P的序列的数目，性质P为：S(3*N)=1 且对于所有的K=0,1,2,…,3*N-1,3*N，有S(K)>0（即所有项的和为１，且所有部分和为正）。
例如N=2 的时候，共有3 组这样的序列：
1, 1, 1, -2, 1, 1, -2
1, 1, 1, 1, -2, 1, -2
1, 1, 1, 1, 1, -2, -2
【数据输入】第一行输入N(N≤1000)。
【数据输出】满足P 性质的序列数目
【样例输入】
2
【样例输出】
3
组B05 洗牌问题（置换群）
【问题描述】
设2n张牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少需要经过多少次洗牌可恢复到初始状态。
【数据输入】输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。
【数据输出】对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。
【样例输入】
10
【样例输出】
6
算A01 植树活动（蛮力法）
【问题描述】春暖花开，万物复苏，这正是植物生长的好季节。珠海校区举行了一次题为“迎百年校庆，添三分绿色”的植树活动。这次植树活动的目的除了美化我们的校园，进一步增强同学们的环保意识以外，还在于迎接即将到来的百年校庆，张江河副院长认为这次活动意义重大，并不亚于其他大型的植树活动。他希望同学们要坚持照顾好自己所种的树，为它们浇水捉虫，让它们茁壮成长。 师生共同植树，打成一片。在这里我们看到的是热情，是团队合作精神，还有同学们为庆祝百年校庆的真诚的心！经过将近一个小时的努力，各单位基本上都把树种好。看到自己亲手种的树，同学们都非常兴奋，纷纷拍照留念，记下这个难忘的时刻！同学们感叹说：“这次活动很有意义啊！”，有的同学则希望能留下一个见证，让他们以后回来母校，可以看到自己的班集体种的树，会觉得很有意义。
这次植树活动有n个部门参加，树种有米兰、玉兰，有桂花、榕树，还有大皇椰等。每个部门分别种了m个树种，每个树种分别种了k1,k2,k3,…,km-1,km棵，现在有一个简单的任务，就请你帮忙计算一下每个部门分别种了多少棵树，全院一共种了多少棵树。
【数据输入】所有的数据都是从键盘输入，其数据格式是：第一行是参与植树的部门数n，
后面跟着的每二行是一个部门的数据，在每一个部门的数据中，第一行是该部门植树的树种数m，第二行是m个树种所种的棵数k1,k2,k3,…,km-1,km。
【数据输出】输出结果为按顺序输出每个部门所种的树棵数，及全院共种树的棵数。
【样例输入】
2
3
4 5 2
4
6 7 3 1
【样例输出】
11
17
28
算A02 密码（蛮力法）
【问题描述】网上流传一句话:"常在网上飘啊，哪能不挨刀啊～"。其实要想能安安心心地上网其实也不难，学点安全知识就可以。 首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件：
(1).密码长度大于等于8，且不要超过16。
(2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。
这四个字符类别分别为：
1.大写字母：A,Z;
2.小写字母：a,;
3.数字：0,9;
4.特殊符号：~,!,@,#,$,%,^;
给你一个密码，你的任务就是判断它是不是一个安全的密码。
【数据输入】输入数据有多组，对于每一组输入第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符输入0退出。
【数据输出】对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。
【样例输入】
3
a1b2c3d4
Linle@ACM
^~^@^@!%
0
【数据输出】
NO
YES
NO
算A03 数制转换（栈）
【问题描述】
有一种数制的基数是3，分别用数码0,1,2表示，如这种数制的101表示十进制数的10，即1*(3^2)+0*(3^1)+1*(3^0)=10，又如这种数制的-10 表示十进制数的-3，即-1*(3^1)+0*(3^0)=-3。编程要求把给定的有符号整数转换为新数制的数，该数的前面不能有多余的0，如10的新数制表示是101，则不要输出成0101。
【数据输入】文件有一行女装品牌大全排行榜
或多行，每行有一个整数N (-2,147,483,647≤N≤2,147,483,647)，整数内不会有其他分隔符。
【数据输出】对输入文件的每一行输出一行，该行是输入行的整数的新数制表示，不能有多余空行，每行之前不能有前导空格。
【样例输入】
10
-3
【样例输出】
101
-10
算A04 愚人节的礼物（栈）
【问题描述】
四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为愚人准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。
