題目鏈接：點擊查看

題目大意：給出一個由 n 個頂點組成的完全圖，求出一個從點 1 出發的歐拉回路，使得字典序最小，不知道歐拉回路的同學請自行百度

題目分析：字典序最小，那么就說明讓序號小的頂點在前面，那么一開始肯定是從點 1 到其他頂點然后再回來是最優的，舉個例子，當 n = 5 時，與點 1 相連接的序列可以為 1 2 1 3 1 4 1 5 ，注意，到了點 n 后，如果再回到點 1 的話，那會使得無路可走了，所以此時可以從點 n 再到點 2 ，再重復上述操作得到的序列為 2 3 2 4 2 5 ，一直這樣操作，最后能得到一個由 n * ( n - 1 ) + 1 個點的序列，因為這個序列在極限數據的情況下能達到 1e10 ，所以題目只要求輸出 [ l , r ] 區間內的這段答案就好了，鑒于已經想出了構造方法，剩下的我們可以寫一個函數 cal( i ) ，返回位置 i 是哪個頂點就好了，至于 cal 函數的實現，我們可以用二分定位一下，然后根據奇偶確定答案，實際實現起來比較簡單

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;LL sum[N],n;int cal(LL pos) {if(pos==n*(n-1)+1)return 1;int j=lower_bound(sum+1,sum+1+n,pos)-sum;int b=pos-sum[j-1];if(b&1)return j;elsereturn j+b/2; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){LL l,r;scanf("%lld%lld%lld",&n,&l,&r);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+2*(n-i);for(LL i=l;i<=r;i++)printf("%d ",cal(i));puts("");}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1334D Minimum Euler Cycle(构造+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。