d********g 发帖数: 10550 | 1 非死不可鸡血杯前20名,2个Java,1个Python,其余全是C/C++
https://www.facebook.com/hackercup/scoreboard?round=185564241586420&page=1
老话说得好:少壮不努力,老大只会Java/Python……
数据结构的思维训练,还是C/C++口味更重 |
p*****2 发帖数: 21240 | 2
这个不对吧?
【在 d********g 的大作中提到】 : 非死不可鸡血杯前20名,2个Java,1个Python,其余全是C/C++ : https://www.facebook.com/hackercup/scoreboard?round=185564241586420&page=1 : 老话说得好:少壮不努力,老大只会Java/Python…… : 数据结构的思维训练,还是C/C++口味更重
|
l*******b 发帖数: 2586 | 3 能混过下一轮就满意了,哈哈
解答居然没有提O(k) solution... |
p*****2 发帖数: 21240 | 4
你应该没问题呀。看你实力蛮强的。
【在 l*******b 的大作中提到】 : 能混过下一轮就满意了,哈哈 : 解答居然没有提O(k) solution...
|
l*******b 发帖数: 2586 | 5 新手上路,新手上路.还是搞ACM的大牛厉害
【在 p*****2 的大作中提到】 : : 你应该没问题呀。看你实力蛮强的。
|
p*****2 发帖数: 21240 | 6
你怎么没有用scala做呢?
【在 l*******b 的大作中提到】 : 新手上路,新手上路.还是搞ACM的大牛厉害
|
l*******b 发帖数: 2586 | 7 着急了还是用得最习惯的,写得顺手些.
poj那里的题做两个就做不动了,不费力气了,搞不定,嗯
话说 ide哪个好用点,熟悉熟悉.一直以来都是用vim的,发现ide的自动import 库啊,检
查错误什么貌似也挺好的.大约参与project一定得会用吧?
【在 p*****2 的大作中提到】 : : 你怎么没有用scala做呢?
|
p*****2 发帖数: 21240 | 8
干嘛那么着急呀?不是72小时吗?可以慢慢做呀。
我用eclipse,好像没什么很好用的IDE for scala。这点确实不爽。我调试还是要
print out出来才行。不过无所谓了下次24小时估计也不用太着急。如果运气好进去,
下一轮很可能裸奔,用什么区别不大。你数学功底好,希望大大的。
【在 l*******b 的大作中提到】 : 着急了还是用得最习惯的,写得顺手些. : poj那里的题做两个就做不动了,不费力气了,搞不定,嗯 : 话说 ide哪个好用点,熟悉熟悉.一直以来都是用vim的,发现ide的自动import 库啊,检 : 查错误什么貌似也挺好的.大约参与project一定得会用吧?
|
l*******b 发帖数: 2586 | 9 有道理,周末试试用scala
下个eclipse研究下, 下那个classic就好用吧? |
p*****2 发帖数: 21240 | 10
好像下普通的就可以了。然后需要安装scala插件。或者你去scala plugin的网站看看
,他上边说了支持什么版本的eclipse
【在 l*******b 的大作中提到】 : 有道理,周末试试用scala : 下个eclipse研究下, 下那个classic就好用吧?
|
|
|
l*******b 发帖数: 2586 | 11 好, 去看一看. vim那个scala插件缩进貌似一直有问题,也没人维护
【在 p*****2 的大作中提到】 : : 好像下普通的就可以了。然后需要安装scala插件。或者你去scala plugin的网站看看 : ,他上边说了支持什么版本的eclipse
|
s*****n 发帖数: 5488 | 12 应该说只有C/C++显得蛋疼去参加怎么杯。
java牛人都去搞架构了。
ruby牛人都去做网站,创业去了。
android/objective c牛人都去写app了。
只有C/C++太底层,写写算法吧。
但是真的有时间,去做做生活中的图论吧,比如公交换乘,C/C++又干不了,因为数据
处理太麻烦还要上python, ruby什么的。
所以无聊的只有去参加facebook杯了。
【在 d********g 的大作中提到】 : 非死不可鸡血杯前20名,2个Java,1个Python,其余全是C/C++ : https://www.facebook.com/hackercup/scoreboard?round=185564241586420&page=1 : 老话说得好:少壮不努力,老大只会Java/Python…… : 数据结构的思维训练,还是C/C++口味更重
|
f*******t 发帖数: 7549 | |
f*******t 发帖数: 7549 | 14 C/C++性能稳定,用于竞赛比较合适。我用Java写了一个线段树的题,算法照搬网上的
解题报告,提交上去就是TLE。
生活中的问题,至少图形学全靠C++,还是用途很多的。
【在 s*****n 的大作中提到】 : 应该说只有C/C++显得蛋疼去参加怎么杯。 : java牛人都去搞架构了。 : ruby牛人都去做网站,创业去了。 : android/objective c牛人都去写app了。 : 只有C/C++太底层,写写算法吧。 : 但是真的有时间,去做做生活中的图论吧,比如公交换乘,C/C++又干不了,因为数据 : 处理太麻烦还要上python, ruby什么的。 : 所以无聊的只有去参加facebook杯了。
|
p*****2 发帖数: 21240 | 15
我感觉也是性能的原因。
【在 f*******t 的大作中提到】 : C/C++性能稳定,用于竞赛比较合适。我用Java写了一个线段树的题,算法照搬网上的 : 解题报告,提交上去就是TLE。 : 生活中的问题,至少图形学全靠C++,还是用途很多的。
|
a********m 发帖数: 15480 | 16 问题是这个不是o(k)而是o(k^2)。。。。在flag[k]里面用for()查找是o(k).
【在 f*******t 的大作中提到】 : 貌似出题的人都不知道有O(k)解法。 : 贴下我的Java代码,时间空间都是O(k),写得比较烂大牛们不要喷 : http://dragon.ak.fbcdn.net/cfs-ak-ash3/676445/743/3271878740576 : 另外找到一个完美的C++版本: : http://dragon.ak.fbcdn.net/cfs-ak-ash3/676392/409/4747196459184
|
a********m 发帖数: 15480 | 17 主要这种纯算法的东西其他语言没啥好处,c++更方便,复杂度好控制。
【在 p*****2 的大作中提到】 : : 我感觉也是性能的原因。
|
p*****2 发帖数: 21240 | 18 是 尤其是性能critical的时候 不过不是所有题那么强调性能 黑客杯就不是那么强调
【在 a********m 的大作中提到】 : 主要这种纯算法的东西其他语言没啥好处,c++更方便,复杂度好控制。
|
a********m 发帖数: 15480 | 19 嗯,比赛题问题不大,所以一般各种语言都没问题。
就是怕某些特别数据结构复杂度不明确,特定情况下有点担心,比如需要map<>的时候c
++可以根据情况选hash或者bst,别的语言就不一定能确定自己在用什么了。
【在 p*****2 的大作中提到】 : 是 尤其是性能critical的时候 不过不是所有题那么强调性能 黑客杯就不是那么强调
|
p*****2 发帖数: 21240 | 20 java scala 应该都可以 ruby python就不好说了 感觉c 其实对java优势不大 对于黑
客杯来说 可能对于acm优势就大了 那帮人也习惯了
【在 a********m 的大作中提到】 : 嗯,比赛题问题不大,所以一般各种语言都没问题。 : 就是怕某些特别数据结构复杂度不明确,特定情况下有点担心,比如需要map<>的时候c : ++可以根据情况选hash或者bst,别的语言就不一定能确定自己在用什么了。
|
|
|
f*******t 发帖数: 7549 | 21 trick在于flag[]只会扫描一遍,所以是O(k)
【在 a********m 的大作中提到】 : 问题是这个不是o(k)而是o(k^2)。。。。在flag[k]里面用for()查找是o(k).
|
p*****2 发帖数: 21240 | 22
你的trick是不是跟我的trick差不多呢?我加了一个小trick程序飞快
【在 f*******t 的大作中提到】 : trick在于flag[]只会扫描一遍,所以是O(k)
|
l*******b 发帖数: 2586 | 23 http://fbcdn-dragon-a.akamaihd.net/cfs-ak-ash3/676637/73/401964
对的,找空位这个操作一直向上,向下只有一种情况,就是之前的第k个数被wrap过来了
数组最终是0到k这k+1个数的一个排列, 所以hash table用一个0到k的数组就实现了,不
需要用map
【在 f*******t 的大作中提到】 : trick在于flag[]只会扫描一遍,所以是O(k)
|
p*****2 发帖数: 21240 | 24
貌似跟我的实现一致吧。
【在 l*******b 的大作中提到】 : http://fbcdn-dragon-a.akamaihd.net/cfs-ak-ash3/676637/73/401964 : 对的,找空位这个操作一直向上,向下只有一种情况,就是之前的第k个数被wrap过来了 : 数组最终是0到k这k+1个数的一个排列, 所以hash table用一个0到k的数组就实现了,不 : 需要用map
|
l*******b 发帖数: 2586 | 25 嗯, 一样的
【在 p*****2 的大作中提到】 : : 貌似跟我的实现一致吧。
|
a********m 发帖数: 15480 | 26 没区别。worst case o(k)不是o(1)。r和k接近的时候空闲位置只有几个,所以隔几个
数字必然从头扫。这个trick俺也有,比每次从零开始扫快几倍,但是肯定没有复杂度
变化。
【在 l*******b 的大作中提到】 : http://fbcdn-dragon-a.akamaihd.net/cfs-ak-ash3/676637/73/401964 : 对的,找空位这个操作一直向上,向下只有一种情况,就是之前的第k个数被wrap过来了 : 数组最终是0到k这k+1个数的一个排列, 所以hash table用一个0到k的数组就实现了,不 : 需要用map
|
l*******b 发帖数: 2586 | 27 嗯? 大部分都没扫描, 而就是之前第k个那个元素本身
扫描是从0到k填数字也是0到k,一共2k步,不区分worst case. 都一样吧
【在 a********m 的大作中提到】 : 没区别。worst case o(k)不是o(1)。r和k接近的时候空闲位置只有几个,所以隔几个 : 数字必然从头扫。这个trick俺也有,比每次从零开始扫快几倍,但是肯定没有复杂度 : 变化。
|
m****t 发帖数: 2329 | |
a********m 发帖数: 15480 | 29 每一个都需要扫,是k*k不是k+k吧。
【在 l*******b 的大作中提到】 : 嗯? 大部分都没扫描, 而就是之前第k个那个元素本身 : 扫描是从0到k填数字也是0到k,一共2k步,不区分worst case. 都一样吧
|
f*******t 发帖数: 7549 | 30 我的代码写的不对,给的那个“完美C++版”也不对。
等下班了我改成不用从头扫
【在 a********m 的大作中提到】 : 每一个都需要扫,是k*k不是k+k吧。
|
|
|
a********m 发帖数: 15480 | 31 好吧,到时候看看。俺能想到klgk,但是想不出来k怎么做。
【在 f*******t 的大作中提到】 : 我的代码写的不对,给的那个“完美C++版”也不对。 : 等下班了我改成不用从头扫
|
f*******t 发帖数: 7549 | 32 看了下,发现删一行就够了。pre是单调递增的,不会超过k
private long getNextMin(long[] map, long start, long k) {
while (map[(int)(start)] > 0)
start++;
return start;
}
public long findNth(long n, long k, long a, long b, long c, long r) {
long[] cache = new long[100010];
long[] map = new long[100010];
long pre = a;
for (int i = 0; i < k; i++) {
long num;
if (i == 0)
num = a;
else
num = (b * pre + c) % r;
cache[i] = num;
if (num <= k + 1)
map[(int) num]++;
pre = num;
}
pre = getNextMin(map, 0, k);
cache[(int)k] = pre;
map[(int)pre]++;
for (int i = 0; i <= k; i++) {
long deque = cache[i];
if (deque > k) {
long x = getNextMin(map, pre, k);
cache[i] = x;
map[(int)x]++;
pre = x;
} else {
if (deque < pre && map[(int)deque] == 1) {
cache[i] = deque;
continue;
}
map[(int)deque]--;
long x = getNextMin(map, pre, k);
cache[i] = x;
pre = x;
map[(int)x]++;
}
}
return cache[(int)((n - 1) % (k + 1))];
}
【在 a********m 的大作中提到】 : 好吧,到时候看看。俺能想到klgk,但是想不出来k怎么做。
|
a********m 发帖数: 15480 | 33 。。。。。。删了那行就计算错误了。。。
【在 f*******t 的大作中提到】 : 看了下,发现删一行就够了。pre是单调递增的,不会超过k : private long getNextMin(long[] map, long start, long k) { : while (map[(int)(start)] > 0) : start++; : return start; : } : : public long findNth(long n, long k, long a, long b, long c, long r) { : long[] cache = new long[100010]; : long[] map = new long[100010];
|
f*******t 发帖数: 7549 | 34 我专门重新下载test case测过了,没错的
【在 a********m 的大作中提到】 : 。。。。。。删了那行就计算错误了。。。
|
a********m 发帖数: 15480 | 35 。。。。。那好吧。。。不和你争了。。。。
【在 f*******t 的大作中提到】 : 我专门重新下载test case测过了,没错的
|
l*******b 发帖数: 2586 | 36 我还是觉得我那个是线性,嗯...
【在 a********m 的大作中提到】 : 。。。。。那好吧。。。不和你争了。。。。
|
f*******t 发帖数: 7549 | 37 晕,程序对就是对,错就是错,怎么叫争。。。
【在 a********m 的大作中提到】 : 。。。。。那好吧。。。不和你争了。。。。
|