网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
acm吧 关注：26,477贴子：48,299
  • 6回复贴，共1页

求助一道题的解法

对于1~N这N个数字，从中任意取两个数字构成对，在考虑顺序的情况下有A(n,2)个数字对。请问如何构建包含所有数字对的序列，同时令序列长度最短？
例如
N=2，数字对有1 2、2 1，则最短序列可以是1 2 1（或2 1 2）
N=3，数字对有1 2、1 3、2 1、2 3、3 1、3 2，则最短序列可以是1 2 1 3 2 3 1


用简洁的话说就是构建一个最短序列，令该序列包含数字1~N的所有有序数字对。
gpt说可以用de Bruijn 序列的思想解决，但它做错了，我也没看出这题和de Bruijn 序列有什么关系


(欧拉路径模板题)
对于任意一个″出入度差不为0的点数(c)为0,或为2且c分别为1/-1″的有向弱联通图,可以线性求出一笔画方案数
原问题可看作每对点间都有一对相向有向边,出入度差都对0,必可一次跑完


好像可以直接构造
设问题为H(n),从点n出发,流程为n对1~n-2都往返一次,再(若有)走到n-1,进行H(n-1),走回来


这是个欧拉回路问题。


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 6回复贴，共1页
分享到: