首页 > 代码库 > poj 1780 欧拉回路构造字符串
poj 1780 欧拉回路构造字符串
和西安邀请赛D题类似的题目
这道题会爆栈,所以要非递归写,但是看了很久其实代码没理解,回头重写
题解:http://blog.csdn.net/dongshimou/article/details/37815377
http://www.cnblogs.com/372465774y/p/3200775.html
#include <cstdio> #include <cmath> #include <iostream> using namespace std; const int SIZE = 100000+10; int a,s; int sta[SIZE*10],li[SIZE*10]; char ans[SIZE*10]; void sea(int v, int m) { int w; while(li[v]<10) { w=v*10+li[v];//相当于左移一位,就是以前一个数的最后n-1位左移一位作为第二个数的前n-1位 li[v]++; //li[v]范围是0-9,,就是第v位,把各种试过来,并且保证前面没出现过,因为上一行li[v]已经用过,所以试li[v]+1 sta[s++]=w;//sta里存的是答案,注意0表示n-1个0 v=w%m; //移位"溢出" } } int main() { int n,m; while(~scanf("%d", &n) && n) { if(n == 1) { printf("0123456789\n"); continue; } int v=0; s=a=0; m=pow(10.0, double (n-1) ); for(int i=0;i<m;i++)li[i]=0; sea(v, m); while(s) { v=sta[--s]; ans[a++]=v%10+'0'; v/=10; sea(v, m); } for(int i=1; i<n; i++)putchar('0'); while(a)putchar(ans[--a]); putchar('\n'); } return 0; }
poj 1780 欧拉回路构造字符串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。