NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組初賽
 G.A|B Problem

作者 主題: G.A|B Problem  (閱讀 157 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
G.A|B Problem
« 於: 十月 17, 2018, 02:39:55 pm »

這題要以二進位來思考,
假設 A=100100010,
則滿足 A+B=A|B 條件的 B,
在 A 中為 1 的位元必定為 0,
也就是 B=0xx0xxx0x,
其中的 x 可為 0 或 1,
因此只要數一下 A 裡面有幾個位元是 0,
算出 2 的次方就可以得到答案。

但是題目又規定 B <=X ,
所以我們要將 X 分段處理,
假設 X=1001000100,
先找出最左邊第一個出現的 1 為 1000000000,
分出第一段數字 xxxxxxxxx,(不含上面的數)
也就是 0 ~ 111111111 (1000000000-1),
再用這一段去找有幾個位元在 A 中是 0。
接下來再找出第二個出現的 1 為 1000000,
而第二段數字為 1000xxxxxx,
也就是 1000000000 ~ 1000111111 (1001000000-1),
數字的最前面固定是 1000,
一樣找出後面的位元有幾個在 A 中是 0。
要注意的是,如果這個位元在 X 和在 A 中同時為 1,
則後面就不會再有答案,必須中斷。

再來,因為這個做法只能處理到 X-1,
所以 X 要另外處理。
最後,因為題目要求要正整數,
但這個做法會包含 0,
所以答案要再減一。

核心程式碼:
代碼: [選擇]
for (bit=(1<<30), ans=0; bit; bit>>=1)
{
    if ((bit&x)==0) continue;
    for (bit2=(bit>>1), c=0; bit2; bit2>>=1)
        if ((bit2&a)==0) c++;
    ans+=A[c];
    if (bit&a) break;
}
if ((a|x)==(a+x)) ans++;
printf("%d\n", ans-1);
PS. A[ i ] 為 2i, 可在程式一開始先算出它們的值。
« 上次編輯: 十月 17, 2018, 09:30:04 pm 由 sagit »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組初賽
 G.A|B Problem