题意:看输出就懂了,暴力枚举题,字符串最大长度是8,所有长度等于8的长度是8!=1x2x3x4x5x6x7x8=40320,数据量比较小的.只是枚举的方向比较怪异,如下,长度等于3的串
a
ab,ba
abc,acb,cab
bac,bca,cba
但是输出确实不好输出,事实上输出的位置是可用计算出来的.
解法:
组成一颗多叉树,根节点是a,那么第1层有俩个孩子,第二层有三个孩子,第三层有4个孩子,一直往下生成,到第八层,然后就是遍历这颗多叉树.
AC时间,80ms
2G内存的电脑还是能刷题的
#include <iostream>
#include <stdio.h>
#include<memory.h>
using namespace std; const int N = 8;
#define null NULL
struct Node
{
char a[8];
int al;
Node* cp[8];
int cl;
Node()
{
memset(a, 0, sizeof(a));
al = 0;
memset(cp, 0, sizeof(cp));
cl = 0;
}
;
};
char le[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' };
const int l = 8;
Node* root = null; void copy(Node* root, Node* node, int index, char c)
{
int k = root->al + 1;
int j = 0;
for (int i = 0; i < k; i++)
{
if (i == index)
{
node->a[node->al++] = c;
continue;
}
node->a[node->al++] = root->a[j++];
}
} void buildTree(Node* root, int index, int n)
{
if (index == n) return;
for (int i = index; i >= 0; i--)
{
Node* node = new Node();
copy(root, node, i, le[index]);
root->cp[root->cl++] = node;
}
for (int i = 0; i < root->cl; i++)
buildTree(root->cp[i], index + 1, n);
}
void blank(int n)
{
for (int i = 0; i < n; i++)
cout << " ";
}
void print(char a[], int l)
{
cout << a[0];
for (int i = 1; i < l; i++)
cout << "," << a[i]; }
void dfs(Node* root, int n, int index, int bs)
{
if (index + 1 == n)
{
blank(bs);
cout << "writeln(";
print(root->a, root->al);
cout << ")" << endl;
return;
}
for (int i = 0; i < root->cl; i++)
{
blank(bs);
if (i == 0)
{
cout << "if ";
}
else if (i == root->cl - 1)
{
cout << "else ";
}
else
{
cout << "else if ";
}
if (i == 0)
{
cout << root->cp[i]->a[index] << " < " << root->cp[i]->a[index + 1]
<< " " << "then";
}
else if (i != root->cl - 1)
{
cout << root->cp[i]->a[index - i] << " < "
<< root->cp[i]->a[index + 1 - i] << " " << "then";
}
cout << endl;
dfs(root->cp[i], n, index + 1, bs + 2);
}
} int main()
{
freopen("C:\\Users\\zzzzz\\Desktop\\1.txt", "r", stdin);
int caseNum = 0;
cin >> caseNum;
while (caseNum--)
{
int m;
cin >> m;
cout << "program sort(input,output);" << endl;
cout << "var" << endl;
print(le, m);
cout << " : " << "integer;" << endl;
cout << "begin" << endl;
int bs = 2;
blank(bs);
cout << "readln(";
print(le, m);
cout << ");" << endl;
int index = 0;
root = new Node();
root->a[root->al++] = le[index];
index++;
buildTree(root, index, m);
//cout << root->cl << endl;
if (m == 1)
{
blank(bs);
cout << "writeln(a)" << endl;
}
else
{
dfs(root, m, 0, bs);
}
cout << "end." << endl;
if (caseNum != 0)
{
cout << endl;
}
} return 0;
}