CF Contest 348 Solution

比赛链接

A

题解

设进行\(x\)场比赛,则最多可以支持\((n-1)\cdot x\)的比赛人数总和。因为对于个人来说每场比赛是一样的,所以只需要保证\((n-1)\cdot x \ge \sum\limits_{i=1}^n a_i\),二分\(x\)即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],n;
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
bool check(int x)
{
	int sum=0;
	for(int i=1;i<=n;i++) sum+=x-a[i];
	return (sum>=x);
}
signed main()
{
	int l=0,r=2e9,ans=0;
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),l=max(l,a[i]);
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}

B

题解

因为一棵树的权值被根节点各子节点的子树平分,因此可以求出叶子节点\(i\)的权值对根节点的贡献,设其为\(\frac{1}{va_i}\)。也就是说,对于节点\(i\),\(1\)权值的比重是\(\frac{1}{va_i \cdot a_i}\),而目标就是将这些叶子节点单位权值的比重统一,并使其最小。因为随着\(a_i\)减小,\(\frac{1}{va_i \cdot a_i}\)增大,所以最终的单位权值比重不会小于\(\frac{1}{va_i \cdot a_i}\)的最大值,且可以被所有\(va_i\)整除(使其他叶子节点能够变化过来)。求出\(lcm(a_i)_{i=1}^n\)小于等于\(min(va_i\cdot a_i)_{i=1}^n\)的最大倍数,也就是剩余的节点权值和,用初始权值和减去它即为答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f3f3f3f3f;
int fst[N],nxt[2*N],v[2*N],cnt;
int a[N],va[N],mi=inf,lcm=1,sum;
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void add(int x,int y)
{
	v[++cnt]=y;
	nxt[cnt]=fst[x],fst[x]=cnt;
}
int gcd(int x,int y) {return (!y)?x:gcd(y,x%y);}
void dfs(int x,int fa)
{
	lcm=lcm*va[x]/gcd(lcm,va[x]);
	if(va[x]>sum || va[x]<0) {printf("%lld",sum); exit(0);}
	int tmp=0,y;
	for(int i=fst[x];i;i=nxt[i])
		if(v[i]!=fa) tmp++;
	if(!tmp) mi=min(mi,va[x]*a[x]);
	for(int i=fst[x];i;i=nxt[i])
	{
		y=v[i];
		if(y==fa) continue;
		va[y]=va[x]*tmp; dfs(y,x);
	}
}
signed main()
{
	int n=read(),x,y;
	for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
	for(int i=1;i<n;i++) 
	{
		x=read(),y=read();
		add(x,y),add(y,x);
	}
	va[1]=1; dfs(1,0);
	printf("%lld",sum-mi/lcm*lcm);
	return 0;
}

C

题解

将集合分为轻重两种,其中重集合中元素个数\(>\sqrt n\),其余区间为轻集合。可以发现,重集合个数\(cnt<\sqrt {10^5}\)。对于每个重集合,记录其元素和\(sum\)与加法懒标记\(add\)。预处理出\(cr[i][j]\)数组,表示第\(i\)个重集合与第\(j\)个集合的相同元素个数。

对于查询操作,如果\(k\)集合为重集合,则答案为\(sum_k+cr[i][k]\cdot add_i\ (1\le i\le cnt)\);否则暴力循环出集合元素和,并加上\(cr[i][k]\cdot add_i\ (1\le i\le cnt)\)。

对于修改操作,若\(k\)集合为重集合,则直接将\(add_k\)加\(x\);否则暴力循环修改集合中的元素,并枚举重集合,将\(sum_i\)加上\(cr[i][k]\cdot x\ (1\le i\le cnt)\)。

代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=1e5+10,M=400;
ll a[N],add[M],sum[M];
int cr[400][N],id[N],h[M],cnt,tmp;
bool exi[400][N];
vector<int> se[N];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
ll query(int x)
{
	int len=se[x].size();
	ll res=0;
	if(len<=tmp)
	{
		for(int i=0;i<len;i++) res+=a[se[x][i]];
		for(int i=1;i<=cnt;i++) res+=add[i]*cr[i][x];
		return res;
	}
	for(int i=1;i<=cnt;i++) res+=add[i]*cr[i][x];
	return res+sum[id[x]]; 
}
void modif(int x,int d)
{
	int len=se[x].size();
	if(len<=tmp)
	{
		for(int i=0;i<len;i++) a[se[x][i]]+=d;
		for(int i=1;i<=cnt;i++) sum[i]+=cr[i][x]*d;
	}
	else add[id[x]]+=d;	
}
signed main()
{
	int n=read(),m=read(),q=read(),k,x;
	for(int i=1;i<=n;i++) a[i]=read();
	tmp=sqrt(n);
	for(int i=1;i<=m;i++)
	{
		k=read();
		if(k>tmp) h[++cnt]=i,id[i]=cnt;
		for(int j=0;j<k;j++) 
		{
			x=read(); se[i].pb(x);
			if(k>tmp) exi[cnt][se[i][j]]=1,sum[cnt]+=a[se[i][j]];
		}
	}
	for(int i=1;i<=m;i++)
	{
		k=se[i].size();
		for(int j=0;j<k;j++)
			for(int p=1;p<=cnt;p++) cr[p][i]+=exi[p][se[i][j]];
	}
	char op;
	while(q--)
	{
		scanf(" %c",&op);
		if(op=='?')
		{
			k=read();
			printf("%lld\n",query(k)); continue;
		}
		k=read(),x=read();
		modif(k,x);
	}
	return 0;
}

D

题解

易得,两条路径一定分别通过\((1,2)\)到\((n-1,m)\)和\((2,1)\)到\((n,m-1)\)的路径。因此可以算出\((1,2)→(n-1,m)\)和\((2,1)→(n,m-1)\)的方案数,将它们相乘,但这样会多余计算在中间有交点的情况。因为\((1,2)→(n,m-1)\)和\((2,1)→(n-1,m)\)的路径一定相交,所以它们方案数之积就等于中间有交点的情况数,减去即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010,mod=1e9+7;
char a[N][N];
int c1[N][N],c2[N][N];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
signed main()
{
	int n=read(),m=read();
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	if(a[1][2]=='#' || a[2][1]=='#' || a[n][m-1]=='#' || a[n-1][m]=='#') {printf("0"); return 0;}
	c1[1][2]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]!='#' && !c1[i][j]) c1[i][j]=(c1[i-1][j]+c1[i][j-1])%mod;
	c2[2][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]!='#' && !c2[i][j]) c2[i][j]=(c2[i-1][j]+c2[i][j-1])%mod;
	printf("%lld",(c1[n-1][m]*c2[n][m-1]%mod-c1[n][m-1]*c2[n-1][m]%mod+mod)%mod);
	return 0;
}
上一篇:NOIP模拟57


下一篇:2021.08.29 膜你赛