题解 CF1322C 【Instant Noodles】

· · 题解

inf计划第三题,评分2300,未看题解

这道题是@Fee_cle6418推荐的

(改编后)有n个X部点，每个点有一个匹配Y部点集合c_i(这样说主要是那个二部图没什么意思),求

\gcd_{S\subseteq U}\left\{\sum_{x\in f_S}x\right\}

其中f_S=\bigcup\limits_{x\in S}c_i

理解一下就是求对于任意点集匹配到的所有位置的和再求\gcd

我一开始一直想怎么从X部点入手然后发现收效甚微，只要这个点和其余X部点有重叠的匹配点就无法算贡献

因此从Y部点a_x=v入手

考虑一个老结论\gcd\{a,a+b\}=\gcd\{a,b\}

在说什么呢，其实是说原本有一些集合(匹配点的并集的和)有一样的贡献，然后考虑上一个新的Y部点只要没有把这些集合全体贡献，那么贡献可以看做在自己该贡献和的位置上多做一次\gcd

非常弱智但我想了一会儿，其实在说对(x,y),被匹配的集合是L_x,L_y

则仅仅对于L_x=L_y时，我们选到任意合法子集时贡献是同步的，否则的话，不相交的部分直接贡献，相交的部分发现先后来也是对的

所以步骤就是求出L_x,把每个权值累加到L_x中去，然后对所有L_x求\gcd

n=read(),m=read(),ans=0;
while(m--)x=read(),y=read(),h[y]+=v[x];
for(i=1;i<=n;++i)if(h[i])mp[h[i]]+=a[i];
for(auto x:mp)ans=__gcd(ans,x.second);