首页 > 其他分享 >(AtCoder Beginner Contest 287)(D 字符串前后缀合并匹配)(E Trie求最长公共前缀(LCP)) (F 树形背包dp)

(AtCoder Beginner Contest 287)(D 字符串前后缀合并匹配)(E Trie求最长公共前缀(LCP)) (F 树形背包dp)

时间:2023-01-29 19:55:05浏览次数:65  
标签:AtCoder 联通 LCP Beginner int Trie 字符串 节点 分量

D - Match or Not(字符串前后缀合并匹配)

题目大意:

给定两个字符串S和T,对于每个x = 0,1,2...|T|求S的子串(前x个字符和后|T|-x个字符在不改变顺序的情况下组成)是否与T相同
(|T|表示字符串T的长度)


解题思路:

只有当s[i] == '?' ||t[i] == '?' || s[i] == t[i]时两个字符串才匹配,所以我们可以对S和T的前后缀进行匹配,如果同时满足pre[i]和suf(|T|-i)才能说明S的子串与T相同(O(1))


代码实现:

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5 + 10, inf = 1e18;

void solve() {

	string s;
	string t;
	cin >> s >> t;
	vector<int> pre(s.size()+1,false),suf(s.size()+1,false);
	pre[0] = true;
	auto cal = [&](char a,char b)->bool{
		return (a=='?'||b=='?'||a==b);	
	};
	
	for(int i = 0;i < t.size();++i){
		if(!cal(s[i],t[i])) break;
		pre[i+1] = true;	
	}
	
	reverse(s.begin(),s.end());
	reverse(t.begin(),t.end());
	
	suf[0] = true;
	for(int i = 0;i < t.size();++i){
		if(!cal(s[i],t[i])) break;
		suf[i+1] = true;
	}
	
	for(int i = 0;i <= t.size();++i){
		if(pre[i]&&suf[t.size()-i]){
			cout<<"Yes"<<endl;
		}
		else cout<<"No"<<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 - Karuta(Trie求最长公共前缀(LCP))

题目大意:

给定N个字符串,求N个字符串对除了自己以外的字符串的最长公共前缀长度(LCP)


解题思路:

Trie树的模板题了,但是因为要求除了自己以外的字符串的LCP,所以我们需要对Trie树的每个节点进行计数,如果同一个节点超过了2,说明该节点除了本字符串至少有1个其他字符串也有该节点,可以对答案进行计数,否则该节点只有当前字符串有,结束计数。


代码实现:

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 5e5 + 10, inf = 1e18, mod = 1e9 + 7;
struct Trie{
	int n;
	int idx;
	vector<vector<int>> son;
	vector<int> cnt;
	Trie(int n_):n(n_){
		son.resize(n+1);
		cnt.resize(n+1);//树的大小
		for(int i = 0;i <= n+1;++i){
			son[i].resize(28);//字符集大小
		}
		idx = 0;
	}
	
	void insert(string s){
		int p = 0;
		for(int i = 0;i < s.size();++i){
			int u = s[i]-'a';
			if(!son[p][u]) son[p][u] = ++idx;
			p = son[p][u];
			cnt[p]++;
		}
	}
	
	int query(string t){
		int p = 0;
		int sum = 0;
		for(int i = 0;i < t.size();++i){
			int u = t[i]-'a';
			p = son[p][u];
			if(cnt[p]<=1) break;
			sum++;
		}
		return sum;
	}
	
};
string a[N];
void solve() {
	int n;
	cin>>n;
	Trie tr(N);
	for(int i = 1;i <= n;++i)
	{
		cin>>a[i];
		tr.insert(a[i]);
	}
	
	for(int i = 1;i <= n;++i){
		cout<<tr.query(a[i])<<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;
}

F - Components(树形背包dp)

题目大意:

给定一个N个节点的树,求该树的导出子图满足有X = 1,2,....N个联通分量的情况


解题思路:

树形背包dp: f[i][j][0/1]表示以i为为根的子树中选j个联通分量,根节点(0/1)选或者不选的情况

考虑到如果相邻两个节点如果同时选,那么对于联通分量的数量不做贡献,如果对于不相邻的节点同时选择会增加联通分量的数量
所以转移如下:
定义g[j][0/1] 表示以u为根的子树中选j个联通分量,其中根节点选/不选

f[u][j][0] = g[j-k][0]*(f[v][k][0]+f[v][k][1]);
f[u][j][1] = g[j-k][1]*f[v][k][0]+g[j-k][1]*f[v][k+1][1]

  • 当根节点u不选时,子节点v选不选都不会影响联通分量的数量
  • 当根节点选时,如果子节点不选那么也不影响联通分量的数量,但是如果子节点也选的话联通分量的数量会减一,所以需要在子节点的树中多选一个联通分量

初始化时对于每个节点f[u][0][0] = f[u][1][1] = 1


代码实现:

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 5100 + 10, inf = 1e18, mod = 998244353;
vector<int> e[N];
int f[N][N][2];//以i为根的子树中选j个联通分量且节点i(0/1)选不选 
int sz[N];
int g[N][2];
void dfs(int u,int fa){
	sz[u] = 1;
	f[u][0][0] = f[u][1][1] = 1;
	for(auto v:e[u]){
		if(v  == fa) continue;
		dfs(v,u);
		for(int j = 0;j <= sz[u]+sz[v];++j){
			g[j][0] = f[u][j][0];
			g[j][1] = f[u][j][1];
			f[u][j][0] = f[u][j][1] = 0;
		}
		for(int j = sz[u]+sz[v];j>=0;--j){
			for(int k = max(0ll,j-sz[u]);k<=min(j,sz[v]);++k){
				f[u][j][0] += g[j-k][0]*(f[v][k][0]+f[v][k][1])%mod;
				f[u][j][1] += (g[j-k][1]*f[v][k][0])%mod+(g[j-k][1]*f[v][k+1][1])%mod;
				(f[u][j][0]+=mod)%=mod;
				(f[u][j][1]+=mod)%=mod;
			}
		}
		sz[u] += sz[v];
	}
}


void solve() {
	int n;
	cin>>n;
	for(int i = 1;i < n;++i){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	dfs(1,0);
	for(int i = 1;i <= n;++i){
		cout<<(f[1][i][0]+f[1][i][1]+mod)%mod<<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;
}

标签:AtCoder,联通,LCP,Beginner,int,Trie,字符串,节点,分量
From: https://www.cnblogs.com/empty-y/p/17073702.html

相关文章

  • 【字典树】Atcoder Beginner Contest 287----E
    题目:E-Karuta(atcoder.jp)题解:这道题就是一个字典树求最长公共前缀的板子题。可以直接交板子。但我在翻题解的时候发现了另一种思路,就是将字符串按字典序排列后,每一个......
  • AtCoder Beginner Contest 287 解题报告
    AtCoderBeginnerContest287解题报告\(\text{ByDaiRuiChen007}\)ContestLinkA.Majority用map分别统计两种字符串出现的次数并与\(\left\lfloor\dfracn2\righ......
  • AtCoder Beginner Contest 287
    A-Majority(abc287a)题目大意给定\(n\)个人对某个提案的意见,问大多数意见是支持还是反对解题思路统计比较即可。神奇的代码#include<bits/stdc++.h>usingnam......
  • AtCoder Beginner Contest 287
    纯纯手速场C首先这张图必须是一棵树,必有\(M=N-1\)。接下来只需求出树的直径,判断其长度(边数)是否为\(N-1\)即可。https://atcoder.jp/contests/abc287/submissions/3......
  • Atcoder Beginner Contest 287
    赛时吃了三个法师,不过问题不大。赛时AB简单字符串处理。C中需要满足:\(m=n-1\)只有两个度数为\(1\)的点,剩下点的度数都为\(2\)。记得判连通!!D根据题目要求观......
  • AtCoder Beginner Contest 130
    AtCoderBeginnerContest130https://atcoder.jp/contests/abc130补补之前的A-Rounding#include<bits/stdc++.h>usingnamespacestd;intmain(){inta......
  • Atcoder ABC244E - King Bombee 题解
    原题:AtcoderABC244E-KingBombee题意给你一张图,从\(S\)到\(T\),经过\(k\)条边,经过\(X\)号点偶数次的方案数。做法设\(f_{i,j,k}\)表示经过\(i\)条边,......
  • AtCoder Beginner Contest 159
    A-TheNumberofEvenPairs相加为偶数只有偶加偶和奇加奇两种情况,其实就是在\(n\)个数中取两个(\(C\binom{2}{n}\)),在\(m\)个数中取两个(\(C\binom{2}{m}\))。B-String......
  • AtCoder Beginner Contest 126
    AtCoderBeginnerContest126https://atcoder.jp/contests/abc126A-ChangingaCharacter#include<bits/stdc++.h>usingnamespacestd;intmain(){int......
  • AtCoder Beginner Contest 162
    A-Lucky7大水题,模拟即可。#include<iostream>#include<cstdio>usingnamespacestd;intmain(){strings;cin>>s;if(s[0]=='7'||s[1]==......