精品欧美日韩中文字幕在线,欧美日韩精品综合久久,久久久精品人妻一区二区三区四

題目列表

C. Brave Seekers of Unicorns
D. Bank Security Unification
G. Biological Software Utilities
I. Binary Supersonic Utahraptors
J. Burnished Security Updates
M. Brilliant Sequence of Umbrellas
N. Best Solution Unknown

C. Brave Seekers of Unicorns題目給出了一個(gè)$unicorn$序列的定義，暫且叫它完美序列，完美序列滿足如下條件：

非空遞增且序列元素的值域?yàn)?$[1,n]$
沒有三個(gè)連續(xù)的元素異或和 $=0$

給定一個(gè)整數(shù)n，對(duì)完美序列計(jì)數(shù)（需要求出完美序列個(gè)數(shù)），答案需要對(duì) $998244353$ 取模

Solution設(shè) $dp_i$ 表示以$i$ 結(jié)尾的數(shù)組的方案數(shù)即
\[dp[i]= \sum\limits_{j=1}^{i-1} (dp[j]-dp[i \bigoplus j]) (i?j<j)\]求出等于 $i\oplus j$ 的數(shù)去掉同時(shí)維護(hù)前綴和，對(duì)于二進(jìn)制下的 $i$ ,如果第 $x$ 位為 $1$，那么$ [2x,2{x+1}-1]$之間的數(shù)都是(除了最高位的$1$除外)，解釋來說，因?yàn)橐紤]$i⊕j⊕k=0 $的情況，根據(jù)異或的性質(zhì)$i,j,k$三個(gè)數(shù)的每一個(gè)二進(jìn)制數(shù)位上最多只有兩個(gè)$1$，那就枚舉$i$的除最高位的二進(jìn)制位為$1$ 的數(shù)位 $x$，固定 $j$ 的第$x$位是也是$1$,此時(shí)$k$ 的第 $x $位為必然為$0$，那么第$x$ 位往后都可以隨便亂取,不會(huì)有影響,也就是$k$的范圍是$[2^x,2^{x+1}-1]$

Code

ll dp[N],f[N],n;void solve() {cin >> n;for (int i = 1; i <= n; ++i) {f[i] = dp[i - 1] + 1;int num = i, bit = 0;while (num) {if ((num & 1) && num != 1) {//此時(shí)i的位上是1f[i] = (f[i] - dp[min(ksm(2, bit + 1) - 1, (ll) i)] + dp[min(ksm(2, bit) - 1, (ll) i)] + mod) % mod;}num >>= 1;bit++;}dp[i] = (dp[i - 1] + f[i]) % mod;}cout << dp[n] << endl;}

D. Bank Security Unification題意：有 $n$個(gè)路由器，第 $i$ 個(gè)路由器的的頻度是 $f_i$, 你選擇任意個(gè)路由器打開，假設(shè)打開$k$了個(gè)路由器 $i_1 , i_2 , … , i_ k$,，則此時(shí)的網(wǎng)絡(luò)安全系數(shù)的值是 $∑ _{i=1}^{k-1}a_i\oplus a_{i+1}$,輸出網(wǎng)絡(luò)安全系數(shù)的最大值是多少，反之就是說從一個(gè)長(zhǎng)度為 $n$ 序列 $a$ 中取出一個(gè)子序列，使得相鄰兩個(gè)元素的按位與值的和最大。求出這個(gè)最大的和

Solution首先我們希望按位與和最大，就是在希望我們選取的相鄰兩個(gè)元素的二進(jìn)制位盡可能相同，顯然$dp[i][j]$表示當(dāng)前在$i$位置，打開$j$ 個(gè)路由器的最大按位與值（安全系數(shù)），但是此時(shí)暴力轉(zhuǎn)移的$dp$是$O(n^2)$ 的，而且$n=1e6$顯然也開不了二維的$dp$數(shù)組，那么可以選擇優(yōu)化，讓$dp_i$表示當(dāng)前最后一位為 $i$ 的子序列答案最大是多少，如果考慮當(dāng)前的一位，顯然是與之二進(jìn)制相同的位是貢獻(xiàn)最大的，所以記錄 $lst[i][0/1] $表示二進(jìn)制第 $i$ 位上一個(gè)是$ 0/1$ 最近的位置在哪里，每次只從對(duì)應(yīng)的$lst$ 轉(zhuǎn)移而來,然后每次取更新$lst$的值

Code

ll n;ll f[N],dp[N],bit[66][2];void solve() {cin >> n;ll mx_bit = 0;for (int i = 1; i <= n; ++i) {cin >> f[i];mx_bit = max(mx_bit, f[i]);}mx_bit = ceil(log2(mx_bit)) + 1;// dbg(mx_bit);for (int i = 1; i <= n; ++i) {//貪心取最近的相同的二進(jìn)制位if (i > 1) {for (int j = 0; j<=mx_bit; ++j) {int tmp = ((f[i] & (1ll << j)) > 0);int pos = bit[j][tmp];//最近的每位二進(jìn)制&相同的位置dp[i] = max(dp[i], dp[pos] + (f[pos] & f[i]));}}// dbg(dp[i]);for (int j = 0; j <= mx_bit; ++j) {//更新bit[j][((f[i] & (1ll << j)) > 0)] = i;}}ll ans = 0;for (int i = 1; i <= n; ++i) {ans = max(ans, dp[i]);}cout << ans << endl; }

G. Biological Software Utilities給出一種好樹的定義，刪除掉一些邊后能變成兩兩匹配的樹是好樹 ?，F(xiàn)在給出節(jié)點(diǎn)的個(gè)數(shù)，求好樹有多少種

Solution考慮到樹的形狀沒有定，且也不知道刪除哪一些點(diǎn)，但是發(fā)現(xiàn)最后的情況一定是兩兩匹配的，那么倒過來想就是把很多兩兩匹配完的點(diǎn)，通過連一些邊變成一些樹。首先把 $2n$ 個(gè)點(diǎn)分成 $n$ 個(gè)兩兩相同的組合的總共情況是