Codeforces Round #651 (Div. 2)题解

Problem B

是这样，原来的数组是偶数长度，所以要么有偶数个奇数和偶数个偶数组成，要么奇数偶数都是奇数个，要求gcd不等于1，那么我们求gcd等于2就好了。直接暴力存奇数偶数，然后输出就好了。

Problem C

首先我们特判1和2，然后如果先手面临奇数的情况，先手必胜，如果是没有奇数因子的偶数，后手必赢，一个数必然可以拆分成为若干个奇数因子和偶数因子相乘，那么此时如果我把所有奇数因子全部除掉，就形成了没有奇数因子的偶数，那么先手必胜，这里要判断一下是否这个偶数因子是2.

代码实现

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005 
#define fi first 
#define se second
#define pb push_back
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
    char ch=getchar(); int x=0, f=1;
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    } while('0'<=ch&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}


int main () { 
  int t;
  scanf ("%d",&t);
  while (t--) {
      int n;
      scanf ("%d",&n);
      if (n==1) printf ("FastestFinger
");
      else if (n==2) printf ("Ashishgup
");
      else if (n%2==1) printf ("Ashishgup
");
      else {
          int flag=0;
          for (int i=2;i*i<=n;i++) {
              if (n%i!=0) continue;
              if (i%2==1&&(n/i)!=2) flag=1;
              if ((n/i)%2==1&&i!=2) flag=1;
          }
          if (flag) printf ("Ashishgup
");
          else printf ("FastestFinger
");
      }
  }
  return 0;
}

Problem D

一道二分的题目，看到最大值最小的话，应该就可以想到了吧，那么我们二分mid，看在奇数和偶数位置上是不是可以小于mid，记下答案就好了。

代码实现

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005 
#define fi first 
#define se second
#define pb push_back
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
    char ch=getchar(); int x=0, f=1;
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    } while('0'<=ch&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}

VI a;

bool check (int x,int flag,int k) {
    rev (i,0,a.size ()) {
        if (k!=0) {
            if (flag) k--,flag^=1;
            else {
                if (a[i]<=x) k--,flag^=1;
            }
        }
    }
    return k==0;
}

int main () { 
  int n,k;
  scanf ("%d %d",&n,&k);
  a.resize (n);
  rev (i,0,n) scanf ("%d",&a[i]);
  int l=1,r=inf;
  int ans;
  while (l<r) {
      int mid=(l+r)>>1;
      if (check (mid,1,k)||check (mid,0,k)) {
          ans=mid;
          r=mid;
      }
      else l=mid+1;
  }
  printf ("%d
",ans);
  return 0; 
}