#33468: 不用map、bitset的作法(C++)


eason9506@gmail.com (Eason Huang)

學校 : 不指定學校
編號 : 197870
來源 : [1.200.161.211]
最後登入時間 :
2023-06-10 19:02:08
e288. 互補CP -- APCS | From: [1.200.66.217] | 發表日期 : 2023-01-07 22:27

1.把字母轉成編號:

  不能直接 減'A',因為會有小寫字母,在ascii碼上它們不是連續編號的,應該判斷大小寫,大寫則可以直接 減'A',小寫則 減'a'後再加26。

2. 二進制與位元運算:

  有了字母編號後,就可以把一組CP轉化成二進制存進int了!先用bool陣列解釋會比較方便。

  bool have[38]={0};

  have[idx]=1; idx是字母轉成的編號,這就代表這組CP有idx這個字母,而要換成int表達的話,就需要用到位元運算

  CP_num += (1LL<<idx); 1LL就是1,只不過是long long 的型態,一定要記得 LL 不然會溢位

  然而這樣子如果CP的字母有重複的話,就會導致CP_num的二進制中 idx的位置進位而變成0

  因此要避免重複加值的話,就改成 bitwise or

  CP_num |= (1LL<<idx); 這樣就能避免重複加值了

  而要找互補CP的方法就是用 bitwise xor

  注意到如果兩個CP是互補的,則他們的 bitwise xor 的二進制就會是 111... m個1

  而根據 bitwise xor 的性質 ( a^b=c,則 a^c=b ,^是bitwise xor在程式中的符號)

  所以 a 的互補CP就是 (111... m個1) ^ a

  而 111... m個1 最快速的生成方法就是 (1LL<<m) - 1

  這是二進制的特性,m個1代表在十進位中這個數字的值是 2**0 + 2**1 + 2**2 + ... + 2**(m-1) (**是次方的意思)

  可以很容易的用等比級數公式證明 m個1就會等於 2**m-1

3. 排序與二分搜

  將每個CP_num存進一個陣列裡,再sort這個陣列(為了二分搜)

  最後 ans += upper_bound( arr, arr+n, arr[i]^( (1LL<<m) - 1) ) - lower_bound( arr, arr+n, arr[i]^( (1LL<<m) - 1) )

  把每個arr[i]有幾個互補CP加進ans,因為每組會重複算到一次,所以答案是 ans>>1

 
#40763: Re: 不用map、bitset的作法(C++)


wubaie (小億)

學校 : 不指定學校
編號 : 123253
來源 : [61.228.45.62]
最後登入時間 :
2024-11-23 14:59:02
e288. 互補CP -- APCS | From: [220.133.154.226] | 發表日期 : 2024-06-11 22:16

1.把字母轉成編號:

  不能直接 減'A',因為會有小寫字母,在ascii碼上它們不是連續編號的,應該判斷大小寫,大寫則可以直接 減'A',小寫則 減'a'後再加26。

2. 二進制與位元運算:

  有了字母編號後,就可以把一組CP轉化成二進制存進int了!先用bool陣列解釋會比較方便。

  bool have[38]={0};

  have[idx]=1; idx是字母轉成的編號,這就代表這組CP有idx這個字母,而要換成int表達的話,就需要用到位元運算

  CP_num += (1LL<

  然而這樣子如果CP的字母有重複的話,就會導致CP_num的二進制中 idx的位置進位而變成0

  因此要避免重複加值的話,就改成 bitwise or

  CP_num |= (1LL<

  而要找互補CP的方法就是用 bitwise xor

  注意到如果兩個CP是互補的,則他們的 bitwise xor 的二進制就會是 111... m個1

  而根據 bitwise xor 的性質 ( a^b=c,則 a^c=b ,^是bitwise xor在程式中的符號)

  所以 a 的互補CP就是 (111... m個1) ^ a

  而 111... m個1 最快速的生成方法就是 (1LL<

  這是二進制的特性,m個1代表在十進位中這個數字的值是 2**0 + 2**1 + 2**2 + ... + 2**(m-1) (**是次方的意思)

  可以很容易的用等比級數公式證明 m個1就會等於 2**m-1

3. 排序與二分搜

  將每個CP_num存進一個陣列裡,再sort這個陣列(為了二分搜)

  最後 ans += upper_bound( arr, arr+n, arr[i]^( (1LL<

  把每個arr[i]有幾個互補CP加進ans,因為每組會重複算到一次,所以答案是 ans>>1

最後一步可以不用二分搜,用雙指針,
while( i<j ) { 
    y = (1LL << m) - 1 - x ;
    i由前往後先統計x值個數a;
    j由後往前統計y值個數b;
    ans += a*b;
}

 
ZeroJudge Forum