Codeforces Round #428 (Div. 2) B 细节 D gcd预处理因子+容斥

题意：给出n行，每行有8个座位， {1, 2} {3 4} {4, 5} {5, 6} {7, 8} 一行中这些位置算相邻，给出k个不同部队的士兵，要求不同部队的士兵部能坐相邻的位置，问能否达到这个目的

思路:

这个题我的思路比较丑..我先把所有奇数的+1判断能否全部坐下,不能就一定不可以了.然后优先考虑人数大于等于4的,放在中间的四人座,如果都填完了,还剩余四人座,在考虑了剩下的奇数的放在四人座,这里需要特别注意的是如果有1的,他可以找一个2的和他一起放在四人座的,就可以了.然后如果都填完了还有剩就要考虑只能放3个了.最后判断一下就好了.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e4+10;

int n,k;
int a[maxn];

int main()
{
	cin>>n>>k;
	int ans=0,sum=0;
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
		if(a[i]%2)
		sum++;
	}
	if(sum>8*n)
	puts("NO");
	else
	{
		ans=4*n;
		int cnt=n;
		for(int i=1;i<=k;i++)
		{
			if(ans==0)
			break;
			if(a[i]>=4)
			{
				int w=a[i]/4;
				if(w>cnt)
				w=cnt;
				a[i]-=w*4;
				ans-=w*4;
				cnt-=w;
				if(cnt==0)
				break;
			}
		}
		if(ans==0)
		puts("YES");
		else
		{
			for(int i=1;i<=k;i++)
			{
				if(ans==0)
				break;
				if(a[i]%2)
				{

					if(a[i]==3)
					ans-=4,a[i]=0;
					else if(a[i]==1)
					{
						int flag=0;
						for(int j=1;j<=k;j++)
						{
							if(a[j]==2)
							{
								ans-=4;
								a[j]=0;
								flag=1;
								break;
							}
						}
						if(!flag)
						{
							ans-=(a[i]+1);
							a[i]=0;
						}
					}

				}
			}
			if(ans==0)
			puts("YES");
			else
			{
				int s= 0;
				for(int i=1;i<=k;i++)
				s+=a[i];
				int a=ans%4;
				int b=ans/4;
				int c=a+3*b+4*n;
				if(s<=c)
				puts("YES");
				else
				puts("NO");
			}
		}
	}
	return 0;
}

题目链接

题意：给定一个集合，求其所有子集的权值的和。集合的权值定义为：如果集合元素 gcd 为1，权值为 0 ；否则权值为集合大小乘以 gcd .

遇到gcd,我们先考虑是否可以枚举因子,这里我们利用和素数筛差不多的算法,枚举出每个gcd对应的数有多少个,利用桶装.

设 f(x) 为 x|gcd 的集合的大小总和。显而易见，这样的集合必然是所有 x 的倍数的子集。设这样的元素有 n 个，则集合总大小为：

\sum k k (n k) = \sum k n (n - 1 k - 1) = n \sum k (n - 1 k) = n \times 2 n - 1

能到各个gcd所对应的可能的集合,直接扫一遍乘起来就好了.但是注意这里存在重复的,即该gcd 会被他所有的因子加一遍.

这里就要用到多校的那个方法了,从后往前倒着容斥.因为最后一个数后面没有比他大的了,所以不存在因子重复的情况了.这样每次就把他自己

加到答案里,他所有因子的都不算.

也可以用莫比乌斯反演来容斥

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+10;
const int maxm=1e6;
ll book[maxn],dp[maxn];

ll qmod(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)
		res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}	
	return res;
} 

int main()
{
	int n,a,i,j;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		book[a]++;
	}
	for(int i=2;i<=maxm;i++)
	{
		for(int j=2*i;j<=maxm;j+=i)
		{
			book[i]+=book[j];
		}
	}
	for(int i=2;i<=maxm;i++)
	{
		if(book[i])
		dp[i]=qmod(2,book[i]-1)*book[i]%mod;
		else
		dp[i]=0;
	}
	for(int i=maxm;i>=2;i--)
	{
		for(int j=2*i;j<=maxm;j+=i)
		{
			dp[i]-=dp[j];
			dp[i]=(dp[i]+mod)%mod;
		}
	}
	ll ans=0;
	for(int i=2;i<=maxm;i++)
	{
		ans=(ans+dp[i]*i)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

秒客网

Codeforces Round #428 (Div. 2) B 细节 D gcd预处理因子+容斥

相关文章