生活随笔
收集整理的这篇文章主要介绍了
2021HDU多校6 - 7028 Decomposition(构造)
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目链接：点击查看
题目大意：给出一个 nnn 个点的无向完全图，现在要求找到 kkk 条简单路径，每条简单路径的长度符合相应的要求，且每条边只能经过一次
题目保证 ∑i=1kli=n(n−1)2\sum\limits_{i=1}^k l_i = \frac{n(n-1)}{2}i=1∑kli=2n(n−1)
题目分析：变形：2019ICPC(上海) - Spanning Tree Removal
因为题目保证了 nnn 是奇数，所以多出来的那个点可以当作中介点，将 n2\frac{n}{2}2n 条欧拉通路连接成欧拉回路，然后依次输出相应的答案就可以了
具体构造方法大同小异，注意行末空格：
代码：
#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;
}
总结
以上是生活随笔为你收集整理的2021HDU多校6 - 7028 Decomposition(构造)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
