专栏文章

绝世好题

NNATO
P13336题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minxwlt2
此快照首次捕获于
2025/12/02 10:09
3 个月前
此快照最后确认于
2025/12/02 10:09
3 个月前
查看原文
神题，笔者并没有找到除官解外的题解，也并没有找到任何有人通过本题的证据（不过似乎是 2015 集训队作业），就来记录一下官方题解神仙做法，给个证明。
首先你发现有解答案上界是 2nn2^nn，暴力模拟状态 SS 和 uu（代表当前每个点经过的奇偶性和当前在那个点）即可。
然后？你不会了看了眼 tag 折半搜索，你尝试把点分成两部分，对两边预处理当前部分状态为 SS，在点 uu，走到另外一部分时的 S′S' 和 u′u'，但你发现你的状态数是没有变化的，似乎还是 2nn2^nn 的。
接下来就是很厉害的想法了。
官解告诉我们保留所有边，直接建反图从 nn bfs 给每个点标记一个 depdep，把没有 bfs 到的扔掉（显然走到那些点不可能有解），然后把 depdep 较小的那一半分到一个集合 BB，剩下的分到另外一个集合 AA。
它告诉我们只用预处理 AA 集合内从状态为 SS，在点 uu，走到另外一部分时的 S′S' 和 u′u'，在 AA 时利用这个东西加速跳，在 BB 时暴力跳就是正确的，在到达 nn 前是不会出现重复的 BB 集合奇偶状态的（如果跳到了那些没有 bfs 的点就无解）！
很反直觉不是吗？
然而官解并没有给出证明，这里我们证明一下。
考虑我现在 BB 集合跳跃状态为 SS，在 BB 中某个点 uu，我现在想要转一圈后 BB 状态仍然是 SS。那么说明我从现在起 uu 的两条边都会走过（现在会走某条边，之后为了消除本次的奇偶翻转还会再走一次），由于它的 depudep_u 是由它的两条出边指向的点更新的，说明它在重复状态前必然会访问到一个 depu−1dep_u-1 的点，由于我们是把 depdep 小的分 BB 内，这个点必然是 BB 内的，继续从 depu−1dep_u-1 的点出发考虑，我们就发现必然会经过 depu−2,depu−3,...dep_u-2,dep_u-3,... 的点，也就是必然会经过点 nn！
所以我们在 BB 跳的次数是不超过 2∣B∣2^{|B|} 次的（官解只给到了 2∣B∣∣B∣2^{|B|}|B|，笔者认为是不可能 SS 一样，uu 不同的，上述证明已经说明了这一点，如果笔者给的上界有误请指出），而 AA 状态数是 2∣A∣∣A∣2^{|A|}{|A|} 的，所以 ∣B∣|B| 取 2222 左右跑得最快。
参考代码：
CPP
#include<bits/stdc++.h>
#define ll long long
#define INF 214748364719260817ll
using namespace std;
ll t,n;
ll l[45],r[45];
ll to[45],td[45];
ll dep[45];
vector<ll>bk[45];
vector<ll>a,b;
struct px
{
	ll nS,nu,c;
};
px dp[1<<18][18];
bool vis[1<<18][18];
px dfs(ll S,ll u)
{
	if(to[u]!=1)return (px){S,u,0};
	if(vis[S][td[u]])return dp[S][td[u]];
	vis[S][td[u]]=1;
	ll nu=u;
	if((S>>td[u])&1)nu=r[u];
	else nu=l[u];
	dp[S][td[u]]=dfs(S^(1<<td[u]),nu);
	++dp[S][td[u]].c;
	return dp[S][td[u]];
}
ll get_ans(ll aS,ll bS,ll u)
{
	if(u==n-1)return 0;
	if(!to[u])return -INF;
	if(to[u]==1)
		return dp[aS][td[u]].c+get_ans(dp[aS][td[u]].nS,bS,dp[aS][td[u]].nu);
	else
	{
		ll nu=u;
		if((bS>>td[u])&1)nu=r[u];
		else nu=l[u];
		return 1+get_ans(aS,bS^(1<<td[u]),nu);
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>t;
	for(ll sb=1;sb<=t;++sb)
	{
		cin>>n;
		memset(to,0,sizeof(to));
		memset(dep,0,sizeof(dep));
		memset(vis,0,sizeof(vis));
		a.clear();b.clear();
		for(ll i=0;i<n;++i)bk[i].clear();
		for(ll i=0;i<n-1;++i)cin>>l[i]>>r[i],--l[i],--r[i];
		for(ll i=0;i<n-1;++i)bk[l[i]].emplace_back(i),bk[r[i]].emplace_back(i);
		queue<ll>q;
		q.emplace(n-1);
		dep[n-1]=1;
		while(!q.empty())
		{
			ll id=q.front();q.pop();
			a.emplace_back(id);
			for(auto it:bk[id])
			{
				if(!dep[it])
				dep[it]=dep[id]+1,q.emplace(it);
			}
		}
		cout<<"Case #"<<sb<<": ";
		if(a.size()<2||!dep[0])
		{
			cout<<"Infinity\n";continue;
		}
		ll where=a.size()/2;
		for(ll i=a.size()-1;i>=max(22ll,where);--i)b.emplace_back(a.back()),a.pop_back();
		swap(a,b);
		ll cot=0;
		for(auto it:a)to[it]=1,td[it]=cot++;
		cot=0;
		for(auto it:b)to[it]=2,td[it]=cot++;
		for(ll i=0;i<(1<<a.size());++i)
			for(ll j=0;j<a.size();++j)
				if(!vis[i][j])
					dfs(i,a[j]);
		ll res=get_ans(0,0,0);
		if(res<0)cout<<"Infinity\n";
		else cout<<res<<'\n';
	}
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...