Codeforces Round #651 (Div. 2) / contest 1370dragonylee的博客-e. binary subsequence rotation

A	B	C	D	E	F
√	√	√	√	√	○

（ √：做出； ●：尝试未做出； ○：已补题 ）

题目地址：https://codeforces.com/contest/1370

A Maximum GCD

题意：

思路：

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } int main() { //freopen("input.txt","r",stdin); int t=read(); while(t--) { int n=read(); printf("%dn",n/2); } return 0; } 

B GCD Compression

题意：数组 a 的大小为 2n，先把 a 丢弃两个元素，然后每次从 a 中选出两个元素，求和之后加入数组 b 中，最后数组 b 是一个大小为 n-1 的数组，要求选取方案，使得最后数组 b 所有元素的 gcd>1 。

思路：显然最后的 gcd 等于 2 。我们记录 a 中奇数和偶数的个数，然后处理一下保证最后奇数个数为偶数就行了。

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } const int maxn=2005; int a[maxn]; int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) { int n=read();         VI x[2]; REP(i,1,n<<1) a[i]=read(),x[a[i]&1].push_back(i); if(x[1].size()&1) {             x[1].pop_back();             x[0].pop_back(); } else { if(x[1].size()>0) x[1].pop_back(),x[1].pop_back(); else x[0].pop_back(),x[0].pop_back(); } for(int i=0;i<x[0].size();i+=2) printf("%d %dn",x[0][i],x[0][i+1]); for(int i=0;i<x[1].size();i+=2) printf("%d %dn",x[1][i],x[1][i+1]); } return 0; } 

C Number Game

题意：给定一个正整数 n，有两种操作：（1）用 n 的一个大于 1 的奇因子除 n；（2）如果 n>1 将 n 减 1。两个人玩游戏，每次每个人可以选择一个操作，最后谁不能操作谁就输。问谁会赢。

思路：先处理 n=1 的特殊情况。然后如果 n 为奇数，那么先手必胜；否则，考虑这个 n 是否存在奇因子，如果不存在那么只能减 1 然后就后手必胜（这里有个特殊情况 2），如果存在奇因子还要再分情况讨论：如果这个 n 可以被 4 整除（也就是说除掉所有奇因子之后剩下的不是 2，如果剩下 2 那就别人赢了），那么我就可以一次性除掉所有奇因子，如果不能被 4 整除（也就是说除了所有奇因子只剩下 2），那么我的最优方案就是除得还剩一个奇因子，这时候就要看是否存在多于 1 个奇因子。

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } int get(int n) { int maxx=0; for(int i=2;i*i<=n;i++) if(n%i==0) { if(i&1) maxx=max(maxx,i); if((n/i)&1) maxx=max(maxx,n/i); } return maxx; } int f(int n) { int ret=0;     n>>=1; for(int i=2;i*i<=n;i++) if(n%i==0) ret++,n/=i,i=1; if(n>1) ret++; return ret; } int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) { int n=read(); if(n==1) puts("FastestFinger"); else if(n&1) puts("Ashishgup"); else { int x=get(n); if(!x) puts(n>2?"FastestFinger":"Ashishgup"); else { if(n%4==0) puts("Ashishgup"); else { int t=f(n); puts(t>1?"Ashishgup":"FastestFinger"); } } } } return 0; } 

D Odd-Even Subsequence

题意：给出一个数组 a，从中选取一个子序列 s，使得
$min{max(s_1,s_3,s_5,…),max(s_2,s_4,s_6,…)}$

min{max(s1​,s3​,s5​,...),max(s2​,s4​,s6​,...)} 这个数尽可能小，并求出这个最小值。

思路：二分答案。对于一个最大值限定 x，分别计算奇子序列最大值不超过 x 和偶子序列最大值不超过 x 能不能有选取方案，如果其中一个有那么 x 就可行。选取的时候要求的子序列每次要找下一个不大于 x 的元素，而不要求的子序列最优方案就是紧跟着要求的元素选取就行了。

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } const int maxn=2e5+5; int n,k,a[maxn]; bool can(int x) { int j=1,tot=0; for(int i=1;i<=k && j<=n;i++) { if(i&1) { while(j<=n && a[j]>x) j++; if(j>n) break;             tot++; j++; } else tot++,j++; } if(tot>=k) return 1;      j=1,tot=0; for(int i=1;i<=k && j<=n;i++) { if(i&1) tot++,j++; else { while(j<=n && a[j]>x) j++; if(j>n) break;             tot++; j++; } } if(tot>=k) return 1; return 0; } int main() { //freopen("input.txt","r",stdin);     n=read(),k=read(); REP(i,1,n) a[i]=read(); int l=0,r=1e9+5,mid; while(l<r-1) {         mid=(l+r)>>1; if(can(mid)) r=mid; else l=mid; }     cout<<r; return 0; } 

E Binary Subsequence Rotation

题意：给定两个仅由 01 构成的字符串 s 和 t，对 s 进行操作，每次可以选取一个子序列，然后把这个子序列所有元素向右移一格（最右边的跑到最左边来），问至少操作多少次，使得 s 变成 t 。

思路：原本 s[i]==t[i] 的可以不考虑，我们把不相等的拎出来。可以发现，如果一次性把其中的若干个通过这样的平移变成相同了，那么原本肯定是 01 交替的形式，也就是说假设 (s[i]=1 && t[i]=0) 这种情况设为 1，(s[i]=0 && t[i]=1) 这种情况设为 0，那么可以一次性平移全部满足的选取方案一定是 01 交替选取的，那么我们实际上只用从前往后遍历，然后维护若干个队列的末尾中 0 有多少个 1 有多少个就行了。

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } const int maxn=1e6+5; char s[maxn],t[maxn]; int a[maxn],tot; int main() { //freopen("input.txt","r",stdin); int n=read(); scanf("%s %s",s+1,t+1); int s1=0,t1=0; REP(i,1,n) s1+=s[i]-'0',t1+=t[i]-'0'; if(s1!=t1) return puts("-1"),0; REP(i,1,n) if(s[i]!=t[i]) a[++tot]=s[i]-'0'; int ans=0,num[2]={0}; REP(i,1,tot) { if(!num[a[i]^1]) ans++,num[a[i]]++; else num[a[i]^1]--,num[a[i]]++; }     cout<<ans; return 0; } 

F The Hidden Pair

题意：交互题。给出一棵树，有两个隐藏节点 u 和 v，每次询问给出一个点集 S，系统会返回两个数 x 和 y，其中
$xin S$

x∈S 并且
$dist(u,x)+dist(v,x)=y$

dist(u,x)+dist(v,x)=y 是点集 S 中对应距离之和最小的。easy version可以询问 14 次，hard version可以询问 11 次。最后目标是找出这两个隐藏节点。

思路：（比赛时的思路，不过没过）（1）询问所有结点得到 dist(u, v)=D0 ；（2）询问 1 号结点得到 d(u)+d(v)=D1 为 u 和 v 的深度之和；（3）二分搜索出 u 和 v 中更深的那个的深度 d1，这里可以二分搜索是因为我们假设 u 和 v 的深度分别为 d1 和 d2，那么对于深度大于 d1（假设 d1 更大）的所有结点询问之后得到的距离一定比 D0 大，而对于深度处于 d2 和 d1 之间的结点询问之后的距离一定等于 D0，这里二分搜索时最初的左边界为 (D1+1)/2，就保证不会搜到比 d2 浅的地方去，二分搜索时询问所有深度等于 mid 的结点；（4）现在就知道 d1 和 d2 了，根据 d2+D0 是否等于 d1 可以判断 u 和 v 是否具有祖先关系，如果有祖先关系只用再询问一次更深的然后找祖先，否则要询问两次（一次深的，一次除了深的那个的祖先之外浅的深度的所有结点）。

我自己觉得挺有道理的，可惜没过……

（补题）思路大致没问题，就是多组数据忘记更新 maxd 了（T_T)，以及有一些地方可以优化，比如得到 D0 的时候就可以把那个点当做根结点，这样就方便很多。

代码通过了 easy version 没有通过 hard version，询问次数最多 12 次，可能是我二分查找这种写法不太好吧。

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } typedef pair<int,int> P; P query(VI x) { printf("? %d ",x.size()); for(int i:x) printf("%d ",i); puts(""); fflush(stdout); int a=read(),b=read(); return P(a,b); } const int maxn=1005; VI G[maxn],nd[maxn]; int n,d[maxn],f[maxn],maxd; char tem[maxn]; void dfs(int u,int fa,int de) {     d[u]=de; f[u]=fa; nd[de].push_back(u);     maxd=max(maxd,de); for(int i:G[u]) if(i!=fa) dfs(i,u,de+1); } bool zuxian(int u,int v) { while(d[v]>d[u]) v=f[v]; return u==v; } int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) {         n=read(); REP(i,0,n) G[i].clear(),nd[i].clear();         maxd=0; mem(d,0); mem(f,0); REP(i,1,n-1) { int u=read(),v=read();             G[u].push_back(v); G[v].push_back(u); }         VI g; REP(i,1,n) g.push_back(i);         P p=query(g); int D0=p.second,root=p.first; dfs(root,0,0); int l=(D0+1)/2,r=min(maxd+1,D0+1),mid; while(l<r-1) {             mid=(l+r)>>1; if(query(nd[mid]).second==D0) l=mid; else r=mid; } int u=query(nd[l]).first; int d2=D0-l; int v; if(D0==l) {             v=root; } else {             g.clear(); for(int i:nd[d2]) if(!zuxian(i,u)) g.push_back(i);             v=query(g).first; } printf("! %d %dn",u,v); fflush(stdout); scanf("%s",tem); } return 0; }