从来没有过任何marroitt或者spg卡，怎么申比较好？# Money - 海外理财
k*k
1 楼
在墙角的一棵小树下面躲着。我过去倒垃圾，看到几次。有次站起来跑开了。我看到它
的一条后腿折了，不知道有没有什么方法能帮它一下。
的一条后腿折了，不知道有没有什么方法能帮它一下。
s*8
2 楼
一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
复原走的路线。
难点是路线里面可能有Cycle，而且会重复。
比如给的是A-->F
线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
复原结果是 A B C D E B C F
到现在没想明白怎么做，请大神指点
给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
复原走的路线。
难点是路线里面可能有Cycle，而且会重复。
比如给的是A-->F
线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
复原结果是 A B C D E B C F
到现在没想明白怎么做，请大神指点
b*1
3 楼
要在26号前申请么？不太理解为什么大家都很关心26号，是不是对我这种marroitt和
SPG都没有过的无所谓，只要等史高offer就好？谢谢
SPG都没有过的无所谓，只要等史高offer就好？谢谢
j*7
4 楼
赞LZ 善心！ 能否明天问问Vet? 没遇到过。 谢谢你。
h*l
5 楼
topological sorting?
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
h*s
6 楼
你在点数贬值至少25%以后才申请```````
a*5
7 楼
叫911吧 他们有专门那种帮助流浪猫狗 抓蛇的警员的
b*n
8 楼
欧拉路径
b*1
9 楼
没办法，当时觉得反正凑不够大小礼包，就没申。。。。
【在 h****s 的大作中提到】
: 你在点数贬值至少25%以后才申请```````
【在 h****s 的大作中提到】
: 你在点数贬值至少25%以后才申请```````
l*z
10 楼
搜索与回溯
顺着走，走过的就拿开，如果下一步有几种可能，选一个，终止条件是所有的线段都用
掉。走不下去了就回到上一次的选择选没用过的选项，再往下走。
把所有的点map到整数，建一个2维数组就容易查询。
A到F map 成0-5数组如下
1
2 2
3 5
4
1
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
顺着走，走过的就拿开，如果下一步有几种可能，选一个，终止条件是所有的线段都用
掉。走不下去了就回到上一次的选择选没用过的选项，再往下走。
把所有的点map到整数，建一个2维数组就容易查询。
A到F map 成0-5数组如下
1
2 2
3 5
4
1
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
d*n
11 楼
DFS
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
b*n
12 楼
简单写，直接所有线段 permutation，然后验证
优化一下，就是 permute 的时候下一个的起点要和上一个的重点重合，
什么时候碰到能用到所有点得 permute 就搞定了
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
优化一下，就是 permute 的时候下一个的起点要和上一个的重点重合，
什么时候碰到能用到所有点得 permute 就搞定了
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
m*t
13 楼
这东西就是个有向图，而且已经把所有的 edge 给你了。把图建好，然后不管是 DFS 还
是 BFS 都能找到起点到终点的路径（前提是存在）
是 BFS 都能找到起点到终点的路径（前提是存在）
p*6
14 楼
还
最短路径算出来是ABCF，得把DFS改成经过每个点至少一次？
【在 m*********t 的大作中提到】
: 这东西就是个有向图，而且已经把所有的 edge 给你了。把图建好，然后不管是 DFS 还
: 是 BFS 都能找到起点到终点的路径（前提是存在）
m*t
15 楼
忘了这茬子了。试了一下，下面这个东西可以算出来正确的路经，但是如果没有解的话
就死循环了。。。
#include
#include
#include
就死循环了。。。
#include
#include
#include
#include
#include
using namespace std;
unordered_map
int edge_count = 0;
stack
const char beg = 'A';
const char end = 'F';
bool DFS(char w) {
assert(edge_count >= 0);
if (dag.find(w) == dag.end()) {
return false;
}
auto& edges = dag.at(w);
auto itr = edges.begin();
while (itr != edges.end()) {
char v = *itr;
history.push(v);
edges.erase(itr);
--edge_count;
if (v == 'F' && edge_count == 0)
return true;
if (DFS(v)) {
return true;
}
// not successful, add this edge in the back;
// if there is no correct solution the program will loop endlessly...
itr = edges.begin();
history.pop();
edges.emplace_back(v);
++edge_count;
}
}
int main() {
dag['B'].emplace_back('C');
dag['D'].emplace_back('E');
dag['A'].emplace_back('B');
dag['C'].emplace_back('F');
dag['E'].emplace_back('B');
dag['B'].emplace_back('C');
dag['C'].emplace_back('D');
dag['D'].emplace_back('A');
dag['F'].emplace_back('D');
dag['A'].emplace_back('F');
edge_count = 10;
// do a special DFS
history.push(beg);
DFS('A');
while (!history.empty()) {
cout << history.top() << "n";
history.pop();
}
return 0;
}
【在 p****6 的大作中提到】
:
: 还
: 最短路径算出来是ABCF，得把DFS改成经过每个点至少一次？
c*n
16 楼
简单啊。
每个section当做一个vertex, 如果两个section 有一头重合，那就画一条edge,
建好图用任何 path finding algo 都可以 （dfs/bfs/dijstra)
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
每个section当做一个vertex, 如果两个section 有一头重合，那就画一条edge,
建好图用任何 path finding algo 都可以 （dfs/bfs/dijstra)
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
c*y
17 楼
怎么画edge?如果 a→b 和 a→c？还是只画另一头？
【在 c******n 的大作中提到】
: 简单啊。
: 每个section当做一个vertex, 如果两个section 有一头重合，那就画一条edge,
: 建好图用任何 path finding algo 都可以 （dfs/bfs/dijstra)
【在 c******n 的大作中提到】
: 简单啊。
: 每个section当做一个vertex, 如果两个section 有一头重合，那就画一条edge,
: 建好图用任何 path finding algo 都可以 （dfs/bfs/dijstra)
l*s
18 楼
感觉先找到最短的，然后找环接环，找不到最短或剩下不成环的即无解。
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
【在 s********8 的大作中提到】
: 一个俄罗斯口音大叔面的，给完题就开电脑玩自己的不给提示，估计挂了。
: 给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
: 复原走的路线。
: 难点是路线里面可能有Cycle，而且会重复。
: 比如给的是A-->F
: 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
: 复原结果是 A B C D E B C F
: 到现在没想明白怎么做，请大神指点
i*h
19 楼
先统计in degree大于一的所有点，找到从这些点开始的loop并移除。剩下的点就是一
条直线了。然后traverse直线的时候把loop加回去。
条直线了。然后traverse直线的时候把loop加回去。
c*y
20 楼
怎么知道加几个loop和加哪些loop？
【在 i****h 的大作中提到】
: 先统计in degree大于一的所有点，找到从这些点开始的loop并移除。剩下的点就是一
: 条直线了。然后traverse直线的时候把loop加回去。
【在 i****h 的大作中提到】
: 先统计in degree大于一的所有点，找到从这些点开始的loop并移除。剩下的点就是一
: 条直线了。然后traverse直线的时候把loop加回去。
n*n
21 楼
比欧拉路径难。老毛子够狠！
【在 b*****n 的大作中提到】
: 欧拉路径
【在 b*****n 的大作中提到】
: 欧拉路径
c*n
22 楼
if there is given a-->b and a-->c
and x-->a
then define
node 1 == "a->b"
node 2 == "a->c"
node 3 == "x->a"
then the new graph has 3->1, 3->2
【在 c*********y 的大作中提到】
: 怎么画edge?如果 a→b 和 a→c？还是只画另一头？
and x-->a
then define
node 1 == "a->b"
node 2 == "a->c"
node 3 == "x->a"
then the new graph has 3->1, 3->2
【在 c*********y 的大作中提到】
: 怎么画edge?如果 a→b 和 a→c？还是只画另一头？
s*l
23 楼
可不可以这样子？
用unordered_multimap
如果value中有detination && map的size还不是1就跳过
否则就
unordered_multimap (放入结果，并把这个从map中删除) -> (放入结果
，并把这个从map中删除)
。。。
直到 value中有detination && map的size还是1 结束
用unordered_multimap
如果value中有detination && map的size还不是1就跳过
否则就
unordered_multimap (放入结果，并把这个从map中删除) -> (放入结果
，并把这个从map中删除)
。。。
直到 value中有detination && map的size还是1 结束
z*o
24 楼
looks right.
【在 i****h 的大作中提到】
: 先统计in degree大于一的所有点，找到从这些点开始的loop并移除。剩下的点就是一
: 条直线了。然后traverse直线的时候把loop加回去。
【在 i****h 的大作中提到】
: 先统计in degree大于一的所有点，找到从这些点开始的loop并移除。剩下的点就是一
: 条直线了。然后traverse直线的时候把loop加回去。
x*9
25 楼
第一反应是DFS，之后反应了好几次，也还只是DFS。。。
这题有够无聊的话说。。。
这题有够无聊的话说。。。
a*6
26 楼
请问可以具体讲一下么？谢谢啦！
【在 z*******o 的大作中提到】
: looks right.
【在 z*******o 的大作中提到】
: looks right.
d*t
27 楼
RE
【在 d****n 的大作中提到】
: DFS
【在 d****n 的大作中提到】
: DFS
a*6
28 楼
itr = edges.begin();
history.pop();
edges.emplace_back(v);
++edge_count;
}
return false;
}
如上，最后加一个false也不能保证terminate嘛？
【在 m*********t 的大作中提到】
: 忘了这茬子了。试了一下，下面这个东西可以算出来正确的路经，但是如果没有解的话
: 就死循环了。。。
: #include
: #include
: #include
history.pop();
edges.emplace_back(v);
++edge_count;
}
return false;
}
如上，最后加一个false也不能保证terminate嘛？
【在 m*********t 的大作中提到】
: 忘了这茬子了。试了一下，下面这个东西可以算出来正确的路经，但是如果没有解的话
: 就死循环了。。。
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: unordered_map
: int edge_count = 0;
h*p
29 楼
上面有人说了，总结下2种方法（需要建立有向图）
#1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
#1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
相关阅读
Usairway divident mile mastercardwake up john怎么完成？UA Miles Expiration Policy[圣诞活动]2012我在money版的收获Amazon Kindle GC = Amazon GC? how to use?[圣诞活动]我的2012年理财[圣诞活动] 2012年我在money版chase ink 50K算好的开卡promo吗,谢谢有没有人DELL GC还没收到的？rw:Chase Sapphire Prefered 还会有50k么？请问UA里程数怎么积累？请教Roth IRA加个authorized user不pull那个user的credit吧？请教UA补偿AMEX的点数可以转到国泰吗？AMX Hilton HonorAMEX Delta Gold -- 30,000 bonus miles 值得申请吗？Chase freedom cashback是不是也有$75/3mon 的limit了?AMX被关卡的一个小问题【圣诞活动】2011-12小结