前言
emmmmmm，这次的题就比较棘手啦！
第三题
题目
标题：魔方状态
二阶魔方就是只有2层的魔方，只由8个小块组成。
如图所示。
小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：
前面：橙色
右面：绿色
上面：黄色
左面：绿色
下面：橙色
后面：黄色
请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。
如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。
请提交表示状态数的整数，不要填写任何多余内容或说明文字。
分析
2×2的魔方乍一看很小，实际上里面的变化非常多。
这道题我比赛的时候由于不会就先跳过了，做完其它会的题再来做这道，然后就做错了。。。
首先我们可以估计一下这个魔方的状态数：
将这个魔方拆开，我们可以得到8个小方块：
通过对它们的旋转，我们会发现有4种块：橙黄绿、黄橙绿、橙橙绿、黄黄绿，每种块各2个。
如果我们将魔方的位置标号放入方块的话，就有C（8,2）*C（6,2）*C（4,2）*C（2,2）=5040种，每一个方块又都有三种方向，那么最后的状态数就是5040*3^8 = 33067440种
但这只是一个状态的上限，因为有两个问题存在：
1.有多少种状态是可以通过整体旋转变成相同状态的呢？
2.是否有拆下又拼回魔方之后无法还原的状态呢？
这些我们都不知道（至少我是不知道。。。）
现在这道题就无从下手了。。。
当你被题目卡住的时候，你的任务应该是去做下一道题，而不是停留在这道题上，那就让我们去做别的题吧
------------------------------------做题ing----------------------------------------------------------------------
现在我们已经做完了其它会做的题，再来看这道题：
虽然我们对魔方的性质知之甚少，但是我们有已知的东西：魔方的初始状态+魔方的转移方法
那么我们就可以尝试着用广搜去找出所有的魔方状态（至少对于电脑来说，存下三千多万的状态压力不大）
代码及运行结果
#include <cstdio>
#include <string>
#include <queue>
#include <set>
using namespace std;
queue<string> que;
void rF(string &s) {
char tmp;
tmp = s[1], s[1] = s[3], s[3] = s[4], s[4] = s[2], s[2] = tmp;
tmp = s[19], s[19] = s[16], s[16] = s[22], s[22] = s[5], s[5] = tmp;
tmp = s[20], s[20] = s[14], s[14] = s[21], s[21] = s[7], s[7] = tmp;
} // 将前面顺时针转90°
void rR(string &s) {
char tmp;
tmp = s[5], s[5] = s[7], s[7] = s[8], s[8] = s[6], s[6] = tmp;
tmp = s[2], s[2] = s[22], s[22] = s[11], s[11] = s[18], s[18] = tmp;
tmp = s[4], s[4] = s[24], s[24] = s[9], s[9] = s[20], s[20] = tmp;
} // 将右面顺时针转90°
void rU(string &s) {
char tmp;
tmp = s[17], s[17] = s[19], s[19] = s[20], s[20] = s[18], s[18] = tmp;
tmp = s[13], s[13] = s[1], s[1] = s[5], s[5] = s[9], s[9] = tmp;
tmp = s[14], s[14] = s[2], s[2] = s[6], s[6] = s[10], s[10] = tmp;
} // 将顶面顺时针转90°
void rB(string &s) {
char tmp;
tmp = s[9], s[9] = s[11], s[11] = s[12], s[12] = s[10], s[10] = tmp;
tmp = s[18], s[18] = s[8], s[8] = s[23], s[23] = s[13], s[13] = tmp;
tmp = s[17], s[17] = s[6], s[6] = s[24], s[24] = s[15], s[15] = tmp;
} // 将背面顺时针转90°
void rL(string &s) {
char tmp;
tmp = s[13], s[13] = s[15], s[15] = s[16], s[16] = s[14], s[14] = tmp;
tmp = s[17], s[17] = s[12], s[12] = s[21], s[21] = s[1], s[1] = tmp;
tmp = s[19], s[19] = s[10], s[10] = s[23], s[23] = s[3], s[3] = tmp;
} // 将左面顺时针转90°
void rD(string &s) {
char tmp;
tmp = s[21], s[21] = s[23], s[23] = s[24], s[24] = s[22], s[22] = tmp;
tmp = s[3], s[3] = s[15], s[15] = s[11], s[11] = s[7], s[7] = tmp;
tmp = s[4], s[4] = s[16], s[16] = s[12], s[12] = s[8], s[8] = tmp;
} // 将底面顺时针转90°
set<string> visit;
void visit_put(string &s) {
// 将前面顺时针转90°，后面也顺时针转90°，相当于将整个魔方绕前面转了90°
// 其它方向的旋转同理
for (int i = 0; i < 4; i++) {
bool flag = true;
rF(s), rB(s);
visit.insert(s);
}
}
void exist(string &s) {
// 将魔方的6个面都转至正面
visit_put(s);
rU(s), rD(s);
visit_put(s);
rU(s), rD(s);
visit_put(s);
rU(s), rD(s);
visit_put(s);
rU(s), rD(s), rL(s), rR(s);
visit_put(s);
rL(s), rL(s), rR(s), rR(s);
visit_put(s);
rL(s), rR(s);
}
int main() {
int ans = 0;
string a = "u000011112222111122220000";
// 魔方的初始状态，0表示橙色，1表示绿色，2表示黄色
que.push(a);
exist(a);
while (!que.empty()) {
string str = que.front();
que.pop();
ans++;
// 一个方向拧和相对方向拧是一样的，所以我们只考虑前右上的旋转
for (int i = 0; i < 4; i++) {
rF(str);
if (visit.find(str) == visit.end()) {
que.push(str);
exist(str);
}
}
for (int i = 0; i < 4; i++) {
rU(str);
if (visit.find(str) == visit.end()) {
que.push(str);
exist(str);
}
}
for (int i = 0; i < 4; i++) {
rR(str);
if (visit.find(str) == visit.end()) {
que.push(str);
exist(str);
}
}
}
// ans表示考虑魔方整体旋转的结果，size表示不考虑魔方整体旋转的结果
printf("ans = %d, size = %d\n", ans, visit.size());
return 0;
}
魔方的展开图如下
运行结果：
代码写的长长长，从结果中可以看出，数是真的大大大，跑得也是真的慢慢慢= =而且答案对不对呢？不知道。。。
所以比赛的时候，遇到这种题，一定要慎重啊= =！
拓展
魔方的状态计数，其实和群论、组合计数等关系更为密切，所以或许有一种计算的方法可以直接把答案求出来吧？
坐等dalao来补充=w=
第四题
题目
标题：方格分割6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图就是可行的分割法。
试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。
分析
想要把一个正方形分割成两个形状相同的图形，只能让他们中心对称。
那么我们就有一种很高效的方法：将这些格子的左半部分染色情况暴力地全部尝试一遍，由于最终图形是中心对称的，所以右半边的图形也可以通过左半边确定。我们只要在画完之后判断其正确性即可（也就是相同颜色的是否连在了一起）。左半边的情况一共有2^18=262144种，对于电脑来说，so easy。
为了方便写出染色的过程，这里我们就用一种与广搜齐名的搜索方法：深度优先搜索。
深搜和广搜相比，有很多独特的优势：
1.代码简单，深搜可以用递归的方式实现（还记得第五题里的函数f吗）
2.不需要记录所有的状态，因为深搜在搜索完一个子状态后，它就可以被扔掉了，这样的话可以节省空间
3.方便剪枝、回溯：由于搜索的状态就像一棵树一样延伸（就像第二题里的三角洲），我们将避免无用状态的方法叫做剪枝，这样可以大大提高运行效率。而回溯是指在一个状态非法时，可以回到它的上一个状态。
深搜的实现和递归一样。
除此以外，我们还有另一种方法。由于分割图形是通过在正方形中画一条折线完成的，我们可以不确定图形，而是去确定这条折线来完成这道题。由于被切割开的两个图形一定是中心对称的，所以这条折线一定经过*点并且关于这个点中心对称。所以我们就让折线从这个中心点出发，一直画到边界为止。
在旋转对称图形相同的情况下，我们让这条折线碰触上边界就OK了。
代码及运行结果
第一种方法：
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 6 + 5;
const int d[5][3] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int mp[MAX_N][MAX_N], ans;
bool visit[MAX_N][MAX_N];
// 以下这两段代码都被称为深度优先搜索
int judge(int x, int y) {
int res = 1;
visit[x][y] = true;
for (int i = 0; i < 4; i++) {
int tx = x + d[i][0], ty = y + d[i][1];
if (tx < 0 || tx > 5) continue;
if (ty < 0 || ty > 5) continue;
if (mp[tx][ty] != mp[x][y]) continue;
if (visit[tx][ty]) continue;
res += judge(tx, ty);
}
return res;
}
void dfs(int x, int y) {
if (y == 6) {
dfs(x + 1, 0);
return;
}
if (x == 3) {
memset(visit, false, sizeof(visit));
if (judge(0, 0) == 18) ans++;
return;
}
mp[x][y] = 0;
mp[5 - x][5 - y] = 1;
dfs(x, y + 1);
mp[x][y] = 1;
mp[5 - x][5 - y] = 0;
dfs(x, y + 1);
}
int main() {
ans = 0;
dfs(0, 0);
printf("ans = %d\n", ans);
return 0;
}
运行结果：
我们发现深搜确实很方便，能让代码缩短很多。所以在比赛中，深搜是一种很实用的方法。
注意到我们还没有考虑题目中的旋转对称属于同一种分割方法。
由于在正方形中，旋转的结果会有四种：90°，180°，270°，不转。所以结果应该是2036÷4=509种
第二种方法：
#include <cstdio>
using namespace std;
const int MAX_N = 6 + 5;
const int d[5][3] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int ans;
bool visit[MAX_N][MAX_N];
void dfs(int x, int y) {
if (x == 0) {
ans++;
return;
}
for (int i = 0; i < 4; i++) {
int tx = x + d[i][0], ty = y + d[i][1];
if (tx > 5 || ty <= 0 || ty > 5) continue;
if (visit[tx][ty]) continue;
visit[tx][ty] = true;
visit[6 - tx][6 - ty] = true;
dfs(tx, ty);
// 搜索结束后，回溯到上一个状态
visit[tx][ty] = false;
visit[6 - tx][6 - ty] = false;
}
}
int main() {
ans = 0;
visit[3][3] = true;
dfs(3, 3);
printf("ans = %d\n", ans);
return 0;
}
运行结果：
当然，如果你对深搜的使用还不熟悉的话，那么你应该先去做其他的题目，然后再回来仔细研究深搜的写法。
深搜相比广搜来说，更加短小精悍，也更加灵活，但是难度也会大一些。