[2019 Multi-University Training Contest 1]

比赛网址

训练详情

时间:2020-5-17 13:00~18:00
rank:
完成情况：

题解

A Rush Hour Puzzle

题意

一个大家都玩过的游戏，求步数

题解

solved by fyh

把6*6哈希压成一个状态，然后直接bfs暴力搜代码写的过于丑，但是基本都是复制粘贴的。

代码

#include<bits/stdc++.h>
#include<map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct State
{
	int st[10][10];
	State() {mem(st,0);}
	ULL Hash()
	{
		ULL res=0;
		for(int i=0;i<6;i++)
			for(int j=0;j<6;j++)
				res=(res+st[i][j])*107; 
		return res;
	}
};
map<ULL,int> vis;
map<ULL,int> dis;
queue<State> Q;
int main()
{	
	State init;
	for(int i=0;i<6;i++)
		for(int j=0;j<6;j++)
			init.st[i][j]=read();
	Q.push(init);
	ULL hinit=init.Hash();
	vis[hinit]=1;
	dis[hinit]=0;
	while(Q.size())
	{
		State now=Q.front();Q.pop();
		ULL hnow=now.Hash();
		if(dis[hnow]>8)return puts("-1"),0;
		if(now.st[2][5]==1 && now.st[2][4]==1)return printf("%d\n",dis[hnow]+2),0;
		for(int i=0;i<6;i++)
			for(int j=0;j<6;j++)
			{
				if(now.st[i][j] && j+1<6 && now.st[i][j]==now.st[i][j+1] && (now.st[i][j+1]!=now.st[i][j+2] || j+2>=6) && (now.st[i][j-1]!=now.st[i][j] || j<=0))//横2车
				{
					if(j>0 && !now.st[i][j-1])//左移
					{
						State tmp=now;
						tmp.st[i][j-1]=now.st[i][j];
						tmp.st[i][j+1]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}
					if(j+2<6 && !now.st[i][j+2])
					{
						State tmp=now;
						tmp.st[i][j+2]=now.st[i][j];
						tmp.st[i][j]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}//右移 
				} 
				else if(now.st[i][j] && j+2<6 && now.st[i][j]==now.st[i][j+1] && now.st[i][j+1]==now.st[i][j+2])//横3车 
				{
					if(j>0 && !now.st[i][j-1])//左移
					{
 
						State tmp=now;
						tmp.st[i][j-1]=now.st[i][j];
						tmp.st[i][j+2]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}
					if(j+3<6 && !now.st[i][j+3])
					{	
						State tmp=now;
						tmp.st[i][j+3]=now.st[i][j];
						tmp.st[i][j]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}//右移 
				}
				else if(now.st[i][j] && i+1<6 && now.st[i][j]==now.st[i+1][j] && (now.st[i+1][j]!=now.st[i+2][j] || i+2>=6) && (now.st[i-1][j]!=now.st[i][j] || i<=0))//竖2车 
				{
					if(i>0 && !now.st[i-1][j])//上移
					{
						State tmp=now;
						tmp.st[i-1][j]=now.st[i][j];
						tmp.st[i+1][j]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}
					if(i+2<6 && !now.st[i+2][j])
					{
						State tmp=now;
						tmp.st[i+2][j]=now.st[i][j];
						tmp.st[i][j]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}//右移 
				}
				else if(now.st[i][j] && i+2<6 && now.st[i][j]==now.st[i+1][j] && now.st[i+1][j]==now.st[i+2][j])//竖3车 
				{
					if(i>0 && !now.st[i-1][j])//上移
					{
						State tmp=now;
						tmp.st[i-1][j]=now.st[i][j];
						tmp.st[i+2][j]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}
					if(i+3<6 && !now.st[i+3][j])
					{
						State tmp=now;
						tmp.st[i+3][j]=now.st[i][j];
						tmp.st[i][j]=0;
						ULL htmp=tmp.Hash();
						if(!vis[htmp])
						{
							dis[htmp]=dis[hnow]+1;
							vis[htmp]=1;
							Q.push(tmp);
						}
					}//右移 
				}
			}
	}
	puts("-1");
	return 0;
}

C Are They All Integers?

solved by hxm

题意

大水题

题解

略

D Tapioka

solved by wxg

题意

删掉一个字符串序列中的指定的字符串

题解

无敌水题，略

E The League of Sequence Designers

solved by wxg&hxm

题意

给定一个数字序列，求最大的连续和乘以长度。

现在给出一个错误的做法，错误做法仅计算最大连续和来更新答案

求构造出一个长度大于$l$小于$2000$的序列，使得错误答案和正确答案相差正好为$k$

题解

分析发现，只要在最大连续和的串前加上一个负数，那么这个做法就会出错，现在要构造出两种答案相差$k$

由于最大长度为$1999$，不妨就构造长度为$1999$的序列，第一位为$-1$，剩下为非负数，和为$a$，则有

$(a - 1) \times 1999 - a \times 1998 = k$

即$a = k + 1999$，算出$a$后，分配给剩下每一位即可

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int K,L;
int ans[maxn];
void work(){
	int sum = 1999 + K;
	printf("1999\n");
	printf("-1");
	for (int i = 1; i <= 1997; i++) printf(" %d",sum / 1998);
	printf(" %d\n",sum - sum / 1998 * 1997);
}
int main(){
	int T = read();
	while (T--){
		K = read(); L = read();
		if (L >= 2000) puts("-1");
		else work();
	}
	return 0;
}

H Mining a

solved by fyh&hxm

题意

$\frac{1}{n} = \frac{1}{a Xor b} + \frac{1}{b}$

给定$n$，$b$是任意的，求最大的$a$使等式成立

题解

化简得$b = n + \frac{n^2}{a Xor b - n}$

枚举分母即可

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
LL n,a,b,N,ans;
int main(){
	int T =read();
	while (T--){
		ans = 0;
		n = read(); N = n * n;
		LL t;
		for (int i = 1; i < n; i++){
			if (N % i == 0){
				//1
				t = i;
				b = N / t + n;
				a = (t + n) ^ b;
				ans = max(ans,a);
				//2
				t = N / i;
				b = N / t + n;
				a = (t + n) ^ b;
				ans = max(ans,a);
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

J Automatic Control Machine

solved by hxm

题意

给定若干个集合，使用最少的集合并成全集

题解

bitset状压dp一下就好了

代码

K Automatic Control Machine

solved by wxg

题意

合并果子，数据还特小，题解略

CVBB ACM Team

目录

[2019 Multi-University Training Contest 1]

训练详情

题解

A Rush Hour Puzzle

题意

题解

C Are They All Integers?

题意

题解

D Tapioka

题意

题解

E The League of Sequence Designers

题意

题解

H Mining a

题意

题解

J Automatic Control Machine

题意

题解

K Automatic Control Machine

题意

训练实况

训练总结

改进

CVBB ACM Team

用户工具

站点工具

目录

[2019 Multi-University Training Contest 1]

训练详情

题解

A Rush Hour Puzzle

题意

题解

C Are They All Integers?

题意

题解

D Tapioka

题意

题解

E The League of Sequence Designers

题意

题解

H Mining a

题意

题解

J Automatic Control Machine

题意

题解

K Automatic Control Machine

题意

训练实况

训练总结

改进

页面工具