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 的大作中提到】
: 。。。。。那好吧。。。不和你争了。。。。
|
