Question 1. 「2024 “釘耙編程” Round.1」I. 數位的關系

給定偏序關系限制串 \(R\)，滿足 \(R\) 中僅含 < 與 > 且長度為 \(m\)，稱一數字串 \(S\) 滿足 \(R\) 的限制，當且僅當：

• \(S\) 的長度為 \(m+1\)。
• 對于任意的 \(i\in [1,m]\)，若 \(R_i\) 為 < 則 \(S_i < S_{i+1}\)，若 \(R_i\) 為 > 則 \(S_i > S_{i+1}\)。

給定一數字串 \(T\)，令 \(f(T,R)\) 表示 \(T\) 中滿足 \(R\) 的限制的（不要求連續(xù)的）子序列的數量。

設 \(I(x)\) 表示將正整數 \(x\) 視作一個不含前導 \(0\) 的數字串，多次給定 \(l,r,R\)，求：

\(T\leq 10, 1\leq l\leq r < 10^{500}, |R|\leq 500\)

感謝我同學 cyj 告訴我怎么寫不那么史。

首先這個看起來很像數位 DP，套路性拆成 \([1,r] - [1,l] + \text{calc}(l)\)，如果你是高精度大神，歡迎挑戰(zhàn)寫 \([1,r] - [1,l-1]\) 版本。

考慮如何搞定后面的 \(\text{calc}(l)\)，不妨考慮直接 DP，令 \(m = |R|\) 則顯然需要 \((m+1)\) 個數，設 \(f_{i,j,x}\) 表示考慮了前 \(i\) 位，拿了 \(j\) 個數丟進滿足 \(R\) 的子序列，最后一次丟了 \(x\)，為了方便，當 \(j = 0\) 的時候僅認為 \(x = 0\) 是合法的。

轉移容易，考慮這一位用不用，如果用，設這一位為 \(x\)，枚舉上一個丟進去的數 \(y\)，考慮 \((y,x)\) 是否滿足當前要求的偏序關系，如果可以，則 \(f_{i,j,x}\gets f_{i-1,j-1,y}\)。

不用的話，則 \(f_{i,j,x}\gets f_{i-1,j,x}\)，初值為 \(f_{0,0,0} = 1\)。

接下來考慮計算 \([1,r]\) 的答案，根據數位 DP 的套路很顯然是會有一個位，在這個位沒有卡滿，同時導致之后的位在 \([0,9]\) 內任意，枚舉這個位，則前面的一定是卡滿的，可以沿用上述的 \(f\)。

考慮這一位之后可以任意填 \(0\sim 9\)，則設 \(g_{i,j,x}\) 表示從后往前考慮到了第 \(i\) 位，拿了 \(j\) 個數丟進滿足 \(R\) 的子序列，最后一次丟了 \(x\)，同理 \(j=0\) 時僅 \(x=0\) 合法，與 \(f\) 不同的是，\(g\) 需要在 \([0,9]\) 中枚舉一個填在該位的 \(x\)。

同時需要注意的是，\(g\) 的“該位不用”的狀態(tài)的轉移，必須在枚舉完所有“用該位，且該位填 \(x\)”的轉移之后，且轉移為 \(g_{i,j,x}\gets 10\times g_{i+1,j,x}\)，其中 \(10\) 表示這一位就 \([0,9]\) 任意了。

考慮此時如何計算答案，假設第 \(i\) 位是這個沒卡滿的位，那么可以通過 \(f_{i-1,j,x}\times g_{i+1,m+1-j,y}\times v\) 來計算答案，其中 \(v\) 是第 \(i\) 位如果不卡滿該位的填數方案的數量，而 \((x,y)\) 依舊需要滿足對應的偏序關系的限制，這種方法表示第 \(i\) 位不計入答案。

同時也可以通過 \(f_{i-1,j,x}\times g_{i,m+1-j,y}\)，表示第 \(i\) 位計入答案，這個邊轉移“用該位”邊算，具體來說轉移 \(g_{i,/,y}\) 時算，偏序限制必須滿足，這種方法表示第 \(i\) 位計入答案。

最終我們會面臨一個問題：前導 \(0\) 在枚舉狀態(tài)時是存在的，但是在選子序列時不存在。但是又能發(fā)現只要填了前導 \(0\) 第一位就沒有卡滿，那么就容易解決：

多轉移一次 \(g\)，枚舉有多少位是前導 \(0\)，假設第 \(i(i\ge 2)\) 位是第一個非 \(0\) 位，考慮第 \(i\) 位用還是不用，用的話把 \(g_{i,m+1,x}\) 計入答案，同理邊轉移“用該位”邊算，不用的話就枚舉最高位最后一個丟進的數 \(y\in [0,9]\)，把所有 \(g_{i+1,m+1,y}\) 計入答案即可。

不要忘記，不存在前導 \(0\) 時，第一位不能填 \(0\)，這一點需要注意。設 \(n = |r|, k = |\Sigma| = 10\)，時間復雜度為 \(\mathcal{O}(Tn^2k^2)\)。

Question 2. Sum of distances

給定一張 \(n\) 個點的有向圖，從 \(i\) 連向 \((i+1)\) 的邊的邊權為 \(a_i\)，從 \(i\) 連向 \((i+2)\) 的邊的邊權為 \(b_i\)，從 \(i\) 連向 \((i+3)\) 的邊的邊權為 \(c_i\)，除此之外沒有邊。

求任意兩點間的最短路之和。

\(n\leq 3\times 10^5, 1\leq a_i,b_i,c_i\leq 10^3\)

考慮分治，設中點為 \(m\)，考慮拿出 \(m-1,m,m+1\) 這三個點，先分別求解完 \([l,mid-2], [mid+2,r]\)，然后考慮 \([l,r]\) 區(qū)間的問題。

顯然當 \(a\in [l,mid-2], b\in [mid+2,r]\) 時，顯然一定要經過 \(m-1,m,m+1\) 中的一個。

設 \(d(x,y)\) 表示 \(\min(x,y)\to \max(x,y)\) 的最短路，先 DP 求解所有 \(d(a,m-1),d(a,m),d(a,m+1)\) 的最短路，注意方向不同 DP 不一定相同。

那么所有一端是 \(m-1,m,m+1\) 的答案容易求得，此處不要重復計數中間三個點之間的答案，考慮求 \(a\in [l,mid-2], b\in [mid+2,r]\) 時的答案。

假定最短路經過 \(x=m-1,y=m,z=m+1\) 中的一個點，且最短路相同時取編號更小者，則：

1. 在 \(x\) 中轉：

   • \(d(a,x) + d(x,b)\leq d(a,y) + d(y,b), d(a,x) + d(x,b)\leq d(a,z) + d(z,b)\)
   • 轉換！\(d(a,x) -d(a,y) \leq d(y,b) - d(x,b), d(a,x) - d(a,z)\leq d(z,b) - d(x,b)\)
   • 也即 \(P_a = (d(a,x) -d(a,y), d(a,x) - d(a,z)), R_b = [0, d(y,b) - d(x,b)]\times [0, d(z,b) - d(x,b)]\)
   • 數點 \(P_a\in R_b\)，增加貢獻 \(\sum d(a,x) + d(x,b)\)

2. 在 \(y\)? 中轉：

   • \(d(a,y) + d(y,b) < d(a,x) + d(x,b), d(a,y) + d(y,b)\leq d(a,z) + d(z,b)\)
   • 轉換！\(d(a,y) -d(a,x) < d(x,b) - d(y,b), d(a,y) - d(a,z)\leq d(z,b) - d(y,b)\)
   • 也即 \(P_a = (d(a,y) -d(a,x), d(a,y) - d(a,z)), R_b = [0, d(x,b) - d(y,b))\times [0, d(z,b) - d(y,b)]\)
   • 數點 \(P_a\in R_b\)，增加貢獻 \(\sum d(a,y) + d(y,b)\)

3. 在 \(z\)? 中轉：

   • \(d(a,z) + d(z,b) < d(a,x) + d(x,b), d(a,z) + d(z,b) < d(a,y) + d(y,b)\)
   • 轉換！\(d(a,z) - d(a,x) < d(x,b) - d(z,b), d(a,z) - d(a,y) < d(y,b) - d(z,b)\)
   • 也即 \(P_a = (d(a,z) -d(a,x), d(a,z) - d(a,y)), R_b = [0, d(x,b) - d(z,b))\times [0, d(y,b) - d(z,b))\)
   • 數點 \(P_a\in R_b\)，增加貢獻 \(\sum d(a,z) + d(z,b)\)

做幾個二維數點即可，離散化后用樹狀數組跑得不慢。

而注意分治邊界為 \(r-l+1\leq 2\)，注意 \(r-l+1 = 2\) 時有一個點對。

時間復雜度為 \(\mathcal{O}(n\log_2^2n)\)。

Question 3. [2nd-Ucup, Stage 12] K. Campus Partition

給定一棵 \(n\) 個節(jié)點的樹，點有點權 \(a_i\)，將樹分成了若干連通塊，每個連通塊的權值為該連通塊所有點權的非嚴格次大值，如果連通塊大小為 \(1\) 則權值為 \(0\)。

將樹劃分成若干連通塊，劃分方案的權值為所有連通塊的權值之和，求所有劃分方案的權值的最大值。

\(n\leq 5\times 10^5, a_i\leq 10^9\)

假設有一個大連通塊，我們找到最大值所在點 \(u\)，找到次大值所在點 \(v\)，設路徑 \(P\) 為 \(u\to v\) 的路徑，顯然這個連通塊的貢獻不變，但是解放了更多點可以造成更多貢獻，是更優(yōu)的。

于是我們有結論：一個連通塊僅需要一條路徑，最大值與次大值分居路徑兩端。

考慮 DP，設 \(f_{u,w}\) 表示以 \(u\) 為根的子樹，有一條需要向上的路徑，路徑另一端的權值為 \(w\) 的最大權值，設 \(g_u\) 表示以 \(u\) 為根的子樹沒有向上的路徑時的最大權值。

則 DP 易求，設 \(v,w\) 為子節(jié)點：

從 \(u\) 開始新開一條路徑：

從 \(u\) 繼承一條子樹的路徑：

\(u\) 不選入路徑（開單點）：

在 \(u\) 處合并兩條路徑：

考慮能否按兒子節(jié)點順序來執(zhí)行 DP 的轉移？可以，那么轉移為：

記得考慮轉移順序，采用前后綴 \(\max\) 優(yōu)化，分別考慮 \(\min(i,j)\) 取 \(i\) 還是取 \(j\)，設 \(pre_{u,j}\) 表示 \(x\leq j\) 時 \(f_{u,x} + x\) 的最大值，同理 \(suf_{u,j}\) 表示 \(x\geq j\) 時 \(f_{u,x}\) 的最大值，改寫為：

容易做到 \(\mathcal{O}(n^2)\)。

發(fā)現兩維狀態(tài)均難以省去，考慮使用線段樹合并進行優(yōu)化，具體的，離散化 \(w\) 后開值域線段樹，每個節(jié)點維護區(qū)間對應的 \(f_{u,i} + i,f_{u,i}\) 的最大值。

難點在于如何合并。設要將 \(q\) 節(jié)點合并到 \(p\) 節(jié)點上，如果均為葉子節(jié)點，則要么是 \(p\) 的值加 \(g_v\)，要么是 \(q\) 的值加 \(S\)，將 \(g_v,S\) 傳入則可以取較大值。

若 \(p\) 為空，則顯然取 \(q\) 的值加 \(S\)；若 \(q\) 為空，則顯然取 \(p\) 的值加 \(g_v\)。當然，這個加值需要下傳，或者標記永久化，不這么做更新的時候會發(fā)現沒有得到這個值。

合并的時候，先 pushdown。

考慮如何順便更新 \(g_u\) 的值，傳址進函數更新，每次遞歸的時候，同時計算當前區(qū)間 \([l,r]\) 對應的 \([1,l-1]\) 的 \(f_{u,i} + i\) 的前綴最大值 \(P\) 與 \([r+1,n]\) 的 \(f_{u,i}\) 的后綴最大值 \(S\)。

根據更新式，顯然在 \(q\) 為空時，或者 \(l=r\) 時，\(g_u\) 需要更新，更新法則根據上述式子也容易得到。

時間復雜度為 \(\mathcal{O}(n\log_2 n)\)，有一點細節(jié)。

旅游去了，東北好玩，天氣挺涼快的。

順便俄羅斯太平洋艦隊的軍艦和指揮部非常明顯，還讓拍照，挺有趣的。

Tips

1. 逆序對指定的排列計數 DP 可以設 \(Q(i)\) 表示表示 \(P(i) > P(j)\) 且 \(i < j\) 的 \(j\) 的數量，然后基于兩個條件求解：
   • \(Q(i)\leq N-i\)
   • \(\sum Q(i) = X\)
2. 有時候不講究復雜度的話，可以在換根時枚舉轉移到的節(jié)點的鄰域，做一些小暴力，時間復雜度為 \(\mathcal{O}(N)\sim \mathcal{O}(N\log_2 N)\)。

Question 4. 「2024 “釘耙編程” Round.1」K. 樹上的 mex

給定一棵 \(n\) 個節(jié)點的樹，點有點權 \(v_i(0\leq v_i\leq n)\)，稱樹上的簡單路徑的權值為路徑上所有點權的 mex。

求最大的非負整數 \(k\)，使得樹上至少有 \(1\) 條路徑使得其權值為 \(k\)，并求出權值為 \(k\) 的簡單路徑（端點 \(x,y\) 滿足 \(1\leq x,y\leq n\)）的數量。

特別的，對于任意點權 \(x\)，都存在樹上的一條簡單路徑，滿足樹上所有點權為 \(x\) 的點位于該路徑上。

\(T\leq 10, n\leq 7\times 10^4, \sum n\leq 3.6\times 10^5\)

首先感覺這東西有單調性，二分 \(k\)，對任意的 \(v\in [0,k)\)，不經過點權 \(v\) 的路徑不合法。

假設要求不經過點權 \(v\) 的路徑，考慮建立點權 \(v\) 的所有點的虛樹，由本題中點權的分布性質，顯然這棵虛樹是一條鏈。

那么考慮虛樹中某個點權為 \(v\) 的點 \(u\)，那么在 \(u\) 的某個兒子 \(x\) 的子樹內的任意兩點肯定不會經過點 \(u\)，那么就不會經過點權 \(v\)。當然，如果子樹內有一個點權為 \(v\) 的點 \(y\)，要把這棵子樹減去。如果用 dfs 序（用 \(d\) 表示 dfs 序，\(s\) 表示子樹大小）區(qū)間來表示就是 \(a,b\in [d_x, d_x + s_x)\) 或者 \(a,b\in [d_x, d_y)\cup [d_y+s_y, d_x + s_x)\)，其中 \(a,b\) 為路徑端點。

考慮上述形式，可以用 \(xOy\) 平面上的矩形來表示，前面一種可以用 \(1\) 個矩形，而后面一種可以用 \(4\) 個矩形。

當然，假設這棵虛樹的“上方”還有一批，分虛樹的根 \(R\) 的權值是否為 \(v\) 討論一下：

• 如果根 \(R\) 的權值為 \(v\)，則顯然不在 \(R\) 的子樹內的任意兩點不經過點權 \(v\)，則 \(a,b\in [1,d_R)\cup [d_R+s_R, n]\)，可以用 \(4\) 個矩形描述。
• 反之，\(R\) 必定存在兩個兒子 \(s,t\)，設 \(d_s < d_t\)，則顯然不在 \(s\) 或 \(t\) 的子樹內的任意兩點不經過點權 \(v\)，即 \(a, b\in [1,d_u)\cup [d_u+s_u, d_v)\cup [d_v+s_v, n]\)，可以用 \(9\) 個矩形描述。

所有矩形的面積并表示所有不合法的路徑數量，設面積并為 \(S\)，則 \(n^2 - S\) 表示合法的路徑數量，于是就容易 check 并計算答案。

估計一下矩形數量的上限：

1. 對于“子樹內”形式的矩形，在每個 \(x\) 處最多 \(4\) 個矩形，最多總計 \(4n\) 個。
2. 對于“虛樹外”形式的矩形，在每個 \(v\) 中最多 \(9\) 個矩形，最多總計 \(9n\) 個。

于是總矩形數量不超過 \(13n\)，單次時間復雜度為 \(\mathcal{O}(n\log_2^2 n)\)，有較大常數，實測上述做法可以通過。

Question 5. 「JOISC 2025 Day2」集郵比賽 4

本題又名：別樣的集郵大戰(zhàn)

給定一條長度為 \(2N\) 的環(huán)形跑道，跑道 \(i\) 連接站點 \(i\) 與站點 \(i+1\)（按照順時針方向為 \(i\to i+1\)），特別的，跑道 \(2N\) 連接站點 \(2N\) 與站點 \(1\)（按照順時針方向為 \(2N\to 1\)），跑道 \(i\) 上有一個集章臺，提供顏色為 \(A_i\) 的印章。

參與者選擇一個站點出發(fā)，支付 \(C_i\) 的代價，然后可以執(zhí)行如下操作：

• 選擇一個不是起點的站點，交換與這個站點相連的兩條跑道上的集章臺，交換一次的代價為 \(X\)。

最后，參與者從站點出發(fā)依次經過 \(2N\) 條跑道，假設先經過的某條跑道上的集章臺的顏色為 \(X\)，后經過的為 \(Y\)（可以是同一條），可以獲得一張「左邊為顏色 \(X\) 右邊為顏色 \(Y\)」的卡。

稱兩張卡不同當且僅當其有至少一邊的顏色不同，給定 \(Q\) 個詢問，每個詢問求得到至少 \(K_q\) 種卡的代價。

\(N,X,Q\leq 5\times 10^5, C_i\leq 10^{18}, K_q\leq N^2\)，且 \(A\) 為 \((1,1,2,2,\cdots, N,N)\) 的一個排列。

我們不妨考慮指定一個起點，在不交換的情況下，依次經過 \(2N\) 條跑道，依次經過的 \(2N\) 個集章臺的印章的顏色構成的序列為 \(B=(B_1,B_2,\cdots, B_{2N})\)。

如果執(zhí)行一次交換操作，則相當于選擇 \(1\leq i < 2N\) 然后交換 \(B_i, B_{i+1}\)。

考慮到每種元素恰好出現兩次，我們不妨設一個長度為 \(2N\) 括號序列 \(S\)，其中某個數值 \(X(1\leq i\leq N)\) 第一次出現的位置 \(i\) 對應的 \(S_i\) 為 (，第二次出現的位置 \(j\) 對應的 \(S_j\) 為 )，那么肯定有 \(S\) 是合法括號序列。

接下來刻畫能夠得到的卡的數量，就是前面是 ( 后面是 ) 的二元組數，嚴謹的說：滿足 \(i < j\) 且 \(S_i\) 為 ( 而 \(S_j\) 為 ) 的 \((i,j)\) 的數量。

同時，對于兩邊顏色相同的卡，兩個章也強制在不同的集章臺蓋章，這將稍微簡化問題的考察。

考慮這個字符串 \(S\)，除非前 \(N\) 個都是 ( 且后 \(N\) 個都是 )，都一定能找到一對 )( 且這兩個括號是相鄰的，執(zhí)行一次交換后變?yōu)?()，并且這個括號序列最終總能變?yōu)椤盖?\(N\) 個都是 ( 且后 \(N\) 個都是 )」的形式，每一次交換會增加一個且僅增加一個 () 的二元組（畢竟交換的是相鄰的）。

所以，設 \(P_i\) 表示從站點 \(i\) 開始得到的這個序列 \(B\) 對應的 \(S\)，不交換的初始情況下，對應的二元組的數量，先暴力求得，時間復雜度為 \(\mathcal{O}(N^2)\)。

接下來對每一個詢問給出的 \(K_q\)，從站點 \(i\) 開始所需要的最小代價為 \(C_i + X\cdot \max(K_q - P_i, 0)\)，與 \(0\) 取 \(\max\) 表示 \(P_i\geq K_q\) 時無需操作，這個也暴力，時間復雜度為 \(\mathcal{O}(QN)\)。

現在總時間復雜度為 \(\mathcal{O}(N(N+Q))\)，考慮對兩個暴力進行優(yōu)化。

已知 \(P_i\) 時對計算答案進行優(yōu)化

這個部分主要需要考慮 \(\max(K_q - P_i , 0)\)，嘗試將 \(P_i\) 從小到大考慮。

此時 \(P_i\) 變得升序了，那么每一個 \(K_q\) 在 \(P_i\) 較小的時候取得 \(K_q - P_i\) 項，代價為 \(C_i + X(K_q - P_i)\)，即 \(X\cdot K_q + (C_i - X\cdot P_i)\)，前者固定 \(K_q\) 后是常數，后者僅跟 \(i\) 有關，可以采用前綴最小值計算。

而在 \(P_i\) 較大的時候取得 \(0\) 項，代價為 \(C_i\)，可以用后綴最小值計算。

對 \(K_q\) 二分其在 \(P_i\) 升序后中的位置，容易在線計算答案，本部分時間復雜度變?yōu)?\(\mathcal{O}(Q\log_2 N)\)。

對 \(P_i\) 的計算進行優(yōu)化

計算 \(P_i\) 的時候需要從位置 \(i\) 斷環(huán)求解序列問題，不妨先將原 \(A_i\) 斷環(huán)成鏈，倍長（復制一段接到末尾），然后求解所有長度為 \(M = 2N\) 的區(qū)間的答案。

求解一段序列中「前面是 ( 后面是 )」的二元組數，可以用線段樹進行維護，具體的，維護每個節(jié)點中 ( 的數量、) 的數量與對應的二元組數量，合并的時候除了兩個子區(qū)間的二元組數量，還要加上左半部取 ( 且右半部取 ) 的方案數，并且這個容易做簡單的修改操作。

不妨隨便指定一個順序（從前往后或從后往前）計算，因為筆者此處的 \(P_i\) 定義的為開頭位置，所以此處選擇從后往前。

開一棵定義在 \([1,2M]\) 區(qū)間上的線段樹，先預處理后半段 \([M+1,2M]\) 的答案，考慮每次往前加入一個位置 \(s\) 帶來的影響。

加入 \(s\) 的同時，要將 \(s+M\) 位置的影響刪除，但是序列是倍長得到的，所以顯然有 \(A_s = A_{s+M}\)，也就是說，我們需要將 \(s\) 位置改成一個 (，同時一定存在另一個位置 \(t\in [s, s+M)\) 滿足 \(A_s = A_t\)，原因還是一樣，要做的是將 \(t\) 位置改成一個 )。而在此之前，\(t\) 位置是 ( 且 \(s+M\) 位置為 )。

所以從前面加入一個位置帶來的影響就是 \(3\) 次單點修改（其實 \(2\) 次就能做了，但是為了貫徹“刪除影響”的描述記為 \(3\) 次），這個是容易做的。

于是邊加入位置邊用線段樹維護計算出 \(P_i\) 即可，時間復雜度為 \(\mathcal{O}(N\log_2 N)\)，實際上考慮的序列的長度已經是 \(4N\) 了，但是實測不會超時，跑起來不算慢。

綜合兩大優(yōu)化，本題得以在 \(\mathcal{O}((N+Q)\log_2 N)\) 的復雜度內求解，可以通過。

Question 6. 「CQOI2011」動態(tài)逆序對

設一長度為 \(n\) 的排列 \(P\)，給定 \(m\) 次操作，每次操作從 \(P\) 中刪除一個指定的數，求每次操作前 \(P\) 中的逆序對數量。

\(m\leq n\leq 10^5\)

先強制欽定出一個排列 \(Q\)，將 \(P\) 中元素按照 \(Q\) 的順序刪除，之后不妨將逆序對 \((i,j)\) 掛到刪除早的元素上，那么無非兩種形式：

與

將下標為第一維，元素值為第二維，刪除時間為第三維解三維偏序，CDQ 分治即可，不要忘記答案是差分過的，后綴和回去即可，時間復雜度為 \(\mathcal{O}(n\log_2 ^2 n)\)。

Tips

1. STL 定義申請空間很慢，所以不要在動態(tài) DP 的矩陣乘法里面的矩陣用 vector 之類的STL！本機實驗相差 10 倍，可以使用 array 之類。
2. 嘗試找出 DP 中兩個運算的分配律關系，構建矩陣乘法維護動態(tài) DP。

Question 7. 「JOISC 2025 Day3」多方通信

\(N\) 個人，每個人手上有一塊白板，初始裁判決定一個人是貴族，其他人是平民，初始時貴族手上的白板上寫有 T，所有平民的白板上寫有 F。

通過執(zhí)行以下操作 \(L\) 輪，找出貴族：

• 每個人先擦去白板上寫有的字符，基于先前輪依次所看過的所有字符（包括初始字符），然后自行選定一個 T 或 F 的字符寫入白板。
• 基于先前輪依次所看過的所有字符（包括初始字符），每個人 \(x\) 指定一個人 \(y\) 并查看 \(y\) 的白板上的字符，此時可以 \(x = y\)。

\(L\) 輪操作后，通過所依次查看過的人及其寫下的字符，報出貴族的編號。

最小化 \(L\)，并依次給出每個人是貴族時的情況時每個人會做什么。

解決 \(N = 4, 32, 48\) 時的問題。

首先考慮一個最簡單的策略，每一輪都是貴族寫 T 平民寫 F，然后每個人遍歷其他 \(N - 1\) 個人，直到找到一個寫 T 的為止，需要 \(L = N-1\) 輪，可以獲得 \(9\) 分。

稍微優(yōu)化以下，遍歷 \(N - 2\) 個人，如果都沒有找到 T，基于自己的字符，推斷剩下的一個人是否為貴族，需要 \(L = N-2\) 輪，可以獲得 \(16\) 分，解決 \(N = 4\) 的問題。

于是策略就出來了，我們不斷排除一些玩家，直到能夠確定貴族是誰，一個比較容易想到的方法是分組，考慮 \(N = 32\)，例如：

• 將 \(32\) 個人分成 \(8\) 組，每組 \(4\) 個人，先在組內 \(3\) 輪找出是否在本組內有，接下來 \(6\) 輪遍歷 \(6\) 個其余組是否有貴族（此時有貴族的組全員寫 T 其余組全員寫 F），最后再在組內問 \(3\) 個人，即可推斷出貴族是誰，總花費 \(12\) 次，可以獲得 \(16 + 48 = 64\) 分。

列一個不等式就可以發(fā)現分組是不可能達到 \(L = 8\) 的目標的，考慮再優(yōu)化。

不妨將 \(32\) 個人放到線段樹上，如果已知是在 \([1,16]\) 中還是在 \([17,32]\) 中，就可以通過遞歸子樹來確定，通過在長度為 \(2\) 的區(qū)間處進行一次推理，可以在 \(4\) 次之內找出（長度為 \(16,8,4,2\) 的區(qū)間各一次）。

至于確認貴族編號的第一次確定，已知其中有一個葉子節(jié)點是貴族，所以按照深度從大到小詢問，深度相同的在一次詢問內進行，每一次詢問合并其左右子樹是否存在（即 \(f_s = f_l \operatorname{OR} f_r\)），詢問方法為：

• 由左右子樹所對應區(qū)間長度相同，左子樹與右子樹節(jié)點一一對應，問自己節(jié)點對應的節(jié)點，寫自己是否已知貴族存在即可。

最終就可以 \(4\) 次恰好分出 \([1,16]\) 還是 \([17,32]\)，疊加上上面的 \(4\) 次詢問，得以在 \(8\) 次解決問題。

至于 \(N = 48\) 時的情況，相當于在合并到 \([1,16], [17,32], [33,48]\) 時通過額外一次確定在哪一組，因為已知自己所在組，隨便詢問另外一組，均不存在可以通過排除法確定貴族所在組，\(L = 9\) 解決。