当前位置：首页 > news >正文

CSP-S模拟18

news 2025/9/14 17:28:38

前言：

哈哈

\(But...\)

疑似\(oi\)重拳出击.....

以及这场比赛的题目名字，看得出来出题人已经很绝望了

\(T1：\) 题目（\(problem\)）【又名：T648878 序列统计】

前言：

一定要好好算时间复杂度啊！！因为看到\(n≤8\)，所以写完\(dfs\)就跑，结果....丢了个\(0\)（其实有一部分原因是我不会算👉👈）

思路：

其实也是\(dfs\)，不过正常的\(dfs\)会像我一样\(T\)掉，所以我们要写\(meet-in-the-middle\)（折半搜索），然后就没啦。

代码：

点击查看代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=10;
int n,s,a[N],ans[1<<20],tot,cnt;
inline void dfs1(int pos,int sum){if(pos>(n+1)>>1){ans[++tot]=sum;//把前一半可能的情况存起来 return ;}int num=1;while(1){num*=a[pos];if(num+sum>s) break;dfs1(pos+1,sum+num);}
}//前一半 
inline void dfs2(int pos,int sum){if(pos>n){cnt+=upper_bound(ans+1,ans+1+tot,s-sum)-ans-1;//总计有多少种情况满足题意 return ;}int num=1;while(1){num*=a[pos];if(num+sum>s) break;dfs2(pos+1,sum+num);}
}//后一半 
signed main(){
//	freopen("problem.in","r",stdin);
//	freopen("problem.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>s;for(int i=1;i<=n;i++) cin>>a[i];dfs1(1,0);sort(ans+1,ans+1+tot);//排序 方便查找 dfs2(((n+1)>>1)+1,0);cout<<cnt<<'\n';//输出答案 return 0;
}

\(T2：\) 名字（name）【与此题相似】

前言：

此题长着一副人畜无害的样子，~~（却干着杀人放火的勾当）~~ 但怒调两小时无果呜呜呜。赛后一看题解，确实是我高攀不起的亚子。依据同机房大佬简单易懂的讲解，我觉得我应该是悟了。

思路：

我们不难知道\(dis_{u,v}=dep_u+dep_v-2*dep_{lca(u,v)}\)，然后由期望的线性可得我们要求的东西就是\(E(dep_u+dep_v-2*dep_{lca(u,v)})~=~E(dep_u) ~ + ~ E(dep_v) ~ ~ - ~2*E(dep_{lca(u,v)})\)。其中，\(E(dep_u)\)很好求[ 我不造啊，ta们说滴 ] ，显然由题意可得，\(dep_i=\sum_{j=1}^{i-1}\frac{a_j}{sum_{i-1}}(dep_j+b_i+b_j)=\frac{\sum_{j=1}^{i-1}a_j*(dep_j+b_j)+\sum_{j=1}^{i-1}a_j*b_i}{sum_{i-1}}\)，显然，\(\sum_{j=1}^{i-1}a_j*(dep_j+b_j)\)这一坨可以用前缀和进行优化。

接着我们来看\(E(dep_{lca(u,v)})\)，我们不妨令\(u<v\)，那么显然\(lca(u,v)\) 只与\(u\)有关。为什么捏？我们假设\(u<v\)（如果不小于的话互换一下不就好了），那么\(lca_{u,v}\)一定为\(1\) ~ \(u-1\)中的一个值，即无论\(v\)为多少，只要\(u\)值一定，那么就会有一个对应的\(lca_{u,v}\)，于是我们可以得到式子啦（式子中的\(i\)为上述的\(u\)）：\(lca_i=\sum_{j=1}^{i}\frac{a_j}{sum_{i}}*lca_j=\frac{\sum_{j=1}^{i-1}a_j*lca_j+dep_i*a_i}{sum_{i}}\)，然后用前缀和优化一下就可以啦~~

最后再输出答案\(E(dep_u) ~ + ~ E(dep_v) ~ ~ - ~2*E(dep_{lca(u,v)})\)就完结撒花啦~~✿✿ヽ(°▽°)ノ✿

代码时间：

code time

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+10,mod=1e9+7;
int n,q,x,y,css;
int a[maxn],b[maxn],sum[maxn],dep[maxn],lca[maxn];
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;}return res;
}//快速幂 
signed main(){
//	freopen("name.in","r",stdin);
//	freopen("name.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>q;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) sum[i]=sum[i-1]+a[i];//前缀和 dep[1]=1;css=a[1]*(1+b[1])%mod;for(int i=2;i<=n;i++){dep[i]=(css+sum[i-1]*b[i]%mod)%mod*qpow(sum[i-1],mod-2)%mod;css=(css+a[i]*(b[i]+dep[i])%mod)%mod;//存dep[j] 前缀和优化 }css=a[1];lca[1]=1;for(int i=2;i<=n;i++){lca[i]=(css+dep[i]*a[i]%mod)*qpow(sum[i],mod-2)%mod;//因为i的lca不包含i所以这里的分母为sum[i] css=(css+lca[i]*a[i]%mod)%mod;//前缀和优化 }for(int i=1;i<=q;i++){cin>>x>>y;if(x==y){cout<<0<<'\n';continue;} //特判 cout<<((dep[x]+dep[y]-2*lca[x]%mod)%mod+mod)%mod<<'\n';//输出答案 }return 0;
}