Codeforces Round #683 (by Meet IT) DIV1 C問題/DIV2 E問題 - Xor Tree

Source

Codeforces Round #683 (by Meet IT) DIV1 C問題 (1250pt)
Codeforces Round #683 (by Meet IT) DIV2 E問題 (2250pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201115-2）のコード

C++に変換後のコードはこちら

//no-unlocked
int N, A[2d5];
int cnt[2d5];

int solve(int N, int A[], int cnt[]){
  int i, j, k, tmp = 0, res = 0;
  
  rep(i,N){
    cnt[i] = 0;
    rep(j,31) if(BIT_ith(A[i],j)) cnt[i] = j+1;
  }

  i = j = 0;
  while(i < N){
    while(j < N && cnt[i] == cnt[j]) j++;
    if(j - i > 1){
      rep(k,i,j) A[k] ^= (1<<(cnt[i]-1));
      res >?= solve(j-i, A+i, cnt+i) + tmp + if[j < N, 1, 0];
    }
    tmp++;
    i = j;
  }

  return max(tmp, res);
}

{
  int res;
  rd(N,A(N));
  rsortA(N,A);
  res = solve(N, A, cnt);
  wt(N-res);
}

Current time: 2024年04月18日11時24分38秒
Last modified: 2020年11月16日03時02分32秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF683 CF_DIV1_C CF_DIV2_E
トップページに戻る

Logged in as: unknown user (not login)