kipsora 最近的时间轴更新 kipsora 最近的时间轴更新 | kipsoraV2EX 第 263363 号会员，加入于 2017-10-29 20:46:13 +08:00今日活跃度排名 22896 |
| 想买个 HPE Proliant Microserver Gen10 PLUS 做 NAS 和 GitLab 托管？ 问与答 kipsora 2020-05-04 00:48:32 AM 最后回复来自 my3157 | 20 |
kipsora 最近回复了
30 天前 回复了 chums822 创建的主题 iPhone 最接近满血版的 iPhone 17pro 外版如何选择？ |
一直在用 iPhone Xs 今年好像不得不换了，Sim 卡槽干脆用旧手机解决好了（现在也是这样解决的 iPhone Xs + iPhone 7 ），然后这样只剩下美版和加版，毫米波好像不是那么重要，甚至我觉得都没有需求在手机上跑超过 10MB/s 的网络，但是多出来的 11/21 可以去日本旅游用，感觉我偏向于选加版（当然我人在加拿大有可能会自己骗自己 hhhh ）
2021-12-10 00:38:19 +08:00 回复了 xabcstack 创建的主题 问与答 咨询道友们一个算法问题：输入元素集合，输出特征短元素集合 |
V2 吞我缩进，放这里了 https://pastebin.com/X0hnmw6A
2021-12-10 00:37:24 +08:00 回复了 xabcstack 创建的主题 问与答 咨询道友们一个算法问题：输入元素集合，输出特征短元素集合 |
```python
P = 177
MOD = 192073433
def main():
strings = input().split(",")
string_hashes = []
max_string_length = 0
for string in strings:
hashes = [0]
for i in range(len(string)):
hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
string_hashes.append(hashes)
max_string_length = max(max_string_length, len(string))
pows = [1] # P ** i
for i in range(max_string_length + 1):
pows.append(pows[-1] * P % MOD)
sorted_indices = list(range(len(strings)))
sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))
disabled_hashes = set()
answers = [None for _ in strings]
for i in sorted_indices:
string = strings[i]
hashes = string_hashes[i]
hash_to_be_disabled = []
min_length = len(string) + 1
for x in range(len(string)):
for y in range(x, len(string)):
substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
substr_hash = (substr_hash + MOD) % MOD
hash_to_be_disabled.append(substr_hash)
if substr_hash not in disabled_hashes and min_length > (y - x + 1):
min_length = y - x + 1
answers[i] = (x, y)
disabled_hashes.update(hash_to_be_disabled)
print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))
if __name__ == "__main__":
main()
```
P = 177
MOD = 192073433
def main():
strings = input().split(",")
string_hashes = []
max_string_length = 0
for string in strings:
hashes = [0]
for i in range(len(string)):
hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
string_hashes.append(hashes)
max_string_length = max(max_string_length, len(string))
pows = [1] # P ** i
for i in range(max_string_length + 1):
pows.append(pows[-1] * P % MOD)
sorted_indices = list(range(len(strings)))
sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))
disabled_hashes = set()
answers = [None for _ in strings]
for i in sorted_indices:
string = strings[i]
hashes = string_hashes[i]
hash_to_be_disabled = []
min_length = len(string) + 1
for x in range(len(string)):
for y in range(x, len(string)):
substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
substr_hash = (substr_hash + MOD) % MOD
hash_to_be_disabled.append(substr_hash)
if substr_hash not in disabled_hashes and min_length > (y - x + 1):
min_length = y - x + 1
answers[i] = (x, y)
disabled_hashes.update(hash_to_be_disabled)
print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))
if __name__ == "__main__":
main()
```
2021-12-10 00:32:42 +08:00 回复了 xabcstack 创建的主题 问与答 咨询道友们一个算法问题：输入元素集合，输出特征短元素集合 |
可能说得不是很清楚，花了点时间写了个法 2 的代码：
```python3
P = 177
MOD = 192073433
def main():
strings = input().split(",")
string_hashes = []
max_string_length = 0
for string in strings:
hashes = [0]
for i in range(len(string)):
hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
string_hashes.append(hashes)
max_string_length = max(max_string_length, len(string))
pows = [1] # P ** i
for i in range(max_string_length + 1):
pows.append(pows[-1] * P % MOD)
sorted_indices = list(range(len(strings)))
sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))
disabled_hashes = set()
answers = [None for _ in strings]
for i in sorted_indices:
string = strings[i]
hashes = string_hashes[i]
hash_to_be_disabled = []
min_length = len(string) + 1
for x in range(len(string)):
for y in range(x, len(string)):
substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
substr_hash = (substr_hash + MOD) % MOD
hash_to_be_disabled.append(substr_hash)
if substr_hash not in disabled_hashes and min_length > (y - x + 1):
min_length = y - x + 1
answers[i] = (x, y)
disabled_hashes.update(hash_to_be_disabled)
print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))
if __name__ == "__main__":
main()
```
输入：dev1,dev2,dev3,v3a,abc,bc
输出：d,2,ev3,v,ab,b
输入：abcabc,a,ab,abc,abca,abcab
输出：cabc,a,b,c,ca,cab
输入：a,aa,aaa,aaaa,aaaaa,aaaaaa
输出：a,aa,aaa,aaaa,aaaaa,aaaaaa
输入：ab,cd,abc,cde,abcd,cdab,cdabb,cac,cab,cacd
输出：a,c,bc,e,bcd,da,bb,ca,cab,acd
```python3
P = 177
MOD = 192073433
def main():
strings = input().split(",")
string_hashes = []
max_string_length = 0
for string in strings:
hashes = [0]
for i in range(len(string)):
hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
string_hashes.append(hashes)
max_string_length = max(max_string_length, len(string))
pows = [1] # P ** i
for i in range(max_string_length + 1):
pows.append(pows[-1] * P % MOD)
sorted_indices = list(range(len(strings)))
sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))
disabled_hashes = set()
answers = [None for _ in strings]
for i in sorted_indices:
string = strings[i]
hashes = string_hashes[i]
hash_to_be_disabled = []
min_length = len(string) + 1
for x in range(len(string)):
for y in range(x, len(string)):
substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
substr_hash = (substr_hash + MOD) % MOD
hash_to_be_disabled.append(substr_hash)
if substr_hash not in disabled_hashes and min_length > (y - x + 1):
min_length = y - x + 1
answers[i] = (x, y)
disabled_hashes.update(hash_to_be_disabled)
print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))
if __name__ == "__main__":
main()
```
输入：dev1,dev2,dev3,v3a,abc,bc
输出：d,2,ev3,v,ab,b
输入：abcabc,a,ab,abc,abca,abcab
输出：cabc,a,b,c,ca,cab
输入：a,aa,aaa,aaaa,aaaaa,aaaaaa
输出：a,aa,aaa,aaaa,aaaaa,aaaaaa
输入：ab,cd,abc,cde,abcd,cdab,cdabb,cac,cab,cacd
输出：a,c,bc,e,bcd,da,bb,ca,cab,acd
2021-12-09 11:34:41 +08:00 回复了 xabcstack 创建的主题 问与答 咨询道友们一个算法问题：输入元素集合，输出特征短元素集合 |
待会要说复杂度这里先定义一些变量吧：假设我们有 n 个字符串，最长长度不超过 m ，假设这个集合不是可重集合
按长度对于从小到大考虑每个字符串。假设当前考虑字符串是 s_i ，那么现在的问题就变成了，找到 s_i 的最短字串 t 使得 t 不是 s_1 到 s_{i-1} 中任何一个字符串的字串。这个问题按照从最暴力到比较聪明的方式我大概想到了如下几种做法：
1. 直接暴力枚举每个串的特征串，这样每个串有 O(m^2) 个字串，每个字串放到前面 i-1 个字串里面跑 KMP ，需要 O(n^2m^3)（或者 O(n^2m^4) 如果直接调用朴素字符串匹配的话），楼主你这个数据量比较小这样 1 秒内应该能出结果；
2. 可以预处理每个串的 Hash ，这样我们枚举出字串之后就可以快速判断一个串是否是之前某个串的字串，注意这里计算 Hash 的方式应该是先通过计算前缀 Hash 然后计算得到子串 Hash ，这样判断字串是否存在是 O(1) 的（方法 1 是 O(m)的），这样总复杂度降低到了 O(nm^2)，关于前缀和字符串 Hash 的可以参考这里 https://blog.csdn.net/SHU15121856/article/details/109553503
3. 一个比较直观的发现是如果 s_i 的某个子串 t 不能成为 s_i 的特征，那么 t 的子串也一定不行。所以我们不用暴力枚举字串，改用双指针的做法，假设当前枚举的子串 t 的左端点是 x ，右端点是 y ，一开始 x = y = 1 （这里我是 1-based ），一开始定住 x 不动，看看 s_i[x..y] 是不是可以成为特征串，如果不行那么 y++ 直到可以。找到可以的串之后 x++，然后重复以上步骤直到 x 扫到 s_i 的最后一个字符。因此在查询完双指针表示的子串之后，只有两种可能，要么 x++ 要么 y++，所以这样最多只会有 O(m) 个子串需要查询，看起来好像我们现在达到了 O(nm) 的复杂度，但其实不然，如果按照方法 2 处理 Hash ，我们预处理的复杂度就达到了 O(nm^2)，所以总复杂度还是 O(nm^2) 的。
这里如果想要进一步优化可以上使用后缀三兄弟（后缀数组 /后缀树 /后缀自动机）：比如先对所有串建立广义后缀自动机（复杂度 O(nm)），每次 y++ 的时候直接看看 s[y] 能否在后缀自动机上走下去，走不下去了就 x++ 然后 Fail 边跳一下。这样总复杂度能做到 O(nm) 即输入复杂度。
不知道题主需要什么程度的复杂度，但 2 应该是足够用了，3 应该是竞赛题中的做法
按长度对于从小到大考虑每个字符串。假设当前考虑字符串是 s_i ，那么现在的问题就变成了，找到 s_i 的最短字串 t 使得 t 不是 s_1 到 s_{i-1} 中任何一个字符串的字串。这个问题按照从最暴力到比较聪明的方式我大概想到了如下几种做法：
1. 直接暴力枚举每个串的特征串，这样每个串有 O(m^2) 个字串，每个字串放到前面 i-1 个字串里面跑 KMP ，需要 O(n^2m^3)（或者 O(n^2m^4) 如果直接调用朴素字符串匹配的话），楼主你这个数据量比较小这样 1 秒内应该能出结果；
2. 可以预处理每个串的 Hash ，这样我们枚举出字串之后就可以快速判断一个串是否是之前某个串的字串，注意这里计算 Hash 的方式应该是先通过计算前缀 Hash 然后计算得到子串 Hash ，这样判断字串是否存在是 O(1) 的（方法 1 是 O(m)的），这样总复杂度降低到了 O(nm^2)，关于前缀和字符串 Hash 的可以参考这里 https://blog.csdn.net/SHU15121856/article/details/109553503
3. 一个比较直观的发现是如果 s_i 的某个子串 t 不能成为 s_i 的特征，那么 t 的子串也一定不行。所以我们不用暴力枚举字串，改用双指针的做法，假设当前枚举的子串 t 的左端点是 x ，右端点是 y ，一开始 x = y = 1 （这里我是 1-based ），一开始定住 x 不动，看看 s_i[x..y] 是不是可以成为特征串，如果不行那么 y++ 直到可以。找到可以的串之后 x++，然后重复以上步骤直到 x 扫到 s_i 的最后一个字符。因此在查询完双指针表示的子串之后，只有两种可能，要么 x++ 要么 y++，所以这样最多只会有 O(m) 个子串需要查询，看起来好像我们现在达到了 O(nm) 的复杂度，但其实不然，如果按照方法 2 处理 Hash ，我们预处理的复杂度就达到了 O(nm^2)，所以总复杂度还是 O(nm^2) 的。
这里如果想要进一步优化可以上使用后缀三兄弟（后缀数组 /后缀树 /后缀自动机）：比如先对所有串建立广义后缀自动机（复杂度 O(nm)），每次 y++ 的时候直接看看 s[y] 能否在后缀自动机上走下去，走不下去了就 x++ 然后 Fail 边跳一下。这样总复杂度能做到 O(nm) 即输入复杂度。
不知道题主需要什么程度的复杂度，但 2 应该是足够用了，3 应该是竞赛题中的做法
2020-09-08 04:03:22 +08:00 回复了 zxCoder 创建的主题 问与答 关于 Online Judge 判题沙箱的学习问题 |
参考一下 VFleaKing 的 UOJ 的沙箱？我很久之前自己仿(chao)造(xie)了一个，docker 可能没办法很好地测量时间和峰值内存吧，自己写隔离肯定不太行，所以比较理想的方案是在 docker 中跑沙箱（或者你对自己的沙箱足够自信也可以不用 docker ）。
具体见： https://github.com/vfleaking/uoj/tree/master/judge_client/1/uoj_judger
不过我觉得从头造轮子这件事，用来学习一下操作系统编程感觉还行，真的要用不如先参考一下市面上有没有现成能拿来用的 OJ，自己写的 OJ 一是你走了之后维护会很麻烦，最后可能也没啥人用。
具体见： https://github.com/vfleaking/uoj/tree/master/judge_client/1/uoj_judger
不过我觉得从头造轮子这件事，用来学习一下操作系统编程感觉还行，真的要用不如先参考一下市面上有没有现成能拿来用的 OJ，自己写的 OJ 一是你走了之后维护会很麻烦，最后可能也没啥人用。
2020-09-03 13:28:21 +08:00 回复了 LMuyi 创建的主题 NVIDIA 6.1 入的 1.1W 2080ti O11G |
换个思路，现在再入一块 2080Ti 就可以平衡损失了（狗头
2020-05-03 13:20:10 +08:00 回复了 SouthCityCowBoy 创建的主题 问与答 IPS 硬屏的抗压程度如何? |
用显示器测试的网站看看有没有坏点之类的？我觉得如果肉眼看不出来真的没有必要纠结，毕竟背板漏光给你带来的影响可能会更大。我自己有台 LG UL850，我偶尔会不小心用指甲或者笔记本的金属边框划到两下屏幕但并没有任何划痕，希望能给你些参考
2020-05-03 13:05:18 +08:00 回复了 kipsora 创建的主题 问与答 想买个 HPE Proliant Microserver Gen10 PLUS 做 NAS 和 GitLab 托管？ |
@glasswm 谢谢你的经验，我觉得我跟你的 case 应该挺像的。请问一下你的 NAS 用的是啥？黑群？ FreeNAS ？
2020-05-03 13:03:20 +08:00 回复了 kipsora 创建的主题 问与答 想买个 HPE Proliant Microserver Gen10 PLUS 做 NAS 和 GitLab 托管？ |
@hanqi7012 我发现群晖某些产品用的是 ARM 的 CPU，我之前在树莓派上跑 docker 很多镜像都不能在 ARM 上跑。。
Select Language