前言
已經(jīng)有三個月未更新算法文章，大廠工作環(huán)境是步步緊逼的，使得所有的人越來越忙碌。余下的學(xué)習(xí)時間，要用于技術(shù)預(yù)研、知識面開闊、底層原理理解等等，慢慢算法只能占用娛樂時間來耍，這個是非常不穩(wěn)定的，畢竟還要四排吃雞、五排王者。
這次更新幾個難題，其他題目見算法文集。
正文
1. Vladik and fractions
題目大意：
給出一個數(shù)字n，求出三個不同的正整數(shù)，要求：
2/n = 1/x + 1/y + 1/z。
如果不存在，輸出-1。
數(shù)據(jù)范圍：
1<=n<=1e4
x, y and z (1?≤?x,?y,?z?≤?1e9, x?≠?y, x?≠?z, y?≠?z)
Examples
input
3
output
2 7 42
input
7
output
7 8 56
題目解析：
題目屬于構(gòu)造題。
第二個樣例給了思路： 2/n = 1/n + 1/(n+1) + 1/n(n+1)
對于這個公式，基本所有的n都能有解；
特別的，n=1的時，存在無解的情況。
2.Chloe and pleasant prizes
題目鏈接
題目大意：
n個節(jié)點的樹，1為根；
每個節(jié)點有權(quán)值a[i]；
現(xiàn)在要求從樹中選擇兩個節(jié)點u、v，切斷u、v與父親的邊，形成兩顆子樹，滿足條件：
1、兩個子樹不重疊；
2、兩個子樹節(jié)點的權(quán)值和最大；
如果存在，輸出權(quán)值和；不存在輸出-1；
數(shù)據(jù)范圍：
(1<=n<=2e5,?-1e9?≤?a[i]?≤?1e9)
Examples
input
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8
output
25
input
4
1 -5 1 1
1 2
1 4
2 3
output
2
input
1
-1
output
Impossible
題目解析：
容易知道，只要有一個節(jié)點存在兩個子樹，那么有解；
在有解的情況下，必然存在這樣一個點P：兩個最優(yōu)子樹T1和T2，都是點P的子樹。
那么維護一個最優(yōu)子樹的值：dp[i] 表示i節(jié)點為根的子樹，子樹的權(quán)值和；
同時在進行狀態(tài)轉(zhuǎn)移的時候，維護一個新的數(shù)組：top[i] 表示i節(jié)點為根的樹，其所有子樹中，子樹權(quán)值和的最大值；
那么對于節(jié)點u和子節(jié)點v，有top[u] = max(dp[u], top[v])；（dp[u]表示以節(jié)點u為根的子樹權(quán)值和，top[v]是u的子樹的最大權(quán)值和）；
并且對于節(jié)點u，如果有多個子節(jié)點v，那么只需保留最大的兩個top[v]即可。
void dfs(int u, int fat) {
dp[u] = a[u];
multiset<lld> childs;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (v != fat) {
dfs(v, u);
dp[u] += dp[v];
tops[u] = max(tops[u], tops[v]);
childs.insert(tops[v]);
if (childs.size() == 3) {
childs.erase(childs.begin());
}
if (childs.size() == 2) {
ans = max(ans, *childs.begin() + *(++childs.begin()));
}
}
}
tops[u] = max(tops[u], dp[u]);
}
3.Hongcow Builds A Nation
題目鏈接
題目大意：
給出一個圖，n個點，m條邊，其中k個點為關(guān)鍵點；
現(xiàn)在在圖上加邊，要求：
1、關(guān)鍵點之間不能存在路徑；
2、不能存在自環(huán)、多重邊；
問，最多能加多少邊。
數(shù)據(jù)范圍：
(1?≤?n?≤?1?000, 0?≤?m?≤?100?000, 1?≤?k?≤?n)
先輸入n，m，k；
接著是k個數(shù)字，表明k個關(guān)鍵點；
接著是m對數(shù)字(u,v)，表明u和v之間存在一條邊；
Examples
input
4 1 2
1 3
1 2
output
2
input
3 3 1
2
1 2
1 3
2 3
output
0
題目解析：
添加的邊不能產(chǎn)生關(guān)鍵點之間的路徑，那么可以換一種思路：
對于和關(guān)鍵點已經(jīng)相連的點，縮成一個關(guān)鍵點；
那么總共會有k個關(guān)鍵點，還有若干個獨立點；
sum[i]表示關(guān)鍵點i的點的數(shù)量（縮點），假設(shè)y=max(sum[i]);
此時能加多的邊：
關(guān)鍵點自己內(nèi)部構(gòu)建成完全圖；
所有的獨立點構(gòu)建成完全圖；
獨立點集和最大的關(guān)鍵點兩兩相連；
最后結(jié)果，減去所有已有的邊。
4.Vladik and cards
題目鏈接
題目大意：
有若干個卡片排成1行，上面有數(shù)字1~8，現(xiàn)在要找到最長的子序列，滿足：
1、所有相同數(shù)字的卡片數(shù)量和c[i]，滿足i,j∈[1,8]，|c[i] - c[j]| <= 1;
2、相同的數(shù)字卡片必須是連續(xù)的；比如說[1,1,2,2]是合法的, [1,2,2,1]是不合法的；
求出最長的子序列。
數(shù)據(jù)范圍：
(1?≤?n?≤?1000)
Examples
input
3
1 1 1
output
1
input
8
8 7 6 5 4 3 2 1
output
8
題目解析：
子序列，n又小，狀態(tài)也少，看起來像動態(tài)規(guī)劃。
問題在于，每個卡片必須選x和x+1張，這個在dp過程中無法控制；
我們只考慮最少的選x張，容易只知道，如果x張可行，那么x-1張可行，具有單調(diào)性；
于是，可以用二分來確定x的大小，現(xiàn)在的問題是給出最小長度x，是否能快速求出x的是否有解；
容易知道，每個數(shù)字只有x/x+1的狀態(tài)，可以用0/1來表示，1~8的數(shù)字狀態(tài)壓縮后，有255種狀態(tài)；
dp[i][j] 表示 前i個，狀態(tài)為j（0101，為1表示對應(yīng)位數(shù)的數(shù)字已經(jīng)選擇過）中選擇x+1的最大數(shù)量；
狀態(tài)轉(zhuǎn)移：
dp[p[k][t]+1][j|(1<<k)]=max(dp[p[k][t]+1][j|(1<<k)],dp[i][j]); 跳轉(zhuǎn)到新的長度，選擇x個
dp[p[k][t]+1][j|(1<<k)]=max(dp[p[k][t]+1][j|(1<<k)],dp[i][j]+1); 選擇x+1個
p[k][t] 存的是數(shù)字k的第t個的下標(biāo)；
當(dāng)len=0特殊處理（出現(xiàn)過的顏色的數(shù)量）。
總結(jié)
題目的代碼在【這里】。
無所事事的時候，嘗試解決一道難題，并享受其帶來的成就感。
