20191003 「HZOJ NOIP2019 Round #8」20191003模拟

综述

试题为常州集训2019SCDay2

得分\(100+30(0)+28\)

时之终结

问题描述

HZOJ1310

题解

构造题。

发现部分分有一档是 \(Y\) 是 \(2^x\) ，于是自然想到很多个三角形连到一起。

然后正解就是在这个基础上删边。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

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

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

int y,opt=2;

bool eps[1007];

bool deal(){

	int bf=y,cnt=0;

	while(1){

		if(bf&1) return (bf==1);

		++cnt;bf>>=1;++opt;

	}

	return 0;

}

namespace Subtask_2{

	void solve(){

		printf("%lld %lld\n",opt,opt*(opt-1)/2);

		for(int i=1;i<opt;i++){

			for(int j=i+1;j<=opt;j++) printf("%lld %lld\n",i,j);

		}

	}

}

namespace Subtask_3{

	void solve(){

		int bf=y;opt=2;int tmp=1;

		while(bf){

			eps[opt]=(bf&1);bf>>=1;

			tmp+=(eps[opt]==0);++opt;

		}

		printf("%lld %lld\n",opt,opt*(opt-1)/2-tmp);

		for(int i=1;i<opt;i++){

			for(int j=i+1;j<=opt;j++){

				if(j==opt&&!eps[i]) continue;

				printf("%lld %lld\n",i,j);

			}

		}

	}

}

signed main(){

	freopen("review.in","r",stdin);freopen("review.out","w",stdout);

	read(y);

	if(y==1){

		puts("2 1");puts("1 2");

		fclose(stdin);fclose(stdout);

		return 0;

	}

	if(y==2){

		puts("3 3");puts("1 2");puts("2 3");puts("1 3");

		fclose(stdin);fclose(stdout);

		return 0;

//		3 3 1 2 2 3 1 3

	}

	if(deal()) Subtask_2::solve();

	else Subtask_3::solve();

	return 0;

}

博士之时

问题描述

HZOJ1311

题解

想象它是肽链和肽环

正难则反

链只能倒过来，环随便转

注意长度相同的链、长度相同的环可以互换。

\(\mathrm{Code}\)

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=2e5+10;

const int M=5e5+10;

const int mod=1e9+7;

int Num,n,m1,m2,A,B,head[N],cnt,n0,n1,n2,n3,f[N][2],opt,g[N],fac[N],ans,num,tot,bin[N];bool d[N],w[N],vis[N],pd;//f链，g环

bool cc[20][20],dd[20][20];

struct edge{int nxt,to;}ed[M<<1];

inline void addedge(int x,int y){

	ed[++cnt].to=y;ed[cnt].nxt=head[x];head[x]=cnt;

	ed[++cnt].to=x;ed[cnt].nxt=head[y];head[y]=cnt;}

inline void Add(int &x,int y){x+=y;x-=x>=mod? mod:0;}

inline int MOD(int x){x-=x>=mod? mod:0;return x;}

inline int Minus(int x){x+=x<0? mod:0;return x;}

inline int fas(int x,int p){int res=1;while(p){if(p&1)res=1ll*res*x%mod;p>>=1;x=1ll*x*x%mod;}return res;}

inline void DFS(int u){

	vis[u]=true;num++;int record=0;

	for(register int i=head[u];i;i=ed[i].nxt){

		int v=ed[i].to;if(vis[v]){record++;continue;}

		DFS(v);

	}

	if(!ed[head[u]].nxt)opt=w[u];

	if(record==2)pd=true;

}

int main(){

	freopen("refrain.in","r",stdin);

	freopen("refrain.out","w",stdout);

	scanf("%d",&Num);

	scanf("%d%d%d",&n,&m1,&m2);

	for(register int i=1;i<=m1;i++){

		scanf("%d%d",&A,&B);

		d[A]=true;d[B]=true;addedge(A,B);

	}

	for(register int i=1;i<=m2;i++){

		scanf("%d%d",&A,&B);

		w[A]=true;w[B]=true;addedge(A,B);

	}

	fac[0]=1;for(register int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;

	bin[0]=1;for(register int i=1;i<=n;i++)bin[i]=2ll*bin[i-1]%mod;

	ans=fac[n];

	for(register int i=1;i<=n;i++)

		if(!vis[i]){

			num=0;pd=false;DFS(i);

			if(num==1)n0++;

			else if(num==2){if(d[i]&&w[i])n3++;else if(d[i])n1++;else n2++;}

			else if(pd)g[num]++;else f[num][opt]++;

		}

	tot=fac[n0];

	tot=1ll*tot*fac[n1]%mod*bin[n1]%mod;

	tot=1ll*tot*fac[n2]%mod*bin[n2]%mod;

	tot=1ll*tot*fac[n3]%mod*bin[n3]%mod;

	for(register int i=3;i<=n;i++)

		if(i&1)tot=1ll*tot*fac[f[i][0]+f[i][1]]%mod;

		else tot=1ll*tot*fac[f[i][0]]%mod*bin[f[i][0]]%mod*fac[f[i][1]]%mod*bin[f[i][1]]%mod;

	for(register int i=4;i<=n;i+=2)

		tot=1ll*tot*fac[g[i]]%mod*fas(i,g[i])%mod;

	ans=Minus(ans-tot);

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

	return 0;

}

巴特西

20191003 「HZOJ NOIP2019 Round #8」20191003模拟

综述

时之终结

问题描述

题解

\(\mathrm{Code}\)

博士之时

问题描述

题解

\(\mathrm{Code}\)

曾有两次

问题描述

题解

最新文章

热门文章