生活随笔
收集整理的這篇文章主要介紹了
2021HDU多校6 - 7028 Decomposition(构造)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目鏈接：點擊查看
題目大意：給出一個 nnn 個點的無向完全圖，現(xiàn)在要求找到 kkk 條簡單路徑，每條簡單路徑的長度符合相應的要求，且每條邊只能經(jīng)過一次
題目保證 ∑i=1kli=n(n?1)2\sum\limits_{i=1}^k l_i = \frac{n(n-1)}{2}i=1∑k?li?=2n(n?1)?
題目分析：變形：2019ICPC(上海) - Spanning Tree Removal
因為題目保證了 nnn 是奇數(shù)，所以多出來的那個點可以當作中介點，將 n2\frac{n}{2}2n? 條歐拉通路連接成歐拉回路，然后依次輸出相應的答案就可以了
具體構(gòu)造方法大同小異，注意行末空格：
代碼：
#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<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
#define lowbit(x) (x&-x)
using namespace std
;
typedef long long LL
;
typedef unsigned long long ull
;
template<typename T>
inline void read(T
&x
)
{T f
=1;x
=0;char ch
=getchar();while(0==isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}while(0!=isdigit(ch
)) x
=(x
<<1)+(x
<<3)+ch
-'0',ch
=getchar();x
*=f
;
}
template<typename T>
inline void write(T x
)
{if(x
<0){x
=~(x
-1);putchar('-');}if(x
>9)write(x
/10);putchar(x
%10+'0');
}
const int inf
=0x3f3f3f3f;
const int N
=1e6+100;
vector
<int>cal(int n
) {vector
<int>ans
;ans
.push_back(n
-1);for(int i
=0;i
<n
/2;i
++) {int sgn
=1,pos
=i
;for(int j
=1;j
<n
;j
++) {ans
.push_back(pos
);pos
=(pos
+sgn
*j
+n
-1)%(n
-1);sgn
*=-1;}ans
.push_back(n
-1);}return ans
;
}
int main()
{
#ifndef ONLINE_JUDGE
#endif
int w
,kase
=0;cin
>>w
;while(w
--) {int n
,m
;read(n
),read(m
);vector
<int>ans
=cal(n
);printf("Case #%d:\n",++kase
);int pos
=0;while(m
--) {int len
;read(len
);len
++;while(len
--) {printf("%d%c",ans
[pos
++]+1,len
==0?'\n':' ');}pos
--;}}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的2021HDU多校6 - 7028 Decomposition(构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
