穿衣搭配的网站？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

穿衣搭配的网站？

穿衣搭配的网站？# Fashion - 美丽时尚

s*m2011-04-30 07:04

1 楼

makefriend，
n个人，每个人都要在其他（n-1)个人中交f个不同的朋友，问所有人都能交且只能交f
个朋友吗（少一个，多一个，都不行）？
比如，makeFriends（n,f）
makeFriends(2,1)=true;
makeFriends(3,1)=false;
makeFriends(3,2)=true;
makeFriends(4,1)=true;
makeFriends(4,2)=true;
因为1,2；1,3；2,4；3,4。这样，每个人就都是2个朋友了

t*e2011-04-30 07:04

2 楼

agent在交而过程中很给力，想买个礼物感谢一下，有啥建议？一两百刀吧！

t*r2011-04-30 07:04

3 楼

我有朋友在国在做一个穿衣搭配的网站，配合卖衣服．
版上jm能推荐一些你们觉得好的网站、商家或者杂志，可供参考么？
先拜谢了

g*o2011-04-30 07:04

4 楼

啥意思？ n*f必须偶数？

c*o2011-04-30 07:04

5 楼

土豪金

s*m2011-04-30 07:04

6 楼

不是吧。
每个人只能且必须交f个朋友。
比如，makeFriends（n,f）
makeFriends(2,1)=true;
makeFriends(3,1)=false;
makeFriends(3,2)=true;
makeFriends(4,1)=true;
makeFriends(4,2)=true;
因为1,2；1,3；2,4；3,4。这样，每个人就都是2个朋友了

【在 g****o 的大作中提到】

: 啥意思？ n*f必须偶数？

G*h2011-04-30 07:04

7 楼

Agent不挣钱吗？应该agent给你买礼物吧。因为你买房子，agent才挣到钱把

【在 t*********e 的大作中提到】

: agent在交而过程中很给力，想买个礼物感谢一下，有啥建议？一两百刀吧！

g*o2011-04-30 07:04

8 楼

我觉得n*f是偶数，并且f否则就是false啊
有反例么？

【在 s*******m 的大作中提到】

: 不是吧。
: 每个人只能且必须交f个朋友。
: 比如，makeFriends（n,f）
: makeFriends(2,1)=true;
: makeFriends(3,1)=false;
: makeFriends(3,2)=true;
: makeFriends(4,1)=true;
: makeFriends(4,2)=true;
: 因为1,2；1,3；2,4；3,4。这样，每个人就都是2个朋友了
:

M*e2011-04-30 07:04

9 楼

同意。

【在 G*****h 的大作中提到】

: Agent不挣钱吗？应该agent给你买礼物吧。因为你买房子，agent才挣到钱把

n*n2011-04-30 07:04

10 楼

题意不清。交朋友有排斥关系吗？

f

【在 s*******m 的大作中提到】

: makefriend，
: n个人，每个人都要在其他（n-1)个人中交f个不同的朋友，问所有人都能交且只能交f
: 个朋友吗（少一个，多一个，都不行）？
: 比如，makeFriends（n,f）
: makeFriends(2,1)=true;
: makeFriends(3,1)=false;
: makeFriends(3,2)=true;
: makeFriends(4,1)=true;
: makeFriends(4,2)=true;
: 因为1,2；1,3；2,4；3,4。这样，每个人就都是2个朋友了

T*e2011-04-30 07:04

11 楼

介绍客人

s*m2011-04-30 07:04

12 楼

举不出反例。
但肯定不能这么做吧，这是一个小时的面试呢。。。

【在 g****o 的大作中提到】

: 我觉得n*f是偶数，并且f: 否则就是false啊
: 有反例么？

y*n2011-04-30 07:04

13 楼

agent从你那争了几千块呢，应该送你礼物，然后你介绍客户。

s*m2011-04-30 07:04

14 楼

什么是排斥关系。

【在 n******n 的大作中提到】

: 题意不清。交朋友有排斥关系吗？
:
: f

M*e2011-04-30 07:04

15 楼

可以给他写正面的review

【在 T****e 的大作中提到】

: 介绍客人

Y*G2011-04-30 07:04

16 楼

如果f是偶数，那就比较容易。把所有的人排成一个圆圈，每个人朋友就是他左边的f/2
个人，右边的f/2个人。
如果f是奇数，则按照上面的方法，可以得到每个人有f-1个朋友的解。然后假设n是偶
数，把所有的人分成男女，男女间隔的排成一个圆圈，按照f-1的思路先每个人有f-1个
朋友。然后每个人必须在不认识的人中找一个异性朋友，问题就解了。
如果f和n都是奇数，则无解。应为n*f/2必须是整数。因为总共的朋友有n*f/2对。

f

【在 s*******m 的大作中提到】

u*q2011-04-30 07:04

17 楼

一封信，谢谢他，顺便问能不能过给些rebate。

k*r2011-04-30 07:04

18 楼

the total degrees of all vertexes in undirected graph should be even number,
so f*n is even is a necessary condition.

y*a2011-04-30 07:04

19 楼

然

【在 u****q 的大作中提到】

: 一封信，谢谢他，顺便问能不能过给些rebate。

s*m2011-04-30 07:04

20 楼

fn是偶数确实个必要条件，
如果follow up是请输出一个解，应该用什么算法呢

number,

【在 k****r 的大作中提到】

: the total degrees of all vertexes in undirected graph should be even number,
: so f*n is even is a necessary condition.

r*42011-04-30 07:04

21 楼

一般是agent给你礼物。

【在 t*********e 的大作中提到】

: agent在交而过程中很给力，想买个礼物感谢一下，有啥建议？一两百刀吧！

n*n2011-04-30 07:04

22 楼

七楼不是给了算法？

【在 s*******m 的大作中提到】

: fn是偶数确实个必要条件，
: 如果follow up是请输出一个解，应该用什么算法呢
:
: number,

l*h2011-04-30 07:04

23 楼

对的。

【在 u****q 的大作中提到】

: 一封信，谢谢他，顺便问能不能过给些rebate。

s*m2011-04-30 07:04

24 楼

没有啊。
下午用bfs试了试
没做出来。
我想输出一个解。

【在 n******n 的大作中提到】

: 七楼不是给了算法？

R*R2011-04-30 07:04

25 楼

你早说呀。
我就忘问了。

【在 u****q 的大作中提到】

: 一封信，谢谢他，顺便问能不能过给些rebate。

w*d2011-04-30 07:04

26 楼

只要f证明：
把每个人看成顶点，好友关系看成边，那么题目要求每个顶点连f条边，那么总共的边
数为：
E = n * f / 2
显然E要是一个整数才行，即nf是偶数。
生成一个例子的算法，可以用greedy：遍历所有顶点，只要边数没达到f，就增加边，
另一头连后面没达到要求的顶点。naive实现为O(f*n^2)复杂度，个人认为可以优化的O
(f*n)。

l*g2011-04-30 07:04

27 楼

不要把agent惯坏了，对大家都不好

【在 t*********e 的大作中提到】

: agent在交而过程中很给力，想买个礼物感谢一下，有啥建议？一两百刀吧！

s*m2011-04-30 07:04

28 楼

关于，生成一个例子的算法
比如1,2,3,4四个人， f=2
用greedy的话，找不到解:
第一步 1和2，1和3
第二部 2和3
然后就结束了，4没有朋友。
但其实是有解的，
1和2,1和3,2和4,3和4；

的O

【在 w*****d 的大作中提到】

: 只要f: 证明：
: 把每个人看成顶点，好友关系看成边，那么题目要求每个顶点连f条边，那么总共的边
: 数为：
: E = n * f / 2
: 显然E要是一个整数才行，即nf是偶数。
: 生成一个例子的算法，可以用greedy：遍历所有顶点，只要边数没达到f，就增加边，
: 另一头连后面没达到要求的顶点。naive实现为O(f*n^2)复杂度，个人认为可以优化的O
: (f*n)。

s*t2011-04-30 07:04

29 楼

我们agent给我们买礼物了。。。

【在 t*********e 的大作中提到】

: agent在交而过程中很给力，想买个礼物感谢一下，有啥建议？一两百刀吧！

g*r2011-04-30 07:04

30 楼

如果要找解法的话可不可以这样：
判断 nf 是不是偶数
base cases:（1）每人只有一个朋友，两两配对
（2）每人有两个朋友，围成一个圈
如果>2个朋友，
以base（2）为起始状态，选择一个node为起点，第一次iteration跳过一个邻居连接两
个node，直到不能再添加edge（没有一个node有超过3个edge）
第二次iteration 跳过两个邻居
。。。
直到每个node有f个outgoing edge

s*a2011-04-30 07:04

31 楼

一般好多client在买房的时候都说什么如果我买下这个房子你送我冰箱或者什么的。。
。。usually他们的potential commission是6%,你买一百万的房子，他能分6万。如果
卖家也用agent的话，那6万他们两个人分。20万的房子的话他也能拿不少。。他送你一
个100-200快的东西应该不成问题吧。。

s*m2011-04-30 07:04

32 楼

试了下您的做法，比如n=8, f=4.
没做出来。
第二次iteration，还剩编号7,8 两个节点，没法达到4个朋友。
贴了一张图。

【在 g*********r 的大作中提到】

: 如果要找解法的话可不可以这样：
: 判断 nf 是不是偶数
: base cases:（1）每人只有一个朋友，两两配对
: （2）每人有两个朋友，围成一个圈
: 如果>2个朋友，
: 以base（2）为起始状态，选择一个node为起点，第一次iteration跳过一个邻居连接两
: 个node，直到不能再添加edge（没有一个node有超过3个edge）
: 第二次iteration 跳过两个邻居
: 。。。
: 直到每个node有f个outgoing edge

a*o2011-04-30 07:04

33 楼

9楼正解啊，因为有联通图的degree是偶数啊，也就是X=N*F, X为偶数就可以啊~~突然
发现最近上上课还是有收获的啊

s*m2011-04-30 07:04

34 楼

现在问题是如何找到一个解。
就是如何构造一个k-regular graph

【在 a*******o 的大作中提到】

: 9楼正解啊，因为有联通图的degree是偶数啊，也就是X=N*F, X为偶数就可以啊~~突然
: 发现最近上上课还是有收获的啊

h*y2011-04-30 07:04

35 楼

数学题吧, n 个节点, 每个节点 n-1个neighbor恒成立。然后剪连接, 直到受影响的节
点覆盖一遍全部。
n为奇数的时候每次减掉两根连接, 因为剪掉一根的话会影响两个节点的度, n奇数不满
足, 减两根覆盖 2* n, 满足。
n为偶数每两个节点间减掉一根, 恒满足。
所以 if n is odd f(n, n + 1 - 2k) = true
always true if n is even.
不知道对不对

s*y2011-04-30 07:04

36 楼

Here is a solution:
http://techinpad.blogspot.com/2015/04/make-friends.html