P4424 HNOI AHOI2018 尋寶遊戲

2022-09-22 19:52:19 字數 1717 閱讀 9746

p4424 [hnoi/ahoi2018]尋寶遊戲

太nt了,直接去想dp了,啥都沒做出來,三十分滾了。

可以發現 \(x | 1 = 1\),\(x \& 0 = 0\),\(x \& 1 = x\),\(x | 0 = x\)。那麼我們可以把操作序列看作是 \(01\) 串。 \(\& \rightarrow 1\),\(| \rightarrow 0\) 那麼當操作序列和數字序列相等時,答案不變,恆為初始值。那麼我們可以按位拆開來算,第 \(n\) 行 \(j\) 位為最高位,一共 \(n\) 位 \(m\) 個數字。合併不等式範圍。

設操作序列為 \(op\),數字序列為 \(x\)。

當 \(op \lt x\) 那麼答案為 \(0\) 考慮他們是第 \(i\) 位產生不同且 \(op_i \lt x_i\) 所以 \(op_i = 0,x_i = 1\) 也就是 \(|1\) 所以最後一個必為 \(1\),對於 \(i+1 \text n\) 位因為相等,所以不影響答案。

當 \(op \gt x\) 那麼答案為 \(1\) 考慮他們是第 \(i\) 位產生不同且 \(op_i \gt x_i\) 所以 \(op_i = 1, x_i = 0\) 也就是 \(\&0\) 所以最後一個必為 \(0\),對於 \(i+1\textn\) 位因為相等,所以不影響答案。

\[\begin

upper\_bound = min_\ \\

lower\_bound = max_\

\end

\]所以對於詢問串 \(q\) ,如果 \(q_i = 0\) 限定了 \(op\) 的上界,\(q_i=1\) 限定了 \(op\) 的下界。所以用最小的上界減去最大的下界就完了。注意當上屆位 \(rk[m+1]\) 時,答案要加 \(1\)。具體看**。

/*

name:

author: gensokyo_alice

date:

description:

*/#include #include #include #include #include #include #include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = (1ll << 20) + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9+7;

ll n, m, q, rk[maxn], ord[maxn], pw[maxn];

string str, now[maxn];

bool cmp(ll x, ll y)

ll calc(ll x, ll y)

int main() for (ll i = 1; i <= m; i++) reverse(now[i].begin(), now[i].end());

for (ll i = 1; i <= n; i++) now[0] += '0', now[m+1] += '1';

for (ll i = 1; i <= m+1; i++) ord[i] = i;

sort(ord+1, ord+m+1, cmp); for (ll i = 1; i <= m; i++) rk[ord[i]] = i; //, cout << rk[i] << endl;

while (q--)

return 0;

}

HNOI AHOI2018

luogu loj首先我們可以把題意轉化為圖的獨立集計數。顯然這個東西是個np hard的。 然後我們可以注意到 m le n 10 ,也就...

HNOI AHOI2018 毒瘤

思路非常精妙的一道虛樹題 簡單題意 給一張圖,求這張圖上的獨立集數量 對於一棵樹的情況,可以設 dp 表示節點 u 選 不選的方案數 顯然有...

HNOI AHOI2018 道路

嘟嘟嘟 雖然題面很長,但是靜下心來看完後,還是掩蓋不了這是一道水體的事實。 發現這是一棵完全二叉樹,而且深度只有40。 那麼dp u l r 表示到達節點u,有 l 條公路,r條鐵路沒修。轉移方程就是分兩種情況遞迴下去就行啦。 然後中間節點只是用來記錄答案的,在葉節點計算。 據說這道題卡空間,但是我...