Codeforces Round #150 DIV1 A問題/DIV2 C問題 - The Brand New Function

Source

Codeforces Round #150 DIV1 A問題 (500pt)
Codeforces Round #150 DIV2 C問題 (1500pt)
Problem description

問題概要

$N$ 要素の正整数からなる配列 $\{A_i\}_{i=1}^N$ が与えられる．
$1 \leq l \leq r \leq N$ に対して，$f(l,r) = A_l | A_{l+1} | \cdots | A_{r}$ の取りうる値は何通りあるかを求める問題．
演算 $|$ はビットごとにORを取るもの．

解法

左端 $l$ を固定して考えると，右端が右に行くにつれて，$f(l,r)$ の値が増えるのはたかだか $20$ 回以下．
各場所について，そこより右で，$i$ 番目のビットが立っている最も左の要素を覚えておくと，次増える場所が $O(1)$ で計算できて，全体で $O(N \log A_i)$ 程度でできる．
他にもいろいろ方法はあって，$r$ を固定して，$f(l,r)$ の取りうる値を全部記憶して，そこから $f(l,r+1)$ の取りうる値を全部計算とかでも，
$f(l,r)$ の $r$ を固定した時の取りうる値の数は $20$ を超えないので同様の計算量で間に合う．
$f(l,r)$ の値はそんなに大きくならない（たかだか$2^{20}$）ので，
　$\verb|array[k]| = 1$ ($f(l,r)=k$ が現れた), $0$ (現れていない)
という配列を作るか，setに突っ込んでいって現れた数を覚えておくと楽．

C言語のスパゲッティなコード

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}

int in[200000], next[200000][20];
int ap[3000000];

int main(){
  int i,j,k,l,m,n,b;

  scanf("%d",&n);
  rep(i,n) scanf("%d",in+i);

  rep(i,3000000) ap[i] = 0;

  rep(j,20) next[n-1][j] = -1;
  for(i=n-2;i>=0;i--){
    rep(j,20) next[i][j] = next[i+1][j];
    rep(j,20) if(in[i+1]&(1<<j)) next[i][j] = i+1;
  }

  rep(i,n){
    k = in[i];
    ap[k]=1;
    j = i;
    for(;;){
      m = 1000000000;
      rep(b,20) if(!(k&1<<b)) if(next[j][b]!=-1 && m > next[j][b]) m = next[j][b];
      if(m==1000000000) break;
      j = m;
      k |= in[j];
      ap[k]=1;
    }
  }

  k = 0;
  rep(i,3000000) k += ap[i];
  printf("%d\n",k);

  return 0;
}

Current time: 2024年04月20日19時42分43秒
Last modified: 2014年03月29日19時34分40秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF150 CF_Div1_A CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：