登录
当前位置： 首页 > 工具软件 > Eurasia > 使用案例 >

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

长孙宜
2023-12-01

A. Nanoassembly

首先用叉积判断是否在指定向量右侧，然后解出法线与给定直线的交点，再关于交点对称即可。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=300020;
typedef long long LL;
typedef pair<int,int>pi;
struct P{
	double x,y;
	P(){x=y=0;}
	P(double _x,double _y){x=_x,y=_y;}
	P operator+(P v){return P(x+v.x,y+v.y);}
	P operator-(P v){return P(x-v.x,y-v.y);}
	P operator*(double v){return P(x*v,y*v);}
	double len(){return hypot(x,y);}
	double len_sqr(){return x*x+y*y;}
	P rot90(){return P(-y,x);}
}a[111111],A,B;
const double eps=1e-8;
int sgn(double x){
	if(x<-eps)return -1;
	if(x>eps)return 1;
	return 0;
}
double cross(P a,P b){
	return a.x*b.y-a.y*b.x;
}
P line_intersection(P a,P b,P p,P q){
	double U=cross(p-a,q-p),D=cross(b-a,q-p);
	return a+(b-a)*(U/D);
}

int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int n,m,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
	while(m--){
		scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
		P t=B-A;
		t=t.rot90();
		//printf("t=%.4f %.4f\n",t.x,t.y);
		for(i=1;i<=n;i++)if(cross(a[i]-A,B-A)>0){
			P o=line_intersection(A,B,a[i],a[i]+t);
			//printf("->%d %.4f %.4f\n",i,(a[i]+t).x,(a[i]+t).y);
			a[i]=(o*2.0)-a[i];
		}
		//for(i=1;i<=n;i++)printf("%.4f %.4f\n",a[i].x,a[i].y);
	}
	for(i=1;i<=n;i++)printf("%.8f %.8f\n",a[i].x,a[i].y);
	return 0;
}

　　

B. Playoff

建树根据dfs括号序列判断是否成祖孙关系即可。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=300020;
int n;
string name[Maxn];
map<string,int>id;
int a[Maxn<<2];

char s[Maxn];
bool check(int id1,int id2){
	id1+=n;id2+=n;
	for(int i=id2;i;i>>=1)if(a[i]==id1)return 1;
	return 0;
}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	while(scanf("%d",&n)!=EOF){
		n=1<<n;
		id.clear();
		for(int i=0;i<n;i++)
		cin>>name[i],id[name[i]]=i,a[n+i]=n+i;
		int cur=n>>1,tot=0;
		scanf("%s",s);
		//printf("sss=%s\n",s);
		for(;cur;cur>>=1){
			for(int i=cur;i<cur<<1;i++){
				char c=s[tot++];
				if(c=='W')a[i]=a[i<<1];
				else a[i]=a[i<<1|1];
			}
		}
		int q;scanf("%d",&q);
		//printf("q=%d\n",q);
		while(q--){
			string s1,s2;
			cin>>s1>>s2;
			int id1=id[s1],id2=id[s2];
			if(check(id1,id2)){
				puts("Win");
			}
			else if(check(id2,id1)){puts("Lose");}
			else puts("Unknown");
		}
	}
}

　　

C. Inequalities

差分约束系统，下界直接作为初始值，然后判断是否出现正环或者超过上限，需要SLF优化。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 1000005 ;
const int MAXE = 1000005 ;

struct Edge {
	int v , c , n ;
	Edge () {}
	Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {}
} ;

Edge E[MAXE] ;
int H[MAXN] , cntE ;
int d[MAXN] , vis[MAXN] , cnt[MAXN] , Q[MAXN] , head , tail ;
int maxv[MAXN] ;
int n , m ;

void init () {
	cntE = 0 ;
	clr ( H , -1 ) ;
}

void addedge ( int u , int v , int c ) {
	E[cntE] = Edge ( v , c , H[u] ) ;
	H[u] = cntE ++ ;
}

int spfa () {
	while ( head != tail ) {
		int u = Q[head ++] ;
		if ( head == MAXN ) head = 0 ;
		vis[u] = 0 ;
		for ( int i = H[u] ; ~i ; i = E[i].n ) {
			//if ( clock () > 1.99 * CLOCKS_PER_SEC ) return 0 ;
			int v = E[i].v ;
			if ( d[v] < d[u] + E[i].c ) {
				d[v] = d[u] + E[i].c ;
				if ( d[v] > maxv[v] ) return 0 ;
				if ( !vis[v] ) {
					vis[v] = 1 ;
					cnt[v] ++ ;
					if ( cnt[v] == n + 1 ) return 0 ;
					if ( d[Q[head]] < d[v] ) {
						-- head ;
						if ( head < 0 ) head = MAXN - 1 ;
						Q[head] = v ;
					} else {
						Q[tail ++] = v ;
						if ( tail == MAXN ) tail = 0 ;
					}
				}
			}
		}
	}
	return 1 ;
}

void solve () {
	init () ;
	int ok = 1 ;
	head = tail = 0 ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		d[i] = -2e9 ;
		maxv[i] = 2e9 ;
		Q[tail ++] = i ;
		vis[i] = 1 ;
		cnt[i] = 0 ;
	}
	for ( int i = 0 ; i < m ; ++ i ) {
		int op , x , xv , y , yv ;
		scanf ( "%d%d%d%d%d" , &op , &x , &xv , &y , &yv ) ;
		if ( x == 0 ) {
			if ( y == 0 ) addedge ( xv , yv , op ) ;
			else maxv[xv] = min ( maxv[xv] , yv - op ) ;
		} else {
			if ( y == 0 ) d[yv] = max ( d[yv] , xv + op ) ;
			else if ( xv + op > yv ) ok = 0 ;
		}
	}
	if ( !ok || !spfa () ) {
		puts ( "NO" ) ;
		return ;
	}
	puts ( "YES" ) ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		printf ( "%d\n" , d[i] ) ;
	}
}

int main () {
	freopen ( "input.txt" , "r" , stdin ) ;
	freopen ( "output.txt" , "w" , stdout ) ;
	while ( ~scanf ( "%d%d" , &m , &n ) ) solve () ;
	return 0 ;
}

　　

D. How to measure the Ocean?

按$s\times p$从小到大排序，然后二分答案，尽量延伸每条线段的长度，看看是否达到$d$即可。

#include <bits/stdc++.h>
using namespace std ;

const int MAXN = 100005 ;

struct Node {
	int p , a ;
	bool operator < ( const Node& t ) const {
		return p < t.p ;
		//return min ( a - p , t.a - p - t.p ) > min ( a - p - t.p , t.a - t.p ) ;
	}
} ;

Node a[MAXN] ;
int d , n ;

void solve () {
	int S , P , A ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%d%d%d" , &S , &P , &A ) ;
		a[i].p = S * P ;
		a[i].a = S * A ;
	}
	sort ( a + 1 , a + n + 1 ) ;
	double l = 0 , r = 1e6 ;
	for ( int o = 0 ; o <= 100 ; ++ o ) {
		double x = ( l + r ) / 2 , mid = x ;
		double D = 0 ;
		int ok = 0 ;
		for ( int i = 1 ; i <= n ; ++ i ) {
			double l = max ( 0.0 , 1.0 * ( a[i].a - x ) / a[i].p ) ;
			D += l ;
			x += l * a[i].p ;
			if ( D >= d ) {
				ok = 1 ;
				break ;
			}
		}
		if ( ok ) l = mid ;
		else r = mid ;
	}
	printf ( "%.10f\n" , l ) ;
}
	
int main () {
	freopen ( "input.txt" , "r" , stdin ) ;
	freopen ( "output.txt" , "w" , stdout ) ;
	while ( ~scanf ( "%d%d" , &d , &n ) ) solve () ;
	return 0 ;
}

　　

E. Navigation

建图跑最短路即可。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 1605 ;
const double INF = 1e50 ;

int n , m , k , vr , vf ;
double d[MAXN] , G[MAXN][MAXN] ;
int vis[MAXN] , p[MAXN] ;
int x[MAXN] , y[MAXN] ;
vector < int > S ;

double get_dis ( int x , int y ) {
	return sqrt ( 1.0 * x * x + 1.0 * y * y ) ;
}

void dij ( int s ) {
	for ( int i = 1 ; i <= n ; ++ i ) {
		d[i] = INF ;
		vis[i] = 0 ;
		p[i] = 0 ;
	}
	d[s] = 0 ;
	for ( int i = 1 ; i < n ; ++ i ) {
		double minv = INF ;
		int u = s ;
		for ( int j = 1 ; j <= n ; ++ j ) {
			if ( !vis[j] && d[j] < minv ) {
				minv = d[j] ;
				u = j ;
			}
		}
		vis[u] = 1 ;
		for ( int j = 1 ; j <= n ; ++ j ) {
			if ( !vis[j] && d[u] + G[u][j] < d[j] ) {
				d[j] = d[u] + G[u][j] ;
				p[j] = u ;
			}
		}
	}
}

void insert ( int o ) {
	if ( p[o] ) {
		insert ( p[o] ) ;
		S.push_back ( p[o] ) ;
	}
}

void solve () {
	S.clear () ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%d%d" , &x[i] , &y[i] ) ;
		for ( int j = 1 ; j <= i ; ++ j ) {
			G[i][j] = G[j][i] = get_dis ( x[i] - x[j] , y[i] - y[j] ) / vf ;
		}
	}
	for ( int i = 0 ; i < m ; ++ i ) {
		int u , v ;
		scanf ( "%d%d" , &u , &v ) ;
		G[u][v] = G[v][u] = G[u][v] * vf / vr ;
	}
	int pre = 1 , now ;
	double ans = 0 ;
	for ( int i = 1 ; i <= k ; ++ i ) {
		scanf ( "%d" , &now ) ;
		dij ( pre ) ;
		insert ( now ) ;
		ans += d[now] ;
		pre = now ;
	}
	dij ( now ) ;
	insert ( n ) ;
	ans += d[n] ;
	S.push_back ( n ) ;
	printf ( "%.10f\n" , ans ) ;
	for ( int i = 0 ; i < S.size () ; ++ i ) {
		i && putchar ( ' ' ) ;
		printf ( "%d" , S[i] ) ;
	}
	puts ( "" ) ;
}

int main () {
	freopen ( "input.txt" , "r" , stdin ) ;
	freopen ( "output.txt" , "w" , stdout ) ;
	while ( ~scanf ( "%d%d%d%d%d" , &n , &m , &k , &vr , &vf ) ) solve () ;
	return 0 ;
}

　　

F. Bets

根据题意模拟即可。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=300020;
typedef long long LL;
typedef pair<int,int>pi;
void scan(LL &x){
	char s[10];scanf("%s",s);
	int ned=5;
	int has=0;
	x=0;
	for(int i=0;s[i];i++){
		if(s[i]=='.'){
			has=1;
			continue;
		}
		x=x*10+s[i]-'0';
		if(has)ned--;
	}
	for(int i=0;i<ned;i++)x=x*10;
}
int main(){
	
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int _;scanf("%d",&_);
	while(_--){
		LL a,b,c;
		scan(a);
		scan(b);
		scan(c);
		LL tot=a*b*c;
		LL res=tot/a+tot/b+tot/c;
		//printf("a=%lld b=%lld c=%lld\n",a,b,c);
		//printf("res=%lld tot=%lld\n",res,tot);
		if(res*100000<tot)puts("YES");
		else puts("NO");
	}
}

　　

G. Ant on the road

留坑。

 

H. Bouquet

将花按照颜色排序，设$f[i][j][k]$表示考虑了前$i$朵花，总价值为$j$，第$i$种花所在的颜色是否需要计入答案为$k$时颜色数的最大值，然后DP即可。

时间复杂度$O(nS)$。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=300020;
typedef long long LL;
typedef pair<int,int>pi;
int n,S;
pi a[Maxn];
int dp[2][50020][2];
void up(int &x,int y){x=max(x,y);}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	while(scanf("%d%d",&n,&S)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%d%d",&a[i].first,&a[i].second);
		}
		sort(a,a+n);
		memset(dp,-1,sizeof dp);
		dp[0][0][0]=0;
		int cs=0;
		for(int i=0;i<n;i++){
			int islast=(i==n-1)||(a[i+1].first!=a[i].first);
			memset(dp[cs^1],-1,sizeof dp[cs^1]);
			int w=a[i].second;
			for(int j=0;j<=S;j++){
				int nw=w+j;
				//if(nw>S)continue;
				for(int k=0;k<2;k++){
					int val=dp[cs][j][k];
					if(val<0)continue;
					up(dp[cs^1][j][islast?0:k],val);
					if(nw>S)continue;
					up(dp[cs^1][nw][islast?0:1],val+(k!=1));
				}
			}
			cs^=1;
		}
		int ans=max(dp[cs][S][0],dp[cs][S][1]);
		if(ans<0)puts("Impossible");
		else printf("%d\n",ans);
	}
}

　　

I. Hash function

倒着解出初始值即可。

#include<cstdio>

typedef unsigned int UI ;

UI Hash ( UI v ) {
	v = v + ( v << 10 ) ;
	v = v ^ ( v >> 6 ) ;
	v = v + ( v << 3 ) ;
	v = v ^ ( v >> 11 ) ;
	v = v + ( v << 16 ) ;
	return v;
}

typedef long long ll;

ll exgcd(ll a,ll b,ll&x,ll&y){
  if(!b)return x=1,y=0,a;
  ll d=exgcd(b,a%b,x,y),t=x;
  return x=y,y=t-a/b*y,d;
}
ll cal(ll a,ll b,ll n){
  ll x,y,d=exgcd(a,n,x,y);
  x=(x%n+n)%n;
  return x*(b/d)%(n/d);
}

UI F(UI v,int B){
  ll a=(1U<<B)+1;
  ll b=v;
  ll n=1LL<<32;
  return cal(a,b,n);
}

UI G11(UI v){
  UI G=v>>21,H=(v>>10)&((1U<<11)-1),I=v&((1U<<10)-1);
  UI A=G;
  UI B=H^A;
  UI C=I^(B>>1);
  return (A<<21)|(B<<10)|(C);
}

UI G6(UI v){
  UI a=v>>26,b=(v>>20)&((1U<<6)-1),c=(v>>14)&((1U<<6)-1),
     d=(v>>8)&((1U<<6)-1),e=(v>>2)&((1U<<6)-1),f=v&((1U<<2)-1);
  UI A=a;
  UI B=A^b;
  UI C=B^c;
  UI D=C^d;
  UI E=D^e;
  UI F=(E>>4)^f;
  return (A<<26)|(B<<20)|(C<<14)|(D<<8)|(E<<2)|F;
}

UI Hash2 ( UI v ) {
	v = F(v,16);
	v = G11(v);
	v = F(v,3);
	v = G6(v);
	v = F(v,10);
	return v;
}

int cal(UI v){
  UI t=v;
  for(int i=1;;i++){
    t=Hash(t);
    if(t==v)return i;
  }
}

UI n ;

int main () {
	freopen ( "input.txt" , "r" , stdin ) ;
	freopen ( "output.txt" , "w" , stdout ) ;
	int T ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		scanf ( "%u" , &n ) ;
		printf ( "%u\n" , Hash2 ( n ) ) ;
	}
	return 0 ;
}

　　

J. Civilization

留坑。

 

K. Master Gambs chairs

每个集合取最小的即可。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=300020;
typedef long long LL;
int n,S;
vector<int>V[Maxn];
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	while(scanf("%d%d",&n,&S)!=EOF){
		vector<int>tmp;
		for(int i=1;i<=n;i++)V[i].clear();
		for(int i=1;i<=n;i++){
			int x,y;scanf("%d%d",&x,&y);
			V[x].push_back(y);
		}
		for(int i=1;i<=n;i++){
			if(!V[i].size())continue;
			sort(V[i].begin(),V[i].end());
			tmp.push_back(V[i][0]);
		}
		sort(tmp.begin(),tmp.end());
		LL cur=0;
		int ans=0;
		for(int i=0;i<tmp.size();i++){
			if(cur+tmp[i]<=S){
				cur+=tmp[i];
				ans++;
			}
			else break;
		}
		printf("%d\n",ans);
	}
}

　　

L. Scrabble

根据题意模拟即可。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=300020;
typedef long long LL;
typedef pair<int,int>pi;
int n,m;
int di[2][2]={{1,0},{0,1}};
int Mp[22][22];
int col[22][22];
int ltc[]={1,1,2,3,1,1};
int wc[]={1,1,1,1,2,3};
int ans[11];
int base[]={0,1,3,2,3,2,1,5,5,1,2,2,2,2,1,1,2,2,2,2,3,10,5,10,5,10,10,10
	    ,5,5,10,10,3};
int main(){

	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	col[1][1]=5;
	for(int i=2;i<=5;i++){
		col[i][i]=4;
	}
	col[6][2]=col[2][6]=3;
	col[4][1]=col[1][4]=col[3][7]=col[7][3]=col[7][7]=2;
	for(int i=1;i<=7;i++){
		for(int j=1;j<=7;j++){
			col[16-i][j]=col[i][16-j]=col[i][j];
		}
	}
	col[8][1]=col[1][8]=col[8][15]=col[15][8]=5;
	col[8][4]=col[4][8]=col[8][12]=col[12][8]=2;
	col[8][8]=1;
	for(int i=1;i<=7;i++){
		for(int j=9;j<=15;j++){
			col[16-i][j]=col[i][j];
		}
	}
	scanf("%d%d",&n,&m);
	//puts("ok");
	for(int i=1,turn=0;i<=m;i++,(turn=(turn+1)%n)){
		int k;scanf("%d",&k);
		//printf("kk=%d\n",k);
		int cnt=0;
		for(int it=0;it<k;it++){
			char d;
			int curx,cury;
			int num;scanf("%d %c%d%d",&num,&d,&curx,&cury);
			int ty=d=='h'?0:1;
			int tmp=0,mul=1;
			for(int it2=0;it2<num;it2++){
				int x;scanf("%d",&x);
				if(!Mp[curx][cury])cnt++;
				Mp[curx][cury]=x;
				tmp+=base[x]*ltc[col[curx][cury]];
				mul*=wc[col[curx][cury]];
				curx+=di[ty][0];
				cury+=di[ty][1];
			}
			ans[turn]+=tmp*mul;			
		}
		if(cnt>=7)ans[turn]+=15;
	}
	for(int i=0;i<n;i++)printf("%d\n",ans[i]);
}

 

总结：

  • D题想复杂了，在错误的道路上越走越远，碰到这种情况应该换人想。
  • 读题速度需要提高，没有来得及阅读的J题其实也可做。

 

 类似资料：

相关阅读

相关文章

相关问答

快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.