update codeforces/constructive/1650D

coderhare · coderhare · commit 2f590042cc4b · 2022-03-14T20:13:18.000+08:00
diff --git a/codeforces/constructive_algorithms/1650D.md b/codeforces/constructive_algorithms/1650D.md
@@ -0,0 +1,29 @@
+# codeforces 1650D
+
+> 这是一类题目，当我们想得到一个序列的时候，就通过最后一个位置的信息进行回溯。相同的做法还有迪杰斯特拉算法最短路径输出
+
+```cpp
+#include <bit/stdc++.h>
+using namespace std;
+int a[10010], b[10010];
+int main(){
+    ios_base::sync_with_stdio(0);
+    cin.tie(0);
+    int t, n;
+    cin >> t;
+    while(t--){
+        cin >> n;
+        for(int i = 0; i < n; i++) cin >> a[i];
+        for(int i = n - 1; i >= 0; i--) { //从后往前回溯
+            int j = find(a, a + n, i + 1) - a;
+            b[i] = (j + 1) % (i + 1);
+            rotate(a, a[j], a + i + 1);
+        }
+        for(int i = 0; i < n; i++) cout << b[i] << ' ';
+        cout << endl;       
+    }
+    return 0;
+}
+```
+
+
