模拟87 考试总结

看天云天雨天正苍

建议改名：TLEcoders

考试经过

上来一看，四个题三个数学题，淦

在爆零了\(998244353\)场后的我终于看出来了期望的线性性，于是15min把T1秒了，紧接着T2开始手玩样例，搞出来之后发现也很水，就秒了，这时刚一个小时，感觉要起飞，然后T3发现不会。。。

还好数据随机，于是开始乱搞，判了特殊性质，觉得保底60不慌，开T4一看是个数论，先半个小时yy出了线性筛法，突然发现这跟之前一个做过的题很像，于是想道枚举平方因子， 然后一波容斥，过样例了！！！开冲，80到手

于是期望得分100+100+[60-80]+80=[340-360] ,剩下基本在检查

出分人傻了，T1

#define int long long

被卡常了60，T2精度被卡了75……

总之参赛体验极差

T1.集合均值卡常题

直接展开，相当于每次把右边的平均数放到左边，设平均数为\(p\),答案就是

\[ans=\sum_{i=1}^{n\times m}\frac{i\times p}{i+1}

\]

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=100050;
int a[N],m,n,inv[200*N];
signed main()
{
	freopen("mos.in","r",stdin);
	freopen("mos.out","w",stdout);
	cin>>n>>m;int sum=0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)sum=(1ll*sum+a[i])%mod;
	inv[1]=1;for(int i=2;i<=n*m+10;i++)inv[i]=(1ll*mod-mod/i)*inv[mod%i]%mod;
	sum=1ll*sum*inv[n]%mod;int ans=0;
	for(int i=1;i<=n*m;i++)ans=(1ll*ans+1ll*sum*i%mod*inv[i+1]%mod)%mod;
	cout<<ans<<endl;
	return 0;
}
           

T2.聚烷撑乙二醇炸精题

从后往前模拟，设\(ans\)初始为0

对于当前的随机数生成器\(i\)，分情况讨论

如果后面的没有当前优，即\(ans<=l_i\)，要当前的不要后面的，\(ans=(l_i+r_i)/2\)

如果后面的完全比当前优，即\(ans>=r_i\)，不管当前的，直接

continue

否则后面的一定在当前的区间中，那么策略就是如果这次选中的数比后面的小就往后选，否则留着当前的，那么答案就是

\[ans=\frac{ans-l_i}{2}\times \frac{ans-l_i}{r_i-l_i}+\frac{ans+r_i}{2}\times \frac{r_i-ans}{r_i-l_i}

\]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=1000050;
const double exs=1e-15;
inline bool pd(double x,double y)
{
	if(x<y)swap(x,y);
	if(x-y<exs)return 1;
	return 0;
}	
int l[N],r[N],n;
signed main()
{
	freopen("pag.in","r",stdin);
	freopen("pag.out","w",stdout);
	cin>>n;for(int i=1;i<=n;i++)l[i]=read(),r[i]=read();
	double ans=0.0;
	for(int i=n;i>=1;i--)
	{
		if(ans<l[i]||pd(ans,l[i])){ans=(1.0*l[i]+r[i])/2.0;continue;}
		if(ans>r[i]||pd(ans,r[i]))continue;
		double p=(ans-l[i])/(1.0*r[i]-l[i]);
		ans=ans*p+(1.0-p)*((1.0*r[i]+ans)/2.0);
	}
	printf("%.5Lf",ans);
	return 0;
}
           

T3.技术情报局

真不知道这名字怎么来的

建出大根笛卡尔树，每个节点维护当前区间前缀之积的和，后缀之积的和，区间积，然后dfs一遍合并统计答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10;
namespace GenHelper{
	unsigned z1, z2, z3, z4, b;
	unsigned rand_()
	{
		b=((z1<<6)^z1)>>13;
		z1=((z1&4294967294U)<<18)^b;	
		b=((z2<<2)^z2)>>27;
		z2=((z2&4294967288U)<<2)^b;
		b=((z3<<13)^z3)>>21;
		z3=((z3&4294967280U)<<7)^b;	
		b=((z4<<3)^z4)>>12;
		z4=((z4&4294967168U)<<13)^b;
		return (z1^z2^z3^z4);
	}
} 
int a[N],ls[N],rs[N],root;
void get(int n,unsigned s,int l,int r) 
{
	using namespace GenHelper;
	z1=s;
	z2=unsigned((~s)^0x233333333U);
	z3=unsigned(s^0x1234598766U);
	z4=(~s)+51;
	for(int i=1;i<=n;i++) 
	{
		int x=rand_()&32767;
		int y=rand_()&32767;
		a[i]=l+(x*32768+y)%(r-l+1);
	}
}
int n,s,l,r,mod,ans;stack <int> st;
int sum[N],p1[N],p2[N];
void dfs(int x)
{
	if(ls[x])dfs(ls[x]);
	if(rs[x])dfs(rs[x]);
	ans=(ans+(p2[ls[x]]*p1[rs[x]]%mod*a[x]%mod+(p1[rs[x]]+p2[ls[x]])%mod*a[x]%mod+a[x])%mod*a[x]%mod)%mod;
	p1[x]=(p1[ls[x]]+(p1[rs[x]]+1)*((ls[x]?sum[ls[x]]:1ll)*a[x]%mod)%mod)%mod;
	p2[x]=(p2[rs[x]]+(p2[ls[x]]+1)*((rs[x]?sum[rs[x]]:1ll)*a[x]%mod)%mod)%mod;
	sum[x]=(ls[x]?sum[ls[x]]:1)*(rs[x]?sum[rs[x]]:1)%mod*a[x]%mod;
}
signed main()
{
	freopen("tio.out","w",stdout);
	freopen("tio.in","r",stdin);
	cin>>n>>s>>l>>r>>mod;
	get(n,s,l,r);
	for(int i=1;i<=n;i++)
	{	
		int p=0;
		while(st.size()&&a[st.top()]<a[i])p=st.top(),st.pop();
		if(st.size())rs[st.top()]=i;
		if(p)ls[i]=p;st.push(i);
	}
	while(st.size()>1)st.pop();root=st.top();
	dfs(root);cout<<ans<<endl;
	return 0;
}
           

T4.肯德基

考虑什么时候没有贡献，就是一个数有平方因子的时候

那么我们就想把平方因子消掉，由于上界是\(\sqrt n\)所以可以，由于会算重所以需要容斥，思考莫比乌斯函数的实际意义会发现容斥系数就是\(\mu\) ,设\(g(x)=\sum_{i=1}^x i\)那么答案就是

\[\sum_{i=1}^{\sqrt n}i^2\times \mu(i)\times g(\lfloor \frac{n}{i^2}\rfloor)

\]

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long 
const int N=10000050;
int p[N],tot,mu[N],f[N];bool v[N];
inline int get(int x)
{
	if(x&1)return ((x+1)>>1)*x;
	else return (x>>1)*(x+1);
}
signed main()
{	
	freopen("kfc.in","r",stdin);
	freopen("kfc.out","w",stdout);
	mu[1]=1;
	for(signed i=2;i<=1e7+10;i++)
	{
		if(!v[i]){p[++tot]=i;mu[i]=-1;}
		for(signed j=1;j<=tot&&p[j]*i<=1e7+10;j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0){mu[p[j]*i]=0;break;}
			else mu[p[j]*i]=-mu[i];
		}
	}
	for(int i=1;i<=1e7+10;i++)f[i]=f[i-1]+mu[i]*i*i;
	int t;cin>>t;
	for(int i=1;i<=t;i++)
	{
		int x;scanf("%llu",&x);
		int ans=0,lim=sqrt(x);
		for(int l=1,r;l<=lim;l=r+1)
		{
			r=min((int)sqrt(x/(x/(l*l))),lim);
			ans+=(f[r]-f[l-1])*get(x/(l*l));
		}
		printf("%llu\n",ans);
	}
	return 0;
}	
           

考试总结

予明日所有失败者 赋万千不灭颂歌