相关链接
题目传送门:http://codeforces.com/contest/782/problem/E
吐槽
没有看懂题,于是跑去问Menci题意
结果Menci先说做法,后说题意 _(:з」∠)_
强行把我带上了紫 *★,°*:.☆( ̄▽ ̄)/$:*.°★* 。
解题报告
我们发现这个$\lceil \ \rceil$和$2n$非常妙啊!
于是乎,我们先搞出欧拉序,然后分成$k$段输出就可以了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 400009; int n,m,k,tot,vis[N],head[N],nxt[N],to[N],que[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void Add_Edge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } void DFS(int w) { vis[w] = 1; que[++tot] = w; for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]]) { DFS(to[i]); que[++tot] = w; } } } int main() { n = read(); m = read(); k = read(); for (int i=1;i<=m;i++) { Add_Edge(read(), read()); } DFS(1); for (int i=1,cur=1,c=ceil(2.0*n/k);i<=k;i++) { if (cur > tot) puts("1 1"); else { if (tot-cur+1 >= c) { printf("%d ",c); for (int j=1;j<=c;j++) printf("%d ",que[cur++]); puts(""); } else { printf("%d ",tot-cur+1); for (int j=cur;j<=tot;j++) printf("%d ",que[j]); puts(""); } } } return 0; }