清北学堂省选刷题冲刺班 Test Day3

时间：2021-08-02 05:01:13

2018.3.27 Test

时间：8:00~11:30

期望得分：100+60+25=185

实际得分：100+40+25=165

这篇基本啥东西没写→_→

T1

//位数和只有[0,72]这73种情况，a次方后也是只有73种情况，枚举后得出x算一下是否满足即可。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=75,LIM=1e9;

int a,K,Ans[666666];

LL b,c,w[76][7];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

void Pre()

{

	for(int i=1; i<=73; ++i)

	{

		LL tmp=i;

		for(int j=1; j<=5; ++j,tmp*=i) w[i][j]=tmp;

	}

}

int main()

{

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

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

	Pre();

	int T=read();

	while(T--)

	{

		a=read(),b=read(),c=read(),K=read(),Ans[0]=0;

		for(int i=0; i<=73; ++i)

		{

			LL tmp=(LL)(w[i][a]*b+c);

			if(tmp>K) break;

			int res=0,ans=(int)tmp;

			for(; tmp; tmp/=10) res+=tmp%10;

			if(res==i) Ans[++Ans[0]]=ans;

		}

		printf("%d\n",Ans[0]);

		if(Ans[0]) for(int i=1; i<=Ans[0]; ++i) printf("%d ",Ans[i]);

		else printf("-1");

		putchar('\n');

	}

	return 0;

}

T2

woc标程T2.T3都5.6k，也没题解，不改了。

T3


考试代码

T2

高斯消元爆精度怎么破。。60分都没拿到当时没学辗转相除的高斯消元。。

打表发现10~15一小段内答案是成倍增长的(确实只有几个数有规律。。精度差太大吧)，然后，也没什么了。。

#include <cmath>

#include <cstdio>

#include <algorithm>

#define mod (1000000007)

typedef long long LL;

const int N=205;

const double eps=1e-9;

const LL delta[7]={1,1,13,13,12,11};

double mat[N][N];

LL n,K;

double Gauss()

{

	for(int j=1; j<n; ++j)

	{

		int mxrow=j;

		for(int i=j; i<n; ++i)

			if(fabs(mat[i][j])>fabs(mat[mxrow][j])) mxrow=i;

		if(!mat[mxrow][j]) return 0;

		if(mxrow!=j) std::swap(mat[mxrow],mat[j]);

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

			if(mat[i][j])

			{

				double t=mat[i][j]/mat[j][j];

				for(int k=j; k<n; ++k)

					mat[i][k]-=t*mat[j][k];

			}

	}

	double res=1.0;

	for(int i=1; i<n; ++i) res*=mat[i][i];

	return fabs(res);

}

void P()

{

	for(int i=0; i<n; ++i,putchar('\n'))

		for(int j=0; j<n; ++j) printf("%.0lf ",mat[i][j]);

	putchar('\n');

}

void Matrix(bool f)

{

	for(int i=0; i<n; ++i)

		for(int j=0; j<n; ++j) mat[i][j]=0;

	for(int i=0; i<K; ++i) mat[i][i]=i+std::min(K,n-i-1);

	for(int i=K; i<n; ++i) mat[i][i]=K+std::min(K,n-i-1);

	for(int i=0; i<n; ++i)

		for(int j=i+1; j<=std::min(n,i+K); ++j)

			--mat[i][j], --mat[j][i];

//	P();

	if(f) printf("%I64d",((LL)Gauss())%mod);

}

double FP(double x,LL k)

{

	double t=1.0;

	for(; k; k>>=1,x=x*x)

		if(k&1) t=t*x;

	return t;

}

//LL Calc(LL b,LL a,LL n){

//	return FP(b*FP(a,mod-2)%mod,n);

//}

int main()

{

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

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

	scanf("%I64d%I64d",&n,&K);

	if(K==1) {putchar('1'); return 0;}

	if(n<=200) {Matrix(1); return 0;}

	LL tmp=n;

	n=delta[K]-1, Matrix(0);

	double a=Gauss();

	++n, Matrix(0);

	double b=Gauss();

	printf("%I64d",((LL)(b*FP(b/a,tmp-n)))%mod);

//	printf("%.0lf",((LL)(FP(b,tmp-n)*FP(FP(a,tmp-n),mod-2)))%mod);	

//	LL a=((LL)Gauss())%mod;

//	LL b=((LL)Gauss())%mod;

//	printf("%I64d",b*Calc(b,a,tmp-n)%mod);//还是脱不了实数快速幂。。

	return 0;

}

打表程序：

#include <cmath>

#include <cstdio>

#include <algorithm>

#define mod (1000000007)

typedef long long LL;

const int N=105;

const double eps=1e-9;

double mat[N][N];

LL n,K;

double Gauss()

{

	for(int j=1; j<n; ++j)

	{

		int mxrow=j;

		for(int i=j; i<n; ++i)

			if(fabs(mat[i][j])>fabs(mat[mxrow][j])) mxrow=i;

		if(!mat[mxrow][j]) return 0;

		if(mxrow!=j) std::swap(mat[mxrow],mat[j]);

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

			if(mat[i][j])

			{

				double t=mat[i][j]/mat[j][j];

				for(int k=j; k<n; ++k)

					mat[i][k]-=t*mat[j][k];

			}

	}

	double res=1.0;

	for(int i=1; i<n; ++i) res*=mat[i][i];

	return fabs(res);

}

void P()

{

	for(int i=0; i<n; ++i,putchar('\n'))

		for(int j=0; j<n; ++j) printf("%.0lf ",mat[i][j]);

	putchar('\n');

}

int gcd(int x,int y){

	return y?gcd(y,x%y):x;

}

int main()

{

//	freopen("like.in","r",stdin);

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

	K=2;

	double pre=1,ans;

	int g;

	for(n=3; n<=50; ++n)

	{

		for(int i=0; i<n; ++i)

			for(int j=0; j<n; ++j) mat[i][j]=0;

		for(int i=0; i<K; ++i) mat[i][i]=i+std::min(K,n-i-1);

		for(int i=K; i<n; ++i) mat[i][i]=K+std::min(K,n-i-1);

		for(int i=0; i<n; ++i)

			for(int j=i+1; j<=std::min(n,i+K); ++j)

				--mat[i][j], --mat[j][i];

//		P();

		printf("f[%I64d][%I64d] = %.0lf\n",n,K,ans=((LL)Gauss())%mod);

		g=gcd((int)ans,(int)pre);

		printf("Rate:%.0lf/%.0lf = %.3lf\t%.0lf/%.0lf = %.3lf = %d/%d\n",pre,ans,pre/ans,ans,pre,ans/pre,(int)ans/g,(int)pre/g);

		pre=ans;

	}

	return 0;

}

T3

以为10^9用bitset说不定能水过去，果然高估机房电脑了233。

cena实测bitset比bool数组慢很多！bool[][]5.6s能跑过1000，bitset10s过不去。。（不过相比也是编译器辣鸡的锅）

#include <cstdio>

#include <cctype>

#include <bitset>

#include <algorithm>

#define rgint register int

#define gc() getchar()

//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1005,MAXIN=5e5;

int n,mod,R,Enum,H[N],to[N<<1],nxt[N<<1],dis[N][N],tmp[N];

LL K,A[N];

std::bitset<N> f[N];

//bool f[N][N];

//char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline void AddEdge(int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;

}

void DFS(int x,int f,int anc,LL sum)

{

	dis[x][anc]=sum;

	for(int i=H[x]; i; i=nxt[i])

		if(to[i]!=f) DFS(to[i],x,anc,(sum*K+A[to[i]])%mod);

}

int main()

{

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

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

	n=read(),mod=read(),K=read(),R=read();

	for(int i=1; i<=n; ++i) A[i]=read();

	for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);

	for(int i=1; i<=n; ++i) DFS(i,i,i,A[i]);

	for(rgint i=1; i<=n; ++i)

		for(rgint j=1; j<=n; ++j) f[i]|=((dis[i][j]==R)<<j);

	LL res=0;

	for(rgint cnt,i=1; i<=n; ++i)//p1

	{

		cnt=0;

		for(int j=1; j<=n; ++j)

			if(!f[i][j]) tmp[++cnt]=j;

		for(rgint j=1; j<=cnt; ++j)

			for(int k=1; k<=cnt; ++k)

				if(!f[tmp[j]][tmp[k]]) ++res;

		cnt=0;

		for(int j=1; j<=n; ++j)

			if(f[i][j]) tmp[++cnt]=j;

		for(rgint j=1; j<=cnt; ++j)

			for(int k=1; k<=cnt; ++k)

				if(f[tmp[j]][tmp[k]]) ++res;

	}

	printf("%I64d",res);

	return 0;

}

相关文章