CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_springtraining6 [2020/05/22 19:00]
mychael
+++ 2020-2021:teams:die_java:front_page_springtraining6 [2020/07/10 14:42] (当前版本)
fyhssgss
@@ 行 1: / 行 1: @@
-====== [2019 Multi-University Training Contest 1] ======
+====== 2019 ICPC Asia Taipei-Hsinchu Regional ======
-[[|比赛网址]]
+[[http://codeforces.com/gym/102460|比赛网址]]
 ===== 训练详情 =====
   * 时间:2020-5-17 13:00~18:00
-  * rank:
+  * rank:''%%93/506%%''
-  * 完成情况：
+  * 完成情况：''%%7/10/13%%''
 ===== 题解 =====
+===== A Rush Hour Puzzle =====
+=== 题意 ===
+一个大家都玩过的游戏，求步数
+=== 题解 ===
+solved by fyh
+把6*6哈希压成一个状态，然后直接bfs暴力搜 代码写的过于丑，但是基本都是复制粘贴的。
+<hidden 代码>
+<code cpp>
+#include<bits/stdc++.h>
+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;
+}
+</code>
+</hidden>
+\\
+===== B The Power Monitor System =====
+=== 题意 ===
+一棵树$n\leq10^5$，初始点和边都是白的，目标是将所有的边和点都染黑。操作代价为1，可以将一个节点和节点的所有出边全部染黑，服从以下三个规则：
+  * rule1:如果一条边被染黑，两个端点也被染黑。
+  * rule2:如果一条边两个点都被染黑，该边被染黑。
+  * rule3:一个点的度数$k>1$且$k-1$条边都被染黑，则剩下一条也被染黑
+=== 题解 ===
+补题 by fyh
+很可怕的一个树形DP
+设计状态$dp[u][0/1/2][0/1]$，第二维度的$0$表示该点由儿子传递过来，$1$表示自己染，$2$表示由父亲传递过来。第三维度的$0$表示不使用规则3进行染色，$1$表示使用规则3进行染色。
+那么就是转移了
+$dp[u][1][0]=\sum min(dp[v][0/1/2][0/1])$ 这个转移很显然，这个点都染上色了，子节点就可以xjb选了
+$dp[u][1][1]$显然离谱，我们就不管他了
+$dp[u][2][0]=\sum dp[v][0][1]$ 不通过规则3染色，故要所有的儿子都是通过规则3生成的，否则$(u,v)$该条边会被染黑
+$dp[u][2][1]$为在$dp[u][2][0]$下选择一颗子树，将其替换成$min\{dp[v][2][0/1]\}$，表示$(u,v)$这条边是由规则3生成染黑的。
+$dp[u][0][0]$ 为至少有一棵子树为$dp[v][1/0][0]$,(前者是儿子直接染黑，后者是儿子被染黑，而且儿子除了父边之外的所有边都是$0$,通过规则3使得$u$被染上的。)+其他子树取$min(00,01,10)$
+$dp[u][0][1]$为在$dp[u][0][0]$ 下的其他子树中选择一颗子树，将其替换成$min\{dp[v][2][0/1]\}$。
+就是感觉这个DP在第三维度定义的很玄学，于是我们的zzh鸽鸽就想到了把状态放在边上的做法…真的太强了。
+<hidden 代码>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define mem(a,b) memset(a,b,sizeof(a))
+typedef long long LL;
+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;
+}
+const int maxn=100010;
+vector<int> G[maxn];
+int n,u,v,dp[maxn][3][2];
+void dfs(int now,int fa)
+{
+    for(int i=0;i<3;i++)for(int j=0;j<2;j++)dp[now][i][j]=maxn;
+    dp[now][1][0]=1;dp[now][2][0]=0;
+    if(G[now].size()==1 && fa)return;
+    dp[now][0][0]=dp[now][0][1]=dp[now][2][0]=dp[now][2][1]=0;
+    int choice[2],tp1[2][2]={0,maxn,maxn,maxn};//choice[]
+    choice[0]=0;choice[1]=maxn;
+    for(auto &v: G[now])
+    {
+        if(v==fa)continue;
+        dfs(v,now);
+        int tmp=min(dp[v][1][0],min(dp[v][0][0],dp[v][0][1]));
+        choice[1]=min(choice[1]+tmp,choice[0]+min(dp[v][0][0],dp[v][1][0])),choice[0]+=tmp;
+        tp1[1][1]=min(tp1[1][1]+tmp,min(tp1[0][1]+min(dp[v][2][0],dp[v][2][1]),tp1[1][0]+min(dp[v][0][0],dp[v][1][0])));
+        tp1[0][1]=min(tp1[0][1]+tmp,tp1[0][0]+min(dp[v][0][0],dp[v][1][0]));
+        tp1[1][0]=min(tp1[1][0]+tmp,tp1[0][0]+min(dp[v][2][0],dp[v][2][1]));
+        tp1[0][0]+=tmp;
+        dp[now][1][0]+=min(min(dp[v][0][0],dp[v][0][1]),min(dp[v][1][0],min(dp[v][2][0],dp[v][2][1])));
+        dp[now][2][1]=min(dp[now][2][0]+min(dp[v][2][0],dp[v][2][1]),dp[now][2][1]+dp[v][0][1]);
+        dp[now][2][0]+=dp[v][0][1];
+    }
+    dp[now][0][0]=choice[1],dp[now][0][1]=tp1[1][1];
+}
+int main()
+{
+    n=read();
+    for(int i=1;i<n;i++)u=read(),v=read(),G[u].push_back(v),G[v].push_back(u);
+    dfs(1,0);
+    printf("%d\n",min(dp[1][1][0],min(dp[1][0][0],dp[1][0][1])));
+    return 0;
+}
+</code>
+</hidden>
+\\
+===== C Are They All Integers? =====
+solved by hxm
+=== 题意 ===
+大水题
+=== 题解 ===
+略
+===== D Tapioka =====
+solved by wxg
+=== 题意 ===
+删掉一个字符串序列中的指定的字符串
+=== 题解 ===
+无敌水题，略
 ===== E The League of Sequence Designers =====
@@ 行 79: / 行 378: @@
 </hidden>
-===== C Are They All Integers? =====
+\\
+===== 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}$
+枚举分母即可
+<hidden 代码>
+<code cpp>
+#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;
+}
+</code>
+</hidden>
+\\
+===== J Automatic Control Machine =====
 solved by hxm
@@ 行 85: / 行 456: @@
 === 题意 ===
-大水题
+给定若干个集合，使用最少的集合并成全集
 === 题解 ===
-略
+bitset状压dp一下就好了
+<hidden 代码>
+<code cpp>
+</code>
+</hidden>
+\\
+===== K Automatic Control Machine =====
+solved by wxg
+=== 题意 ===
+合并果子，数据还特小，题解略
+===== J Largest Quadrilateral =====
+=== 题意 ===
+求平面点组成的最大四边形面积，$n\leq5000$
+=== 题解 ===
+补题by fyh
+求凸包后先枚举对角线，然后通过旋转卡壳把剩下两个点找到，复杂度$O(n^2)$
+当求出凸包只有三个点的时候，所得四边形是一个凹四边形。
+<hidden 代码>
+<code cpp>
+#include<iostream>
+#include<algorithm>
+#include<cmath>
+#include<cstdio>
+#include<cstring>
+#include<cstdlib>
+#include<queue>
+using namespace std;
+#define mem(a,b) memset(a,b,sizeof(a))
+typedef long long LL;
+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;
+}
+const int maxn=2010;
+const double eps=1e-8;
+struct Point{
+	double x,y;
+	Point() {}
+	Point(double _1,double _2):x(_1),y(_2) {}
+	Point operator - (const Point&s) const {return Point(x-s.x,y-s.y);}
+	double operator * (const Point&s) const {return x*s.y-y*s.x;}
+	double len() {return x*x+y*y;}
+}a[maxn],p[maxn];
+typedef Point Vec;
+double dis(Point a,Point b){
+	return (a-b).len();
+}
+double S(Point a,Point b,Point c){
+	return abs((b-a)*(c-a));
+}
+bool judgeOnLeft(int p0,int p1,int p2){
+	double s=(a[p1]-a[p0])*(a[p2]-a[p0]);
+	return s<0 || (s==0 && dis(a[p1],a[p0])>=dis(a[p2],a[p0]));
+}
+bool cmp(Point p0,Point p1){
+	double s=(p0-a[1])*(p1-a[1]);
+	return s<0 || (s==0 && dis(p0,a[1])>=dis(p1,a[1]));
+}
+int n,top,sta[maxn];
+double ans;
+int Graham()
+{
+	int temp=1,m=0;
+	for(int i=2;i<=n;i++)
+		if(a[i].x<a[temp].x || (a[i].x==a[temp].x && a[i].y<a[temp].y))temp=i;
+	swap(a[temp],a[1]);
+	sort(a+2,a+n+1,cmp);
+	a[n+1]=a[1];
+	sta[++top]=1;sta[++top]=2;
+	for(int i=3;i<=n+1;i++)
+	{
+		while(top>1 && judgeOnLeft(sta[top-1],i,sta[top]))top--;
+		sta[++top]=i;
+	}
+	for(int i=1;i<=top;i++)p[m++]=a[sta[i]];//,printf("%lf %lf\n",p[i-1].x,p[i-1].y);
+	return m-1;
+}
+double solve()
+{
+	if(n<4)return 0.000;
+	double ans=0;
+	for(int i=0;i<n;i++)
+	{
+		int k=i+1,l=i+3;
+		for(int j=i+2;j<n;j++)
+		{
+			while(S(p[i],p[j],p[(k+1)%n])-S(p[i],p[j],p[k])>-eps)k=(k+1)%n;
+			while(S(p[i],p[j],p[(l+1)%n])-S(p[i],p[j],p[l])>-eps)l=(l+1)%n;
+			ans=max(ans,S(p[i],p[j],p[k])+S(p[i],p[j],p[l]));
+//			printf("%d %d %d %d\n",i,j,k,l);
+		}
+	}
+	return ans/2.0;
+}
+int main()
+{
+	n=read();
+	if(n<3)return puts("0.000"),0;
+	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
+	n=Graham();
+	printf("%.3lf\n",solve());
+}
+</code>
+</hidden>
 ===== 训练实况 =====
+~15min hxm，wxg横扫**K,C,D**三个签到题
+min~1h20min 口糊出**A**,fyh开写**A**,wxg,hxm讨论**E**,并讨论出来
+h20min~1h28min **A** 本机编译错误，哈希出现问题 hxm开**E**,并A
+h28min~1h??min 想出**H**,写**H** 并A
+h~2h14min hxmA**J**,其他人在读题
+h14min~2h36min fyhA**A**,
+h36min~ 读完所有题并确认全不可做，结束比赛
 ===== 训练总结 =====
+像**A**这种代码量较大的题要尽量往后放，否则会增加罚时
+尽早放弃

CVBB ACM Team

用户工具

站点工具

页面工具