CF54D P4683

CF54D

暴力枚举，遇到1就在序列中加入子序列并判断是否成立

需要注意的细节是0的时候不能是子序列开头

P4683

//很容易发现，建立trie树之后总的答案数就是每颗子树的大小*2减去最长的单词的长度
//最长的长度也可以在进行递归时统计
//在递归时统计输出和答案大小，这就需要算法保证离线
//输出顺序只需要保证最长的单词最后在输出就可以了
//给最长单词所在的整棵根节点的子树打上标记，访问到后就跳过
//最后在将这颗子树递归输出，还是到了被标记的子树后先输出不被标记的，最后再输出标记的子树

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

bool en[N];
bool k[N];
char le[N];
int tree[N][26];//第一维是节点，第二维是节点的什么儿子

int n, m, ans;
string s, output, ml;

int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
//建立trie
int tot;
void insert(string s) {
	int p = 0;
	for (int i = 0; s[i]; i++) {
		int x = s[i] - 'a';
		if (!tree[p][x])
			tree[p][x] = ++tot;
		le[tree[p][x]] = x + 'a';
		p = tree[p][x];
	}
	en[p] = 1;
}
void mark(string s) {
	int p = 0;
	for (int i = 0; s[i]; i++) {
		int x = s[i] - 'a';
		k[tree[p][x]] = 1;
		p = tree[p][x];
	}
}
void dfs(int x) {
	if (en[x] == 1 && x != 0) {
		ans++;
		output += "P";
	}
	if (ans == n) {
		cout << output.size() << endl;
		for (int i = 0; output[i]; i++)
			cout << output[i] << endl;
		return;
	}
	int reg;
	for (int i = 0; i < 26; i++) {//先输出不带标记的
		reg = tree[x][i];
		if (k[reg] == 0 && reg != 0) {
			output += le[reg];
			dfs(reg);
			output += "-";
		}
	}
	for (int i = 0; i < 26; i++) {//最后输出带标记的
		reg = tree[x][i];
		if (k[reg] && reg) {
			output += le[reg];
			dfs(reg);
			output += "-";
		}
	}
}
int main() {
	n=read();
	//cout<<n;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		insert(s);
		if (ml.size() < s.size()) ml = s;
	}
	mark(ml);
	dfs(0);
	return 0;
}