Codeforces 1322C C. Instant Noodles（hash+思维）_C

题目链接:C. Instant Noodles

题意：给定一个二分图的右半部分和对应权值，以及全部边，对于左边部分的任意集合S，都有对应集合N（S）包含所有和集合S中相连的来自右边的点，f（S）代表N（S）中所有点权的和，现让你求所有集合S对应f（S）的最大公因数

题解：我们设集合Xi代表点i连接的左边点组成的集合，那么对于任意i，j满足Xi==Xj时，这两个点要么同时出现在某个集合N（S）中，要么同时不出现，那么我们可以利用hash映射每个右边点对应的Xi，把相同X的点缩点，因为缩点后每个点都是独立的可选或不可选，那么f(s)一定是缩点后点对应权值的自由组合，所以求所以f（s）的gcd时就相当于每个缩点后单独点权的gcd，即gcd（a,a+b+c）==gcd(a,gcd(b,c)) ，即对缩点后的每个点直接求公共gcd即可，

注意：记得特判X为空集合时

不懂和细节间代码及注释：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
	#ifndef local
	#define endl '\n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll MAXN=2e6+10;
const ll N=1e5+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN]/*流量*/,cost[MAXN]//费用;
/* 
void add(ll u,ll v,ll w,ll s){
	to[++cnt]=v;net[cnt]=head[u];edge[cnt]=w;cost[cnt]=s;head[u]=cnt;
	to[++cnt]=u;net[cnt]=head[v];edge[cnt]=0;cost[cnt]=-s;head[v]=cnt;
}
struct elemt{
	int p,v;
};
-----------------------------------
求[1,MAXN]组合式和逆元 
ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}	
		a=a*a%mod;
		b/=2;
	}
	return res;
}
ll fac[MAXN+10],inv[MAXN+10]
ll C(int m,int n){//组合式C(m,n); 
	if(!n){
		return 1;
	}
	return fac[m]*(inv[n]*inv[m-n]%mod)%mod;
}
fac[0]=1;inv[0]=1;
for(ll i=1;i<=MAXN;i++){
	fac[i]=(fac[i-1]*i)%mod;
	inv[i]=mi(fac[i],mod-2);
}
---------------------------------
 unordered_mapmp;
//优先队列默认小顶堆 ， greater --小顶堆  less --大顶堆  
priority_queue,comp>q;
struct comp{
	public:
		bool operator()(elemt v1,elemt v2){
			return v1.v::iterator it=st.begin();
*/
// vector>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
  //mapmp[N]; 
ll base=1331;
ll h[5*N];
struct elemt{//hsh代表当前右边点连接的左边点组成的集合映射的hash值，c代表当前点上的权值
	ll hsh,c;
};
elemt a[5*N];
void init(int n){
	h[0]=1;
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*base;
	}
}
ll gcd(ll a,ll b){
	return a%b==0?b:gcd(b,a%b);
}
bool comp(elemt v1,elemt v2){
	return v1.hsht;
	while(t--){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++){//用多少清多少
			a[i].hsh=0;
		}
		for(int i=1;i<=n;i++){
			cin>>a[i].c;
		}
		for(int i=1;i<=m;i++){//确定各点连接的左边点组成的集合
			int u,v;
			cin>>u>>v;
			a[v].hsh+=h[u];
		}
		sort(a+1,a+n+1,comp);//按hsh排序，就能找到对应集合相同的点并缩点
		vectorval;//缩点后对应权值
		for(int i=2;i<=n;i++){
			if(a[i].hsh==a[i-1].hsh){
				a[i].c+=a[i-1].c;
			}
			else if(a[i-1].hsh){//hsh为0说明是空集合，不能算到gcd里面
				val.push_back(a[i-1].c);
			}
		}
		if(a[n].hsh){//hsh为0说明是空集合，不能算到gcd里面
			val.push_back(a[n].c);
		}
		ll ans=val[0];
		for(int i=1;i 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/584883.html

Codeforces 1322C C. Instant Noodles（hash+思维）

发表评论

评论列表（0条）