题目列表：
第一题：扑克牌。
题意：一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。现在给定52张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。输出模2^64之后的值。牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。Y为花色，为S、H、D、C中的一个。如2S、2H、TD等。
输入：第一行为一个整数T，为数据组数。之后每组数据占一行。这一行首先包含一个整数N，表示给定的牌的张数，接下来N个由空格分隔的字符串，每个字符串长度为2，表示一张牌。每组数据中的扑克牌各不相同。
思路：小数据搜索就能过，大数据（N<=52）需要用动态规划（记忆化搜索）。可以有两种思路。
1、四维dp。dp[a][b][c][d]表示用a个只出现1次的、b个出现2次的、c个出现3次的和d个出现4次的能够放置的方法数。每次枚举当前位放置的是出现几次（1~4）的，然后求和。对于当前放置出现1~4次的转移方程见代码。拿出现3次的来解释：当前位放置的方法数有3c个，这样放置会减少一个出现3次的，增加一个出现两次的，所以剩下的放置数是dp(a,b+1,c-1,d)。但是后者包括下一个位置放置的与当前位相同的情况，所以要减去这种情况。与当前位相同有两种选择，所以是2*dp(a+1,b,c-1,d)。但是一定注意，这样减又减多了，因为减去的部分包括下一位和下下位都相同的情况，而这种在dp(a,b+1,c-1,d)里是不会出现的，所以还得加回来。如此这般，转移方程就写好了。
2、dp[a][b][c][d][pre]表示用a个只出现1次的、b个出现2次的、c个出现3次的和d个出现4次的以及上一位是pre次能够放置的方法数。总体思路与1差不多，这样的好处是不用考虑加多减多。状态转移方程见代码。
注意：题目要求对答案模2^64，那么应该用unsigned long long 来存储（输出是%llu），而且相当于不做任何处理直接加即可，因为如果溢出就相当于模2^64运算。
思路1：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define MOD 1<<64#define N 54#define M 13char ch[5];int num[M+5],hh[1000];int T,c,n;unsigned long long dp[M+3][M+3][M+3][M+3];void init(){int i;for(i = 2;i<=9;i++)hh['0'+i] = i;hh['T'] = 10;hh['J'] = 11;hh['Q'] = 12;hh['K'] = 13;hh['A'] = 1;memset(dp, -1, sizeof(dp));dp[0][0][0][0]= 1;}unsigned long long test(int a,int b,int c,int d){unsigned long long res = 0;if(dp[a][b][c][d] != -1)return dp[a][b][c][d];if(a > 0)//放置出现一次的res += a*test(a-1,b,c,d);if(b > 0)//放置出现两次的res += 2*b*(test(a+1, b-1, c, d) – test(a, b-1, c, d));if(c > 0)//放置出现三次的res += 3*c*(test(a, b+1, c-1, d) – 2*(test(a+1,b,c-1,d) – test(a,b,c-1,d)));if(d > 0)//放置出现四次的res += 4*d*(test(a, b, c+1, d-1) – 3*(test(a,b+1,c,d-1) – 2*(test(a+1,b,c,d-1) – test(a,b,c,d-1))));return dp[a][b][c][d] = res;}int main(){init();scanf("%d",&T);for(c = 1;c<=T;c++){int i,x,y,z,w;memset(num, 0, sizeof(num));scanf("%d",&n);for(i = 1;i<=n;i++){scanf("%s",ch);num[hh[ch[0]]]++;}x = y = z = w = 0;for(i = 1;i<=M;i++){if(num[i]==1)x++;else if(num[i] == 2)y++;else if(num[i] == 3)z++;else if(num[i] == 4)w++;}printf("Case #%d: %llu\n",c,test(x,y,z,w));}return 0;}思路2：#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define MOD 1<<64#define N 54#define M 13char ch[5];int num[M+5],hh[1000];int T,c,n;unsigned long long dp[M+3][M+3][M+3][M+3][5];void init(){int i;for(i = 2;i<=9;i++)hh['0'+i] = i;hh['T'] = 10;hh['J'] = 11;hh['Q'] = 12;hh['K'] = 13;hh['A'] = 1;memset(dp, -1, sizeof(dp));for(i = 0;i<5;i++)dp[0][0][0][0][i] = 1;}unsigned long long test(int a,int b,int c,int d,int pre){unsigned long long res = 0;if(dp[a][b][c][d][pre] != -1)return dp[a][b][c][d][pre];if(a > 0){if(pre != 1)res += a*test(a-1,b,c,d,0);elseres += (a-1)*test(a-1,b,c,d,0);}if(b > 0){if(pre != 2)res += 2*b*(test(a+1, b-1, c, d ,1));elseres += 2*(b-1)*(test(a+1, b-1, c, d ,1));}if(c > 0){if(pre != 3)res += 3*c*(test(a, b+1, c-1, d ,2));elseres += 3*(c-1)*(test(a, b+1, c-1, d ,2));}if(d > 0){if(pre != 4)res += 4*d*(test(a, b, c+1, d-1 ,3));elseres += 4*(d-1)*(test(a, b, c+1, d-1 ,3));}return dp[a][b][c][d][pre] = res;}int main(){init();scanf("%d",&T);for(c = 1;c<=T;c++){int i,x,y,z,w;memset(num, 0, sizeof(num));scanf("%d",&n);for(i = 1;i<=n;i++){scanf("%s",ch);num[hh[ch[0]]]++;}x = y = z = w = 0;for(i = 1;i<=M;i++){if(num[i]==1)x++;else if(num[i] == 2)y++;else if(num[i] == 3)z++;else if(num[i] == 4)w++;}printf("Case #%d: %llu\n",c,test(x,y,z,w,0));}return 0;}
第二题：攻城略地。
题意：A、B两国间发生战争。已知A国共有n个城市（编号1, 2, …, n），城市间有一些道路相连。每座城市的防御力为w，直接攻下该城的代价是w。若该城市的相邻城市（有道路连接）中有一个已被占领，则攻下该城市的代价为0。除了占领城市，B国还要摧毁A国的交通系统，因而他们需要破坏至少k条道路。由于道路损毁，攻下所有城市的代价相应会增加。假设B国可以任意选择要摧毁的道路，那么攻下所有城市的最小代价是多少？
输入：第一行一个整数T，表示数据组数，以下是T组数据。每组数据第一行包含3个整数n, m, k。第二行是n个整数，分别表示占领城市1, 2, …, n的代价w。接下来m行每行两个数i, j，表示城市i与城市j间有一条道路。
闽南的花市，一开始是来自漳州百花村，
