今年突然變成四道題了，還是三個小時，說實話時間感覺有點不夠用，但是變成實時oj了，可以直觀看多少分，倒數第二題最后沒想出來解法，只有暴力搜索混分了，
1. 監控二叉樹
給定一個二叉樹，我們在樹的節點上安裝攝像頭，
節點上的每個攝影頭都可以監視其父物件、自身及其直接子物件，
計算監控樹的所有節點所需的最小攝像頭數量，
https://leetcode-cn.com/problems/binary-tree-cameras/solution/
leetcode 原題
貪心就好了：找任一個葉結點，把照相機放到父結點上，然后刪掉他的祖父、父、他和他的兄弟，然后在新的樹（或者說森林）重新找葉結點，
O ( N ) O(N) O(N)
2. 因子遞推
給N < M < 1e5, 從p出發走一步可以到p+k( k是p 因數且k != 1 且 k != p），求N到M最小步數
遞推就完了 O ( N 1.5 ) O(N^{1.5}) O(N1.5)
//偽代碼，記得初始化之類的
#define MAX 10000
#define INBOUND(i) i <= MAX
s[MAX + 1];//代表從s[i] N出發到達i的最少步數
s[N] = 0;
int solve(){
for(int i = N; i <= M; i ++){
int root = ceil(sqrt(i)) + 1;
for(int j = 2; j < root; j ++){
if(i % j == 0){
int k = i / j;
INBOUND(i + j) && s[i + j] = min(s[i + j], s[i] + 1);
INBOUND(i + k) && s[i + k] = min(s[i + k], s[i] + 1);
}
}
}
return s[M];
}
3. 最大運算式
給一串共N個數字排成一環，數字間有邊，邊上有乘號或者加號，去掉一條邊之后，將兩邊數字按照邊上算符可以合并成一新的個數字，可以遞回地洗掉邊最終得到一個數字，求第一次去掉哪一條邊能獲得最大數字?
例子 1 + 2
X X
4 + 5
第一次洗掉12 中間的+號有：2 X 5 + 4 X 1，再分別刪掉 第二個、第一個、第三個得到最大值18
N <= 50
動態規劃
第一次刪哪條邊不是重點，遍歷就完了
重要的子問題
排成一列的數字，中間有+或x，問合并后的最大值？
使用
M
[
i
,
j
]
M[i,j]
M[i,j] 代表第
i
i
i到
j
j
j個數字合并后可以產生的最大正值，
N
[
i
,
j
]
N[i,j]
N[i,j]代表
i
i
i 到
j
j
j個數字合并后可以產生的最大負值，就有
M
[
i
,
j
]
=
M
a
x
o
p
∈
O
p
{
M
[
i
,
k
]
+
M
[
k
,
j
]
(
o
p
[
k
]
=
′
+
′
)
,
M
a
x
(
M
[
i
,
k
]
?
M
[
k
,
j
]
,
N
[
i
,
k
]
?
N
[
k
,
j
]
)
(
o
p
[
k
]
=
′
×
′
)
}
M[i,j] = Max_{op \in Op}\{ M[i,k] + M[k,j] (op[k] ='+'),\\ Max(M[i, k] * M[k,j] , N[i,k] * N[k,j])(op[k] ='\times')\}
M[i,j]=Maxop∈Op?{M[i,k]+M[k,j](op[k]=′+′),Max(M[i,k]?M[k,j],N[i,k]?N[k,j])(op[k]=′×′)}
(就是說，當符號為+時，正最大值就是兩邊最大值的和；符號為x時，取正最大值的積和負最大值的積的最大值）
N
[
i
,
j
]
=
M
i
n
o
p
∈
O
p
{
N
[
i
,
k
]
+
N
[
k
,
j
]
(
o
p
[
k
]
=
′
+
′
)
,
M
a
x
(
M
[
i
,
k
]
?
N
[
k
,
j
]
,
N
[
i
,
k
]
?
M
[
k
,
j
]
)
(
o
p
[
k
]
=
′
×
′
)
}
N[i,j] = Min_{op \in Op}\{ N[i,k] + N[k,j] (op[k] ='+'),\\ Max(M[i, k] * N[k,j] , N[i,k] * M[k,j])(op[k] ='\times')\}
N[i,j]=Minop∈Op?{N[i,k]+N[k,j](op[k]=′+′),Max(M[i,k]?N[k,j],N[i,k]?M[k,j])(op[k]=′×′)}
一個意思
復雜度 O ( N 3 ) O(N^3) O(N3)
4. 樹上鐘同步
有一棵樹，樹上每個節點有一個鐘（取值范圍0-11），鐘上有一個初始值，
一個人從某個點出發(出發時不會自增1）
只能經過邊到達另一個點，
到達某點時，該點的值自增一（超過11置為0），
求所有的可行初始節點，使得從這些節點出發存在一條路徑（可重復經過邊經過點）可以將樹上所有鐘的值都置為0，
節點數不超過2500
強子命題
考慮要求這個人最后必須回到初始點的命題，是否存在一條可以將鐘都置為0的路徑，
此時他一定在每條邊都走了偶數次，且兩個方向的次數相等
這樣的話，通過葉結點 A A A計算要置為0對應邊應該走的次數 k = 12 ? i k = 12 - i k=12?i，并將 k k k加到相鄰點上后刪去 A A A，迭代地這樣做，最后一個點的值為0就存在，否則不存在，
原命題 = 一條不重復路徑+強子命題
因為某點最終的值和他到達該點的時間無關，只和次數相關，并且走
k
k
k次等價于
12
+
k
12+k
12+k次，
再考慮原問題，他走的路徑一定可以等價成一條不重復的路徑再加上一次從終點開始回到終點的路徑，
那么我們只需要dfs遍歷所有的不重復路徑，最后再判定強子命題能否成立就可以了，時間復雜度是
O
(
N
3
)
O(N^3)
O(N3)，會超時，
改進，動態更新
其實我們再看強子命題計算中，當我們使用拓撲排序排好了一個排列后 a [ 1... n ] a[1...n] a[1...n]，最后一個點的值也一定能展開為 ( ? 1 ) ( k a i ) c l o c k a i (-1)^{(k_{a_i})}clock_{a_i} (?1)(kai??)clockai??，于是我們能將每個 k a i k_{a_i} kai?? 記錄下來，將初始最后一個節點值也記錄下來，之后每次對點加一操作時，我們就對最后一個節點值加 ( ? 1 ) ( k a i ) (-1)^{(k_{a_i})} (?1)(kai??)，當最終點值變為0時，說明我們找到了一個好的路徑，
時間復雜度下降到 O ( N 2 ) O(N^2) O(N2)，可以ac了
一個不保證正確性的剪枝
現場的時候，我直接認為若 A A A是可行的初始節點，那么其他節點出發的不重復路徑一定不能經過 A A A，雖然讓我A了，但現在想起來可能會有點問題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/77108.html
標籤：其他