【考后总结】8 月 CSP-S 模拟赛 10
8.25 夜 CSP 模拟 30++
When I Was Your Man - Bruno Mars
Same bed but it feels just a little bit bigger now
Our song on the radio but it don´t sound the same
When our friends talk about you
All that it does is just tear me down
Cause my heart breaks a little when I hear your name
And it all just sound like uh uh uh
Hmmm too young too dumb to realize
That I should have bought you flowers and held your hand
Should have gave you all my hours when I had the chance
Take you to every party
Cause all you wanted to do was dance
Now my baby is dancing
But she´s dancing with another man
My pride my ego my needs and my selfish ways
Caused a good strong woman like you to walk out my life
Now I never never get to clean up the mess I made
And it haunts me every time I close my eyes
It all just sounds like uh uh uh uh
Too young too dumb to realize
That I should have bought you flowers and held your hand
Should have gave all my hours when I had the chance
Take you to every party
Cause all you wanted to do was dance
Now my baby is dancing
But she´s dancing with another man
Although it hurts I´ll be the first to say that I was wrong
Oh I know I´m probably much too late
To try and apologize for my mistakes
But I just want you to know
I hope he buys you flowers I hope he holds your hand
Give you all his hours when he has the chance
Take you to every party
Cause I remember how much you loved to dance
Do all the things I should have done when I was your man
Do all the things I should have done when I was your man
咋还有加赛？？？咋还有加赛？？？咋还有加赛？？？
T1 工业题
容易发现 \(f_{x,0}\) 对 \(f_{n,m}\) 贡献的系数是 \(a^{m-x}b^n\)，同时贡献的方案数是格路计数 \(\binom{n+m-x-1}{m-x}\)，这里 \(-1\) 是因为钦定第一步必须向右走。
同理 \(f_{0,y}\) 贡献的系数是 \(a^mb^{n-y}\)，方案数 \(\binom{n+m-y-1}{n-y}\)。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
ll n,m,a,b;
ll A[maxn],B[maxn];
int fact[maxn<<1],inv_fact[maxn<<1];
int pwa[maxn],pwb[maxn];
inline int C(int N,int M){
return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}
int ans;
int main(){
n=read(),m=read(),a=read()%mod,b=read()%mod;
for(int i=1;i<=n;++i) A[i]=read()%mod;
for(int i=1;i<=m;++i) B[i]=read()%mod;
fact[0]=1,inv_fact[0]=1;
for(int i=1;i<=n+m;++i) fact[i]=1ll*fact[i-1]*i%mod;
inv_fact[n+m]=q_pow(fact[n+m],mod-2,mod);
for(int i=n+m-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
pwa[0]=1,pwb[0]=1;
for(int i=1;i<=m;++i) pwa[i]=1ll*a*pwa[i-1]%mod;
for(int i=1;i<=n;++i) pwb[i]=1ll*b*pwb[i-1]%mod;
for(int i=1;i<=n;++i) ans=(ans+1ll*pwa[m]*pwb[n-i]%mod*C(n-i+m-1,n-i)%mod*A[i]%mod)%mod;
for(int i=1;i<=m;++i) ans=(ans+1ll*pwa[m-i]*pwb[n]%mod*C(m-i+n-1,m-i)%mod*B[i]%mod)%mod;
printf("%d\n",ans);
return 0;
}
T2 卡常题
原图是基环树。
树的部分 DP 是平凡的，设 \(f_{u,0/1}\)，对 X 类点表示将子树内所有 Y 类点激活且 \(u\) 有/没有被选择的最小代价，对 Y 类点表示将子树内所有 Y 类点激活，且 \(u\) 有/没有被激活的最小代价。
环上变成若干 X 类点与 Y 类点交替，要求相邻 X 类点至少有一个被激活，断环成链 DP 即可。
点击查看代码
int n,a,b;
int w[maxn];
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int pre[maxn],tmp[2];
bool vis[maxn];
vector<int> L;
void dfs_loop(int u,int fa){
pre[u]=fa;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa) continue;
if(pre[v]){
if(!tmp[0]) tmp[0]=u,tmp[1]=v;
}
else dfs_loop(v,u);
}
}
int f[maxn][2];
void dfs(int u,int fa){
if(u<=n){
f[u][1]=w[u];
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa||vis[v]) continue;
dfs(v,u);
f[u][0]+=f[v][1];
f[u][1]+=min(f[v][0],f[v][1]);
}
}
else{
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa||vis[v]) continue;
dfs(v,u);
f[u][0]=f[v][0];
f[u][1]=f[v][1];
}
}
}
int ans[2][2],tmpans[2][2];
int main(){
n=read(),a=read(),b=read();
for(int i=1,u,v;i<=n;++i){
u=read(),v=read();
add_edge(u,n+i);
add_edge(v,n+i);
w[u]+=a,w[v]+=b;
}
dfs_loop(1,2*n+1);
for(int u=tmp[0];;u=pre[u]){
vis[u]=true;
if(u<=n) L.push_back(u);
if(u==tmp[1]) break;
}
for(int u:L) dfs(u,0);
for(int u:L){
if(u==L[0]){
ans[0][0]=f[u][0],ans[1][1]=f[u][1];
ans[0][1]=ans[1][0]=inf;
}
else{
tmpans[0][0]=ans[0][1]+f[u][0];
tmpans[0][1]=min(ans[0][0],ans[0][1])+f[u][1];
tmpans[1][0]=ans[1][1]+f[u][0];
tmpans[1][1]=min(ans[1][0],ans[1][1])+f[u][1];
ans[0][0]=tmpans[0][0],ans[0][1]=tmpans[0][1];
ans[1][0]=tmpans[1][0],ans[1][1]=tmpans[1][1];
}
}
printf("%d\n",min({ans[0][1],ans[1][0],ans[1][1]}));
return 0;
}
T3 玄学题
诈骗题。
注意到 \(d(ij)\) 为奇数是当且仅当 \(ij\) 是完全平方数。把 \(i\) 表示成 \(p^2q\) 的形式，其中 \(q\) 不含平方因子，设 \(f(i)=q\)，\(f(i)\) 为积性函数，可以线性求出。
之后对于 \(i\)，先将其补为 \(if(i)\)，那么剩下的完全平方数部分个数是 \(\left\lfloor\sqrt{\frac{m}{f(i)}}\right\rfloor\)。
点击查看代码
int n;
ll m;
int pr[maxn];
bool vis[maxn];
int f[maxn];
inline void linear_sieve(){
f[1]=1;
for(int i=2;i<=lim;++i){
if(!vis[i]) pr[++pr[0]]=i,f[i]=i;
for(int j=1;j<=pr[0]&&i*pr[j]<=lim;++j){
vis[i*pr[j]]=true;
f[i*pr[j]]=f[i]*pr[j];
if(i%pr[j]==0){
if(f[i]%pr[j]) f[i*pr[j]]=f[i]*pr[j];
else f[i*pr[j]]=f[i]/pr[j];
break;
}
}
}
}
int ans;
int main(){
n=read(),m=read();
linear_sieve();
for(int i=1;i<=n;++i){
ll x=m/f[i];
int cnt=sqrt(x);
if(cnt&1) --ans;
else ++ans;
}
printf("%d\n",ans);
return 0;
}
反演得到的式子是：
处理是二层数论分块 \(O(n\log \log n+m^{3/4})\)。
也可写作：
处理是 Min_25 筛 \(O\left(n\log \log n+\dfrac{m^{3/4}}{\log m}\right)\)。
反思
T1 和 T2 做法识别的很快。
T3 反演一整场，得到了 \(O\left(n\log \log n+\dfrac{m^{3/4}}{\log m}\right)\) 的“优秀做法”，结果是被诈骗了！咋整的呀？