2020.12.16 模拟赛x+1

A. 接力比赛

跑两遍背包，再进行一些玄学的剪枝

代码

#include<cstdio>

#include<algorithm>

#define rg register

inline int read(){

	rg int x=0,fh=1;

	rg char ch=getchar();

	while(ch<'0' || ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0' && ch<='9'){

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*fh;

}

const int maxn=1e3+5,maxm=1e6+5;

int n,m,maxa,maxb,mmax;

long long fa[maxm],fb[maxm],ans=0;

struct asd{

	int val,cost;

}b1[maxn],b2[maxn];

bool cmp(asd aa,asd bb){

	return aa.val>bb.val;

}

int main(){

	n=read(),m=read();

	for(rg int i=1;i<=n;i++){

		b1[i].cost=read(),b1[i].val=read();

	}

	for(rg int i=1;i<=m;i++){

		b2[i].cost=read(),b2[i].val=read();

	}

	mmax=700;

	std::sort(b1+1,b1+1+n,cmp);

	std::sort(b2+1,b2+1+m,cmp);

	for(rg int i=1;i<=mmax;i++){

		maxa+=b1[i].cost;

	}

	for(rg int i=1;i<=mmax;i++){

		maxb+=b2[i].cost;

	}

	for(rg int i=1;i<=maxa;i++){

		fa[i]=-0x3f3f3f3f3f3f3f3f;

	}

	for(rg int i=1;i<=maxb;i++){

		fb[i]=-0x3f3f3f3f3f3f3f3f;

	}

	for(rg int i=1;i<=mmax;i++){

		for(rg int j=maxa;j>=b1[i].cost;j--){

			fa[j]=std::max(fa[j],fa[j-b1[i].cost]+b1[i].val);

		}

	}

	for(rg int i=1;i<=mmax;i++){

		for(rg int j=maxb;j>=b2[i].cost;j--){

			fb[j]=std::max(fb[j],fb[j-b2[i].cost]+b2[i].val);

		}

	}

	for(rg int i=1;i<=maxa;i++){

		ans=std::max(ans,fa[i]+fb[i]);

	}

	printf("%lld\n",ans);

	return 0;

}

B. 树上竞技

单独考虑每一条边的贡献

设该边一侧关键点的个数为 \(x\) ，则另一侧关键点的个数为 \(m-x\)

那么最终的集合点一定会选在点比较多的那一侧，因为我们要让尽量少的点经过这条边

设该边一侧点的个数为 \(s\) ，则另一侧点的个数为 \(n-s\)

该边的答案就是 \(\sum_{i=1}^{m-1}C_s^i \times C_{n-s}^{m-i} \times min(i,m-i)\)

带着 \(min\) 不好处理，我们把它展开

\[\sum_{i=1}^{\frac{m-1}{2}} C_{S}^{i} C_{n-S}^{m-i} \times i + \sum_{i=1}^{\frac{m-1}{2}} C_{S}^{m-i} C_{n-S}^{i} \times i + [m\%2=0] \times C
_{S}^{\frac{m}{2}} \times C_{n-S}^{\frac{m}{2}} \times \frac{m}{2}\]

前两项本质是相同的，最后一项加的时候特判一下即可

变一下形式\(\sum_{i=1}^{\frac{m-1}{2}} C_{S}^{i} C_{n-S}^{m-i} \times i=\sum_{i=1}^{\frac{m-1}{2}} C_{S-1}^{i-1} C_{n-S}^{m-i} \times s\)

令 \(k=\frac{m-1}{2}\)

则 \(G(S) = \sum_{i=1}^{k} C_{S-1}^{i-1} C_{n-S}^{m-i}\)

所以我们只需要求出 \(G(s)\) 即可

我们现在考虑 \(G(s)\) 的组合意义,可以理解为 \(n-1\) 个物品里一共要选 \(m-1\) 个，前面 \(s-1\) 个里最多选 \(k-1\) 个的方案数

要从 \(G(i)\) 变成 \(G(i+1)\)，发现答案变少的部分就是前面 \(i-1\) 个选了 \(k-1\) 个，而 \(i\) 也被选中了

只有这种情况会被 \(G(i)\) 计算而不会被 \(G(i+1)\) 计算

\(O(n)\) 递推即可计算,最后枚举每一条边算贡献再累加即可

代码

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#define rg register

inline int read(){

	rg int x=0,fh=1;

	rg char ch=getchar();

	while(ch<'0' || ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0' && ch<='9'){

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*fh;

}

const int mod=1e9+7,maxn=1e6+5;

int h[maxn],tot=1,n,m;

struct asd{

	int to,nxt;

}b[maxn<<1];

void ad(rg int aa,rg int bb){

	b[tot].to=bb;

	b[tot].nxt=h[aa];

	h[aa]=tot++;

}

int siz[maxn],ans;

void dfs(rg int now,rg int lat){

	siz[now]=1;

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==lat) continue;

		dfs(u,now);

		siz[now]+=siz[u];

	}

}

int ny[maxn],jc[maxn],jcc[maxn],fa[maxn];

int getC(rg int nn,rg int mm){

	return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;

}

void pre(){

	ny[1]=1;

	for(rg int i=2;i<maxn;i++){

		ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;

	}

	jc[0]=jcc[0]=1;

	for(rg int i=1;i<maxn;i++){

		jc[i]=1LL*jc[i-1]*i%mod;

		jcc[i]=1LL*jcc[i-1]*ny[i]%mod;

	}

}

int anss[maxn];

int js(rg int aa,rg int bb){

	if(aa>bb) std::swap(aa,bb);

	if(anss[aa]!=-1) return anss[aa];

	rg int nans=0;

	for(rg int i=1;i<=m-1;i++){

		rg int j=m-i;

		if(aa<i) break;

		if(bb<j) continue;

		nans+=1LL*getC(aa,i)*getC(bb,j)%mod*std::min(i,j)%mod;

		if(nans>=mod) nans-=mod;

	}

	return anss[aa]=nans;

}

void dfs2(rg int now,rg int lat){

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==lat) continue;

		ans+=js(siz[u],n-siz[u]);

		if(ans>=mod) ans-=mod;

		dfs2(u,now);

	}

}

int getsum(int num){

	return 1LL*num*(num+1)/2LL%mod;

}

bool haha=1;

int main(){

	memset(h,-1,sizeof(h));

	memset(anss,-1,sizeof(anss));

	n=read(),m=read();

	for(rg int i=2;i<=n;i++){

		fa[i]=read();

		if(fa[i]!=i-1) haha=0;

		ad(fa[i],i);

		ad(i,fa[i]);

	}

	pre();

	if(n<1000000 && m>=200000) {

		rg int cs;

		if(m!=1){

			pre();

			for(rg int i=1;i<=n;i++){

				if(i-1<m/2 || n-i<m/2) continue;

				cs=1LL*getC(i-1,m/2)*getC(n-i,m/2)%mod;

				ans+=1LL*cs*(m/2)%mod*getsum(i-1)%mod*ny[i-1]%mod;

				if(ans>=mod) ans-=mod;

				ans+=1LL*cs*(m/2)%mod*getsum(n-i)%mod*ny[n-i]%mod;

				if(ans>=mod) ans-=mod;

			}

		}

	} else {

		dfs(1,0);

		dfs2(1,0);

	}

	printf("%d\n",ans);

	return 0;

}

C. 虚构推理

可以枚举每一个时刻，然后取最小值

但是秒不一定是整数，所以直接枚举精度不大好处理

于是可以模拟退火

把时针和分针提前排好序可以做到 \(log(n)\) 计算答案，可以多做不少遍模拟退火

代码比较玄学，多交几遍可以 \(AC\)

代码

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<ctime>

#define rg register

const int maxn=5e4+5;

typedef double db;

const db eps=1e-6,xs=0.999;

struct asd{

	int a,b,c;

}jl[maxn];

struct jie{

	db jd;

	int id;

}orza[maxn],orzb[maxn];

bool cmp(jie aa,jie bb){

	return aa.jd<bb.jd;

}

int n,jla,jlb;

db jlc,ans=1000;

db jsfz(rg db a1,rg db b1,rg db c1,rg db a2,rg db b2,rg db c2){

	rg db ans1=(db)b1*6.0+(db)c1/10.0;

	rg db ans2=(db)b2*6.0+(db)c2/10.0;

	return fabs(ans1-ans2);

}

db jssz(rg db a1,rg db b1,rg db c1,rg db a2,rg db b2,rg db c2){

	rg db ans1=a1*30+(db)b1/2.0+(db)c1/120.0;

	rg db ans2=a2*30+(db)b2/2.0+(db)c2/120.0;

	return fabs(ans1-ans2);

}

int ef1(db aa){

	rg int l=1,r=n,mids;

	if(aa>=360) aa-=360;

	if(aa<0) aa+=360;

	while(l<=r){

		mids=(l+r)>>1;

		if(orza[mids].jd>=aa) r=mids-1;

		else l=mids+1;

	}

	return l;

}

int ef2(db aa){

	rg int l=1,r=n,mids;

	if(aa>=360) aa-=360;

	if(aa<0) aa+=360;

	while(l<=r){

		mids=(l+r)>>1;

		if(orzb[mids].jd>=aa) r=mids-1;

		else l=mids+1;

	}

	return l;

}

db jsa(rg int now,rg db aa,rg db bb,rg db cc){

	rg int id;

	if(now<1 || now>n) return 0;

	rg db ans1,ans2;

	id=orza[now].id;

	ans1=jsfz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);

	ans2=jssz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);

	ans1=std::min(ans1,360.0-ans1);

	ans2=std::min(ans2,360.0-ans2);

	return std::max(ans1,ans2);

}

db jsb(rg int now,rg db aa,rg db bb,rg db cc){

	rg int id;

	if(now<1 || now>n) return 0;

	rg db ans1,ans2;

	id=orzb[now].id;

	ans1=jsfz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);

	ans2=jssz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);

	ans1=std::min(ans1,360.0-ans1);

	ans2=std::min(ans2,360.0-ans2);

	return std::max(ans1,ans2);

}

db js(rg db aa,rg db bb,rg db cc){

	rg db nans=0,jd1=jssz(aa,bb,cc,0,0,0),jd2=jsfz(aa,bb,cc,0,0,0);

	rg int wz=ef1(jd1+180.0);

	nans=std::max(nans,jsa(wz-1,aa,bb,cc));

	nans=std::max(nans,jsa(wz,aa,bb,cc));

	nans=std::max(nans,jsa(1,aa,bb,cc));

	nans=std::max(nans,jsa(n,aa,bb,cc));

	wz=ef2(jd2+180.0);

	nans=std::max(nans,jsb(wz-1,aa,bb,cc));

	nans=std::max(nans,jsb(wz,aa,bb,cc));

	nans=std::max(nans,jsb(1,aa,bb,cc));

	nans=std::max(nans,jsb(n,aa,bb,cc));

	return nans;

}

void mnth(){

	db t=1.0;

	rg int aa=12,bb=60;

	while(t>eps){

		if(aa) aa--;

		if(bb) bb--;

		rg int na=(jla+aa*(rand()%2-1))%12;

		rg int nb=(jlb+bb*(rand()%2-1))%60;

		db nc=jlc+(rand()*2-RAND_MAX)%60*t;

		if(na<0) na+=12;

		if(nb<0) nb+=60;

		if(nc<0) nc+=60;

		if(nc>=60) nc-=60;

		db nw=js(na,nb,nc);

		db cha=nw-ans;

		if(cha<0){

			jla=na,jlb=nb,jlc=nc,ans=nw;

		} else if(exp(-cha/t)*RAND_MAX>rand()){

			jla=na,jlb=nb,jlc=nc;

		}

		t*=xs;

	}

}

int main(){

	srand(time(0));

	scanf("%d",&n);

	rg char ch1,ch2;

	for(rg int i=1;i<=n;i++){

		scanf("%02d%c%02d%c%02d",&jl[i].a,&ch1,&jl[i].b,&ch2,&jl[i].c);

		jl[i].a%=12;

		orza[i].id=orzb[i].id=i;

		orza[i].jd=jssz(jl[i].a,jl[i].b,jl[i].c,0,0,0);

		orzb[i].jd=jsfz(jl[i].a,jl[i].b,jl[i].c,0,0,0);

	}

	std::sort(orza+1,orza+1+n,cmp);

	std::sort(orzb+1,orzb+1+n,cmp);

	ans=js(jla,jlb,jlc);

	for(rg int i=1;i<=350;i++){

		mnth();

	}

	printf("%.8f\n",ans);

	return 0;

}

D. 记忆碎片

考虑 \(DP\)

设 \(f[i][s]\) 表示当前考虑了前 \(i\) 短的边,联通状态为 \(s\) 的方案数,\(s\) 的表示方法可以使用最小表示法(其实就是\(sort\)之后拿\(vector\)存一下再用 \(map\) 映射)

状态数不是很多，最多只有 \(37338\)

转移时只需要分两种情况

1、当前的边不是最小生成树中的边，此时只能从某一个联通块中选两个没有边的点去连

2、当前的边是最小生成树中的边，考虑当前边连接了哪两个之前没有相连的联通块即可

常数巨大

代码

#include<cstdio>

#include<algorithm>

#include<vector>

#include<map>

#define rg register

const int maxn=45,maxm=40005,mod=1e9+7;

int n,f[maxn*maxn][maxm],tot,sum[maxm],m;

bool vis[maxn*maxn];

std::vector<int> g[maxm],cs;

std::map<std::vector<int>,int> mp;

void dfs(rg int now,rg int lat){

	if(lat==0){

		if(now==0){

			g[++tot]=cs;

			for(rg int i=0;i<g[tot].size();i++){

				rg int u=g[tot][i];

				sum[tot]+=1LL*u*(u-1)/2%mod;

				if(sum[tot]>=mod) sum[tot]-=mod;

			}

		}

		return;

	}

	dfs(now,lat-1);

	if(now>=lat){

		cs.push_back(lat);

		dfs(now-lat,lat);

		cs.pop_back();

	}

}

int main(){

	scanf("%d",&n);

	m=(n-1)*n/2;

	rg int aa;

	for(rg int i=1;i<n;i++){

		scanf("%d",&aa);

		vis[aa]=1;

	}

	dfs(n,n);

	for(rg int i=1;i<=tot;i++){

		std::reverse(g[i].begin(),g[i].end());

		mp[g[i]]=i;

	}

	f[0][1]=1;

	for(rg int i=0;i<m;i++){

		for(rg int j=1;j<=tot;j++){

			if(f[i][j]){

				if(vis[i+1]){

					for(rg int k=0;k<g[j].size();k++){

						for(rg int o=k+1;o<g[j].size();o++){

							cs.clear();

							cs.push_back(g[j][k]+g[j][o]);

							for(rg int p=0;p<g[j].size();p++){

								if(p!=k && p!=o){

									cs.push_back(g[j][p]);

								}

							}

							std::sort(cs.begin(),cs.end());

							f[i+1][mp[cs]]+=1LL*f[i][j]*g[j][k]%mod*g[j][o]%mod;

							if(f[i+1][mp[cs]]>=mod) f[i+1][mp[cs]]-=mod;

						}

					}

				} else {

					f[i+1][j]+=1LL*f[i][j]*(sum[j]-i)%mod;

					if(f[i+1][j]>=mod) f[i+1][j]-=mod;

				}

			}

		}

	}

	printf("%d\n",f[m][tot]);

	return 0;

}

巴特西

2020.12.16 模拟赛x+1

A. 接力比赛

代码

B. 树上竞技

代码

C. 虚构推理

代码

D. 记忆碎片

代码

最新文章

热门文章