2023牛客暑期多校训练营6
A.Tree
题意：给出一颗树，树上的每个节点要么是黑色，要么是白色，编号为\(x\)的点可以通过花费\(cost[x]\)的代价来使得颜色反转，定义一个颜色不同的点对\((u,v)\)的利润为从\(u\)到\(v\)的经过的边的权值的最大值，问如果可以进行任意次反转颜色操作，最后利润-代价的最大值是多少。
Solution
连夜跑去学kruskal重构树，这个性质太好用了，将题目给的树跑一遍kruskal重构，我们发现，对于每一个非叶子节点，它的贡献为：
\(该点权值*(左子树黑点数*右子树白点数+左子树白点数*右子树黑点数)\)
这就可以变为一个树形dp了
我们定义\(dp[i][j]\)表示在编号为\(i\)的树中，左右子树共取\(j\)个黑点的最大答案
然后我们遍历左子树取的黑点个数，从而更新\(dp[i][j]\)即可
struct node
{
int u,v,w;
bool operator <(const node& t)const &{
return w < t.w;
}
};
vector<node>g;
int n;
vector<int>e[N<<1];
int t[N<<1];
int find(int x)
{
return t[x]==x?t[x]:t[x]=find(t[x]);
}
int idx=n;
int w[N<<1];
int c[N];
int p[N];
void kruskal()
{
for(auto it:g)
{
int u=it.u,v=it.v,ww=it.w;
int x=find(u),y=find(v);
if(x!=y)
{
idx++;
t[idx]=idx;
t[x]=t[y]=idx;
w[idx]=ww;
e[x].push_back(idx);
e[y].push_back(idx);
e[idx].push_back(x);
e[idx].push_back(y);
}
}
}
int dp[N<<1][N];
int sz[N<<1];
void dfs(int x)
{
if(x<=n)
{
sz[x]=1;
if(!p[x])
{
dp[x][0]=0,dp[x][1]=-c[x];
}else
{
dp[x][0]=-c[x],dp[x][1]=0;
}
return;
}
int lson=e[x][0],rson=e[x][1];
dfs(lson),dfs(rson);
sz[x]=sz[lson]+sz[rson];
for(int i=0;i<=sz[x];i++)
{
dp[x][i]=-1e18;
for(int j=max(0LL,i-sz[rson]);j<=min(i,sz[lson]);j++)
{
dp[x][i]=max(dp[x][i],dp[lson][j]+dp[rson][i-j]+w[x]*(j*(sz[rson]-(i-j))+(i-j)*(sz[lson]-j)));
}
}
}
原作者题解
B.Distance
题意：给出两个\(multiset\) \(S\)和\(T\)，定义操作为选取\(S\)或\(T\)中的任意一个数，使其\(+1\)，可以进行任意次操作，定义\(C(A,B)\)为使得\(multiset\) \(A\)和\(B\)变得完全相同的最小操作次数，现在询问\(sum\)的大小。
Solution
先对数组排序，然后我们可以计算出对于\(S\)中的第\(i\)个数和\(T\)中的第\(j\)个数对答案的贡献，很明显，贡献为
由范德蒙卷积公式可化简
PS:找个时间把推论都整理一遍，防止忘记
void init()
{
fac[0]=1;
for(int i=1;i<N;i++)
{
fac[i]=(fac[i-1]*i)%mod;
}
inv[2000]=ksm(fac[2000],mod-2);
for(int i=2000-1;i>=0;i--)
{
inv[i]=(inv[i+1]*(i+1))%mod;
}
}
int C(int n,int m)
{
if(n<m||n<0||m<0)return 0;
else return ((fac[n]*inv[n-m])%mod*inv[m])%mod;
}
void solve()
{
init();
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)
{
s[i][0]=1;
for(int j=1;j<=i;j++)
{
s[i][j]=(s[i][j-1]+C(i,j))%mod;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int x=C(i+j-2,min(i,j)-1),y=C(n*2-i-j,min(n-i,n-j));
ans=(ans+(x*y%mod)*(abs(a[i]-b[j]))%mod)%mod;
}
}
cout<<ans<<"\n";
}
C.idol!!
题意：定义\(x!!\)为一种新的计算方式，其中：
如果\(x\)为奇数：则\(x!!=1\times3\times5\times...\times x\)
如果\(x\)为偶数：则\(x!!=2\times4\times6\times...\times x\)
给出\(n\)，求\(1!!\times2!!\times...\times n!!\)的尾部有多少个0
Solution
考虑到题目的计算方式，我们不难发现2的个数是远小于5的个数的，所以我们只需统计5的个数即可
分奇数和偶数讨论
先看奇数的，5,7,9,11,13,15,17,19,21,23,25,27,....
我们发现，5,7,9,11,13对答案会有1次贡献，15,17,19,21,23对答案有2次贡献，这是一个数列
考虑到25,125,625等会对答案会有多次贡献，我们每次每个数列的贡献只算一次，每次对第一个数乘5，这样可以保证不会重复计算贡献
我们先得到数列长度，然后对长度除以相同贡献的长度，这就得到了最大贡献-1，得到最大贡献后，我们可以计算出整个数列的贡献，加到答案里面即可
偶数同理，但是长度要额外除以2
用python写的，高精度狗都不写
n = int(input())
ans=0
x=5
temp=n
if temp%2==0:
temp-=1
while x<=temp:
cnt=(n-x)//2+1
maxx=cnt//x+1
ans+=x*maxx*(maxx-1)//2;
ans+=maxx*(cnt%x)
x*=5
x=10
temp=n
if temp%2!=0:
temp-=1
while x<=temp:
cnt=(n-x)//2+1
maxx=cnt//(x//2)+1
ans+=(x//2)*maxx*(maxx-1)//2
ans+=maxx*(cnt%(x//2))
x*=5
print(ans)
E.Sequence
题意：给出一个长为\(n\)的数组\(a\)，有\(q\)次询问，每次询问能否把区间\([l,r]\)分成\(k\)个区间和为偶数的区间
Solution
先把数组的奇数变为1，偶数变为0，我们发现，要尽可能多的分区间，那么从左往右，1必须找最近的1形成一个区间，0尽量单独成一个区间，那么我们可以预处理出一个11区间长度前缀和，分奇数1开头和偶数1开头，这样就可以算出所有区间的偶数区间最大个数，和\(k\)比较即可
void solve()
{
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
int flag=0;
int flag1=0,flag2=0;
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++)
{
s[i]=s[i-1];
s1[i]=s1[i-1];//奇数1开头的11区间长度前缀和
s2[i]=s2[i-1];//偶数1开头的11区间长度前缀和
if(flag1)cnt1++;
if(flag2)cnt2++;
if(a[i]&1)
{
s[i]++;
if(flag1)
{
s1[i]+=cnt1;
cnt1=0;
flag1=0;
}else
{
cnt1++;
flag1=1;
}
if(flag2)
{
s2[i]+=cnt2;
cnt2=0;
flag2=0;
}else if(flag)
{
cnt2++;
flag2=1;
}else
{
flag=1;
}
}
}
while(q--)
{
int l,r,k;cin>>l>>r>>k;
int cnt=s[r]-s[l-1];
if(cnt&1)
{
cout<<"NO\n";
continue;
}
int op;
if(s[l]!=s[l-1]) op=s[l]&1;
else op=(!(s[l]&1));
int len;
if(op)len=r-l+1-(s1[r]-s1[l-1])+cnt/2;
else len=r-l+1-(s2[r]-s2[l-1])+cnt/2;
if(len<k)cout<<"NO\n";
else cout<<"YES\n";
}
}
G.Gcd
题意：给出一个集合，最开始只有\(x,y\)，每次可以选择集合中的两个不同的数\(a,b\)，加入\(a-b\)或者\(gcd(|a|,|b|)\)，问能否通过多次操作加入\(z\)
Solution
很明显的辗转相减，\(gcd(b-a,a)=gcd(a,b)\)
所以\(z\)要满足是\(gcd(a,b)\)的倍数即可，如果\(z\)是0，还得特判一下\(x\)或\(y\)是不是0
void solve()
{
int x,y,z;cin>>x>>y>>z;
if(z==x||z==y)cout<<"YES\n";
else if(z!=0&&z%gcd(x,y)==0)cout<<"YES\n";
else cout<<"NO\n";
}