Peculiar Movie Preferences（字典树/贪心）

题目

题意：给定n个长度不超过3的字符串。从中可以删去若干个字符串，使得剩下的字符串，按顺序拼接后，是回文数。

思路：由于可以删字符串，所以我们只需要判断 这n个字符串是否有回文串，或者存在前后两个字符串，能配成回文串，即可。

#include 
using namespace std;
const int maxn = 100010;

int n, m;
string s;
set st;

const int tree_mx = 26;
struct Tree {
	bool flag;
	Tree* nxt[tree_mx];
	Tree() {
		memset(nxt, 0, sizeof(nxt));
		flag = 0;
	}
};
void ins(Tree *&root, string &s) {
	Tree *rt = root;
	int len = s.length();
	for (int i = 0, x; i nxt[x] == NULL) {
			rt->nxt[x] = new Tree();
		}
		rt = rt->nxt[x];
	}
	rt->flag = 1;
}
bool find1(Tree *rt, string &s, bool is_strict = false) {
	int len = s.length();
	for (int i = 0, x; i nxt[x] == NULL) {
			return false;
		}
		rt = rt->nxt[x];
	}
	return is_strict ? rt->flag : true;
}
void solve() {
	scanf("%d", &n);
	st.clear();
	bool flag = 0;
	Tree *root = new Tree();
	for (int i = 0; i > s;
		if (flag) {
			continue;
		}
		int len = s.length();
		if (s[0] == s[len-1]) {//判断自身能否回文 
			flag = 1;
		} else {
			string t = s;
			reverse(t.begin(), t.end());
			string t2 = t.substr(0, t.length()-1);
			// 能和之前的回文串组成回文 (考虑多一个字符的情况) 
			// 或者自身第一个字符做为中间字符，和之前的回文串回文
			// exp 1. "abc" + "ba", "ab" + "ba" 2. "ab" + "cba" 
			if (find1(root, t) || find1(root, t2, true)) {
				flag = 1;
			}
		}
		ins(root, s);
	}
	
	printf("%s\n", flag ? "YES" : "NO");
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}