Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/526-585cc3b0
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 2150 - Counting Subsequences [SUBSEQ] (この記事を編集する[管理者用])

Source

IPSC 2006
SPOJ 2150 [SUBSEQ]

問題概要

長さnの整数列が与えられるので,その連続する部分列で和が47になるものの数を求める問題.
問題文には書かれていないが,nの最大値は数十万~百万程度の様子.

解法

最初から和を計算していって,同時に 和-47 の値が今まで出てきた回数を足していけば答えになるはず.

C言語によるスパゲッティなコード
#include<stdio.h>
#include<string.h>

int UINT_HASH_SIZE;
unsigned uint_hash_n[2000000]; int uint_hash_d[2000000];

void uintHashClear(){
  memset(uint_hash_d,0,UINT_HASH_SIZE*sizeof(int));
}

int uintHashFunction(unsigned a){
  return (a*1007)%UINT_HASH_SIZE;
}

int uintHashGet(unsigned a){
  int i=uintHashFunction(a);
  for(;;){
    if(uint_hash_n[i]==a && uint_hash_d[i]) break;
    if(!uint_hash_d[i]) break;
    i++; if(i==UINT_HASH_SIZE) i=0;
  }
  if(uint_hash_n[i]!=a) return 0; return uint_hash_d[i];
}

int uintHashIncrease(unsigned a){
  int i=uintHashFunction(a);
  for(;;){
    if(uint_hash_n[i]==a && uint_hash_d[i]) break;
    if(!uint_hash_d[i]) break;
    i++; if(i==UINT_HASH_SIZE) i=0;
  }
  uint_hash_n[i]=a; return ++uint_hash_d[i];
}

int main(){
  int k,n,res,size;
  unsigned sum;

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    UINT_HASH_SIZE=n*2; uintHashClear();
    res=0; sum=0; uintHashIncrease(0);
    while(n--){
      scanf("%d",&k); sum+=k;
      res+=uintHashGet(sum-47); uintHashIncrease(sum);
    }
    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/526-585cc3b0
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。