Codeforces Round #119 (Div 1) A~C

表現差強人意，希望下次能再做得好點 :-)

A: 給了兩個$1\cdots N$的排列，對於任意一個排列，可以取出最右邊的數字並可以放在餘下數字中任意位置(除了不能原封不動)。問最少需要多少次操作才能把排列$A$變成排列$B$。良久後才發現如果$A_1, A_2, \cdots, A_p$的相對次序在$B$中並沒有改變，則只需要把剩下$N-p$個數字按插其中即可。答案就是找出最大的$p$並輸出$N - p$。

B: 給了$M$種車輛，並且給了第$i$輛車在一個$N$個城市之間的行走時間。現有$R$場賽事，每場賽事表示要從$s$城到$t$城的最短路，而且只能允許中途轉換最多$K$次車輛。

基本上我看漏了很多東西…首先，$R \le 10^5$，表明最短路需要預計算。其次，$K \le 1000, N \le 60$其實不太可能轉車$1000$次吧？即是其實$K$最多只有$N-1$而已。知道後其實題目是在層圖上做所有點對的最短路。首先固定一種車輛求最短路，然後迭代$N-1$次在層圖上再做Floyd-Warshall即可。

C: 題目給了$N$點及$M$條路，然後在$K$個不同的點上皆放了指示牌。每個指示牌只能顯示長度$q$的路線，問從$s$到$t$，$q$最少是甚麼？保証點$s$一定有路牌。

首先想到的是二分找$q$吧。不過固定了$q$，怎樣才能判斷$s$可以到達$t$？這問題好像和為網絡封包找最少的ttl差不多。不過想到的是直接用BFS，然後記下通過一點時還餘多少步。這樣一來好像跟Shortest Path沒分別，而且狀態一共有$O(Nq)=O(N^2)$個，好像不行。提交時也不能過pretest，以為算法錯了。怎料事後發現自己初始餘下步數的數組為$0$，即是剛好剩一步便到終點的話便沒法更新，改了初始值是$-1$後便AC了。到現在我沒法証明這算法的Worst case complexity…總之應該很快就是。