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;
}