时间戳

首页 > 技术文章 > 2021.3.31模拟赛

2021.3.31模拟赛

SYDevil 2021-03-31 19:27 原文

2021.3.31模拟赛

这次的题好像挺简单的，应该出的是弱省省选题

T1

序列\(a\)有\(n\)个元素，每次操作可以使相邻两数每次其中一个\(-1\)，另一个\(-2\)，求最少操作多少次使全部数不大于\(0\)

\(n,a_i\leq 10^6\)

应该没有人会想网络流吧

开始一直在打贪心，但打的都是假的

后来只能打了个\(O(nh^2)\)的\(\tt dp\),我赛上估计的\(50pt\)，但好像因为常数小，拿了\(70pt\).（赛后估出来常数\(\frac{1}{8}\)左右，然后弄过去了

正解是反悔型贪心

所谓反悔型贪心，在我看来，其实就是我们想要更改以前的操作，但是为了不造成时间复杂度的爆炸，而构造出一些操作，使得我们一定可以通过此些操作变回我们希望的最优选择

对于这道题呢，我们只需要构造\(3\)种操作即可

（白嫖一张图

代码超级超级超级简单！！！

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;char k;bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int main(){fre("building");
	ll ans=0;
	for(int s=read,x,y,z,t=0,w,v=0;s--;){
		w=read-v;
		if(w<=0){t=0;v=0;continue;}
		x=min(w/3,t);w-=3*x;
		y=w/2;w-=y*2;
		z=w;w-=z;
		ans+=x+y+z;
		v=z*2+y;t=x*2+y;
	}
	cout<<ans;
	return 0;
}

T2

\(n\)个珠子串成一圈，\(k\)种颜色，每颗珠子随意染或不染，但相邻的\(2\)颗不能都染色，求本质不同的方案数

当且仅当\(2\)种方案中，存在一种旋转方案，使得相同位置上的珠子颜色均相同，二种方案本质相同

\(n,k\leq 10^9\)

不难想到\(\tt poly\)，于是我们可以推出下式

\(Ans=\frac{1}{n}\sum_{i=1}^n f(\gcd(i,n))\)

其中\(f(x)\)表示\(x\)颗珠子，不考虑旋转，要求首尾不能同时有色满足条件的方案数

先不管\(f\),继续变换

\[\begin{align} Ans&=\frac{1}{n}\sum_{i=1}^nf(\gcd(i,n))\\ &=\frac{1}{n}\sum_{d|n}f(d)\sum_{i=1}^n[\gcd(i,n)==d]\\ &=\frac{1}{n}\sum_{d|n}f(d)\sum_{i=1}^{\frac{n}{d}}\varepsilon(\gcd(i,\frac{n}{d}))\\ &=\frac{1}{n}\sum_{d|n}f(d)\sum_{i=1}^{n\over d}\sum_{j|\gcd(i,\frac{n}{d})}\mu(j)\\ &=\frac{1}{n}\sum_{d|n}f(d)\sum_{j|\frac{n}{d}}\mu(j)\sum_{i=1}^\frac{n}{jd}1\\ &=\frac{1}{n}\sum_{d|n}f(d)\sum_{j|\frac{n}{d}}\mu(j)\text{id}(\frac{n}{jd})\\ \because &I*\varphi=\text{id}\\ \therefore &\mu *\text{id}=\varphi\\ Ans&=\frac{1}{n}\sum_{d|n}f(d)\varphi(\frac{n}{d}) \end{align} \]

\(f\)怎么求呢？

我们设\(g(x)\),表示不考虑旋转，满足条件的方案数

\(g(x)=k\cdot g(x-2)+g(x-1)\)

\(g(0)=1,g(1)=k+1\)

不难得到\(f(x)=2k\cdot g(x-3)+g(x-2)\)

为什么呢？

假设我们要求\(c0***0,0***0,0***0c\)情况的方案数(c为有色，0为无色，*未知)

\(c0***0=(***)\cdot k\)

\(0***0=***\)

其实就表示我们先钦定前后的一些位置为什么，然后变成对首尾无限制的情况

\(g\)的话可以推通项公式（不建议），也可以矩阵快速幂，反正随便搞搞就行了

这样我们就可以枚举\(d\),求出结果了

但是\(n\leq 10^9\),怎么求\(\varphi\)呢

如果暴力求\(\varphi\),看上去时间复杂度为\({\LARGE\int}_0^\sqrt n\sqrt xdx=O(n^{3\over 4})\)

但是经过暴力枚举，发现\(10^9\)内约数最多的数为\(735134400\),共有\(1344\)个约数

这样运行次数上界约为\(4*10^7\)

我觉得不保险，所以先筛出了\(10^7\)以内的\(\varphi\)与素数

每次查时先查表，再用素数筛

最坏也只用求\(100\)次\(\varphi\),每次为\(O(\frac{\sqrt n}{\ln n})\)

运行次数约为\(3*10^5\)

但是因为要筛\(10^7\)内的值所以跑的比\(\tt std\)慢

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;char k;bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 1000000007
struct Mat{
	ll a[2][2];
	Mat(){memset(a,0,sizeof(a));}
	ll* operator [](unsigned n){return a[n];}
	Mat operator *(Mat b){
		Mat c;
		c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
		c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
		c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
		c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
		return c;
	}
	Mat& operator *=(Mat b){return *this=*this*b;}
};
int n,k;
# define M 65535
map<int,int>ma[M+1];
ll F(int n){
	if(n==0)return 1;
	if(n==1)return k+1;
	int &va=ma[n&M][n];
	if(va)return va;
	Mat x,y;x[0][0]=k+1;x[0][1]=2*k+1;
	y[1][0]=1;y[0][1]=k;y[1][1]=1;
	--n;
	for(;n;n>>=1,y*=y)
		if(n&1)x*=y;
	return va=x[0][0];
}
ll G(int n){
	if(n==1)return 1;
	if(n==2)return 2*k+1;
	return (F(n-3)*2ll*k+F(n-2))%mod;
}
bool vis[10000005];
int prime[1000005],phi[10000005];
const int N=10000000;
void init(){phi[1]=1;
	for(int i=2;i<=N;++i){
		if(!vis[i])prime[++prime[0]]=i,phi[i]=i-1;
		for(int j=1;j<=prime[0]&&prime[j]*i<=N;++j){
			vis[prime[j]*i]=1;
			if(!(i%prime[j])){phi[prime[j]*i]=phi[i]*prime[j];break;}
			phi[prime[j]*i]=phi[i]*(prime[j]-1);
		}
	}
}
ll Phi(ll n){
	if(n<=N)return phi[n];
	ll t=n;
	for(int i=prime[1],j=1;i*i<=n;i=prime[++j])
		if(!(n%i)){
			t=t/i*(i-1);
			while(!(n%i))n/=i;
		}
	if(n>1)t=t/n*(n-1);
	return t;
}
ll qkpow(ll n,int m){
	ll t=1;
	for(;m;m>>=1,n=n*n%mod)
		if(m&1)t=t*n%mod;
	return t;
}
int main(){
	fre("bracelet");
	init();
	n=read,k=read;ll ans=0;
	for(int i=1;i*i<=n;++i)
		if(!(n%i)){
			ans=(ans+G(i)*Phi(n/i))%mod;
			if(n!=i*i)ans=(ans+G(n/i)*Phi(i))%mod;
		}
	cout<<ans*qkpow(n,mod-2)%mod;
	return 0;
}

T3

给定\(n,k\)，\(n\)次操作,每次往可重集\(A\)加入或删除一个数\(a_i\)后，询问\(A\)中有多少对数的\(\gcd\)为\(k\)

\(1\leq k\leq a_i\leq 10^5,n\leq 10^5\)

这次考试最简单的一道，但是容易想复杂

直接说正解

题目即要求我们求\(\sum_{i=1}^n\sum_{j=i+1}^n[\gcd(A_i,A_j)==k]\)

不难发现，如果\(k\nmid A_i\)，则\(A_i\)对结果不产生贡献

所以下文我们默认\(A_i\)除了\(k\)的

那么变为\(\sum_{i,j\in[1,n],i<j}\varepsilon(\gcd(A_i,A_j))\)

\[\begin{align} Ans&=\sum_{i,j\in[1,n],i<j}\space \sum_{d|\gcd(A_i,A_j)}\mu(d)\\ &=\sum_{d=1}^\infty \mu(d){\sum_{d \mid A_i} 1\choose 2} \end{align} \]

所以我们直接存下每个\(d\)在\(A\)中的倍数个数，每次\(\sqrt{n}\)的修改，就可以了

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;char k;bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
bool vis[100005];
int prime[100005],mu[100005];
const int N=100000;
void init(){mu[1]=1;
	for(int i=2;i<=N;++i){
		if(!vis[i])prime[++prime[0]]=i,mu[i]=-1;
		for(int j=1;j<=prime[0]&&prime[j]*i<=N;++j){
			vis[prime[j]*i]=1;
			if(!(i%prime[j])){mu[prime[j]*i]=0;break;}
			mu[prime[j]*i]=-mu[i];
		}
	}
}
int n,k,h[100005],hv[100005];
ll ans;
ll S(ll x){return x*(x-1)/2;}
int main(){
	fre("number");
	init();
	n=read,k=read;
	for(int i=1;i<=n;printf("%lld\n",ans),++i)
		if(read){
			int x=read;++hv[x];
			if(x%k)continue;
			x/=k;
			for(int j=1;j*j<=x;++j)
				if(!(x%j)){
					ans-=mu[j]*S(h[j]);
					++h[j];
					ans+=mu[j]*S(h[j]);
					if(j*j!=x){
						int t=x/j;
						ans-=mu[t]*S(h[t]);
						++h[t];
						ans+=mu[t]*S(h[t]);
					}
				}
		}else{
			int x=read;
			if(x%k||!hv[x])continue;
			--hv[x];x/=k;
			for(int j=1;j*j<=x;++j)
				if(!(x%j)){
					ans-=mu[j]*S(h[j]);
					--h[j];
					ans+=mu[j]*S(h[j]);
					if(j*j!=x){
						int t=x/j;
						ans-=mu[t]*S(h[t]);
						--h[t];
						ans+=mu[t]*S(h[t]);
					}
				}
		}
	return 0;
}
题外话

老实说，这次自己也没想到\(\rm T1\)能拿\(70pt\),本来只打算拿\(50pt\)的，看来还是常数小

这次状态不是很好，一来就肝\(\rm T1\)并非一个正确的选择，下次还是先看完所有题再敲吧

还有，做之前先证明！！！

\(\rm T1\)之所以打这么久主要还是因为打了\(4、5\)个假贪心，打了\(2h+\),要不是这次题不是很难，就阴沟里翻船了

推荐阅读