差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:codeforces_round_651_div._2_zars19 [2020/07/01 15:05]
zars19 ↷ 页面名由2020-2021:teams:wangzai_milk:codeforces_round_651_div._2改为2020-2021:teams:wangzai_milk:codeforces_round_651_div._2_zars19
+++ 2020-2021:teams:wangzai_milk:codeforces_round_651_div._2_zars19 [2020/07/02 12:51] (当前版本)
zars19
@@ 行 1: / 行 1: @@
 [[https://codeforces.com/contest/1370|Codeforces Round #651 (Div. 2)]]
+====== A. Maximum GCD ======
+$1$到$n$中任选两个数字$a,b$，能够得到的最大$\gcd(a,b)$
+题解：$\gcd(\lfloor\frac n 2 \rfloor,2·\lfloor\frac n 2 \rfloor)=\lfloor\frac n 2 \rfloor$
+<hidden><code cpp>
+#include<cstdio>
+#include<cstring>
+#include<iostream>
+using namespace std;
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n;
+		scanf("%d",&n);
+		printf("%d\n",n/2);
+	}
+	return 0;
+}
+</code></hidden>
+\\
+====== B. GCD Compression ======
+数组$a$大小为$2n$，先任选两个数字丢掉，再将其余数字两两一组变成二者的和化为大小$n-1$的数组$b$。要求使得数组$b$的最大公因数不为$1$。
+题解：两奇数相加得偶数，两偶数相加还是偶数。只要使得奇、偶数数目为偶数个即可。故如果初始奇、偶数为偶数个，扔掉两奇数或两偶数；初始奇、偶数为奇数个，扔掉一奇一偶。最大公因数$2$
+<hidden><code cpp>
+#include<cstdio>
+#include<cstring>
+#include<iostream>
+#include<stack>
+using namespace std;
+int a[5005];
+stack<int>e,o;
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n;
+		scanf("%d",&n);
+		for(int i=1;i<=2*n;i++)
+		{
+			scanf("%d",&a[i]);
+			if(a[i]&1)o.push(i);
+			else e.push(i);
+		}
+		if(o.size()&1)o.pop(),e.pop();
+		else if(o.size()>=2)o.pop(),o.pop();
+		else e.pop(),e.pop();
+		while(!o.empty())
+		{
+			printf("%d ",o.top());
+			o.pop();
+			printf("%d\n",o.top());
+			o.pop();
+		}
+		while(!e.empty())
+		{
+			printf("%d ",e.top());
+			e.pop();
+			printf("%d\n",e.top());
+			e.pop();
+		}
+	}
+	return 0;
+}
+</code></hidden>
+\\
+====== C. Number Game ======
+初始给出正整数$n$，两玩家轮流操作，每次可以选择在数字大于一的情况下减一或除以大于一的奇因子。无法操作者败
+题解：分类讨论。
+- $n$为奇数。除以它本身先手必胜（$1$是特例，必败）。
+- $n$为偶数且没有大于一的奇因子。先手只能减一之后对方得到上一种局面必胜，故必败（$2$是特例，必胜）。
+- $n$为偶数有大于一的奇因子。先手将奇因子除掉将第二种局面交给对方，故如果因子$2$个数不为一，先手必胜。而当因子$2$个数为一时，若奇因子个数为一，$2·p$减一变奇数必败，除以奇因子必败，总之必败；若奇因子个数不为一，可以除以部分奇因子将$2·p$的局面交给对方以获得必胜。
+<hidden><code cpp>
+#include<cstdio>
+#include<cstring>
+#include<iostream>
+using namespace std;
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n;
+		scanf("%d",&n);
+		if(n==1){puts("FastestFinger");continue;}
+		if(n==2){puts("Ashishgup");continue;}
+		if(n&1){puts("Ashishgup");continue;}
+		int cnt1=0,cnt2=0;
+		while(n%2==0)n/=2,cnt2++;
+		for(int i=3;i*i<=n;i+=2)
+		{
+			while(n%i==0)n/=i,cnt1++;
+		}
+		if(n!=1)cnt1++;
+		if((cnt2>1&&cnt1>0)||cnt1>1)puts("Ashishgup");
+		else puts("FastestFinger");
+	}
+	return 0;
+}
+</code></hidden>
+\\
+====== D. Odd-Even Subsequence ======
+给定一个长度为$n$的数组$a$，可以选择长度为$k$的子序列（重新标号，从$1$开始），请最小化$\min(\max(s_1, s_3, s_5, \ldots), \max(s_2, s_4, s_6, \ldots))$。
+题解：这个长得还挺二分的哦。check某个$\text{mid}$能否成立的时候，分成使得奇数位满足和使得偶数位满足两种，贪心地看能否凑够子序列长度。
+<hidden><code cpp>
+#include<cstdio>
+#include<cstring>
+#include<iostream>
+using namespace std;
+int n,k,a[200005];
+bool check(int x)
+{
+	int j=1;
+	for(int i=1;i<=n;i++)
+	{
+		if((j&1)&&a[i]<=x)j++;
+		else if((j&1)==0)j++;
+		if(j>k)return true;
+	}
+	j=1;
+	for(int i=1;i<=n;i++)
+	{
+		if((j&1)==0&&a[i]<=x)j++;
+		else if(j&1)j++;
+		if(j>k)return true;
+	}
+	return false;
+}
+int main()
+{
+	scanf("%d%d",&n,&k);
+	int l=1000000000,r=1,ans;
+	for(int i=1;i<=n;i++)scanf("%d",&a[i]),l=min(l,a[i]),r=max(r,a[i]);
+	while(l<=r)
+	{
+		int mid=(l+r)>>1;
+		if(check(mid))r=mid-1,ans=mid;
+		else l=mid+1;
+	}
+	printf("%d\n",ans);
+	return 0;
+}
+</code></hidden>
+\\
+====== E. Binary Subsequence Rotation ======
+给出长度为$n$的$01$字符串$s,t$，每次操作可以选一个子序列顺时针旋转，问最少几次从$s$变到$t$。
+题解：能够变换成功当仅当两串为anagram。显然满足$s_i=t_i$的位置是不需要被考虑的。而观察发现剩余位置里每次旋转形如$\mathsf{01010101、101010}$的子序列是最优的，可以贪心地扫一遍详见代码。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e6+10;
+int n,cnt1,cnt2;
+char s[N],t[N];
+int main()
+{
+	scanf("%d%s%s",&n,s,t);
+	for(int i=0;s[i];i++)if(s[i]=='1')cnt1++;
+	for(int i=0;t[i];i++)if(t[i]=='1')cnt2++;
+	if(cnt1!=cnt2)puts("-1");
+	else
+	{
+		int w0=0,w1=0;	//waiting for 0\waiting for 1
+		for(int i=0;s[i];i++)
+		if(s[i]!=t[i])
+		{
+			if(s[i]=='0')
+			{
+				if(w0)w0--;
+				w1++;
+			}
+			else
+			{
+				if(w1)w1--;
+				w0++;
+			}
+		}
+		printf("%d\n",w0+w1);
+	}
+	return 0;
+}
+</code></hidden>
+\\
+====== F. The Hidden Pair ======
+交互。给出一棵$n(2 \le n \le 1000)$个节点的树，对方选定两个节点$s,f$给你猜。你可以做出若干询问，询问给出一个点集$a$，对方会提供点集中到$s,f$距离之和最小的点和这个距离。
+easy version最多$14$问，hard version $11$问。
+题解：我还挺喜欢这个题的，赛时wa了E看这个还挺有思路的，刚刚好写完，结果莫名其妙的wa了就结束了。后来发现是打错了某个地方的变量名，，，
+首先可以想到，询问全部点，距离之和最小的只能是在$s$到$f$路径上，且距离之和是$d_0=dist(s,f)$，于是我们得到一个$sf$链上的点$x_0$。问题数量差不多是$\log n$级别的，于是想到二分。二分得到的$d_0$，每次dfs得到距离$x_0$为$mid$的点集询问，找出最远的使得$d=d_0$的距离及点$x_1$，则$x_1$是距离$x_0$较远一端的端点（得到答案之一）。之后再询问距离$x_1$为$d_0$的点集得到另一个答案$x_2$。
+其间，二分区间如果是$[1,d_0]$可能会在二分过程中消耗$10$个问题，总问题数$12$过不了hard version。可以想到距离链上一点较远的点距离肯定大于链长之半，所以二分$[\frac {d_0} 2,d0]$可以恰控制在$11$次询问内。
+<hidden><code cpp>
+#include<cstdio>
+#include<cstring>
+#include<iostream>
+#include<vector>
+using namespace std;
+int n,head[1005],cnt;
+char s[100];
+vector<int>v;
+struct Node
+{
+	int nxt,to;
+}Edges[5005];
+void addedge(int u,int v)
+{
+	Edges[++cnt].nxt=head[u];
+	head[u]=cnt;
+	Edges[cnt].to=v;
+}
+void dfs(int u,int f,int d)
+{
+	if(d==0){v.push_back(u);return;}
+	for(int i=head[u];~i;i=Edges[i].nxt)
+	{
+		int v=Edges[i].to;
+		if(v!=f)dfs(v,u,d-1);
+	}
+}
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		scanf("%d",&n);
+		memset(head,-1,sizeof(head));
+		cnt=0;
+		for(int i=1;i<n;i++)
+		{
+			int u,v;
+			scanf("%d%d",&u,&v);
+			addedge(u,v),addedge(v,u);
+		}
+		printf("? %d ",n);
+		for(int i=1;i<=n;i++)printf("%d ",i);
+		puts(""),fflush(stdout);
+		int x0,d0,x,d;
+		scanf("%d%d",&x0,&d0);
+		int l=d0/2,r=d0,ans1=x0;
+		while(l<=r)
+		{
+			v.clear();
+			int mid=(l+r)>>1;
+			dfs(x0,0,mid);
+			if(v.size()==0){r=mid-1;continue;}
+			printf("? %d ",v.size());
+			for(int i=0;i<v.size();i++)printf("%d ",v[i]);
+			puts(""),fflush(stdout);
+			scanf("%d%d",&x,&d);
+			if(d==d0)ans1=x,l=mid+1;
+			else r=mid-1;
+		}
+		v.clear();
+		dfs(ans1,0,d0);
+		printf("? %d ",v.size());
+		for(int i=0;i<v.size();i++)printf("%d ",v[i]);
+		puts(""),fflush(stdout);
+		scanf("%d%d",&x,&d);
+		printf("! %d %d\n",ans1,x);
+		cin>>s;
+	}
+	return 0;
+}
+</code></hidden>
+\\

CVBB ACM Team

用户工具

站点工具

差别

页面工具