XVI Open Cup named after E.V. Pankratiev. GP of Peterhof

时间：2023-01-01 14:34:18

A. (a, b)-Tower

当指数大于模数的时候用欧拉定理递归计算，否则直接暴力计算。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<string>

#include<iostream>

using namespace std;

typedef long long LL;

int pw(int x,int y,int mod){

	int ret=1;

	for(int i=0;i<y;i++){

		ret=1LL*ret*x%mod;

	}

	return ret;

}

int solve(int l,int r,int p){

	if(l==1)return 1;

	if(l==r){

		return l%p;

	}

	int phi=0;

	for(int i=1;i<=p;i++)if(__gcd(p,i)==1)phi++;

	return pw(l,solve(l+1,r,phi)+phi,p);

}

int main(){

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

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

	int a,b;

	while(scanf("%d%d",&a,&b)!=EOF){

		printf("%d\n",solve(a,b,10));

	}

}

　　

B. Bridges Construction

留坑。

C. Equivalence Relation

留坑。

D. Formula-1

留坑。

E. Ideal Photo

三分第一个人的位置即可。

#include <bits/stdc++.h>

using namespace std ;

const int MAXN = 205 ;

int n;

vector<int>V;

double check(double x){

	double ret=0;

	for(int i=0;i<V.size();i++){

		ret+=sqrt(1.0+1.0*(V[i]-x-i)*(V[i]-x-i));

	}

	return ret;

}

void solve () {

	V.clear();

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

		int x;scanf("%d",&x);

		V.push_back(x);

	}

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

		int x;scanf("%d",&x);

		V.push_back(x);

	}

	sort(V.begin(),V.end());

	double l=-3e6;

	double r=3e6;

	for(int i=0;i<300;i++){

		double l1=l+(r-l)/3,l2=l+(r-l)/3*2;

		double t1=check(l1),t2=check(l2);

		if(t1>t2)l=l1;else r=l2;

	}

	double ans=check(l);

	//printf("%.12f %.12f\n",l,r);

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

	//for(double l=-5;l<=5;l+=0.1)printf("%.12f\n",check(l));

}

int main () {

	freopen ( "make-a-row.in" , "r" , stdin ) ;

	freopen ( "make-a-row.out" , "w" , stdout ) ;

	while ( ~scanf ( "%d" , &n ) ) solve () ;

	return 0 ;

}

　　

F. (p, q)-Knight

首先通过exgcd求出一组可行解，然后暴力调整若干项即可。

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<string.h>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<queue>

#include<time.h>

#include<assert.h>

#include<iostream>

using namespace std;

typedef long long LL;

typedef pair<int,int>pi;

const LL Inf=1LL<<60;

LL exgcd(LL a,LL b,LL &x,LL &y){

	if(!b)return x=1,y=0,a;

	LL d=exgcd(b,a%b,y,x);

	y-=a/b*x;return d;

}

LL ans;

void up(LL &x,LL y){if(x>y)x=y;}

void check(LL t1,LL t2,LL x,LL y){

	if(abs(t1%2)!=abs(x%2))return;

	if(abs(t2%2)!=abs(y%2))return;

	up(ans,max(abs(t1),abs(x))+max(abs(t2),abs(y)));

	//if(x==10&&y==-3)printf("val=%lld\n",max(abs(t1),abs(x))+max(abs(t2),abs(y)));

	//if(x==10&&y==-3)printf("t1=%lld t2=%lld ans=%lld\n",t1,t2,ans);

}

int main(){

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

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

	LL p,q;

	while(scanf("%lld%lld",&p,&q)!=EOF){

		if(p>q)swap(p,q);

		if(p==0){

			puts(q==1?"1":"-1");

			continue;

		}

		if(p==1){

			if(q%2==1)puts("-1");

			else printf("%lld\n",q+1);

			continue;

		}

		if(__gcd(p,q)!=1){

			puts("-1");

			continue;

		}

		LL x,y;

		LL t1=p,t2=q;

		exgcd(p,q,x,y);

		//printf("x=%lld y=%lld\n",t1,t2);

		ans=Inf;

		for(int i=-2;i<=2;i++){

			check(t1,t2,x+i*q,y-i*p);

		}

		x=-x,y=-y;

		for(int i=-2;i<=2;i++){

			check(t1,t2,x+i*q,y-i*p);

		}

		if(ans==Inf){

			puts("-1");

		}

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

	}

	return 0;

}

　　

G. Random Wormholes

如果能到1，那么直接走过去，否则随机走向下一个点。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<string>

#include<iostream>

using namespace std;

typedef long long LL;

int main(){

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

	//freopen("abtower.out","w",stdout);

	while(1){

		LL RAND=(1LL<<32)-1;

		printf("1\n");

		fflush(stdout);

		string s;

		cin>>s;

		if(s=="yes"){break;}

		while(1){

			LL x=(rand()%65536)*65536LL+rand()%65536;

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

			fflush(stdout);

			cin>>s;

			if(s=="yes")break;

		}

	}

}

　　

H. Second Maximum

分段积分。

#include <bits/stdc++.h>

using namespace std ;

const int MAXN = 205 ;

int n;

vector<int>V;

int l[55],r[55];

double a[55];

double b[55];

void mul(double t0,double t1){

	memset(b,0,sizeof b);

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

		if(i)b[i]+=a[i-1]*t1;

		b[i]+=a[i]*t0;

	}

	for(int i=0;i<=n+1;i++)a[i]=b[i];

}

void solve () {

	double ans=0;

	V.clear();

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

		scanf("%d%d",l+i,r+i);

		V.push_back(l[i]);

		V.push_back(r[i]);

	}

	sort(V.begin(),V.end());

	V.erase(unique(V.begin(),V.end()),V.end());

	for(int it=0;it<V.size()-1;it++){

		int curl=V[it],curr=V[it+1];

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

			if(r[i]<=curl)continue;

			memset(a,0,sizeof a);

			a[0]=1;

			//if(curr>l[i])mul((curr+0.0)/(r[i]-l[i]),1.0/(l[i]-r[i]));

			bool flag=1;

			for(int j=0;j<n;j++){

				if(i==j)continue;

				if(curr<=l[j]){flag=0;break;}

				if(curl<r[j]){

					mul((l[j]+0.0)/(l[j]-r[j]),1.0/(r[j]-l[j]));

				}

			}

			if(!flag)continue;

			/*

			if(it==1&&i==0){

				puts("wa");

				for(int j=0;j<=n;j++)printf("%.2f ",a[j]);puts("");

			}

			*/

			a[0]=0;

			for(int j=1;j<=n;j++)a[j]*=j;

			if(curr>l[i])mul((r[i]+0.0)/(r[i]-l[i]),1.0/(l[i]-r[i]));

			for(int j=1;j<=n+1;j++)a[j]/=j+1;

			double rr=curr*curr,ll=curl*curl;

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

				ans+=a[j]*(rr-ll);

				rr=rr*curr;

				ll=ll*curl;

			}

			//printf("it=%d i=%d ans=%.2f\n",it,i,ans);

		}

	}

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

}

int main(){

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

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

	while(~scanf("%d",&n))solve();

}

　　

I. Ticket To Ride

留坑。

总结：

  • 尽快适应数学场。

相关文章