1樓：匿名使用者
該題是2023年全國資訊學奧林匹克競賽分割槽聯賽（noip）複賽的第三題
套用一下furong大牛的解題報告：
問題分析】
在考慮問題的解決方法之前，我們先考慮問題的最終狀態：它是一個排列。很顯然，我們首先可以根據題目給出的資訊，用掃描的辦法構造出一組可行排列：
從第1個人開始，先任意訪問一個與之相鄰的人a，接著，再從a開始，依次訪問下去，最終如果回到第1個人，則說明問題有解，否則問題無解。
由於本問題人都是圍成一個圓圈的，所以考慮開始狀態是 ，我們首先求出的可行目標狀態為 ，則 也是可行的目標狀態，並且他們旋轉所形成的狀態也是可行的目標狀態。而問題的解決，就是在這些所有可行的目標狀態中，找出所需交換次數最少的。
下面考慮從初狀態 到目標狀態 的最少交換次數：
(1) 我們可以找到交換次數的最小值：對於 ，設有 個元素存在 。顯然，這 個元素是不需要調整的。而剩下的所有元素，每個至少調整一次，則交換次數的最小值為 。
(2) 是否一定存在交換次數為 的解答呢？答案是肯定的：對於置換群 ，由於交換的次序任意，每一個迴圈 中，我們按照 的順序，只需修改一次，能將迴圈重置成任意想要的順序，而這個操作消耗題目中的代價為 。
於是對於每一個迴圈都如此操作，總的操作代價就是 。
綜上所述，要想構造可行解，由(1)知交換次數不得少於 ，由(2)知數目為 的方案是一定存在的，於是最優解即為 。
按照這個思路，我們需要對每一組可行解進行一次掃描，每一次掃描的時間複雜度為 ，共進行 次，其時間複雜度為 ，對於 ，是不能在規定時限內得到解的。通過觀察我們發現：對於 ，無論如何旋轉， 與 的相對位置是不會改變的。
所以，我們只要首先計算出 與 的相對位置，將它們放入hash表，最後找出hash表中的最大值（對應了上文中 的最大值），就可以在 的時間內統計出 的最小值，也就是最優解，問題解決。
2樓：匿名使用者
對題目的問題：
(b1, b2,... bm -1, bm)
這個命令，是指的必須從位置1到位置m變換，還是可以從位置i+1到位置i+m變換？這很關鍵
一道C語言程式設計題，一道C語言程式設計題
include include define change 0 int main void 你的串號我已經記下，採納後我會幫你製作 應該算是比較完整的程式了,如果你的問題還有補充的話請告訴我.author banxi1988 date 2010 12 9 include include define...
一道c 的程式設計數學題，一道C 的程式設計數學題
這可以直接套公式算啊，用不著一個個去試，幹嘛要寫程式.首先 n m k 先確定每個 box 裡面放幾個，我們安排 n 個位置，1 k 是 box 1的，k 1 2k 是 box2 的.這樣前 m k 個位置分配給了 m 個 box 的固定位置 然後，剩餘 n m k 個位置，我們把 m 1 個 隔板...
一道簡單的c語言程式設計題，C語言指標一道簡單的程式設計題
include include int main c語言程式如下，源謝謝採納。不借助臨時變數 include include void main 不用藉助變數藉助變數 int a,b,c 同樣的輸入 c a a b b c 這是核心演算法，其版餘的加齊 權就行了 數字是多大哦，幾百億？include...