信息學國家集訓隊作業(yè)1070rep

1、環(huán)城汽車賽的解題【問題描述】一個有向環(huán)有 n（不超過 100000）個點。每條弧和每個點上都值。你要找出這樣的點：以這個點為起點沿該環(huán)“走”一圈，初始計數(shù)為 0，每到達一個點就得到相應的權值，每經(jīng)過一條弧就扣去相應的權值，給定的權值保證滿足到達終點的時候計數(shù)依然為 0，即點權和等于邊權和，要保證任何時刻的計數(shù)都不小于 0?！痉治雠c算法】首先，先來分析一下樣例。發(fā)現(xiàn)從點 112（即權值為 1 的點）和點 3（即權值為 5 的點）無法完成任務，因為從它們出發(fā)根本就到不了下一個點！。而從點 2 和點 4 出發(fā)就可以完成，因為當它們到達點 1或點 3 時有 1 點的“儲備”，所以就不會被扣成負數(shù)了。6

2、7362這給一個啟示，就是點權和邊權都不是最重要的，所關心的并不是它們而是它們的差。它們的差反5映了移動到下一個點所導致的計數(shù)值的變化。第 i 個點的點權減去它連接到下一個點的弧上的權值，所得的差為 Di。設容易發(fā)現(xiàn)，第一個點滿足條件當且僅當同時滿足 D10，D1+D20，D1+D2+D30，D1+D2+Dn=00。同理，容易得出，第二個點滿足條件當且僅當同時滿足 D20，D2+D30，D2+D3+D40，D2+D3+Dn+D10。那么，這兩個條件之間把第二個點的條件兩端都加上關系呢？D1，就會得到 D1+D2D1，D1+D2+D3D1，D1+D2+D3+D4D1，D1+D2+D3+Dn+D1

3、= D1D1。發(fā)現(xiàn)不等式左端又變成了 D1，D1+D2，D1+D2+D3，D1+D2+Dn。因此，使用。在判斷第一個點時計算出來的不等式左邊的值可以保留到以后但是，由于仍然要判斷 N2 個等式是否成立，算法的時間復雜度仍然是O(n2)，那么，如何利用這個特性來降低算法的時間復雜度呢？由于每一個不等式組中所有的不等式的右邊都是相等的，設某個不等式組中所有不等式的右邊值為 q，立刻min(D1,D1+D2,D1+D2+D3,D1+D2+Dn)q。由于 min(D1,D1+D2,D1+D2+D3,D1+D2+Dn)是固定的，不等式組立刻被簡化為不等式。最后一步，又發(fā)現(xiàn)這些簡化以后得到的不等式的右邊同

4、樣可以被寫成D1+D2+Dk，1kn 的形式。最后，1、2、3、得到一個異常簡單的算法：求出 D。令 S0=0，Si=Si-1+Di，求出 S，并求出 S 的最小值。求出 S 中有多少個數(shù)等于最小值。每個等于最小值的數(shù)就對應了一個符合條件的節(jié)點?！拘〗Y】這道題目難度并不大，但是題目的數(shù)學味道比較濃，解法也比較簡潔而巧妙。對于這類題目，可以通過去掉冗余信息簡化題目，利用已經(jīng)求出的值來減少計算量，最終找到一個令人滿意的算法。【附原題】（來源：TongJi Online Judge 1070）環(huán)城汽車賽XYZ 城要舉行一場汽車賽，因為 XYZ 城的巿長是個怪人，所以這次汽車賽有特殊的規(guī)則。在這次比賽

5、的環(huán)形賽道上設有 N 個汽車。選手可以選擇任意一個作為起點。比賽開始時每輛汽車油箱里都沒有油。在到達第 i 個時了，汽車可以有那加 Oi 升的油。(設一升油可以開一 km，并和速度無關)。所以的油加起來正好可以開完全程。最快開完全程(逆時針)的選手將獲得第一名。當然，所有的選手都想奪冠，所以他們都想先知道從哪些開始可以跑完全程。這個任務就交給你了！Input第一行為一整數(shù) T，表示有 T 組測試數(shù)據(jù)。每組測試數(shù)據(jù)二行。每組測試數(shù)據(jù)的第一行是一個數(shù)字 N(4=N100000)第二行是用空格分開的 2N 個整數(shù)，第一個數(shù)是第一個可以提供的油 O1升，第二個數(shù)是第一站到第二站距離 D1km(N 個站是逆時針排列的)，最后一個是第 N 站個第一站的距離 DNkm。(Oi,Di=100000)Output對于每一組測試數(shù)據(jù)你輸出一行兩個數(shù)第一個數(shù)是一共有多少站可以那開始完成全程，第二個數(shù)是最小的可以完成全程的的(如果第一個數(shù)是