專(diao)題大賞
USACO の small Trick雜題
核心Trick使用粗體強調
1.Breakdown P
刪改加不多說
考慮\(K\)很小，不妨meet in the middle，此時\(k = 4\)
處理出只包含一條邊，兩條邊的“小組件”去“拼出”最短路，每次加邊只需要更新新邊端點涉及的組件以及最短路即可
2.Making Friends P
掃一遍，每個點向比他大的點建關系，然后合并
可以用\(set\)，也可以使用線段樹合并
3.Palindromes P
考慮每一對字母移到某區間對稱位置的貢獻，位置\(l,r\)，區間\([L,r]\)，貢獻\(|l + r - L - R|\)
分奇偶性討論，每次由內向外從一對擴展到另一對，使用樹狀數組維護\(l + r\),\(L + R\)
4.Tractor Paths P
倍增
預處理出每個區間向左/右跳\(2^i\)步最遠能跳到哪個區間，這個可以求出第一問
對于第二問，考慮前綴和，沿用上面的倍增，求出\(2^i\)步內有多少個特殊區間，最后使用右-左即為答案
5.Mana Collection P
推式子
設確定要收集的點集為\({c_k}\)，對應到達時刻為\({t_k}\)那么有式子\(ans = \sum\limits_{i = 1}^k m_{c_k}\times t_k\)
考慮時間拉滿肯定不劣，所以\(t_i = s - \sum\limits_{j = i}^{k - 1}d(c_j,c_{j + 1})\)
帶入:
之所以把后面變一下，是方便狀壓預處理
第一維表示選的點集，第二維是終點，\(d\)用\(Floyd\)預處理,\(sum = \sum_{i = 1}^k m_{c_i}\)
然后回到式子，發現可以令\(B = - \sum\limits _{i = 1}^{k - 1}d(c_i,c_{i + 1})\sum\limits_{j = 1}^{i}m_{c_i}\),也就是\(dp_{S,c_k}\)，\(K = \sum_{i = 1}^k m_{c_i}\)，\(x = s\)就是直線，可以上李超樹，注意終點不同的要放入不同的樹中
動態維護即可，復雜度沒問題
Hungry Cow P
利用線段樹的merge實現類似平推操作
考慮到要把新加的草往右勻，原先有草吃的天跳過，以此計算貢獻，使用線段樹實現，記錄當前區間有草吃天數\(has\)，多出的草\(more\)，答案\(sum\)，以及向后勻的貢獻\(giv\)（根據線段樹的結構，就是填右子區間的貢獻）
理論可勻 $\max(mor - [(r - mid) - has],0) $,最多 \(r - mid\)，二者比大小實現草的剩余等量的轉移
考慮到1e14的威壓一定要多取模還要考慮線段樹大小以及維護的區間的大小
Subtree Activation P
搞出優秀路徑及其性質后跑大炮
定義一個點被標記為某時刻該點滿足了條件1，將點按照標記先后排列到樹上形成若干路徑
根據樣例和手摸可以猜到優秀路徑只可能是下面幾種
然后接著手玩可以發現標記一條序列上所有點的最小花費是深度最淺的點的\(siz\)的兩倍
接著可以想到最優情況下序列互不交叉
然后可以使用樹形大炮，用沒標記的鏈結合當前節點拼路徑
Problem Setting P
狀壓出每道題的難易程度，得到\(n\)個\(m\)位的狀態，結合題意會發現選擇的相鄰兩道題前者是后者的子集（認為這道題難的下一道仍然難，還有一部分從后一道題開始認為難）
狀態相同的可以合并，方案 $ = \sum\limits_{i = 1}^{num} A_{num}^i$
設\(dp_s\)表示最后一道題狀態是\(s\)的方案數
枚舉當前最后一道題的狀態\(S\)，那么前面一共有\(1 + \sum dp_s\)種方案，其中\(s \subseteq S\)，\(+1\)是因為前面可以不選，乘上自己的方案數就是\(dp_S\)
但是實際只有\(60\)，考慮優化
可以沿用\(dp\)的尿性，欽定子集只比全集少一個\(1\)，這樣枚舉每一位即可，那就預處理\(ret_{s,j}\)表示狀態為\(s\)，與全集相比最大的少一處為\(j\)的情況下的\(dp\)總和，也就是說，可能有多位少\(1\)，\(j\)位是編號最大的一位
轉移即可
Watching Cowflix P
看牛片
首先\(dp\)，設\(dp_{u,0/1}\)表示節點\(u\)是否屬于連通塊，然后有
然后可以有\(naive\)的\(n^2\)，考慮優化
使用 驚人的觀察力 發現部分答案的差一定而且差單調遞減，考慮使用根號分治
\(k < \sqrt n\)時暴力大炮
\(k > \sqrt n\)時二分出所有差變化的位置，然后遞推即可
注：卡常，使用\(dfn\)序優化把搜索改成線性遍歷
Pareidolia P
使用線段樹維護矩陣（？？？）
無修改時有大炮，使用矩陣轉移，帶修改的話對每一位字符構一個矩陣，使用線段樹維護
Good Bitstrings P
真史登場
數形結合
規定射線\((x,y)\)表示從原點出發經過\((x,y)\)的線
定義點\((ia,ib)\)，將變化過程畫到平面上，得到從\((0,0)\)到\((a,b)\)的路徑
結合判斷條件以及圖形可得：當前點在射線\((a,b)\)上方時向右走，反之向上走
那么路徑上的整點就是所有前綴
考慮合法點\((x,y)\)的性質
1.射線\((a,b)\)和射線\((x,y)\)中間沒有路徑上的其他點
證明：顯然如果有的話會出現不同的決策，矛盾
2.已知合法點\(f_1,f_2\)，如果\(f\)代表的射線在\(f_1,f_2\)中間，且有\(f_1 \times f_2 = 1\)（向量叉積），那么\(f = k_1f_1 + k_2f_2\)
證明：\(f = (f \times f_1)f_2 + (f \times f_2)f_1\)
這樣就有\(f = f_1 + f_2\)
然后就有算法，見第一篇題解
簡單手膜發現還有一些東西
3.結束時\(f_1,f_2\)中有一個滿足等于\((\frac{a}{\gcd(a,b)},\frac{\gcd(a,b)})\)，且另一個與\((a,b)\)叉積的值為\(\gcd\)
也就是說整個過程就是個輾轉相減，可以轉化成輾轉相除從而實現\(log\)的復雜度
剩下一些細節見tj
Triples of Cows P
\(deep ♂ dark ♂ fantacy\) 不可做
Paired Up P
大炮
- \(T = 1\)
相對簡單，設\(dp_{i,j}\)表示前\(i\)頭\(H\),\(j\)頭\(G\)完成配對時最大體重和
\(ans = \sum W - dp_{H,G}\)
- \(T = 2\)
考慮直接\(dp\)出答案
定義\(dp_{i,j,k}\)表示前\(i\)頭\(H\),\(j\)頭\(G\)完成配對，最后一個未配對的牛是\(k\)的最大值
這樣轉移是三次方的，考慮優化
保留前兩維，我們可以使用兩個數組分別表示最后一個未配對的牛是\(H\)或是\(G\)，然后可以互相轉移，通過提前預處理某區間內極大配對牛數量和一頭牛的最小標號配對?？梢詫崿F快速轉移
注：這里的區間\(lst_{i,j}\)表示第\(i - numh\),第\(j - numg\)頭牛中的極大配對數
HILO
轉化成期望
定義\(dp_{i,j,0/1}\)表示還剩下\(i\)個小于\(x\)的有效數字，\(j\)個大于\(x\)的有效數字，前一次喊的是
LO(0)/HI(1)，然后用反向跑的方法去大炮
那么每次選擇一個數，都只影響其所在的區域（> / <\(x\)），另一維不影響，考慮到選擇后廢棄的數字有多種可能，所以要遍歷。如果前一次喊的是HI，那么這次如果喊LO期望次數就會增加，增量為\(\frac{i}{i + j}\)
即
使用前綴和優化即可
Minimizing Haybales P
聚聚爆
對于每個數，二分找出他可以換到的位置區間，可以使用線段樹維護區間最值實現，然后在活動區間中找到最左邊的大于該數的位置，把他扔到那里，那么可能一些位置有多個數，為了字典序最小，使用\(multiset\)維護即可（因為有重復元素）
貪（luan）心（gao）
所有正確的貪心一定有科學的理由
國王游戲
根據直覺按照\(b\)升序排列能得一半分
考慮大臣1和大臣2位置能交換的必要條件是：大臣2放在大臣1的前面得到的最大值更加小。那么討論兩種情況下的最值：
如果大臣1放在前面，他倆獲得的金幣數分別為：\(\frac{a_0}{b_1},\frac{a_0 \times a_1}{b_2}\)
如果大臣2放在前面，他倆獲得的金幣數分別為：\(\frac{a_0}{b_2},\frac{a_0 \times a_2}{b_1}\)
約去式子里面的a0，就變成了比較：\(\max(\frac{1}{b_1},\frac{a_1}{b_2})\)和\(\max(\frac{1}{b_2},\frac{a_2}{b_1})\)的大小
根據\(a > 0\)，可得: \(\frac{a_1}{b_2} \geq \frac{1}{b_2}\)、\(\frac{1}{b_1} \leq \frac{a_2}{b_1}\)
那么，如果\(\frac{1}{b_1}\)是最大的，則\(\frac{1}{b_1} \geq \frac{a_2}{b_1}\)，只可能左右兩邊相等，則有\(\frac{1}{b_2} \leq \frac{a_2}{b_1}\)，所以兩種情況的最大值是一樣的，則不用交換。同理可得\(\frac{1}{b_2}\)是最大的情況也不用交換。
那么如果\(\frac{a_1}{b_2} > \frac{a_2}{b_1}\)，那么就要交換，變形得：
$$a_1 \times b_1 > a_2 \times b_2$$
表示要交換，我們排序就只要按照\(a \times b\)的從小到大排就可以了。
高精傳統美德
皇后游戲
根據直覺認為\(a\)越小越好（減少大值的累加），\(b\)越大越好（在\(\sum a\)還小的時候加入大值），兩種情況分別跑一遍然后取\(\min\)可得\(70\)...
首先證明直覺有一定正確性
沿用上一道題的方法，考慮相鄰兩個人的交換條件。由于獎金單調，所以后一個人的一定更大。設大臣\(i\)后面的大臣為\(j\)，\(i\)前面的\(\sum a\)為\(x\)，\(i\)前面一位大臣獎金為\(y\),則
化簡為：\(\max(y + b_i + b_j,x + a_j + b_i + b_j,x + a_i + a_j + b_i)\)
同理可得交換后\(i\)的獎金
那么不交換更優，那么
其中\(y + b_i + b_j\)沒有本質上的影響，直接消掉。類似的，\(x\)也能消掉：
然后提出相同的，移項
較大數會被減掉，留下較小數的相反數，變個號得到
分討：
-
\(a_i < b_i\),\(a_j < b_j\)時，\(a_i \leq a_j\)，按照\(a\)升序
-
都相等：無所謂
-
\(a_i > b_i\),\(a_j > b_j\)時，\(b_i \geq b_j\)，按照\(b\)降序
所以猜想是有合理性的，重點在于\(a,b\)誰的“影響力”更大
所以維護\(a,b\)的大小關系，由此排序
其中$del$只會是$-1,0,1$
bool cmp1(node x,node y)
{
// return min(x.a,y.b) < min(y.b,y.a);
if(x.del == y.del)
{
if(x.del <= 0) return x.a < y.a;
else return x.b > y.b;
}
return x.del < y.del;
}
加法
首先二分答案，考慮用貪心搞\(check\)
那么為了最大化效果，肯定選當前可選區間中右端點最大的，所以使用優先隊列維護備選區間，然后遇到需要填的數字時，如果原先有的區間數不夠，就從隊列里取新的，但是新區間要滿足右端點長于當前位置才能使用，掃一遍即可
賽道修建
- \(m = 1\)：直徑
點擊查看代碼
if(m == 1)//直徑
{
dfs(1,0); st = pos;
memset(d,0,sizeof(d));
dfs(st,0); ed = pos;
printf("%d\n",d[ed]);
return 0;
}
- \(a_i = 1\): 菊花圖，此時賽道最多兩條邊。最優肯定是兩兩組合。分討，如果兩兩組合能湊夠\(m\)條，那肯定是用排序后的邊中后\(2m\)條組，大配小即可。否則需要用一些單邊當賽道，那么首先要最小化單邊數量，然后肯定用最大的邊做單邊，剩下的大配小
點擊查看代碼
if(ifjh)//菊花
{
sort(val + 1,val + num + 1);
if(m <= (n - 1) / 2)
{
int pos = n - 1 - m * 2;
int l = pos + 1,r = num;
for(int i = 1;i <= m;i++) pat[++tot] = val[l] + val[r],l++,r--;
sort(pat + 1,pat + tot + 1);
printf("%d\n",pat[1]);
}
else
{
int x = (n - 1 - m); int sig = n - 1 - 2 * x;
int l = 1,r = num - sig;
for(int i = 1;i <= x;i++) pat[++tot] = val[l] + val[r],l++,r--;
for(int i = 2 * x + 1;i <= num;i++) pat[++tot] = val[i];
sort(pat + 1,pat + tot + 1);
printf("%d\n",pat[1]);
}
return 0;
}
- \(b_i = a_i + 1\)：鏈，二分答案+貪心\(check\)即可，注意\(val\)數組不能排序，是\(dfs\)的遍歷順序
點擊查看代碼
if(ifchain)//鏈
{
dfs(1,0); num = 0;
for(int i = 2;i <= n;i++) val[++num] = d[i] - d[i - 1];
int res = 0,L = 1,R = all;
while(L <= R)
{
int mid = L + R >> 1;
if(check(mid)) res = mid,L = mid + 1;
else R = mid - 1;
}
printf("%d\n",res);
return 0;
}
以上一共\(55\)分
std:
首先二分答案
對于每個點，優先將他的兒子之間配對形成賽道，剩下未配對的兒子中挑個最大的傳上去（與祖先們形成賽道）
考慮配對方式。如果一個兒子就已經滿足二分的值，就不配了直接刪。否則找一個最小的與當前兒子加起來能滿足二分值的兒子，將二者同時刪去，一直配到不能再配為止
由于重復元素，使用\(multiset\)維護
一些特判：
-
如果找到的位置是自己，指針往后跳一位
-
如果當前集合里就剩一個元素，直接比對不配了
點擊查看代碼
int Dfs(int x,int fa,int lim)
{
s[x].clear();
for(int i = head[x];i;i = e[i].next)
{
int k = e[i].to;
if(k == fa) continue;
int ret = Dfs(k,x,lim) + e[i].w;
if(ret >= lim) sum++;
else s[x].insert(ret);
}
int maxx = 0;
while(!s[x].empty())
{
int tmp = *s[x].begin();//待配對元素
if(s[x].size() == 1) return max(maxx,tmp);
auto pos = s[x].lower_bound(lim - tmp);
if(pos == s[x].begin()) pos++;//找到它自己，往后跳一個
if(pos == s[x].end())//沒找見
{
maxx = max(maxx,tmp);
s[x].erase(s[x].begin());
}
else//配對的一起刪
{
sum++;
s[x].erase(pos); s[x].erase(s[x].begin());
}
}
return maxx;
}
讓我們贏得選舉
明顯，在\(B_i \neq -1\)時，獲得協作者必能得到選票
所以考慮按照\(B\)排序。
然后考慮到有些州\(B\)很大但\(A\)很小，所以用大炮維護
但是大炮有一個問題：
大炮是遍歷，然而最優策略其實是先選人再去專心拿票，這就使得走的州的順序在排序后的數列上可能是跳躍的
怎么辦呢？
但有一點是不變的：選人肯定從前若干個選
然后就很騷了：枚舉選了多少個人(\(x\))，然后將大炮兩維定義為票數和人數，在計入拿票代價時直接除以\(x + 1\)，其他正常
注意第七行
for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) dp[i][j] = 1.0e9;
dp[0][0] = 0;
for(int i = 1;i <= lim;i++)
{
for(int j = 0;j <= x;j++)
{
dp[i][j] = min(dp[i][j],dp[i - 1][j] + sta[i].a * 1.0 / (x + 1));
if(j > 0 && sta[i].b != 1e9) dp[i][j] = min(dp[i][j],dp[i - 1][j - 1] + sta[i].b * 1.0 / j);
}
}
接著，這\(x\)個人能拿的票數\(\in [x,k]\)，那么枚舉他們拿的票數\(i\)，此時這里還有一個性質：這\(i\)張票肯定全部來自前\(i\)個州。那么第\(i + 1\)到第\(n\)部分 按照\(A\)貪心 去選剩的\(k - i\)張，然后與大炮合并即可
點擊查看代碼
db res = 1.0e9;
for(int i = lim;i >= x;i--)//這里要倒序，因為要排序，正向的話會亂
{
sort(a + i + 1,a + n + 1);
int sum = 0;
for(int j = i + 1;j <= lim;j++) sum += a[j];
res = min(res,dp[i][x] + sum * 1.0 / (x + 1));
}
ans = min(ans,res);
雙序列拓展
性質題
首先翻譯一個東西：\(\forall 1 \le i,j \le l_0\) 都有 \((f_i - g_i)(f_j - g_j) > 0\)。實際上就是\(\forall i \in [1,l_0],f_i > g_i\)或\(f_i < g_i\)
結合這個東西，就能得到拓展的目的：如果當前位的\(Y\)與\(X\)不符合關系，將前面的\(Y/X\)延展過來
那么不妨使用第一項確定一種大小關系去搞，如果不符合就把序列交換一下看行不行
不妨設為\(X< Y\)
那么首先可以有一個大炮\(dp_{i,j}\)表示當前匹配到\(X\)的第\(i\)位，\(Y\)的第\(j\)位是否能擴展，\(dp_{1,1} = 1\),然后當\(X_i < Y_j\)時轉移即可
點擊查看代碼
dp[1][1] = 1;
for(int i = 1;i <= lena;i++)
for(int j = 1;j <= lenb;j++)
if(a[i] < b[j]) dp[i][j] = (dp[i][j] | dp[i][j - 1] | dp[i - 1][j] | dp[i - 1][j - 1]);
然后觀察特殊性質，發現提到了最值，提醒我們從這方面考慮
再次注意到題目中有一個條件：\(L\)是一個正整數序列
這個條件比較重要，這說明：\(Y\)中的每一個元素都會與\(X\)中某個元素相對
那么，如果\(Y_{min} \leq X_{min}\)，就說明\(Y_{min}\)這個位置一定不能滿足\(X < Y\)的要求，\(Y_{max} \leq X_{max}\)同理，即沒有\(Y\)能勝任\(X_{max}\)所在位置
此時我們得到了兩個判據，接下來進一步發掘性質
\(dp\)的轉移形式似乎暗示著可以使用網格建立模型，那么我們可以得到：
有一個網格\(A\)，\(A_{i,j} = [X_i < Y_j]\)，\(1\)表示能走，\(0\)表示不能走，能否從\((1,1)\)走到\((n,m)\)
那么以\(Y_{min} \leq X_{min}\)為例，反應到網格上就是\(\forall i \in [1,n],(i,pos[Y_{min}])\)都是堵死的，也就是走不到。另一個同理
把條件反一下呢？
如果\(Y_{min} > X_{min}\)，此時所有\(Y\)都比\(X_{min}\)大，即：\(\forall i \in [1,m],(pos[X_{min}],i)\)全是通路，另一個同理，\(\forall i \in [1,n],(i,pos[Y_{max}])\)全是通的，形如
此時已經變成了左上和右下兩個子問題（特殊性質只有左上），那么遞歸處理即可
這是左上的check，pre是前綴最值，右下check只需把pre改成suf并修改邊界即可
bool chk1(int posx,int posy)
{
if(posx == 1 || posy == 1) return 1;
node X = prex[posx - 1],Y = prey[posy - 1];
if(x[X.mn] < y[Y.mn]) return chk1(X.mn,posy);
if(x[X.mx] < y[Y.mx]) return chk1(posx,Y.mx);
return 0;
}
丁香之路
個人認為不是很優美。。。
想到應該構造形如下圖狀物
首先建出\(m\)條邊，然后考慮怎么貪心
然后就有神秘小策略：如果當前點為奇點，就往下一個點（編號相鄰）連邊，如果下一個點變成奇點，則繼續往后連，直到沒奇點
就是先把所有點捏成若干個紅圈圈。造完之后考慮連通性。可以使用最小生成樹，但是要注意的是代價是樹邊和的兩倍，因為此時的路徑形如\(dfs\)，一條邊走兩次
最后起終點也要連邊。。。
數學
Small Permutation Problem (Easy Version)
轉化題
將排列轉化為\((i,p_i)\)，那么就變成了\((i,i)\)與原點形成的矩形中有\(a_i\)個點，那么每次\(a_i\)變化就是在兩個正方形形成的\(L\)形中加點（這也說明\(a_i\)單調不降）
考慮到排列形成的點橫縱坐標各不相同，所以一個\(L\)里最多兩個點，因此\(|\Delta a_i| \leq 2\)，可以判斷有無解
然后如果差為\(1\)，那么只用在\(L\)的一支上加點，而上一個正方形占掉了\(a_{i-1}\)個橫縱坐標，所以方案數為\(2(i - a_{i - 1}) - 1\)，減一是因為\((i,i)\)重復算了
類似的可得，差為\(2\)就是\((i - a_{i - 1} - 1)^2\)，因為\((i,i)\)一定不能填點
最后，判斷無解還有首項不大于\(1\)和末項必須為\(n\)的要求
乘法原理統計即可
Multiple Lamps
人類智慧構造題。。。
很快就能想到一個燈最后能亮的條件是按下的按鈕編號中有奇數個是其編號的因數
然后發動傳統藝能人類智慧：將\(1\)到\(n\)全按一遍，最后亮的就是完全平方數
然后你就會發現在\(n \geq 20\)的時候就符合題目條件了。。。
so直接狀壓預處理剩下的\(n\)然后每次詢問\(check\)預處理的合法狀態即可
wtf
方案數
做了前置題后這道題就好做一些了 （別問前置題怎么找到的），設\(dp_i\)表示不經過其他障礙到達障礙\(i\)的方案數，原理和前置題相同
然后處理判定以及該題下的“距離”，那么就需要一個輔助數組\(g_{i,j,k}\)來表示當三個維度二進制下\(1\)的個數分別為\(i,j,k\)時的方案數，枚舉每一位轉移即可
如下，組合表示新加的$1$的分布情況
g[0][0][0] = 1;
for(int i = 0;i <= 60;i++)
{
for(int j = 0;j <= 60;j++)
{
for(int k = 0;k <= 60;k++)
{
if(i == 0 && j == 0 && k == 0) continue;
for(int x = 1;x <= i;x++)
g[i][j][k] = (g[i][j][k] + g[i - x][j][k] * C[i][x] % mod) % mod;
for(int x = 1;x <= j;x++)
g[i][j][k] = (g[i][j][k] + g[i][j - x][k] * C[j][x] % mod) % mod;
for(int x = 1;x <= k;x++)
g[i][j][k] = (g[i][j][k] + g[i][j][k - x] * C[k][x] % mod) % mod;
}
}
}
判定就按題意判定即可
Construct Matrix
很快發現要求每行\(1\)的個數奇偶性相同，列一樣，那么奇數一定不行，然后\(k = n,k = n^2,k = 0\)較方便，不說，主要看偶數。偶數有兩大類
- \(k = 4p\)
這個手摸\(n = 4,k = 8\)得到一個合法構造
當然還有別的，但這個規侓性很強，可以發現是由以下“基元矩陣”組成：
而且發現只要不重疊，隨便怎么放都行，那就直接一個密鋪過去
點擊查看代碼
int H = 1,W = 1;
while(k)
{
for(int i = H,oi = 1;oi <= 2;i++,oi++)
for(int j = W,oj = 1;oj <= 2;j++,oj++)
a[i][j] = 1;
W += 2;
if(W > n) H += 2,W = 1;
k -= 4;
}
print();
- \(k = 4p + 2\)
這個麻煩些，手摸\(n = 4,k = 10\)可得：
發現左上角那個\(3 \times 3\)可以把\(k\)的個數削成\(4p'\)，那么就可以繼續沿用上面的基元矩陣密鋪，不過\(3\)是個奇數，那就擴一圈\(0\)成為\(4 \times 4\)，然后去鋪剩的。最后發現鋪完后會剩\(4\)個或\(8\)個\(1\)，后者無解，前者扔進\(4 \times 4\)即可
I Wanna be the Team Leader
咕
字符串
字符串匹配
枚舉循環節（\(AB\)）長度，算出能有多少節，然后暴力枚舉節數和\(A\)長度，前者可以得到\(C\)，然后比對即可，有\(48\)分
枚舉長度和節數是\(n\log n\)的，可以保留，考慮優化計算答案
發現每當長度加一，\(A\)的可能只增加一種，就是上一次的\(AB\)，然后可以預處理出前/后綴字符個數為奇數的字符數，每次得到\(C\)后開桶統計，枚舉完當前長度后把當前長度扔進桶即可
復雜度\(O(26n\log n)\)，谷上過不去，要寫樹狀數組？26和log26也妹啥區別吧
Short Code
建成trie樹，然后把末尾標記點往空祖先跳，要求最小化標記點深度總和
就是把最深的往上提，注意不是直接讓最深的跳到當前最淺（樣例2過不去），而是從下往上一步一步跳，每次從兒子中選一個最深的跳
先搜在跳
void cal(int x,int d)
{
for(int i = 1;i <= 26;i++)
{
if(tr[x][i])
{
int k = tr[x][i];
cal(k,d + 1);
while(!q[k].empty()) q[x].push(q[k].top()),q[k].pop();
}
}
if(x != 1 && !cnt[x])
{
// cout << q[x].top() << endl;
ans -= q[x].top();
ans += d;
q[x].pop();
q[x].push(d);
}
}
串串題
很明顯有兩個性質：
-
\(B\)中出現的元素不能被刪
-
\(B\)中沒有且妨礙匹配（\(A\)中有）的要刪掉
那么就可以把\([1,W]\)中所有\(B\)沒有的算出來，記為\(All\)（這些都可以選），然后把\(A\)中在\(B\)出現的元素的下標提取出來，在掃這個下標序列的時候用雙指針和桶維護要刪掉的元素總數\(del\)（相當于一個長為\(m\)的滑動窗口），用\(KMP\)匹配，如果能配上，那么答案就是\(C_{All - del}^{d - del}\)，意即必選這\(del\)個數，然后再剩余中選夠\(d\)個
Cezar
字典序 \(\to\) 拓撲，經典套路
就是按照\(a\)的限定，建\(S_{a_i} \to S_{a_j} (j > i)\)的邊，具體的，找出\(S_{a_i},S_{a_j}\)第一個不同的位\(x\)，則有\(S_{a_i,x} \to S_{a_j,x}\)。如果沒找見，而且\(S_{a_i}\)還比\(S_{a_j}\)長，則肯定無解。然后判環，跑拓撲即可
CSPS2023B消消樂
定義\(dp_{i}\)表示\([1,i]\)的子串的合法方案數，那么答案就是\(\sum\limits_{i = 1}^{n}dp_i\)
另定義\(pos_i\)表示使得\([pos_i,i]\)為合法串的位置，那么有\(dp_i = dp_{pos_i - 1} + 1\)。至于如何得到\(pos_i\)，可以類比\(next\)，初始化為\(i - 1\)，然后不斷向前跳，即\(pos_i \to pos_{pos_i} - 1\)，直到\(s_{pos_i} = s_i\)
Keyboard Design
首先一個字符最多和兩個字符相鄰，扔到圖上就是合法序列都是鏈，沒有環。
所以可以先判環，扔掉不符合條件的單詞，然后把剩下的串精簡一下，因為我們只會關心相鄰關系，像樣例的\(abacaba\)就可以簡化為\(bac\)，然后建\(AC\)自動機（多模式串匹配必備工具），注意相鄰不分順序，所以還要把串反過來再扔進去，然后經典小套路：\(W_{i} += W_{fail_i}\)以及經典小大炮：\(dp_{i,S}\)表示當前走到\(i\)節點，已經選擇的字符集為\(S\)，式子很簡單：
\(\large dp_{s | 2^j,tr_{i,j}} = \max(dp_{s,i} + W_{tr_{i,j}})\)
最后要輸出方案，記錄一下前驅狀態以及前驅節點即可
Hossam and Range Minimum Query
奇偶性 \(\to\) 異或，還算經典
然后考慮到 \(3 \oplus 2 \oplus 1 = 0\)的坑，要賦隨機權值來異或。然后區間內出現次數使用主席樹來維護，詢問的話在主席樹上二分就行了
Comfortably Numb
考慮區間分治。設區間為\([l,r]\)，中點\(mid\)，假設最值在\([mid + 1,r]\)（在左邊同理）
在\([mid + 1,r]\)內枚舉右端點\(i\)，然后找到最靠左的左端點\(j\)使得區間最值\(mx\)不變（就是最值只能通過擴展\(i\)更新），設\(s_x\)表示前綴異或和，那么子區間最值就是在\(s_j,s_{j + 1},...s_{mid + 1}\)里選一個與\(s_i \oplus mx\)異或使得和最大，這個使用字典樹維護
點擊查看代碼
void sol(int l,int r)
{
if(l == r) return;
int mid = l + r >> 1;
sol(l,mid),sol(mid + 1,r);
int mx = -1;
for(int i = 1;i <= tot;i++) tr[i][0] = tr[i][1] = 0; tot = 1;
rt = 1; sum[l - 1] = 0;
for(int i = l;i <= r;i++) sum[i] = sum[i - 1] ^ a[i];
for(int i = mid + 1,j = mid + 1;i <= r;i++)
{
mx = max(mx,a[i]);
while(j > l && a[j - 1] <= mx) j--,ins(sum[j - 1]);
int ret = sum[i] ^ mx;
ans = max(ans,ret ^ query(ret));
}
mx = 0;
for(int i = 1;i <= tot;i++) tr[i][0] = tr[i][1] = 0; tot = 1;
rt = 1; sum[r + 1] = 0;
for(int i = r;i >= l;i--) sum[i] = sum[i + 1] ^ a[i];
for(int i = mid,j = mid;i >= l;i--)
{
mx = max(mx,a[i]);
while(j < r && a[j + 1] < mx) j++,ins(sum[j + 1]);
int ret = sum[i] ^ mx;
ans = max(ans,ret ^ query(ret));
}
}
CF の 人類智慧題
Another Array Problem
本來以為是什么\(n \log n\)，結果手玩發現\(n \ge 4\)時一定有辦法將整個序列染成最值（把邊上兩個（不含最值）艸成\(0\)，先用最值染掉一邊，再把另一端艸成\(0\)，就染完了。。。），然后\(n \leq 3\)分討即可。。。
The Human Equation
將\(a\)做前綴和，記作\(sum\)，那么每次操作相當于在\(sum\)中選一些數\(+1\)或\(-1\)，\(sum\)全零時\(a\)也全零，那么答案就是最大整數和最小負數的絕對值和，又稱最大值\(-\)最小值。。。
Prefix Enlightenment
三個集合不交就是一盞燈最多在兩個集合中，此時我們先假設每盞燈都由兩個集合控制，所以要補一個“虛集合”，即\(k++\)
如果當前燈為\(1\)，那么兩個集合 要么都選，要么都不選，反之，為\(0\)時兩個集合 只選一個
有點像\(2-SAT\)，或者叫種類并查集（同食物鏈），對于集合\(i\)，令\(i\)表示選，\(i + k\)表示不選，每次按邏輯合并，合并時維護答案即可
不過我們是用\(size\)維護答案的，\([k + 1,2k]\)也有\(size\)，但是不選就是沒操作所以要除以\(2\)
現在考慮只有一盞燈，此時要查詢虛集合所屬的連通塊，然后只能選擇不包含虛集合的部分（在這里虛集合編號為\(0\)）
Flip and Reverse
黑曜色人類智慧
這是字符串題？NO~ ，這是 圖論題
假設我們從點\(x\)出發，掃一遍串，當前字符是\(0\)時向\(x+1\)連邊并走到\(x + 1\)，是\(1\)時向\(x - 1\)連邊并走到\(x - 1\)（當然也可以反過來），就形成了一張有向圖
考慮操作的本質，\(01\)個數相等說明選中的串代表了一條 歐拉回路，取反+翻轉說明 改變了當前路的方向
形如下圖
要求字典序最小，則考慮貪心往大的數走，但是有條件：首先得有邊，其次要滿足回路的特點，即如果\(x \to x - 1\)有一條邊，那么\(x \to x + 1\)至少有兩條邊時才能走
Bicolored Segments
看錯題了qwq。以為要求全一色且兩兩不交，后來發現是“同時滿足”，即只要求異色不能相交。。。
先離散化，使得\(l,r \in [1,tot]\)
點擊查看代碼
for(int i = 1;i <= n;i++) p[++cnt] = l[i],p[++cnt] = r[i];
sort(p + 1,p + cnt + 1);
cnt = unique(p + 1,p + cnt + 1) - p - 1;
for(int i = 1;i <= n;i++)
{
l[i] = lower_bound(p + 1,p + cnt + 1,l[i]) - p;
r[i] = lower_bound(p + 1,p + cnt + 1,r[i]) - p;
sg[r[i]].push_back(i);
}
定義\(dp_{l,r,0/1}\)表示考慮了\([0,r]\)這段坐標，其中\([l + 1,r]\)這一段區間內的線段都是顏色\(0/1\)的最大方案數，分為同色合并和異色合并，固定右端點，根據左端點計算
然后給\(l\)一維上一個線段樹去維護區間修改和查詢最值即可
點擊查看代碼
for(int i = 1;i <= cnt;i++)
{
for(int x : sg[i]) ST[t[x]].add(0,l[x] - 1,0,cnt,1,1);
int mx1 = ST[1].query(),mx0 = ST[0].query();
ST[0].add(i,i,0,cnt,1,mx1); ST[1].add(i,i,0,cnt,1,mx0);
}
int ans = max(ST[0].query(),ST[1].query());
printf("%d\n",ans);
Xor-Subsequence (hard version)
首先有個顯然
然后考慮優化
注意到條件是異或，考慮字典數
一開始想的是\(a_j \oplus i < a_i \oplus j \to a_j\oplus j < a_i \oplus i\)，因為我們每次只能知道\(i,a_i\)，但是這個轉化顯然不成立
不過我們可以拆分一下：之所以小于是因為前若干位相同，某一位為\(0,1\)
對于前面相同的部分，上面的轉化是成立的，即設\(a_j,i,a_i,j\)相同部分為\(x,y,z,w\)，有\(x \oplus y = z \oplus w\)，則\(x \oplus w = y \oplus z\)。因此我們可以將\(a_i \oplus i\)插入字典樹去跑，順便把大炮值扔進去更新\(\max\)
點擊查看代碼
void ins(int x,int id,int val)
{
int p = 1;
for(int i = 30;i >= 0;i--)
{
int u = (x >> i) & 1,v = (a[id] >> i) & 1;
if(!tr[p][u]) tr[p][u] = ++tot;
p = tr[p][u];
mx[p][v] = max(mx[p][v],val);
}
}
然后考慮不同位，沿用上面的設法，則有\(x \oplus y = 0,z \oplus w = 1\)，說明\(x = y,z,w\)中分別為\(1,0\)，那么當\(x = y = z\)時，\(x \oplus w = 1,y \oplus z = 0\)，另一情況類似，說明答案會在\(!(a_i \oplus i)\)的一側更新，跑字典樹時比對即可
點擊查看代碼
int query(int id)
{
int p = 1;
int res = 0;
int x = a[id] ^ id;
for(int i = 30;i >= 0;i--)
{
int u = (x >> i) & 1,v = (id >> i) & 1;
if(tr[p][!u]) res = max(res,mx[tr[p][!u]][!v]);
p = tr[p][u];
if(!p) break;
}
return res;
}
然而你會發現\(mx\)數組的跑使用的是\(i\)和\(a_i\)分開的結果。實際上，用\(a_i \oplus i\) 只能說明不相等，大小關系是未知的，我們還是要按題目的要求，用當前\(a\)去和下標比對，然后為了保證小于，要求\(a_i,j\)異或為\(1\)，即對應位上的數不相等，所以mx第二位有感嘆號
當然也可以用\(a\)插入，不過查詢時相當于求的是\(a_j,i\)，對應位要相等，就沒有感嘆號了
最后注意答案是\(\max(dp_i)\)
浙公網安備 33010602011771號