见过这么轴的狗么！？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

见过这么轴的狗么！？

见过这么轴的狗么！？# pets - 心有所宠

r*e2013-09-23 07:09

1 楼

https://code.google.com/codejam/contest/4214486/dashboard#s=p1
有什么好的思路没有

c*u2013-09-23 07:09

2 楼

我家大傻妞，就玩儿一个牌子，一个形状的玩具。其他的一概不碰。这都换了几个了啊
～～～
还好target竟然有货了，不然每次都要网上定。还要付运费。。。

r*e2013-09-23 07:09

3 楼

我的思路就是模拟倒的过程
每个酒杯溢出部分就3等分的给它下方的三个酒杯
但是结果不对，是不是少考虑了什么

K*a2013-09-23 07:09

4 楼

很专一，很好嘛～～

r*e2013-09-23 07:09

5 楼

我用BFS，但是结果不对

c*u2013-09-23 07:09

6 楼

我能说伊是死心眼儿么～～

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

: 很专一，很好嘛～～

r*32013-09-23 07:09

7 楼

可以计算第i层每个酒杯占了从上一层多出来的酒的几分之几
比如第四层
1，7，10 分别占了1/18
2，3，4，6，8，9分别占了2/18
5占了3/18
p.s. 刷Google code jam的题对g的面试有多大帮助？有出现原题的情况吗

r*a2013-09-23 07:09

8 楼

专一，有长性，给她娘省钱
是啥玩具啊？

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

: 我家大傻妞，就玩儿一个牌子，一个形状的玩具。其他的一概不碰。这都换了几个了啊
: ～～～
: 还好target竟然有货了，不然每次都要网上定。还要付运费。。。

r*e2013-09-23 07:09

9 楼

double bfs(double volum, int level, int num){
map > shack;
shack[0][0] = volum;
queue > Q;
Q.push(make_pair(0,0));
while(!Q.empty()){
pair p = Q.front();
Q.pop();
if(p.first == level && p.second == num){
return min(shack[p.first][p.second],G);
}
if(shack[p.first][p.second] <= G) continue;
double left = shack[p.first][p.second]-G; left /= 3.0f;
shack[p.first][p.second] = G;
if(shack[p.first+1].count(p.second) == 0){
Q.push(make_pair(p.first+1, p.second));
}
shack[p.first+1][p.second] += left;
if(shack[p.first+1].count(p.second+p.first+1) == 0){
Q.push(make_pair(p.first+1, p.second+p.first+1));
}
shack[p.first+1][p.second+p.first+1] += left;
if(shack[p.first+1].count(p.second+p.first+2) == 0){
Q.push(make_pair(p.first+1, p.second+p.first+2));
}
shack[p.first+1][p.second+p.first+2] += left;
}
return 0.0f;
}

c*u2013-09-23 07:09

10 楼

我得回家看看去。。。
说来都好笑，我们头一个这样的玩具是在公园里捡的。

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

: 专一，有长性，给她娘省钱
: 是啥玩具啊？

r*e2013-09-23 07:09

11 楼

上面的code是错误的

s*m2013-09-23 07:09

12 楼

好聪明啊，狗娃的意思是咱别花自己钱，公园里拣去就好了。话说轴是哪里的方言？

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

: 我得回家看看去。。。
: 说来都好笑，我们头一个这样的玩具是在公园里捡的。

m*22013-09-23 07:09

13 楼

这个题应该是四个题里面最简单的呢。
就是简单的模拟一下就可以了。一层一层地流。
下面的代码可以过large
https://github.com/Linzertorte/test/blob/master/GoogleAPAC_B/B.cpp

c*u2013-09-23 07:09

14 楼

问题是上哪儿每次都能捡着一模一样的啊？还不是得后妈花钱买。。
轴我也不知道是哪里方言。意思明白就好～～

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

: 好聪明啊，狗娃的意思是咱别花自己钱，公园里拣去就好了。话说轴是哪里的方言？

r*e2013-09-23 07:09

15 楼

我另外三个都过了，就这道搞不懂
最不理解的就是
double over = (a[i][j]-250)/3.0;
a[i][j] = 250;
b[i][j] += over;
b[i+1][j] += over;
b[i+1][j+1] += over;
为什么是从a[i][j]到
b[i][j]
b[i+1][j]
b[i+1][j+1]

m*f2013-09-23 07:09

16 楼

多好啊，这么专一～～

r*e2013-09-23 07:09

17 楼

这个二维矩阵行列的含义是什么呢？

r*a2013-09-23 07:09

18 楼

不坏就不用花钱买新的呀

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

: 问题是上哪儿每次都能捡着一模一样的啊？还不是得后妈花钱买。。
: 轴我也不知道是哪里方言。意思明白就好～～

m*22013-09-23 07:09

19 楼

Level 2:
1
2 3
这们一个level跟杨辉三角一样的布局。你可以放到二维数组里
但是要左边对齐
即
1
2 3
4 5 6
这样就很容易找到下一层touch他的三个杯子。

k*e2013-09-23 07:09

20 楼

轴是神马意思嘛！
连个脸都不露的。。

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

m*22013-09-23 07:09

21 楼

另外搭车问一下第四题large怎么过。四个题里就这个不会。

c*u2013-09-23 07:09

22 楼

总坏呀～

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

: 不坏就不用花钱买新的呀

r*e2013-09-23 07:09

23 楼

好吧，我明白你的意思了
第4题括号匹配是一个Catalan Number的问题
你看下http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics里面有个浅蓝色的图
就是有箭头的那张，每个向右的箭头对应一个‘（’，每个向上的箭头对应一个‘）’
,同时要满足任何时候'（'的数量>=')'的数量
所以递推式就是 f(i,j) = (j-1>=i?f(i,j-1):0) + （i-1>=0?f(i-1,j):0),其中i是
行，j是列,行对应‘）’，列对应‘（’
算完整个矩阵后，n对括号，第k大的问题就是从f(n,n)开始往f(0,0)走，走的过程中比
较f(i,j)和k的关系，从而决定该往下走，还是往左走，同时加上括号，如果当前在(i,
j）的位置，如果i-1>=0&&f(i-1,j)>=k,就向下走同时加一个'(',否则向左走同时加一
个‘）’，并且更新k-=f(i-1,j)

c*u2013-09-23 07:09

24 楼

：P

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

: 多好啊，这么专一～～

c*u2013-09-23 07:09

25 楼

PU妈俺错了，今天回家就给伊照相去。
轴，就是二，就是一根筋，就是冥顽不化，就是stubborn。

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

: 轴是神马意思嘛！
: 连个脸都不露的。。

k*e2013-09-23 07:09

26 楼

等皂片！

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

: PU妈俺错了，今天回家就给伊照相去。
: 轴，就是二，就是一根筋，就是冥顽不化，就是stubborn。