D.Journey

题目大意：

给定n+1个点(从0开始),每两个相邻的点之间有一条边，最初每条边上有一个方向('L'或者'R') 表示从该点沿着这条路能够移动的方向。每次移动后，所有边上的方向都换变化('L' \(\rightarrow\) 'R' ||'R' \(\rightarrow\) 'L' )。问从每个点出发所能到达的最多的点的个数。

解题思路：

对于一个点我们可以考虑向左走或者向右走，我们模拟一下向右走就会发现，只有如：RLRLRL这种情况我们才能不断的往右走，向左走同理。所以我们可以根据此来考虑一个dp。

定义f_l[N][2] 为节点i状态为j时所能向左到达的最多节点数，其中状态j只有两种，0表示初始状态，1表示变化后的状态，据此得到状态转移，如果(j^l[i] (表示边i初始状态是否可以向左走) )则f[i][j] += f[i-1][j^1]

最后对于每个点将向左和向右的答案合并即可

代码实现：

#include<iostream>
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 3e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;
const int esp = 1e-6;
int l[N], r[N];
void solve() {
	int n;
	memset(l, 0, sizeof l);
	memset(r, 0, sizeof r);
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		char c;
		cin >> c;
		if (c == 'L') l[i] = 1;
		else r[i - 1] = 1;
	}
	vector<vector<int>> f_l(n + 1, vector<int>(2, 0)), f_r(n + 1, vector<int>(2, 0));
	f_l[0][0] = f_l[0][1] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0 ; j < 2; ++j) {
			f_l[i][j] = 1;
			if (j ^ l[i]) f_l[i][j] += f_l[i - 1][j ^ 1];
		}
	}

	f_r[n][0] = f_r[n][1] = 1;
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 2; ++j) {
			f_r[i][j] = 1;
			if (j ^ r[i]) f_r[i][j] += f_r[i + 1][j ^ 1];
		}
	}
	for (int i = 0; i <= n; i ++)
		cout << f_l[i][0] + f_r[i][0] - 1 << ' ';
	cout << endl;
}

int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
	cin >> tt;
	while (tt--) solve();


	return 0;
}

E.Pattern Matching

题目大意：

给定n个长度为k的S串和m个T串，每个T串我们希望他的第一匹配串为x（重新排序后）,问是否存在这种排序。

第一匹配串是指：对于一个T串i，他能够和S串1,3,5匹配，他的目标第一T串为3，所以他希望排序后的串顺序要让3在最前，例如：315,351...

解题思路:

我们先不考虑如何匹配S串和T串，仅考虑排序，对于一个T串，如果他想要满足第一T串为x，那么他的目标实际上就是让串x在其他匹配的S串之前即可，那么这就与拓扑序很像，所以我们每次对于一个T串，我们找到所有与他匹配的S串(u),对 x$\rightarrow $ u 连一条边，当所有的边连完以后，如果这个图是一个拓扑图，那么它就满足条件，按照拓扑序输出即可。

考虑匹配： 将所有的S串存入trie中进行匹配

在查询的时候因为要找出所有匹配的S串，所以考虑递归的在trie树中转移。

代码实现

#include<iostream>
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 3e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;
const int esp = 1e-6;
int tr[N][27];
int cnt = 1;
int a[N];
int n, m, k;
vector<int> v;
bool check(string s,string t){
	for(int i = 0;i < k;++i){
		if(s[i]!=t[i]&&s[i]!='_'&&t[i] != '_') return false;
	}
	return true;
}
void insert(string s, int id) {
	int p = 1;
	for (int i = 0 ; s[i]; ++i) {
		int u;
		if (s[i] == '_') u = 26;
		else u = s[i] - 'a';
		if (!tr[p][u]) tr[p][u]  = ++cnt;
		p = tr[p][u];
	}
	a[p] = id;
}

void que(string& s, int p, int now) {
	if (now == k) {
		v.push_back(a[p]);
		return;
	}
	char c = s[now];
	if (c == '_') {
		for (int i = 0; i < 27; ++i) {
			if (tr[p][i])
				que(s, tr[p][i], now + 1);
		}
	} else {
		if (tr[p][26]) que(s, tr[p][26], now + 1);
		if (tr[p][s[now] - 'a']) que(s, tr[p][s[now] - 'a'], now + 1);
	}
}
vector<int> e[N];
int d[N];
int ans[N], tot;
bool top() {
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (d[i] == 0) q.push(i);
	}
	tot = 0;
	while (q.size()) {
		auto u = q.front();
		q.pop();
		ans[++tot] = u;
		for (auto v : e[u]) {
			d[v]--;
			if (d[v] == 0) {
				q.push(v);
			}
		}
	}
	return tot == n;
}
string t[N];
void solve() {
	bool ok = true;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> t[i];
		insert(t[i], i);
	}
	for (int i = 1; i <= m; ++i) {
		string s;
		int x;
		cin >> s >> x;
		
		if(!ok) continue;
		if(!check(s,t[x])){
			ok = false;
			continue;
		} 
		v.clear();
		que(s, 1, 0);
		
		for (auto u : v) {
			if(x == u) continue;
			e[x].push_back(u);
			d[u]++;
		}
	}

	if (!ok) {
		cout << "NO" << endl;
		return;
	}
	if (!top()) {

		cout << "NO" << endl;
		return;
	}
	cout << "YES" << endl;
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << " ";
	}
}

int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
//	cin >> tt;
	while (tt--) solve();


	return 0;
}