題目連結：https://codeforces.com/contest/1370
最後的F題卡了半天，不過最後還是找到了問題。補了3.5題~
A - F 題解
-
- A. Maximum GCD
- B. GCD Compression
- C. Number Game
- D. Odd-Even Subsequence
- E. Binary Subsequence Rotation
- F2. The Hidden Pair (Hard Version)
A. Maximum GCD
設 g c d ( a , b ) = k ， a = x k , b = y k ， x 與 y 互 質 設gcd(a,b)=k ，a=xk,b=yk，x與y互質 設gcd(a,b)=k，a=xk,b=yk，x與y互質，想讓k更大的話,x和y要盡量小，x=1，y=2正好是最小的。是以不難發現k=n/2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>
#include<stack>
#include<set>
#include<algorithm>
#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define ROF(i,l,r) for(int i=l;i>=r;i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define r(x) read(x)
#define rr(x,y) read(x);read(y)
#define rrr(x,y,z) read(x);read(y);read(z)
#define sss(str) scanf("%s",str+1)
#define ssf(x) scanf("%lf",&x)
#define aLL(x) x.begin(),x.end()
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pt;
const int N=2e5+5;
const int M=2e3+5;
const int INF=2e9;
const int sz=15;
const int mod=1e9+7;
const double eps = 1e-8;
const double pi= acos(-1);
template<class T>
inline void read(T &x)
{
char c;x=1;
while((c=getchar())<'0'||c>'9') if(c=='-') x=-1;
T res=c-'0';
while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
x*=res;
}
int n,m;
char str[N];
int f[N];
int main()
{
int t;
r(t);
while(t--){
r(n);
cout<<n/2<<endl;
}
return 0;
}
B. GCD Compression
假設有x個奇數，y個偶數。
根據國小的姿勢，奇數+奇數=偶數，偶數+偶數=偶數。
這裡一共有偶數個數，我們隻需要讓奇數和奇數比對，偶數和偶數比對【比對不了的丢掉，多出來的丢一對】就好了
int n,m;
char str[N];
int f[N];
int main()
{
int t;
r(t);
while(t--){
r(n);
vector<int> v1,v2;
FOR(i,1,n*2){
int a;
r(a);
if(a&1) v1.pb(i);
else v2.pb(i);
}
int a=0,b=0,c=v1.size(),d=v2.size();
if(v1.size()%2==0){
if(v1.size()) a=2;
else b=2;
}
else{
c--;
d--;
}
for(int i=a;i<c;i+=2){
cout<<v1[i]<<' '<<v1[i+1]<<endl;
}
for(int i=b;i<d;i+=2){
cout<<v2[i]<<' '<<v2[i+1]<<endl;
}
}
return 0;
}
C. Number Game
找規律。
①：n=1，此時先手必輸
②：n為奇數，此時先手必勝
③：n=2，先手必勝
④：把n質數分解，若含2個及以上的2，和其他質數，那必勝
⑤：隻有一個2，如果其他質數多于1個，必勝，否則必輸
⑥：必輸
int n,m;
char str[N];
int f[N];
int main()
{
int t;
r(t);
while(t--){
r(n);
int a=0;
if(n&1){
if(n==1) cout<<"FastestFinger\n";
else cout<<"Ashishgup\n";
continue;
}
if(n==2){
cout<<"Ashishgup\n";
continue;
}
while(n%2==0){
a++;
n>>=1;
}
if(n>1&&a>=2){
cout<<"Ashishgup\n";
}
else if(n>1&&a>=1){
bool flag=1;
FOR(i,2,sqrt(n)){
if(n%i==0){
flag=0;
break;
}
}
if(!flag) cout<<"Ashishgup\n";
else cout<<"FastestFinger\n";
}
else{
cout<<"FastestFinger\n";
}
}
return 0;
}
D. Odd-Even Subsequence
答案肯定是數組中的一個，二分答案，如果他可以攜帶的序列不少于k個，那肯定可以，再找更小的
【假如說答案在奇數/偶數段】偶數/奇數段随便都可以選，奇數/偶數段的數必須不大于這個答案
int n,m;
char str[N];
int f[N],g[N];
bool check(int x,bool tmp)
{
int ans=0;
FOR(i,1,n){
if(tmp){
ans++;
tmp^=1;
}
else{
if(f[i]<=g[x]){
ans++;
tmp^=1;
}
}
}
return ans>=m;
}
int main()
{
rr(n,m);
FOR(i,1,n){
r(f[i]);
g[i]=f[i];
}
sort(g+1,g+n+1);
int l=1,r=n;
int ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid,1)||check(mid,0)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<g[ans]<<endl;
return 0;
}
E. Binary Subsequence Rotation
這題一直不知道怎麼處理，原來要把串相同的地方去掉，之後就好做了。
剩下的就是0000110100101之類的串，我們每次操作都選擇01010101來消除，這樣消除的就是最大的。
int n,m;
char str1[N],str2[N];
int f[N];
int main()
{
r(n);
sss(str1);
sss(str2);
int a=0,b=0;
FOR(i,1,n){
if(str1[i]=='1') a++;
if(str2[i]=='1') b++;
}
if(a!=b){
cout<<-1<<endl;
return 0;
}
vector<char> v;
FOR(i,1,n){
if(str1[i]!=str2[i]){
v.pb(str1[i]);
}
}
a=b=0;
for(char x:v){
if(x=='1'){
a++;
if(b) b--;
}
else{
b++;
if(a) a--;
}
}
cout<<a+b<<endl;
return 0;
}
F2. The Hidden Pair (Hard Version)
互動題，一開始就有思路。
首先找所有的點，輸出一定是 這條路徑中的一個點 和 這條路徑的長度
然後我們以已知的這個點為根dfs，記錄每層有什麼點。
假設路徑長度為k，答案之一距離根的max肯定大于等于(k+1)/2，我們就先找這個遠的點。
下界為(k+1)/2,上界為k，二分查找即可。
得到這個點之後，再以這個點為根，那麼距離這個點k距離的點集中再查詢一次，即可得到另一個點
int n,m;
char str[N];
int f[M];
vector<int> v[M],lvl[M],tmp;
pt query(vector<int> &tt)
{
if(!tt.size()) return mp(-1,-1);
cout<<"? "<<tt.size();
for(int x:tt) cout<<" "<<x;
cout<<endl;
int a,b;
cin>>a>>b;
return mp(a,b);
}
void dfs(int x,int fa,int dep)
{
m=max(m,dep);
lvl[dep].pb(x);
for(int y:v[x]){
if(y!=fa){
dfs(y,x,dep+1);
}
}
}
int main()
{
int t;r(t);
while(t--){
r(n);
m=0;
tmp.clear();
lvl[0].clear();
FOR(i,1,n){
v[i].clear();
lvl[i].clear();
tmp.pb(i);
}
FOR(i,1,n-1){
int a,b;rr(a,b);
v[a].pb(b);
v[b].pb(a);
}
pt res=query(tmp);
int root=res.fi,dep=res.se;
dfs(root,0,0);
int l=(dep+1)/2,r=min(m,dep),ans1;
while(l<=r){
int mid=l+r>>1;
res=query(lvl[mid]);
if(res.se==dep){
ans1=res.fi;
l=mid+1;
}
else r=mid-1;
}
FOR(i,0,n) lvl[i].clear();
dfs(ans1,0,0);
res=query(lvl[dep]);
cout<<"! "<<ans1<<' '<<res.fi<<endl;
string s;
cin>>s;
}
return 0;
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)