洛谷 P4683 [IOI2008] Type Printer
题目来源于：洛谷
题目本质：深搜，字典树Trie
当时想法：当时看了题目标签，就有思路了（见代码注释），但一直RE+WA最后只剩下RE。
正确思路：
我们使用字典树来完成。
首先，有一个点大大的降低了题目难度，就是打印结束时，允许有部分字母留在打印机内
众所周知，字典树很好地利用了字符串的公共前缀，这也就是上一行出现的原因。
如果我们想要操作数尽可能少，那我们的删除数的操作就要尽可能的少。
插入函数：
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] = ++ind; // 建点
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];
}
}dfs：
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() {
cin >> n;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
shu(s);
if (s.size() > p.size()){//一样要判断字符串长度
p = s;
}
}
mark(p);
dfs(0);//将输出掺杂到dfs里
return 0;
}我写的纯RE代码（思路可供参考）（洛谷高达64大分）：
//第二版不负众望又RE+WA了
//最后一次！
//What can I say！
//依旧感觉会崩掉
//纯RE没有WA了，CAO！
//前两版就不发了，大错特错！
#include<bits/stdc++.h>
using namespace std;
const int N = 25005;
const int M = 30;
int n, cur = 0, step = 1;
int tr[N][M];
char d[N];
bool mo[N], fla[N];
bool flag = false;
string q, p;
void shu(string s) {
int fu = 0;
int len = s.size();
for (int i = 0; i < len; ++i) {
int t = s[i] - 'a';
if (tr[fu][t] == 0){
tr[fu][t] = ++cur;
}
d[tr[fu][t]] = char(t + 'a');
fu = tr[fu][t];
}
mo[fu] = true;
}
void mark(string s) {
int fu = 0;
int len=s.size();
for (int i = 0; i < len; ++i) {
int t = s[i] - 'a';
fla[tr[fu][t]] = true;
fu = tr[fu][t];
}
}
void dfs(int mao) {
if (mo[mao]) {
++step;
q = q + 'P';
}
if (step > n) {
cout << q.size() << endl;
int len=q.size();
for (int i = 0; i < len; ++i){
cout << q[i] << endl;
}
exit(0);//直接退出
}
int x;
int tmp = -1;//使用tmp做临时标记
for (int i = 0; i < 26; ++i) {
x = tr[mao][i];
if (fla[x]){
tmp=x;
}
if (x != 0 && !fla[x]) {
q = q + d[x];
dfs(x);
}
}
if (tmp != -1) {
q = q + d[tmp];
dfs(tmp);
}
if (tmp == -1 && fla[mao]){
flag=true;
}
if (!flag){
q = q + '-';
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
shu(s);
if (s.size() > p.size()){//一样要判断字符串长度
p = s;
}
}
mark(p);
dfs(0);//将输出掺杂到dfs里
return 0;
}正解参考于：P4683 详解 - 洛谷专栏 (luogu.com.cn)
原文地址：https://blog.csdn.net/xiebohang/article/details/142210026
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！