标签：dots approx const vert 报告 int void 解题 ABC287

Atcoder Beginner Contest 287

姗姗来迟的解题报告

C 题漏了一个细节，狂 WA，心态爆炸，暴跌 58 rating

Contest link

My result

A - Majority

直接统计 For 的个数，与 \(\dfrac{n}{2}\) 比较即可。

int n,cnt;
string a;
void Solve()
{
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a;cnt+=(a=="For");}
	cout<<(cnt*2>=n?"Yes":"No");
}

B - Postal Card

直接将 \(S_i\) 截取后三位然后与各个 \(T_j\) 比较即可。

const int N=1005;
int n,m,cnt;
string s[N],t[N];
void Solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){cin>>s[i];s[i]=s[i].substr(3);}
	for(int i=1;i<=m;i++)cin>>t[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i]==t[j]){cnt++;break;}
	cout<<cnt;
}

C - Path Graph?

Path graph 就是一条单链，可以直接 dfs 判。然鹅我赛时 WA 了 7 times 最后硬是没调出来

const int N=200005;
int n,m,u,v,d[N],total;
int head[N],nxt[N<<1],to[N<<1],tot;
void add(int u,int v)
{
	to[++tot]=v,nxt[tot]=head[u],head[u]=tot;
}
bool vis[N];
bool dfs(int now,int fa)
{
	vis[now]=1;total++;
	int cnt=0;
	for(int i=head[now];i;i=nxt[i])
		if(to[i]!=fa)
		{
			if(vis[to[i]]||!dfs(to[i],now))return 0;
			cnt++;
			if(cnt>1)return 0;
		}
	return 1;
}
void Solve()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		add(u,v),add(v,u);
		d[u]++,d[v]++;
	}
	for(int i=1;i<=n;i++)
		if(d[i]==1)
		{
			cout<<(dfs(i,0)&&total==n?"Yes":"No");
			return;
		}
	cout<<"No";
}

D - Match or Not

一个重要结论：两个字符 \(x\) 和 \(y\) 匹配，当且仅当 \(x=\texttt{?}\) 或 \(y=\texttt{?}\) 或 \(x=y\)。

设 \(\left\vert S\right\vert=n,\left\vert T\right\vert=m\)，"match"看成 \(\approx\) 符号。

于是，输出 Yes 当且仅当 \(S[1\dots i]\approx T[1\dots i]\) 且 \(S[n-m+i+1\dots n]\approx T[i+1\dots m]\)。

而 \(S[1\dots i]\approx T[1\dots i]\)，当且仅当 \(S[1\dots i-1]\approx T[1\dots i-1]\) 且 \(S_i\approx T_i\)。

于是，我们可以扫一遍前缀与后缀，对于每个问题答案就是前后缀都成立。

时间复杂度 \(O(n+m)\)。

const int N=300005;
string s,t;
bool a[N],b[N],ok;
void Solve()
{
	cin>>s>>t;
	ok=1;
	for(int i=0;i<=t.size();i++)
	{
		a[i]=ok;
		if(i<t.size()&&s[i]!='?'&&t[i]!='?'&&s[i]!=t[i])ok=0;
	}
	ok=1;
	for(int i=0;i<=t.size();i++)
	{
		if(i&&s[s.size()-i]!='?'&&t[t.size()-i]!='?'&&s[s.size()-i]!=t[t.size()-i])ok=0;
		b[i]=ok;
	}
	for(int i=0;i<=t.size();i++)
		cout<<(a[i]&&b[t.size()-i]?"Yes":"No")<<endl;
}

E - Karuta

建一棵字典树，然后把所有字符串插入。对于每个字符串，结果就是最后一个遍历次数 \(\ge2\) 的节点的深度。

时间复杂度 \(O(\sum s_i)\)。

const int N=500005;
int n;
string s[N];
namespace trie
{
int tot;
struct tree
{
	int cnt,son[62];
}tr[N];
int f(char ch)
{
	if(ch>='0'&&ch<='9')return ch-'0';
	if(ch>='a'&&ch<='z')return ch-'a'+10;
	return ch-'A'+36;
}
void build()
{
	for(int i=0;i<=tot;i++)
	{
		tr[i].cnt=0;
		for(int j=0;j<62;j++)tr[i].son[j]=0;
	}
	tot=0;
}
void mdf(string s)
{
	int now=0;
	for(int i=0;i<s.size();i++)
	{
		if(!tr[now].son[f(s[i])])tr[now].son[f(s[i])]=++tot;
		now=tr[now].son[f(s[i])],tr[now].cnt++;
	}
}
int query(string s)
{
	int now=0;
	for(int i=0;i<s.size();i++)
	{
		now=tr[now].son[f(s[i])];
		if(tr[now].cnt<=1)return i;
	}
	return s.size();
}
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		trie::mdf(s[i]);
	}
	for(int i=1;i<=n;i++)cout<<trie::query(s[i])<<endl;
}

F - Components

考虑 dp，设 \(dp_{x,y,c}\) 为在以 \(x\) 为根的子树中，形成 \(y\) 个连通块，\(x\) 被选中的状态为 \(c\) 的总方案数。

标签：dots,approx,const,vert,报告,int,void,解题,ABC287
From： https://www.cnblogs.com/No-play-Yes-splay/p/solution-abc287.html