【水】做题家每天做题碎碎念

因为被陆老师嫌弃了，开个水贴每次做题的时候抱怨一下自己有多弱智
【引用自 Lunasol】:
NG找工投简历记录贴
a老师你该开个力扣贴了 在划水人的帖子里下面奋斗 想隐藏了
为什么要做题：

规则：

为了不浪费生命，除了DP以外的题瞪眼5分钟找不到最优解思路直接写暴力+看题解

由于leetcode数据弱，能用暴力解决的不浪费太多生命写优化算法

心里没底或者懒了用python，否则用c++

感觉自己太笨了，怎么办

广告：

\color{red}征友，\color{blue}希望可以婚绿\color{orange}130

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

广告2：
【引用自 未知】:
公司印度烂校硕士去年十几个烙印互相挂名灌水十几篇文章，快速生成上百citation，还有印度媒体报道，吹自己搞的模型性能堪比 llama 2，今年申EB1A了，妥妥的game the system！ 征集伙伴组队灌水文章，重点deep learning 和 LLM 应用，有没有感兴趣的？目的是一两年内fill EB1A！从自己擅长出发，提供idea，交叉领域，coding，写文章，做实验，合作共…
【引用自 ATF】:
NG找工投简历记录贴
circle jerk time
每天睡觉前，他都要默诵“知足常乐，老天厚爱，你已功成名就，睡觉”；早晨醒来，再激励自己继续“奋斗”，默诵“不知足常进取，功名就在前边，努力前行”。

支持 一起刷题 一起进步

今天是一道签到题级别的分治，我却需要看一眼（非官方）题解才能想出平均nlogn思路

我已经彻底是个傻逼了

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs

（题解显然不是分治）

先拉黑魔芋大师

amex什么鬼

为什么要抛弃 cf 刷 lc……

刷 kattis 也比刷 lc 快乐啊……

这个题有点难啊，如果path定义为必须经过root还好一些，现在不经过root来计算path，每对nodes都要找到common parent才行，这样复杂度立刻就上去了。还没想到一个好解法。

【引用自 aqua】:
为什么要抛弃 cf 刷 lc
要努力找工作而且cf时间实在太阴间，准备去打洛谷的比赛
【引用自 aqua】:
kattis
不好的回忆，悲
【引用自 雨过天晴】:
每对nodes都要找到common parent才行
从父节点找左右子树的叶子节点配对

我没想清楚每个节点代表什么，感觉上可以存当前节点下面的leaf和distance，但没想清楚如何汇总，以及如何去重

明天再看看吧

插眼zszs

https://www.luogu.com.cn/problem/B3785

T1: b-c<0 显然会向下而不是向上取整，随便找一个符合条件的输入，秒了

T2: 题干说

需要注意的是，刷新缓冲区是一件速度很慢的事情，如果刷新次数太多，会导致程序超时。

直接输出1e5个std::cerr造tle，秒了
program nitan(output);

var i : integer;
var t: integer;

begin
readln(t);
if t=1 then writeln('69 4 20')
else begin
writeln('19999');
for i := 1 to 19999 do writeln('std::cerr');
end;
end.

今天做了两道题了，明天的题如果难的话就摸鱼

太自律了，谭友个个身怀绝技还不断进步

看了一眼

10秒钟后，尼玛这是medium，怎么感觉是hard呢……

【引用自 收束观测者】:
尼玛这是medium
因为转化成朴素的图然后从每个叶子节点BFS这种暴力到不敢想的算法是题解1，而且可以过全部样例AC
【引用自 ATF】:
leetcode数据弱

这玩意儿一眼直觉上去就是DP

DP = Hard

Q.E.D.

再次尝到了不读题的后果

脑仁疼 lz你施法了吗

想了一会儿

貌似这样就可以了：

后续遍历
对每个节点生成2个数组，分别对应当前节点的左子树和右子树，数组记录【距离当前节点距离为n的子树叶片数】n为数组index
遍历完一个节点后可以清除其所有子节点的数组，所以空间是log(n)
【引用自 ATF】:
我写的空间O(n)的算法，我是sb
又想了一下我这么搞空间不是log(n)，因为遍历右树时候左子节点的数组是保留在那里的。所以一直遍历到右树最右叶片的时候整个枝上每一层都留着左子节点的信息。加起来应该还是O(n)

所以最后还是时间空间都O(n)

我写的空间O(n)的算法，我是sb

【引用自 收束观测者】:
左子节点的数组
遍历右树的时候左树应该已经遍历完了，留下的个数组最大长度O(logn)？

【引用自 ATF】:
（题解显然不是分治）
我也没什么elegant的思路，读了题目两分钟内的第一个想法，就是既然distance 只有10，我可以递归统计每一个node下面距离d的leaf有几个，然后从root开始往下做sum

这样的复杂度就是O(n)，只不过系数会很大，不知道会不会TLE

我当年是买了九章的课的（不是推荐他们卖课）我自己反正总结不出来那些方法，他们总结的真的挺好，上完了前150题都会做差不多。

假设深度为10的完全树

遍历到最右叶时

root的左子数组长度9

最右枝depth=1节点的左子数组长度8

最右枝depth=2节点的左子数组长度7

…

以此类推

全加起来应该是O(n)

PASCAL???

【引用自 vczh】:
不知道会不会TLE
【引用自 ATF】:
因为转化成朴素的图然后从每个叶子节点BFS这种暴力到不敢想的算法是题解1，而且可以过全部样例AC

https://leetcode.com/problems/lucky-numbers-in-a-matrix/

注意到元素唯一，直接时间O(mn)空间O(mn)秒了

打开题解看到空间O(1)算法，瞪眼法无法解决，但有点牛逼

https://www.luogu.com.cn/problem/P10765

莫名其妙爆零，看了题解发现1. 自己的递推公式似乎不总是对 2. 没用long long

我是sb

https://www.luogu.com.cn/problem/P10766

看了题解，还是不怎么会写，自杀了

我很笨，接受现实了

怎么有人的day cnt， cnt每天是真的++的

继续坚持 多亏没寄生在我的高楼里（

别吧陆老师，我做这dp做玉玉了

【引用自 ATF】:
注意到元素唯一，直接时间O(mn)空间O(mn)秒了
不是很明白，你在每一行找一个最小的，然后验证他是不是列里面最大的，那时间肯定是O(mn)空间肯定是O(1)啊。难道是我读错题了？
【引用自 ATF】:
莫名其妙爆零
这一题明显就是二进制，从低到高看见1填1看见2填0，最后+1就是答案了。不知道题目会不会有什么非法数据

这道题瞪眼了几分钟没什么想法，感觉就是找到第一个和最后一个不一样的，然后做出一个修改，让至少一个边缘的数字变对，然后让跟边缘连在一起的数字变对的越多越好，从而缩小范围。如果有多个得分一样的做法的话就DP。我不知道怎么证明这个方法对还是不对

路老师最近挺能撩拨男人们的心弦啊。仅昨天，我就见到两个男的因为你的只言片语和爱答不理而心里抓狂了，哈哈哈哈哈哈哈

楼主一边做洛谷一边做leetcode难道不会人格分裂吗，这两个画风差异这么大

【引用自 vczh】:
然后验证他是不是列里面最大的
我用的哈希，应该是O(m+n)
【引用自 vczh】:
从低到高看见1填1看见2填0
但取决于有没有出现过2一次
【引用自 vczh】:
如果有多个得分一样的做法的话就DP
题解：注意到每个位置最多出现两次操作且每次操作必定是先设01，DP转移方程是朴素的

我这辈子用尽所有智商也注意不到

我已经是个弱智了

【引用自 ATF】:
注意到每个位置最多出现两次操作且每次操作必定是先设01
一开始确实会觉得不明显，你可能会想那我多出来的操作不能是为了把旁边的操作连起来从而减少一次吗？不过很快就会想到，哪怕是为了连起来，那也是放在前面的

接下来就可以去想是不是锥形的操作必然可以被处理成一个底盘上面叠加离散的操作，不过我没有最终证明，只是隐约觉得可以。还是不喜欢用DP

今天脑子转不过来，滑铁卢：

https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums

贪心，没想到思路

https://leetcode.com/problems/find-maximal-uncovered-ranges

简单的区间合并，但是怎么都写不出来

今日运势不好

https://www.luogu.com.cn/problem/P10704?contestId=167433

数论，不会写，下线了，再见家人们

数学题直接不做

https://leetcode.com/problems/build-a-matrix-with-conditions

瞪眼30秒看不出结果，打开标签就写出来了

行和列分别拓扑排序，特判环，然后根据拓扑序决定每个元素的行/列

dfs和拓扑排序写了30分钟，我是sb

但是我觉得难度完全和hard不沾边的

https://www.luogu.com.cn/problem/P1020

毒瘤题，我现在还是没搞懂n log n求LIS的原理是什么，我是SB

不是哥们

几岁了

还做题

脑细胞已经退化了

要刷题的工作一律不找

【引用自 hztravel】:
要刷题的工作一律不找
我也想啊，可惜对我来说选择比较少，我毕竟不能玩RPG线上去亚超杀鱼办EB3，只能当做题家

【引用自 ATF】:
行和列分别拓扑排序，特判环，然后根据拓扑序决定每个元素的行/列
这不就是全连通子图算法，整道题只要O(n)，但是要我默写我一下子也写不出来

这个算法真的是超级有用，以至于我把它做成了一个模板函数扔进去之后就再也没看了，所以早就不记得是什么样子了。举个例子，C++的struct成员的类型不能有环，class的基类不能有环，#include 不能有环，通通走全连通子图

en.wikipedia.org

Kosaraju's algorithm

In computer science, Kosaraju-Sharir's algorithm (also known as Kosaraju's algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same s...

【引用自 ATF】:
我现在还是没搞懂n log n求LIS的原理是什么
不知道什么是LIS，但这道题我下意识就会用DP来写，不过复杂度可能到不了O(nlgn)

你贴的这个算法常数要大一些

我一开始也也以为要莫比乌斯反演，但是这里面没有像样的数论函数，应该还是靠什么根号分块

【引用自 ATF】:
我现在还是没搞懂n log n求LIS的原理是什么
确实毒瘤，我就说1999年的题怎么有人考n log n，结果是后来新增的数据。nlogn维护一个单调队列就完了，原理是显然的

你这叫背题家

【引用自 vczh】:
这不就是全连通子图算法
这题不需要找强连通分量（甚至遇到大小>1的强连通分量可以直接润），一个DFS就够了

强连通分量我一般用背下来的tarjan模板
【引用自 vczh】:
但这道题我下意识就会用DP来写
俺也一样，就是一种dp可以二分一种不可以
【引用自 ctzsm】:
应该还是靠什么根号分块
确实就是分块，不需要磨逼钨丝繁衍
【引用自 ctzsm】:
nlogn维护一个单调队列就完了，原理是显然的
主要是下意识dp[i]=第i个数结尾的lis，就不显然了
【引用自 cynthialin】:
你这叫背题家
没办法，我笨

https://leetcode.com/problems/minimum-cost-to-reach-city-with-discounts

看题应该是把图拷贝discount遍；题解是爆改dijkstra，which i don’t like

image1179×771 36.2 KB

没想到还有这功能

我用的200个人一起买的一个号

要不你用我的号 我就可以获得一面绿墙了 有membership

image840×144 15.6 KB

我现在的就是面试墙 有绿就是有面试

这么多面试

好啊好啊陆老师，现在这个号每10分钟就会被挤下去

https://leetcode.com/problems/sort-array-by-increasing-frequency/

哈希表+c++ lambda低分飘过

image697×332 12.8 KB

再多点的话还能用jump list，100感觉都不想思考了

实不相瞒，我至今没用过跳表，只在狗操的面试八股里见过

跳表不是skip list吗，轮子哥说的是啥玩意。

我有bbst用锤子的跳表

突然发现我忘回了

我今晚开完会改一下密码给你

确实是skip list，被windows api干扰了，jump list是windows 7的新feature

index不是非常大的时候skip list能实现的非常cache friendly

【引用自 Lunasol】:
改一下密码
推荐一个密码：kri-kri-killshot

【引用自 圆形箱装猪头鹅】:
Σοί, μετὰ τρισχιλίους ἐνιαυτούς. 🐐:
推荐一个密码：kri-kri-killshot
我要是用了这个密码，我的号就该变成几十人的公车号了……

（因为开盒我leetcode账号很容易）

完蛋 用不上这么好的密码了

Kri-Kri

【引用自 圆形箱装猪头鹅】:
Σοί, μετὰ τρισχιλίους ἐνιαυτούς. 🐐:
这么好的密码
这也只能leetcode这种乐色网站用了

没有特殊符号没有大小写还有连续的kri……

【引用自 Lunasol】:
没有特殊符号没有大小写还有连续的kri……
Kri-"@a100"-Kri_Killshot

correcthorsebatterystaple

https://leetcode.com/problems/sort-the-jumbled-numbers

感谢陆老师爆的金币

今天题不难，但我脑子一开始没转过弯来

用的比较sb的需要特判的小学数学处理方式，实际上用字符串更简单而且不需要特判
for (int idx = 0; idx < nums.size(); ++idx) {
int t = 0;
for (int i = 1; nums[idx] / i != 0; i *= 10) {
t+= (mapping[(nums[idx] / i) % 10] * i);
}
t= nums[idx]==0?mapping[0]:t;
// more shit here
}

不是很懂难点在哪，你把每一个num[i]都换成tuple{mapped, i}，直接对array of tuple排序，然后输出第一个元素，不是最简单的做法吗，还不用字符串，全程保持cache friendly

没说难，就是一开始没想到用pair<int, int>，讲武德
【引用自 vczh】:
mapped
字符串是计算这个用

算mapping 不断除以10就好了，不会不小心产生内存碎片

讲道理图省事把这个transform写进comparator就完了，也就多transform log倍。时间换空间，能做到inplace。

打表解决一切

今天是模板题，写的归并排序改了半天才改对，写的一坨屎，我好傻逼

114514

（用std::array<int, N>代替std::vector<int>速度直接提升5倍，holy shit）

混淆过的代码（看起来很像高中时候的模板就是了）：
void mergee(vector<int>& v, int l, int mid, int r) {
int i=0, j=l, k=mid;
for (;j<mid && k<r; tmp[i++] = v[j] <= v[k] ? v[j++] : v[k++]);
for (;j<mid; tmp[i++]=v[j++]);
for (;k<r; tmp[i++]=v[k++]);
for (int ii=l;ii<r;v[ii++]=tmp[ii-l]);
}

题呢

https://leetcode.com/problems/sort-an-array

我也刚打开copy link你就抢发了

share账号有助于我跟着atf刷题（因为不想我的账号完全变成atf的形状就只有我自己跟着做/看了 ）

不是我心不甘情不愿借账号， 是我挺希望绿墙记录我的进度……

【引用自 Lunasol】:
因为不想我的账号完全变成atf的形状
我可以發這個嗎

这题真烦呀，这要求最小的空间，其实只能堆排和快排这样的in place排序算法。你归并排序是要额外O(n)的空间的。

icc面试就考这题

10~15分钟撸一个堆问题不大，快排容易写错。

其实可以O(1): 优化原地归并排序：实现 O(1) 空间复杂度

【引用自 ATF】:
（用std::array<int, N>代替std::vector<int>速度直接提升5倍，holy shit）
要不下次试试deque，可以在不知道N的情况下性能也不会太差

666，你这么一说我想起来确实有这个东西，但是从来没有会过就忘了。大致看了一下这个博文，感觉这个东西好像破坏了本来归并排序分治的性质，那么是不是就不能拿来求逆序对啥的了。

这个方法感觉非常不直观，正确性证明我都有点想不明白

https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

想了半天是不是魔改Dijkstra，点进提示发现Floyd-Warshall就可以过；随便写了个用vvi的完全没有优化的Floyd O(n^3)，击败了97%的答案

我震惊了，wtf bro，他们不会是用的Dijkstra每个点跑一遍吧

image943×177 11.4 KB

题解123居然分别是Dijkstra, B-F和SPFA，这可是在求全源最短路啊哥们

image943×775 47.3 KB

而且管队列优化B-F叫SPFA的，鉴定为老中

leetcode就是老中开的 ，而且欣宜姐姐在那里实习过（此处又 @Lunasol ？ ），据她讲自己的mentor也是中国人，应该挺多人都是中国人的。以前他们找过我验题啥的，不过我没去，找人的标准估计也是中国人优先。

我们最近做的一个东西很有意思可以出利口题 （虽然某种意义上利口题都没意思）

不知道有没有啥利口出题贡献渠道

感觉全泥潭只有我不知道xy在三次元的真身了

【引用自 ATF】:
Floyd-Warshal
完全忘记怎么写了

工作万年用不上for循环，floyd可是一下子就要用三个for循环嵌套的高级玩意

【引用自 Lunasol】:
出题贡献渠道
我记得他们以前题目来源主要是面经，真直接收别人给他们出题的话就没意思了，毕竟这个网站是面试为导向。要出题的话去codechef可能可以。codeforces应该只能卖成套的，而且你最好找个红名背书，而且价格一般。

https://leetcode.com/problems/minimum-cost-to-convert-string-i

又是一道傻逼floyd，没看题所以" that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i]."写错了，纯傻逼

算法课提过，全忘了

client = OpenAI()

client.chat.completions.create(
model="gpt-4o",
messages=[
{"role": "system", "content": "You are a helpful assistant."},
{"role": "user", "content": "Write me, in C++, an example implementation of Floyd-Warshall algorithm."}
]
)

只做过100题的我看的津津有味

有没有人多看看我的广告

小弟不才 只能看看

我上班全是在弄typescript和c++的类型体操，每天做脑筋急转弯的感觉

今天题好难，摸了

https://leetcode.com/problems/count-number-of-teams/

树状数组，不会，看题解发现不需要DP直接n^2模拟就行，我真是sb

题目看了一半，下意识以为是把人刚好分成几个team然后不剩下，问有几种分法，下意识觉得难道不是二分吗？结果看完了才知道是穷举

脑子里蹦出来的想法就是，可以按照比如说递增关系，把整个队伍做成partial ordered graph，每一个successor projection出来的链表都是单调的，接受O(n)空间复杂度的话构造这个graph时间复杂度应该也是O(n)，这样也形如DP了

如果是自己的项目我肯定会这么做的，因为虽然worst case还是n^2，但是日常数据应该会无限逼近n。不过leetcode 的不可能这么麻烦，可能真的穷举就好了

O(n^2)穷举，STL没有的数据结构除了并查集我是基本不会自己写的

我从来都是自己写stl的（除了只能编译器开后门的那些，比如 type_traits 或者 atomic啥的）。只有有思路，实现都不是问题

我会写但是很懒，而且细节经常处理不好，很难受

你需要能帮你做unit test，code coverage和memory leak的工具，习惯了会对测试上瘾

这题如果不会
【引用自 ATF】:
树状数组
也是可以做的。就是我们前两天说过的
【引用自 ctzsm】:
归并排序
求
【引用自 ctzsm】:
逆序对
做两遍就行，第一遍求二元逆序对的数量，第二遍根据第一遍的结果求三元逆序对的数量。因为rating是unique的，方便了查询，带个log就完事了。复杂度O(n log^2 n)吧，用hash可以做到伪O(n log n)。

放弃治疗了，我爱暴力

下次见到大哥给你出四元逆序对

直接上dp，或者
【引用自 ATF】:
今天题好难，摸了

https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/

前缀和+后缀和，轻松秒了

直觉上就是往字符串砍一刀，要求左边的b和右边的a加起来最小。字符串得每一个字符都是有效信息，所以复杂度最低必然是O(n)，从左到右试一下也是O(n)

https://leetcode.com/problems/filling-bookcase-shelves/

一开始以为是3d dp，看了提示发现是1d dp

d_i=\min_{j: \sum_i^j{w_j} \leq W}{\max_{k\in \{i, \cdots, j-1\}}{h_k} + d_j}

差不多这么个意思，秒了

https://leetcode.com/problems/toss-strange-coins

简单的概率dp，边界条件需要复习一下

d_{i, h}=d_{i-1, h-1}\mathbb{P}_i(\text{H})+d_{i-1, h}\mathbb{P}_i(\text{T})

日常写一坨屎发泥潭：
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
dp: Callable[[int, int], float] = (lru_cache(maxsize=len(prob)*target+64)(lambda i, heads: 1.0 if i==-1 and heads == 0 else 0.0 if i<0 or heads < 0 else (dp(i-1, heads-1)*prob[i] + dp(i-1, heads)*(1-prob[i]))))
return dp(len(prob)-1, target)

又是带锁题，再见

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:

Input: prob = [0.4], target = 1 Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125

Constraints:

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

【引用自 ATF】:
秒了
你小子整天就秒了

我还在这里复习怎么写sort

这他妈怎么面试啊

#include "algorithm"
#include "functional"
using namespace std;

template <class T>
vector<T> aws_sort(vector<T>& data, function<bool(T&, T&)> comp) {
vector<T> result(data.begin(), data.end());
sort(result.begin(), result.end(), comp);
return result;
}

秒了
【引用自 AWS】:
我还在这里复习怎么写sort
【引用自 未知】:
【水】做题家每天做题碎碎念 搬砖
今天是模板题，写的归并排序改了半天才改对，写的一坨屎，我好傻逼
[image]
114514
（用std::array<int, N>代替std::vector<int>速度直接提升5倍，holy shit）
混淆过的代码（看起来很像高中时候的模板就是了）：
void mergee(vector<int>& v, int l, int mid, int r) {
int i=0,…

主要好久不写sort了得复习下

之前一直偷懒用heapify
# break into halfs (recursive)
# only focus on merge function
# -> which is basically same as merging two sorted linked lists

def MergeSort(arr):
n = len(arr)

if n <= 1:
return arr

mid = n // 2

left = arr[:mid]
right = arr[mid:]

left = MergeSort(left)
right = MergeSort(right)

return _merge(left, right)

def _merge(left, right):
res = []
i = j = 0

while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1

res.extend(left[i:])
res.extend(right[j:])

return res

arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = MergeSort(arr)
print("Sorted array:", sorted_arr)

NMD周二easy run秒了

image2064×934 108 KB

【引用自 AWS】:
n = len(arr)
这里没有异常检测，what if your arr is None?

可以认为前提条件就是arr是一个仅包含全部可以互相比较的元素的可索引类型，检查未必一定要在这些函数里执行

如果假设成立，那垃圾输入==垃圾输出，没毛病
【引用自 AWS】:
之前一直偷懒用heapify
我有一计，sorted(arr)秒了

是这么假设的

【引用自 ATF】:
那垃圾输入==垃圾输出
垃圾输入能搞崩程序，一堆try catch太不优雅

不一定try catch，可以写守门员函数或者用类型提示+静态分析工具

下意识会使用二分，左边a次概率多少，右边b次概率多少，然后加起来是target，求个和，就是不知道会不会OOM

哪有给sort写守门员函数的呀，我一般观察candidate有没有这个意识。experienced hire更看他有没有开发经验了，over engineering is a red flag

我觉得会TLE，但我不好说

说实话完全没看懂轮子哥这个是啥东西。这题显然就是个dp，套了概率皮的01背包。

来一起刷题吗，要被pip了得捡起leetcode了

我每天没事就做一道

【引用自 ctzsm】:
以前他们找过我验题啥的
才发现，巨佬%%%%%%%%

【引用自 ctzsm】:
以前他们找过我验题啥的
开贴给我们辅导辅导刷题吧…年纪大了刷不动，咋办

那应该找小年轻，比如wuzhengkai老师这样的超级选手。不过吴老师应该不需要做题了。

而且这贴不是已经在讨论做题了。

吴老师是不是icpc wf participant
【引用自 ctzsm】:
而且这贴不是已经在讨论做题了。
不要啊c神，我要做题

吴老师是icpc wf银牌选手

%%%%%%%%%%%

该进行开盒了

吴老师都是实名上网的，没啥要开盒的说实话。。

去顺着网线跪下求吴老师给一个内推

https://leetcode.com/problems/number-of-senior-citizens
len([1 for s in details if int(s[11:13]) > 60])

这题太简单了，洛谷启动

吊大的痰友们，请问C++里不做类型体操有什么办法可以用lambda一行秒？

我唯一能想到的就是std::reduce，但是

今天学习到了std::transform_reduce
int countSeniors(vector<string>& details) {
return std::transform_reduce(details.begin(), details.end(), int{0}, [](const int l, const int r)->int {return l+r;},[](const string& s)->int {return ((s[11]-'0')*10+(s[12]-'0'))>60?1:0;});
}

改进版（HT
【引用自 ctzsm】:
没学全啊 ，stl有plus
）
int countSeniors(vector<string>& details) {return std::transform_reduce(details.begin(), details.end(), int{0}, std::plus<int>( ),[](const string& s)->int {return ((s[11]-48)*10+(s[12]-48))>60?1:0;});}

什么是洛谷

return sum(1 if int(string[11:13]) > 60 else 0 for string in details)

luogu.com.cn

首页 - 洛谷 | 计算机科学教育新生态

洛谷创办于2013年，致力于为参加noip、noi、acm的选手提供清爽、快捷的编程体验。它拥有在线测题系统、强大的社区、在线学习功能。很多教程内容由各位oiers提供的，内容广泛。无论是初学oi的蒟蒻，还是久经沙场的神犇，均可从中获益，也可以帮助他人，共同进步。是学习noip等竞赛时理想的网站。

新知识啊，去学习

摸了zs

没学全啊 ，stl有plus

https://en.cppreference.com/w/cpp/utility/functional/plus

谢谢c巨佬

这种循环数组题直接前后接起来+滚动数组轻松秒了

明天就不做题了，戒做题一天
【引用自 ATF】:
在另一个话题中

https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/?

直接看元素是否完全相同，

不失一般性地，如果两个数组中如果1中元素在i在2中在j且i<j，通过不停交换(j, j-1)即可不影响其他元素顺序而让元素i交换到元素j；余下的证明是朴素的
【引用自 ATF】:
明天就不做题了，戒做题一天
明天戒

你怎么挑的？

好 我明天上号

我今天做了几个

tmd

要没时间了咋办

好久没做了，复习下经典
## Course Schedule

# trying to detect a cycle
# first convert into graph structure

# recursive dfs is easy to write
# add a path boolean array, refresh after calling finishing recursive stack resolves

# def recursive_dfs(v, visited, graph):
# if not visited[v]:
# visited[v] = True
# for w in graph[v]:
# recursive_dfs(w, visited, graph)

class Solution:
def __init__(self) -> None:
self.cycle = False

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
self.path = [False] * numCourses
self.visited = [False] * numCourses

graph = self._graph(numCourses, prerequisites)

for i in range(numCourses):
self._dfs(graph, i)

return not self.cycle

def _graph(self, numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
for (after, before) in prerequisites:
graph[before].append(after)
return graph

def _dfs(self, graph, start):
if self.path[start]:
self.cycle = True

if self.visited[start] or self.cycle:
return

self.visited[start] = True

self.path[start] = True
for child in graph[start]:
self._dfs(graph, child)
self.path[start] = False

## Course Schedule 2

# Topological sort DFS
# Find a linear ordering of the directionality of the nodes (cannot be done if there is a cycle)
# Simply reverse the postorder traversal (post order means left -> right -> node)
# In post order children are before parents
# Topological sort requires parents before children

# DFS preorder -> before children loop
# DFS postorder -> after children loop

class Solution:
def __init__(self) -> None:
self.cycle = False
self.postorder = []

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
self.path = [False] * numCourses
self.visited = [False] * numCourses

graph = self._graph(numCourses, prerequisites)

for i in range(numCourses):
self._dfs(graph, i)

if self.cycle:
return []

return reversed(self.postorder)

def _graph(self, numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
for (after, before) in prerequisites:
graph[before].append(after)
return graph

def _dfs(self, graph, start):
if self.path[start]:
self.cycle = True

if self.cycle or self.visited[start]:
return

self.visited[start] = True
self.path[start] = True

for child in graph[start]:
self._dfs(graph, child)

self.postorder.append(start)
self.path[start] = False

每日例题
【引用自 Lunasol】:
好 我明天上号
【引用自 Lunasol】:
账号完全变成atf的形状

image979×656 26.3 KB

https://leetcode.com/problems/longest-repeating-substring/

虽然很低效，但是非常好写

卧槽，premium过期了

卧槽

我是傻子

image714×650 34.9 KB

没过期 只不过我头像比较微妙 他p掉了

我在说我的账户premium过期了

你们都什么电子连体婴

陆老师我帮你改好了

你这样sort是不是不如hashmap

力扣遛衣是啥意思啊

【引用自 AWS】:
力扣遛衣
是的，取决于实现最差复杂度是 \mathcal{O}(n \log n) ，用哈希表可以做到 \mathcal{O}(n)

https://leetcode.com/problems/rotate-list

继续写坨狗屎：
ListNode* rotateRight(ListNode* head, int k) {
array<ListNode*, 521> lst;
int len = 0;
if (!head) return head;
for (ListNode* n = head; n; n = n->next) lst[len++] = n;
if (!(k % len)) return head;
lst[len-1]->next=head;
lst[len-k%len-1]->next=0;
return lst[len-k%len];
}

话说monotonic queue算八股文吗

怎么有人问这种狗屎啊

单调栈就基础知识吧 算八股文 咋就狗屎了

基础不牢，反思

惭愧，我也不会写

感觉课上也没学过啊

就那一个题还是看着design写的，做了一遍忘了

看61第一反应是reverse三次是我的问题吗

趁机复习一下92

看了眼recursive solution感觉自己是个笨逼，看半天没看懂
class Solution:
def reverseBetween(self, head: Optional[ListNode], n: int, m: int) -> Optional[ListNode]:
dummy = ListNode(0, head)

left, cur = dummy, head
for _ in range(n - 1):
left, cur = cur, cur.next

prev = None
for _ in range(m - n + 1):
savenext = cur.next
# reverse
cur.next = prev
# move forward
prev = cur
cur = savenext

left.next.next = cur
left.next = prev

return dummy.next

from collections import deque

class M_Queue:
def __init__(self):
self.nums = deque()

def push(self, ele):
while len(self.nums) > 0 and self.nums[-1] < ele:
self.nums.pop()
self.nums.append(ele)

def pop(self, ele):
if ele == self.nums[0]:
self.nums.popleft()

def max(self):
return self.nums[0]

再多做几个类似的题看看能不能用上

结果周末一到你们几个卷王就疯狂刷题？

刷题何止是周末……

都不知道这是什么题型，linear pass?

# merge intervals

# order by start
# if new head in the interval, extend the tail
# if new head outside the tail, append

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []

intervals.sort(key=lambda x: x[0])

# the start is always here
res = [intervals[0]]

for head, tail in intervals[1:]:
last = res[-1]
if head <= last[-1]:
last[1] = max(last[1], tail)
else:
res.append([head, tail])

return res

class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
merged = []
i = 0
n = len(intervals)

# add before first
while i < n and intervals[i][1] < newInterval[0]:
merged.append(intervals[i])
i += 1

# merge
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(intervals[i][0], newInterval[0])
newInterval[1] = max(intervals[i][1], newInterval[1])
i += 1

merged.append(newInterval)

# add rest
while i < n:
merged.append(intervals[i])
i += 1

return merged

这种打竞赛的一般叫模拟吧

我没想通评论区说这题可以merge sort k的思路 我是笨蛋

sum_subarrays = []

n = len(nums)
for i in range(0,n):
running_sum = 0
for j in range(i,n):
running_sum += nums[j]
sum_subarrays.append(running_sum)
sum_subarrays.sort()

return sum(sum_subarrays[left-1:right]) % ( 10**9+7)

有没有个靓仔贴一下题，怎么感觉你们做的都不是一个题

这个暴力做法啊不行啊
【引用自 ctzsm】:
贴一下题
您好 您点的题上了 其实一般就是每日一题

https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/description/?envType=daily-question&envId=2024-08-04

image1368×164 21.3 KB

这个cmt竟然46个赞 我已经比47个人笨了

借用这个宝地问问

一个oa题实在做不出来

we need to find the maximum length of a subarray of a given string such that the frequency of the most frequent integer is equal to the frequency of the least frequent integer within that subarray.

array.length = 2e5

integer of array <=1e9

另外一个做不出的OA题也求问

We have an array executionTime which tells us how long each job takes to complete.

In each operation, we can choose a job to be the “major job” and execute it for x seconds, while all other jobs execute for y seconds.

Our goal is to find the minimum number of operations required to complete all jobs.

number of jobs <=2e5,

我终于懂了，因为 1 <= nums[i] <= 100所以i开始的子数必定是单调的

怎么没人给e老师讲oa

以下全部是扯淡：
【引用自 elijahqi】:
frequency of the most frequent integer is equal to the frequency of the least frequent integer within that subarray
频率相等，直接从长到短暴力遍历所有 i\in [0, \cdots, n) 开始的字串，维护一个哈希表统计频率，所有数字的频率都相等就返回长度
【引用自 elijahqi】:
We have an array executionTime which tells us how long each job takes to complete.
In each operation, we can choose a job to be the “major job” and execute it for x seconds, while all other jobs execute for y seconds.
Our goal is to find the minimum number of operations required to complete all jobs.
我觉得是贪心+线段树（OP写了用模拟会TLE），but let me google that for you：

原来这题是二分，懂了

stackoverflow.com

Greedy algorithm - minimize number of operations to complete task

algorithm, greedy

asked by

Donald

on 03:09AM - 13 May 19 UTC

LZ牛逼啊

【引用自 ATF】:
明天就不做题了，戒做题一天
【引用自 ATF】:
明天戒
不是戒做题吗

忍不住了，LC欲望太强

俗称LC succubus

昨天我没做题啊，玩了一天cs

我看cs第一反应是畜生是不是中国论坛逛多了

现在是cs2了，不然我会说go了一天

之前看新闻报道很久

除了引擎有啥区别

外挂变多了

那我再想想，我当时提交以后ac了就没细想

【引用自 ATF】:
频率相等，直接从长到短暴力遍历所有 i\in [0, \cdots, n)i∈[0,⋯,n)i\in [0, \cdots, n) 开始的字串，维护一个哈希表统计频率，所有数字的频率都相等就返回长度
我做的时候 好像是这么做的不过TLE了

hash 统计频率是怎么个意思呢是unordered_map吗

思路应该没区别

今天不做题了，谢谢大家

我描述的有问题是

int array

就是1 2 3 100 101这样子的

https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii

很简单的一道题，完全不配中等难度，一眼贪心

贪心写算法容易证明难，但是使用交换论证，证明是朴素的：

OK，该去fluz贴要饭了

什么毒瘤题

https://leetcode.com/problems/integer-to-english-words

integer指的到底是啥意思

4444这串是认为表示1个4444，还是既算一个4444也算三个44（带重叠）也算四个4？

有没有样例让我理解一下题目

遇到毒瘤题只能打表解决，草泥马的，浪费我人生中的一个小时
class Solution {
public:
array<string, 10> th_post = {"", "Thousand", "Million", "Billion", "Trillion"};
array<string, 1100> u1000 = {"Zero",
"One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen","Twenty","Twenty One","Twenty Two","Twenty Three","Twenty Four","Twenty Five","Twenty Six","Twenty Seven","Twenty Eight","Twenty Nine","Thirty","Thirty One","Thirty Two","Thirty Three","Thirty Four","Thirty Five","Thirty Six","Thirty Seven","Thirty Eight","Thirty Nine","Forty","Forty One","Forty Two","Forty Three","Forty Four","Forty Five","Forty Six","Forty Seven","Forty Eight","Forty Nine","Fifty","Fifty One","Fifty Two","Fifty Three","Fifty Four","Fifty Five","Fifty Six","Fifty Seven","Fifty Eight","Fifty Nine","Sixty","Sixty One","Sixty Two","Sixty Three","Sixty Four","Sixty Five","Sixty Six","Sixty Seven","Sixty Eight","Sixty Nine","Seventy","Seventy One","Seventy Two","Seventy Three","Seventy Four","Seventy Five","Seventy Six","Seventy Seven","Seventy Eight","Seventy Nine","Eighty","Eighty One","Eighty Two","Eighty Three","Eighty Four","Eighty Five","Eighty Six","Eighty Seven","Eighty Eight","Eighty Nine","Ninety","Ninety One","Ninety Two","Ninety Three","Ninety Four","Ninety Five","Ninety Six","Ninety Seven","Ninety Eight","Ninety Nine","One Hundred",
"One Hundred One","One Hundred Two","One Hundred Three","One Hundred Four","One Hundred Five","One Hundred Six","One Hundred Seven","One Hundred Eight","One Hundred Nine","One Hundred Ten","One Hundred Eleven","One Hundred Twelve","One Hundred Thirteen","One Hundred Fourteen","One Hundred Fifteen","One Hundred Sixteen","One Hundred Seventeen","One Hundred Eighteen","One Hundred Nineteen","One Hundred Twenty","One Hundred Twenty One","One Hundred Twenty Two","One Hundred Twenty Three","One Hundred Twenty Four","One Hundred Twenty Five","One Hundred Twenty Six","One Hundred Twenty Seven","One Hundred Twenty Eight","One Hundred Twenty Nine","One Hundred Thirty","One Hundred Thirty One","One Hundred Thirty Two","One Hundred Thirty Three","One Hundred Thirty Four","One Hundred Thirty Five","One Hundred Thirty Six","One Hundred Thirty Seven","One Hundred Thirty Eight","One Hundred Thirty Nine","One Hundred Forty","One Hundred Forty One","One Hundred Forty Two","One Hundred Forty Three","One Hundred Forty Four","One Hundred Forty Five","One Hundred Forty Six","One Hundred Forty Seven","One Hundred Forty Eight","One Hundred Forty Nine","One Hundred Fifty","One Hundred Fifty One","One Hundred Fifty Two","One Hundred Fifty Three","One Hundred Fifty Four","One Hundred Fifty Five","One Hundred Fifty Six","One Hundred Fifty Seven","One Hundred Fifty Eight","One Hundred Fifty Nine","One Hundred Sixty","One Hundred Sixty One","One Hundred Sixty Two","One Hundred Sixty Three","One Hundred Sixty Four","One Hundred Sixty Five","One Hundred Sixty Six","One Hundred Sixty Seven","One Hundred Sixty Eight","One Hundred Sixty Nine","One Hundred Seventy","One Hundred Seventy One","One Hundred Seventy Two","One Hundred Seventy Three","One Hundred Seventy Four","One Hundred Seventy Five","One Hundred Seventy Six","One Hundred Seventy Seven","One Hundred Seventy Eight","One Hundred Seventy Nine","One Hundred Eighty","One Hundred Eighty One","One Hundred Eighty Two","One Hundred Eighty Three","One Hundred Eighty Four","One Hundred Eighty Five","One Hundred Eighty Six","One Hundred Eighty Seven","One Hundred Eighty Eight","One Hundred Eighty Nine","One Hundred Ninety","One Hundred Ninety One","One Hundred Ninety Two","One Hundred Ninety Three","One Hundred Ninety Four","One Hundred Ninety Five","One Hundred Ninety Six","One Hundred Ninety Seven","One Hundred Ninety Eight","One Hundred Ninety Nine","Two Hundred",
"Two Hundred One","Two Hundred Two","Two Hundred Three","Two Hundred Four","Two Hundred Five","Two Hundred Six","Two Hundred Seven","Two Hundred Eight","Two Hundred Nine","Two Hundred Ten","Two Hundred Eleven","Two Hundred Twelve","Two Hundred Thirteen","Two Hundred Fourteen","Two Hundred Fifteen","Two Hundred Sixteen","Two Hundred Seventeen","Two Hundred Eighteen","Two Hundred Nineteen","Two Hundred Twenty","Two Hundred Twenty One","Two Hundred Twenty Two","Two Hundred Twenty Three","Two Hundred Twenty Four","Two Hundred Twenty Five","Two Hundred Twenty Six","Two Hundred Twenty Seven","Two Hundred Twenty Eight","Two Hundred Twenty Nine","Two Hundred Thirty","Two Hundred Thirty One","Two Hundred Thirty Two","Two Hundred Thirty Three","Two Hundred Thirty Four","Two Hundred Thirty Five","Two Hundred Thirty Six","Two Hundred Thirty Seven","Two Hundred Thirty Eight","Two Hundred Thirty Nine","Two Hundred Forty","Two Hundred Forty One","Two Hundred Forty Two","Two Hundred Forty Three","Two Hundred Forty Four","Two Hundred Forty Five","Two Hundred Forty Six","Two Hundred Forty Seven","Two Hundred Forty Eight","Two Hundred Forty Nine","Two Hundred Fifty","Two Hundred Fifty One","Two Hundred Fifty Two","Two Hundred Fifty Three","Two Hundred Fifty Four","Two Hundred Fifty Five","Two Hundred Fifty Six","Two Hundred Fifty Seven","Two Hundred Fifty Eight","Two Hundred Fifty Nine","Two Hundred Sixty","Two Hundred Sixty One","Two Hundred Sixty Two","Two Hundred Sixty Three","Two Hundred Sixty Four","Two Hundred Sixty Five","Two Hundred Sixty Six","Two Hundred Sixty Seven","Two Hundred Sixty Eight","Two Hundred Sixty Nine","Two Hundred Seventy","Two Hundred Seventy One","Two Hundred Seventy Two","Two Hundred Seventy Three","Two Hundred Seventy Four","Two Hundred Seventy Five","Two Hundred Seventy Six","Two Hundred Seventy Seven","Two Hundred Seventy Eight","Two Hundred Seventy Nine","Two Hundred Eighty","Two Hundred Eighty One","Two Hundred Eighty Two","Two Hundred Eighty Three","Two Hundred Eighty Four","Two Hundred Eighty Five","Two Hundred Eighty Six","Two Hundred Eighty Seven","Two Hundred Eighty Eight","Two Hundred Eighty Nine","Two Hundred Ninety","Two Hundred Ninety One","Two Hundred Ninety Two","Two Hundred Ninety Three","Two Hundred Ninety Four","Two Hundred Ninety Five","Two Hundred Ninety Six","Two Hundred Ninety Seven","Two Hundred Ninety Eight","Two Hundred Ninety Nine","Three Hundred",
"Three Hundred One","Three Hundred Two","Three Hundred Three","Three Hundred Four","Three Hundred Five","Three Hundred Six","Three Hundred Seven","Three Hundred Eight","Three Hundred Nine","Three Hundred Ten","Three Hundred Eleven","Three Hundred Twelve","Three Hundred Thirteen","Three Hundred Fourteen","Three Hundred Fifteen","Three Hundred Sixteen","Three Hundred Seventeen","Three Hundred Eighteen","Three Hundred Nineteen","Three Hundred Twenty","Three Hundred Twenty One","Three Hundred Twenty Two","Three Hundred Twenty Three","Three Hundred Twenty Four","Three Hundred Twenty Five","Three Hundred Twenty Six","Three Hundred Twenty Seven","Three Hundred Twenty Eight","Three Hundred Twenty Nine","Three Hundred Thirty","Three Hundred Thirty One","Three Hundred Thirty Two","Three Hundred Thirty Three","Three Hundred Thirty Four","Three Hundred Thirty Five","Three Hundred Thirty Six","Three Hundred Thirty Seven","Three Hundred Thirty Eight","Three Hundred Thirty Nine","Three Hundred Forty","Three Hundred Forty One","Three Hundred Forty Two","Three Hundred Forty Three","Three Hundred Forty Four","Three Hundred Forty Five","Three Hundred Forty Six","Three Hundred Forty Seven","Three Hundred Forty Eight","Three Hundred Forty Nine","Three Hundred Fifty","Three Hundred Fifty One","Three Hundred Fifty Two","Three Hundred Fifty Three","Three Hundred Fifty Four","Three Hundred Fifty Five","Three Hundred Fifty Six","Three Hundred Fifty Seven","Three Hundred Fifty Eight","Three Hundred Fifty Nine","Three Hundred Sixty","Three Hundred Sixty One","Three Hundred Sixty Two","Three Hundred Sixty Three","Three Hundred Sixty Four","Three Hundred Sixty Five","Three Hundred Sixty Six","Three Hundred Sixty Seven","Three Hundred Sixty Eight","Three Hundred Sixty Nine","Three Hundred Seventy","Three Hundred Seventy One","Three Hundred Seventy Two","Three Hundred Seventy Three","Three Hundred Seventy Four","Three Hundred Seventy Five","Three Hundred Seventy Six","Three Hundred Seventy Seven","Three Hundred Seventy Eight","Three Hundred Seventy Nine","Three Hundred Eighty","Three Hundred Eighty One","Three Hundred Eighty Two","Three Hundred Eighty Three","Three Hundred Eighty Four","Three Hundred Eighty Five","Three Hundred Eighty Six","Three Hundred Eighty Seven","Three Hundred Eighty Eight","Three Hundred Eighty Nine","Three Hundred Ninety","Three Hundred Ninety One","Three Hundred Ninety Two","Three Hundred Ninety Three","Three Hundred Ninety Four","Three Hundred Ninety Five","Three Hundred Ninety Six","Three Hundred Ninety Seven","Three Hundred Ninety Eight","Three Hundred Ninety Nine","Four Hundred",
"Four Hundred One","Four Hundred Two","Four Hundred Three","Four Hundred Four","Four Hundred Five","Four Hundred Six","Four Hundred Seven","Four Hundred Eight","Four Hundred Nine","Four Hundred Ten","Four Hundred Eleven","Four Hundred Twelve","Four Hundred Thirteen","Four Hundred Fourteen","Four Hundred Fifteen","Four Hundred Sixteen","Four Hundred Seventeen","Four Hundred Eighteen","Four Hundred Nineteen","Four Hundred Twenty","Four Hundred Twenty One","Four Hundred Twenty Two","Four Hundred Twenty Three","Four Hundred Twenty Four","Four Hundred Twenty Five","Four Hundred Twenty Six","Four Hundred Twenty Seven","Four Hundred Twenty Eight","Four Hundred Twenty Nine","Four Hundred Thirty","Four Hundred Thirty One","Four Hundred Thirty Two","Four Hundred Thirty Three","Four Hundred Thirty Four","Four Hundred Thirty Five","Four Hundred Thirty Six","Four Hundred Thirty Seven","Four Hundred Thirty Eight","Four Hundred Thirty Nine","Four Hundred Forty","Four Hundred Forty One","Four Hundred Forty Two","Four Hundred Forty Three","Four Hundred Forty Four","Four Hundred Forty Five","Four Hundred Forty Six","Four Hundred Forty Seven","Four Hundred Forty Eight","Four Hundred Forty Nine","Four Hundred Fifty","Four Hundred Fifty One","Four Hundred Fifty Two","Four Hundred Fifty Three","Four Hundred Fifty Four","Four Hundred Fifty Five","Four Hundred Fifty Six","Four Hundred Fifty Seven","Four Hundred Fifty Eight","Four Hundred Fifty Nine","Four Hundred Sixty","Four Hundred Sixty One","Four Hundred Sixty Two","Four Hundred Sixty Three","Four Hundred Sixty Four","Four Hundred Sixty Five","Four Hundred Sixty Six","Four Hundred Sixty Seven","Four Hundred Sixty Eight","Four Hundred Sixty Nine","Four Hundred Seventy","Four Hundred Seventy One","Four Hundred Seventy Two","Four Hundred Seventy Three","Four Hundred Seventy Four","Four Hundred Seventy Five","Four Hundred Seventy Six","Four Hundred Seventy Seven","Four Hundred Seventy Eight","Four Hundred Seventy Nine","Four Hundred Eighty","Four Hundred Eighty One","Four Hundred Eighty Two","Four Hundred Eighty Three","Four Hundred Eighty Four","Four Hundred Eighty Five","Four Hundred Eighty Six","Four Hundred Eighty Seven","Four Hundred Eighty Eight","Four Hundred Eighty Nine","Four Hundred Ninety","Four Hundred Ninety One","Four Hundred Ninety Two","Four Hundred Ninety Three","Four Hundred Ninety Four","Four Hundred Ninety Five","Four Hundred Ninety Six","Four Hundred Ninety Seven","Four Hundred Ninety Eight","Four Hundred Ninety Nine","Five Hundred",
"Five Hundred One","Five Hundred Two","Five Hundred Three","Five Hundred Four","Five Hundred Five","Five Hundred Six","Five Hundred Seven","Five Hundred Eight","Five Hundred Nine","Five Hundred Ten","Five Hundred Eleven","Five Hundred Twelve","Five Hundred Thirteen","Five Hundred Fourteen","Five Hundred Fifteen","Five Hundred Sixteen","Five Hundred Seventeen","Five Hundred Eighteen","Five Hundred Nineteen","Five Hundred Twenty","Five Hundred Twenty One","Five Hundred Twenty Two","Five Hundred Twenty Three","Five Hundred Twenty Four","Five Hundred Twenty Five","Five Hundred Twenty Six","Five Hundred Twenty Seven","Five Hundred Twenty Eight","Five Hundred Twenty Nine","Five Hundred Thirty","Five Hundred Thirty One","Five Hundred Thirty Two","Five Hundred Thirty Three","Five Hundred Thirty Four","Five Hundred Thirty Five","Five Hundred Thirty Six","Five Hundred Thirty Seven","Five Hundred Thirty Eight","Five Hundred Thirty Nine","Five Hundred Forty","Five Hundred Forty One","Five Hundred Forty Two","Five Hundred Forty Three","Five Hundred Forty Four","Five Hundred Forty Five","Five Hundred Forty Six","Five Hundred Forty Seven","Five Hundred Forty Eight","Five Hundred Forty Nine","Five Hundred Fifty","Five Hundred Fifty One","Five Hundred Fifty Two","Five Hundred Fifty Three","Five Hundred Fifty Four","Five Hundred Fifty Five","Five Hundred Fifty Six","Five Hundred Fifty Seven","Five Hundred Fifty Eight","Five Hundred Fifty Nine","Five Hundred Sixty","Five Hundred Sixty One","Five Hundred Sixty Two","Five Hundred Sixty Three","Five Hundred Sixty Four","Five Hundred Sixty Five","Five Hundred Sixty Six","Five Hundred Sixty Seven","Five Hundred Sixty Eight","Five Hundred Sixty Nine","Five Hundred Seventy","Five Hundred Seventy One","Five Hundred Seventy Two","Five Hundred Seventy Three","Five Hundred Seventy Four","Five Hundred Seventy Five","Five Hundred Seventy Six","Five Hundred Seventy Seven","Five Hundred Seventy Eight","Five Hundred Seventy Nine","Five Hundred Eighty","Five Hundred Eighty One","Five Hundred Eighty Two","Five Hundred Eighty Three","Five Hundred Eighty Four","Five Hundred Eighty Five","Five Hundred Eighty Six","Five Hundred Eighty Seven","Five Hundred Eighty Eight","Five Hundred Eighty Nine","Five Hundred Ninety","Five Hundred Ninety One","Five Hundred Ninety Two","Five Hundred Ninety Three","Five Hundred Ninety Four","Five Hundred Ninety Five","Five Hundred Ninety Six","Five Hundred Ninety Seven","Five Hundred Ninety Eight","Five Hundred Ninety Nine","Six Hundred",
"Six Hundred One","Six Hundred Two","Six Hundred Three","Six Hundred Four","Six Hundred Five","Six Hundred Six","Six Hundred Seven","Six Hundred Eight","Six Hundred Nine","Six Hundred Ten","Six Hundred Eleven","Six Hundred Twelve","Six Hundred Thirteen","Six Hundred Fourteen","Six Hundred Fifteen","Six Hundred Sixteen","Six Hundred Seventeen","Six Hundred Eighteen","Six Hundred Nineteen","Six Hundred Twenty","Six Hundred Twenty One","Six Hundred Twenty Two","Six Hundred Twenty Three","Six Hundred Twenty Four","Six Hundred Twenty Five","Six Hundred Twenty Six","Six Hundred Twenty Seven","Six Hundred Twenty Eight","Six Hundred Twenty Nine","Six Hundred Thirty","Six Hundred Thirty One","Six Hundred Thirty Two","Six Hundred Thirty Three","Six Hundred Thirty Four","Six Hundred Thirty Five","Six Hundred Thirty Six","Six Hundred Thirty Seven","Six Hundred Thirty Eight","Six Hundred Thirty Nine","Six Hundred Forty","Six Hundred Forty One","Six Hundred Forty Two","Six Hundred Forty Three","Six Hundred Forty Four","Six Hundred Forty Five","Six Hundred Forty Six","Six Hundred Forty Seven","Six Hundred Forty Eight","Six Hundred Forty Nine","Six Hundred Fifty","Six Hundred Fifty One","Six Hundred Fifty Two","Six Hundred Fifty Three","Six Hundred Fifty Four","Six Hundred Fifty Five","Six Hundred Fifty Six","Six Hundred Fifty Seven","Six Hundred Fifty Eight","Six Hundred Fifty Nine","Six Hundred Sixty","Six Hundred Sixty One","Six Hundred Sixty Two","Six Hundred Sixty Three","Six Hundred Sixty Four","Six Hundred Sixty Five","Six Hundred Sixty Six","Six Hundred Sixty Seven","Six Hundred Sixty Eight","Six Hundred Sixty Nine","Six Hundred Seventy","Six Hundred Seventy One","Six Hundred Seventy Two","Six Hundred Seventy Three","Six Hundred Seventy Four","Six Hundred Seventy Five","Six Hundred Seventy Six","Six Hundred Seventy Seven","Six Hundred Seventy Eight","Six Hundred Seventy Nine","Six Hundred Eighty","Six Hundred Eighty One","Six Hundred Eighty Two","Six Hundred Eighty Three","Six Hundred Eighty Four","Six Hundred Eighty Five","Six Hundred Eighty Six","Six Hundred Eighty Seven","Six Hundred Eighty Eight","Six Hundred Eighty Nine","Six Hundred Ninety","Six Hundred Ninety One","Six Hundred Ninety Two","Six Hundred Ninety Three","Six Hundred Ninety Four","Six Hundred Ninety Five","Six Hundred Ninety Six","Six Hundred Ninety Seven","Six Hundred Ninety Eight","Six Hundred Ninety Nine","Seven Hundred",
"Seven Hundred One","Seven Hundred Two","Seven Hundred Three","Seven Hundred Four","Seven Hundred Five","Seven Hundred Six","Seven Hundred Seven","Seven Hundred Eight","Seven Hundred Nine","Seven Hundred Ten","Seven Hundred Eleven","Seven Hundred Twelve","Seven Hundred Thirteen","Seven Hundred Fourteen","Seven Hundred Fifteen","Seven Hundred Sixteen","Seven Hundred Seventeen","Seven Hundred Eighteen","Seven Hundred Nineteen","Seven Hundred Twenty","Seven Hundred Twenty One","Seven Hundred Twenty Two","Seven Hundred Twenty Three","Seven Hundred Twenty Four","Seven Hundred Twenty Five","Seven Hundred Twenty Six","Seven Hundred Twenty Seven","Seven Hundred Twenty Eight","Seven Hundred Twenty Nine","Seven Hundred Thirty","Seven Hundred Thirty One","Seven Hundred Thirty Two","Seven Hundred Thirty Three","Seven Hundred Thirty Four","Seven Hundred Thirty Five","Seven Hundred Thirty Six","Seven Hundred Thirty Seven","Seven Hundred Thirty Eight","Seven Hundred Thirty Nine","Seven Hundred Forty","Seven Hundred Forty One","Seven Hundred Forty Two","Seven Hundred Forty Three","Seven Hundred Forty Four","Seven Hundred Forty Five","Seven Hundred Forty Six","Seven Hundred Forty Seven","Seven Hundred Forty Eight","Seven Hundred Forty Nine","Seven Hundred Fifty","Seven Hundred Fifty One","Seven Hundred Fifty Two","Seven Hundred Fifty Three","Seven Hundred Fifty Four","Seven Hundred Fifty Five","Seven Hundred Fifty Six","Seven Hundred Fifty Seven","Seven Hundred Fifty Eight","Seven Hundred Fifty Nine","Seven Hundred Sixty","Seven Hundred Sixty One","Seven Hundred Sixty Two","Seven Hundred Sixty Three","Seven Hundred Sixty Four","Seven Hundred Sixty Five","Seven Hundred Sixty Six","Seven Hundred Sixty Seven","Seven Hundred Sixty Eight","Seven Hundred Sixty Nine","Seven Hundred Seventy","Seven Hundred Seventy One","Seven Hundred Seventy Two","Seven Hundred Seventy Three","Seven Hundred Seventy Four","Seven Hundred Seventy Five","Seven Hundred Seventy Six","Seven Hundred Seventy Seven","Seven Hundred Seventy Eight","Seven Hundred Seventy Nine","Seven Hundred Eighty","Seven Hundred Eighty One","Seven Hundred Eighty Two","Seven Hundred Eighty Three","Seven Hundred Eighty Four","Seven Hundred Eighty Five","Seven Hundred Eighty Six","Seven Hundred Eighty Seven","Seven Hundred Eighty Eight","Seven Hundred Eighty Nine","Seven Hundred Ninety","Seven Hundred Ninety One","Seven Hundred Ninety Two","Seven Hundred Ninety Three","Seven Hundred Ninety Four","Seven Hundred Ninety Five","Seven Hundred Ninety Six","Seven Hundred Ninety Seven","Seven Hundred Ninety Eight","Seven Hundred Ninety Nine","Eight Hundred",
"Eight Hundred One","Eight Hundred Two","Eight Hundred Three","Eight Hundred Four","Eight Hundred Five","Eight Hundred Six","Eight Hundred Seven","Eight Hundred Eight","Eight Hundred Nine","Eight Hundred Ten","Eight Hundred Eleven","Eight Hundred Twelve","Eight Hundred Thirteen","Eight Hundred Fourteen","Eight Hundred Fifteen","Eight Hundred Sixteen","Eight Hundred Seventeen","Eight Hundred Eighteen","Eight Hundred Nineteen","Eight Hundred Twenty","Eight Hundred Twenty One","Eight Hundred Twenty Two","Eight Hundred Twenty Three","Eight Hundred Twenty Four","Eight Hundred Twenty Five","Eight Hundred Twenty Six","Eight Hundred Twenty Seven","Eight Hundred Twenty Eight","Eight Hundred Twenty Nine","Eight Hundred Thirty","Eight Hundred Thirty One","Eight Hundred Thirty Two","Eight Hundred Thirty Three","Eight Hundred Thirty Four","Eight Hundred Thirty Five","Eight Hundred Thirty Six","Eight Hundred Thirty Seven","Eight Hundred Thirty Eight","Eight Hundred Thirty Nine","Eight Hundred Forty","Eight Hundred Forty One","Eight Hundred Forty Two","Eight Hundred Forty Three","Eight Hundred Forty Four","Eight Hundred Forty Five","Eight Hundred Forty Six","Eight Hundred Forty Seven","Eight Hundred Forty Eight","Eight Hundred Forty Nine","Eight Hundred Fifty","Eight Hundred Fifty One","Eight Hundred Fifty Two","Eight Hundred Fifty Three","Eight Hundred Fifty Four","Eight Hundred Fifty Five","Eight Hundred Fifty Six","Eight Hundred Fifty Seven","Eight Hundred Fifty Eight","Eight Hundred Fifty Nine","Eight Hundred Sixty","Eight Hundred Sixty One","Eight Hundred Sixty Two","Eight Hundred Sixty Three","Eight Hundred Sixty Four","Eight Hundred Sixty Five","Eight Hundred Sixty Six","Eight Hundred Sixty Seven","Eight Hundred Sixty Eight","Eight Hundred Sixty Nine","Eight Hundred Seventy","Eight Hundred Seventy One","Eight Hundred Seventy Two","Eight Hundred Seventy Three","Eight Hundred Seventy Four","Eight Hundred Seventy Five","Eight Hundred Seventy Six","Eight Hundred Seventy Seven","Eight Hundred Seventy Eight","Eight Hundred Seventy Nine","Eight Hundred Eighty","Eight Hundred Eighty One","Eight Hundred Eighty Two","Eight Hundred Eighty Three","Eight Hundred Eighty Four","Eight Hundred Eighty Five","Eight Hundred Eighty Six","Eight Hundred Eighty Seven","Eight Hundred Eighty Eight","Eight Hundred Eighty Nine","Eight Hundred Ninety","Eight Hundred Ninety One","Eight Hundred Ninety Two","Eight Hundred Ninety Three","Eight Hundred Ninety Four","Eight Hundred Ninety Five","Eight Hundred Ninety Six","Eight Hundred Ninety Seven","Eight Hundred Ninety Eight","Eight Hundred Ninety Nine","Nine Hundred",
"Nine Hundred One","Nine Hundred Two","Nine Hundred Three","Nine Hundred Four","Nine Hundred Five","Nine Hundred Six","Nine Hundred Seven","Nine Hundred Eight","Nine Hundred Nine","Nine Hundred Ten","Nine Hundred Eleven","Nine Hundred Twelve","Nine Hundred Thirteen","Nine Hundred Fourteen","Nine Hundred Fifteen","Nine Hundred Sixteen","Nine Hundred Seventeen","Nine Hundred Eighteen","Nine Hundred Nineteen","Nine Hundred Twenty","Nine Hundred Twenty One","Nine Hundred Twenty Two","Nine Hundred Twenty Three","Nine Hundred Twenty Four","Nine Hundred Twenty Five","Nine Hundred Twenty Six","Nine Hundred Twenty Seven","Nine Hundred Twenty Eight","Nine Hundred Twenty Nine","Nine Hundred Thirty","Nine Hundred Thirty One","Nine Hundred Thirty Two","Nine Hundred Thirty Three","Nine Hundred Thirty Four","Nine Hundred Thirty Five","Nine Hundred Thirty Six","Nine Hundred Thirty Seven","Nine Hundred Thirty Eight","Nine Hundred Thirty Nine","Nine Hundred Forty","Nine Hundred Forty One","Nine Hundred Forty Two","Nine Hundred Forty Three","Nine Hundred Forty Four","Nine Hundred Forty Five","Nine Hundred Forty Six","Nine Hundred Forty Seven","Nine Hundred Forty Eight","Nine Hundred Forty Nine","Nine Hundred Fifty","Nine Hundred Fifty One","Nine Hundred Fifty Two","Nine Hundred Fifty Three","Nine Hundred Fifty Four","Nine Hundred Fifty Five","Nine Hundred Fifty Six","Nine Hundred Fifty Seven","Nine Hundred Fifty Eight","Nine Hundred Fifty Nine","Nine Hundred Sixty","Nine Hundred Sixty One","Nine Hundred Sixty Two","Nine Hundred Sixty Three","Nine Hundred Sixty Four","Nine Hundred Sixty Five","Nine Hundred Sixty Six","Nine Hundred Sixty Seven","Nine Hundred Sixty Eight","Nine Hundred Sixty Nine","Nine Hundred Seventy","Nine Hundred Seventy One","Nine Hundred Seventy Two","Nine Hundred Seventy Three","Nine Hundred Seventy Four","Nine Hundred Seventy Five","Nine Hundred Seventy Six","Nine Hundred Seventy Seven","Nine Hundred Seventy Eight","Nine Hundred Seventy Nine","Nine Hundred Eighty","Nine Hundred Eighty One","Nine Hundred Eighty Two","Nine Hundred Eighty Three","Nine Hundred Eighty Four","Nine Hundred Eighty Five","Nine Hundred Eighty Six","Nine Hundred Eighty Seven","Nine Hundred Eighty Eight","Nine Hundred Eighty Nine","Nine Hundred Ninety","Nine Hundred Ninety One","Nine Hundred Ninety Two","Nine Hundred Ninety Three","Nine Hundred Ninety Four","Nine Hundred Ninety Five","Nine Hundred Ninety Six","Nine Hundred Ninety Seven","Nine Hundred Ninety Eight","Nine Hundred Ninety Nine"};
string numberToWords(int num) {
int curr_post = 0;
int remaining = num;
if (num == 0) return u1000[0];
deque<string> dq;
while (remaining != 0) {
int curr = remaining % 1000;
remaining /= 1000;
if (curr != 0) {
if (curr_post > 0) dq.push_front(th_post[curr_post]);
dq.push_front(u1000[curr]);
}
curr_post++;
}
string res;
for (auto it = dq.begin(); it != dq.end(); ++it) {
res += *it;
if (next(it) != dq.end()) res += " ";
}
return res;
}
};

广告： \color{red}征友，\color{blue}希望可以婚绿\color{orange}130

ok，去水贴去了

那你干嘛还要做

想跳槽你司

复习经典
# Trapping Rain Water

# naive
# for each i, find left max and right max
# trapped = min(lmax, rmax)

# using a dp table goes from O(n^2) to O(n)

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
water = 0

l_max, r_max = [0] * n, [0] * n

l_max[0] = height[0]
r_max[n-1] = height[n-1]

for i in range(1, n):
l_max[i] = max(l_max[i-1], height[i])

for i in range(n-2, -1, -1):
r_max[i] = max(r_max[i+1], height[i])

for i in range(1, n-1):
water += min(l_max[i], r_max[i]) - height[i]

return water

# advanced
# use two pointer for one pass
# we dont actually need to know r_max
# if l_max < r_max only update l_max
# else update r_max

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
left, right = 0, n-1
l_max, r_max = 0, 0

water = 0

while left < right:
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])

if l_max <= r_max:
water += l_max - height[left]
left += 1
else:
water += r_max - height[right]
right -= 1

return water

我好笨

https://leetcode.com/problems/spiral-matrix-iii

从原点开始在坐标上一直转，加上偏移量之后不在范围内的就不输出，直到输出足够多的元素为止。感觉这个写法应该能1A。

确实，但我一开始读题没读懂

我好像见过这个的简单版

LC 54是直接四个维度max

walk就行吧

何以解忧，唯有暴力

https://leetcode.com/problems/magic-squares-in-grid
if (
grid[i][j] + grid[i][j+1] + grid[i][j+2] == 15 &&
grid[i+1][j] + grid[i+1][j+1] + grid[i+1][j+2] == 15 &&
grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2] == 15 &&
grid[i][j] + grid[i+1][j] + grid[i+2][j] == 15 &&
grid[i][j+1] + grid[i+1][j+1] + grid[i+2][j+1] == 15 &&
grid[i][j+2] + grid[i+1][j+2] + grid[i+2][j+2] == 15 &&
grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2] == 15 &&
grid[i+2][j] + grid[i+1][j+1] + grid[i][j+2] == 15
) {}

广告： \color{red}征友，\color{blue}希望可以婚绿\color{orange}130

怎么会有这么无聊的题目 不过三阶幻方中心一定是5，所以可以只check5为中心的3x3

看了一眼标签，是一个比较幽默的并查集：

https://leetcode.com/problems/regions-cut-by-slashes

广告： \color{red}征友，\color{blue}希望可以婚绿\color{orange}130

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island

很有意思的毒瘤题，原本以为是并查集，看了看原来是观察法+tarjan找割点

广告： \color{red}征友，\color{blue}希望可以婚绿\color{orange}130

这周老板回来了没法划水好累

话说developer天天说没requirement干不了活好烦啊，就不能自己搞个design doc么

需要找割点吗，我感觉根据有没有2cc直接看度数就行了

考虑
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0

和
0 1 1 1 0 0
0 1 0 1 0 0

元素(0, 2)的度数都是2但是一个是割点一个不是，最后的答案也一个是2一个是1

我感觉

如果本来就不联通，答案是0

如果整个图都是一个scc，答案是2（易证一定存在度数为2的格子）

否则答案是1

（排除两个格子或以下的特殊情况）

一看hard直接题都不想读……
【引用自 ATF】:
观察法
我的直觉应该也属于观察法

大概分类讨论的类应该是有限的 只会有几种固定形态 然后考虑完所有可能的基本情况再继续思考

same

陆老师做了多少hard了

hard只要不是经典我不做啊哈哈

我还觉得单调栈是经典呢 我看你也不做啊

你这纯造谣了
【引用自 AWS】:
感觉课上也没学过啊
就那一个题还是看着design写的，做了一遍忘了
image2994×318 57.8 KB

【引用自 Lunasol】:
单调栈是经典呢
what the are you even talking about?

栈 is stack

【引用自 AWS】:
queue
【引用自 Lunasol】:
栈
@ATF

难怪卧槽

哦 单调队列……那不更基础知识了吗

我看到mono 就自动补全单调栈了

明显mono stack题多

你看我的样例2，所有节点强连通但是答案是1
【引用自 AWS】:
陆老师做了多少hard了
leetcode的难度也就图一乐
【引用自 Lunasol】:
我看到mono 就自动补全单调栈了
为什么要看mono，不去看homo

images300×168 5.93 KB

你们做的都太难
【引用自 ATF】:
图一乐
我这种土逼做不出来

【引用自 ATF】:
不去看homo
the homo is erect

样例二不强连通啊？

既视感和图论表示不大一样，因为斜着是没有边的，1和2都强连通（你是想说1像是完全图吗）

SCC指任意两点存在两条不相交连通路径啊

以及我刚刚交了个答案，至少lc的test case都是对的

哦你说的这个不是SCC，是BCC（双联通分量），这个问题确实可以认为在求图是否点双连通，但是求图是否是双联通图和求是否存在割点应该是等价的

当然我肯定是选择暴力枚举以后找连通分量个数，因为我懒

我看了下我2020年写的做法，并不需要找什么割点

思路是判断唯一一个联通分量的双连通性还是别的什么我悟不到的

这个思路找割点应该是时间复杂度最低的，但暴力好写也能过样例

嗯数据规模很小，我的做法就是暴力的

想了一下应该是只要把一个格子分离出去就好了，这样最多就两天。然后找一下有没有一天的解决方案，割点确实是很直观的想法，不过算法从来没记住过

这种题确实适合轮子哥

脑子生锈了，找了资料看了好几遍才再次学会

确实

如果有>1个连通分量返回0

如果唯一的联通分量有割点返回1（tarjan O(m+n)或者暴力枚举O(m²+n²)）

否则联通分量双联通，返回2

我已经不会tarjan了，只会背板子；有向图找联通分量我也是用kosaraju

这题真不是图论吧，m,n<=30明示O(n^4)可过。考虑左上角格子，知道结果不会超过2。那实际上判断0/1即可。

无视数据范围写最优解的话就是图论，不然虽然还是要迫真dfs一下但就是纯纯的暴力

【引用自 Sleepless】:
m,n<=30明示O(n^4)可过
又不是考试，这样弄多没有意思。而且我司面试很多人也是不给数据范围的，因为现实中的数据是海量的，累计超过nlgn的方案都是没有实际意义的，好在现实中的问题一般会对一个数据集问很多次，有很多奇技淫巧可以用

那是不是面试你司不给n log n就会挂

这倒不会，哪怕是做不出来也可能能过的，拿满分不是唯一标准

到时候希望轮子哥给我个strong hire

傻逼了，原本想着用平衡树，写到一半想起来为什么不用小顶堆

https://leetcode.com/problems/kth-largest-element-in-a-stream/

还有个特判，那是真的sb

广告： \color{red}征友，\color{blue}希望可以婚绿\color{orange}130

【引用自 ATF】:
征友，希望可以婚绿130
开新帖啊，最好有图

【引用自 ATF】:
上周没买到的熟食被发现产线被污染，食物中毒43人住院多人死亡
我是虚弱的肥肥老登，见过我的几个钛金可以作证
哭了zs

你为啥做的题都这么奇怪

每日一题啊

哦…

今天复习dp

泥潭都不敢发

征友 提供婚绿

【引用自 ATF】:
征友，希望可以婚绿130
话说这啥，html?

DP啥DP，暴搜然后@lru_cache秒了
【引用自 ATF】:
日常写一坨屎发泥潭：
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
dp: Callable[[int, int], float] = (lru_cache(maxsize=len(prob)*target+64)(lambda i, heads: 1.0 if i==-1 and heads == 0 else 0.0 if i<0 or heads < 0 else (dp(i-1, heads-1)*prob[i] + dp(i-1, heads)*(1-prob[i]))))
return dp(len(prob)-1, target)
【引用自 AWS】:
话说这啥，html?
【引用自 未知】:
魔法小课堂
\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{red}\, 水老师小课堂开课啦 \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\co…

你做的多可以啊，我写不出来转移方程不是直接傻逼

我的见解：不要纠结转移方程，尝试寻找DP维度和每个维度的含义（也就是需要什么转移状态而不是怎么转移状态；或者说给定哪些状态可以求出相应答案），然后直接爆搜你会豁然开朗

抱歉，可能理解错了，我以为大家在讨论leetcode每日一题。

n~1000的话你是对的，要求一个articulation point。但这种题更可能在codeforces上出现吧。

我还以为这俩是一起的

我是这个意思

确实是lc每日一题，我就是喜欢讨论一下能过lc弱数据的解法和能想到的最优解法

毕竟我写lc不打cf一是脑子不好使，二是生活所迫……

lc什么时候更新的UI

我一直在用老的

@atf @lunasol

【引用自 AWS】:
转移方程
这不是必要的，能理解转移的现实意义也能写出来

不行下次不能说中文了

https://leetcode.com/problems/combination-sum-ii

我知道是回溯，捣鼓半天写出来了但还是不懂，屌大的坛友能不能讲讲为什么“如果不选择元素i，那所有和a[i]相等的元素全部不能选”和“没有重复的组合”是等价的？

我的代码：
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end(), std::greater<int>());
vector<vector<int>> soln;
std::function<void(int, int, vector<int>&, int)> search = [&](int idx, int remaining, vector<int>& curr_nums, int ignore) -> void {
if (remaining == 0) {
vector<int> s (curr_nums);
soln.push_back(s);
return;
}
if (idx >= candidates.size()) return;
if (candidates[idx] <= remaining && candidates[idx] != ignore) {
curr_nums.push_back(candidates[idx]);
search(idx + 1, remaining - candidates[idx], curr_nums, ignore);
curr_nums.pop_back();
}
search(idx + 1, remaining, curr_nums, candidates[idx]);
};
vector<int> temp;
search(0, target, temp, -1);
return soln;
}

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

【引用自 ATF】:
如果不选择元素i，那所有和a[i]相等的元素全部不能选
这个题里这不是说了里面都只出现一次吗

求的是和那不就等价吗

又一个一看组合题就不读题的是吧

因为这题的定义里是不区分相同元素。对于相同元素，如果你已经选了一个，只可能是继续叠加才能不同；而如果你skip了一个，继续选择则有可能会出现相同的组合。

对于这种题目我一般会先预处理出所有元素的频次，然后搜索的时候做整体处理，对于每一个元素递归进选0、1、2…个的情况，也就不会有重复的了。有点类似于多重背包的处理手法。

wocao，太透彻了，%%%

只做过i 等会看看

https://leetcode.com/problems/find-k-th-smallest-pair-distance/

写了好久二分，最后看题解发现

需要滑动窗口（我本来以为是再用lower_bound二分）
桶排序也是可以过的

说实话，现在写二分也写不动了，ctmd，我废了

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

这题里的abs其实是没用的，直接排序之后只计数 (i, j) where i < j 的所有pair就跟原来的abs等价了。接下来就二分答案，对于每个 i 看看有多少个使得 a[j] - a[i] < ans ，算一下比 k 多还是少。两重二分 O(n log^2 n) 。
【引用自 ATF】:
滑动窗口
确实可以优化掉第二个二分。不过如果是打比赛我肯定想不起

膜%%%%%%%

今天题非常简单，模拟+贪心

https://leetcode.com/problems/lemonade-change

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

https://leetcode.com/problems/minimum-moves-to-get-a-peaceful-board/

还有这种贪心题，就是你觉得可能确实是贪心，写出来也能过样例，但是你就是想不通为什么是对的

大家快来看呀，这里有个变钛啦

https://leetcode.com/problems/maximum-distance-in-arrays/

有一种贪心的即视感，最后写出来确实也是维护最大的最大值和最小的最小值，然后用2sum那种回头看来保证没有重复

一开始还以为是两个大小为2的堆，我真是弱智

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

https://leetcode.com/problems/tuple-with-same-product/

观察法可以得出每两组积相同的数对可以有8个元组（222），那n个积相同的数对就有 \binom{n}{2}\times8 个

最后用Python写的，因为STL没有comb函数

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

comb是什么函数

算组合数咯

就是 a!/b!(a-b)! 吗？

对的

确实，但是自己写就要考虑溢出、打表、复杂度，不如换个语言用现成的

https://leetcode.com/problems/maximum-number-of-points-with-cost

朴素O(mn^2)解法会TLE，DP很简单但是仔细一看就会发现DP完全没有复用任何状态，本质就是暴力

看了题解才知道是DP套DP可以O(mn)，真tm弱智

也可以dp套单调栈

比如对于第一行，想象每个位置都是一个高度是对应的值，然后左右斜率-1/1的帐篷形状，易发现只需要维护帐篷的天际线就可以满足下一行的转移。

这个天际线很容易用单调栈计算。

然后之后每一行帐篷高度就是那个位置的dp值，这样还不用像题解一样2 pass，1 pass就可以了。
My Solution
impl Solution {
pub fn max_points(points: Vec<Vec<i32>>) -> i64 {
let m = points.len();
let n = points[0].len();

let mut last_row: Vec<(i64, i64)> = Vec::with_capacity(n);
let mut this_row: Vec<(i64, i64)> = Vec::with_capacity(n);

let mut points_it = points.into_iter();
for (i, v) in points_it.next().unwrap().into_iter().enumerate() {
let i = i as i64;
let v = v as i64;
if last_row.last().map(|last| v > last.1 + last.0 - i).unwrap_or(true) {
while last_row.last().map(|last| last.1 <= v + last.0 - i).unwrap_or(false) {
last_row.pop();
}
last_row.push((i, v));
}
}

for row in points_it {
let mut candidate_it = last_row.drain(..).peekable();

let mut candidate = candidate_it.next().unwrap();
for (i, v) in row.into_iter().enumerate() {
let i = i as i64;
let v = v as i64;
if let Some(new_candidate) = candidate_it.next_if(|new_candidate| candidate.1 + candidate.0 + new_candidate.0 <= new_candidate.1 + 2 * i) {
candidate = new_candidate;
}
let v = v + candidate.1 - candidate.0.abs_diff(i) as i64;
if this_row.last().map(|last| v > last.1 + last.0 - i).unwrap_or(true) {
while this_row.last().map(|last| last.1 <= v + last.0 - i).unwrap_or(false) {
this_row.pop();
}
this_row.push((i, v));
}
}
drop(candidate_it);
std::mem::swap(&mut this_row, &mut last_row);
}

last_row.into_iter().map(|(_, v)| v).max().unwrap()
}
}

经典题经典做法斜率优化但是rust

原来还能斜率优化，%%%%%%%

这个题解写的不好。切换输入法太麻烦，接下来打英文了，见谅。

Use DP. Let dp[i][j] be the max result obtained at row i, col j. The transition is just dp[i][j] = points[i][j] + max_k (dp[i-1][k]+ |j-k|). Now let us consider all k<=j. This expression can be simplified to points[i][j] + j + max_{k<=j} (dp[i-1][k]-k). This means if we take a linear scan from left to right, we can maintain max_{k<=j} (dp[i-1][k]-k) with O(1) update time. Similar consideration gives the pass from right to left.

其实rust挺适合写lc的，懒得开本地开发环境的情况下在lc上debug segfault可太痛苦了。

我现在一般看lc.cn的题解，写得比英文版好的不是一点半点，和大佬您写得思路差不多

%%%%%%%

我打lc比赛全都是在网页上直接写的 问题不大，只要不在乎排名就都无所谓

CF爆零以后捶桌子，LC爆零以后哈哈大笑

meanwhile我还在给我GacUI的几十个control做unit test，录屏成矢量图后跟snapshot比，每天做点苦力活，好久没写feature了

https://leetcode.com/problems/ugly-number-ii/

寄

这里只聊每日一题吗，今天周赛好难啊

周赛T4确实一时半会看不到思路，T2应该是用栈吧

楼上还有洛谷和CF上分讨论，有没有Codeforces交流

这题确实有挑战性，比赛一个小时很容易就挂了。以下仍用英文，见谅。

Notice the following points:

let RV[i] be the largest index j so that s[i,j] is k-constraint. Then we can compute RV[i] for all i in O(n) time with two-pointer method
For query (l,r), the result is just \sum_{k=l}^r (\min(RV[k],r)-k+1). That is, we consider each starting position k, then the possible ending positions are k,k+1,\cdots,\min(RV[k],r).
RV[i]\geq i and RV[i] is non-decreasing in i. So we can use binary search to find the largest \hat k where RV[\hat k]\leq r. The rest can be done with prefix-sum.

想渲染 \LaTeX 可以用 $ 包起来

可以当作数组不断变长的三路归并

是这样的，本来想用数论方法解但是想了想还得用队列

Discourse对$含义的启发式算法对非分词语言是非常不友好的

但是 你 也 不能 期望 所有 中文 使用者 在 交流 的 时候 分词

考虑到$524 = (1+1)*4+514-11+4-5+14$，证明Chase野兽先辈说成立是朴素的。\blacksquare
考虑到$524 = (1+1)*4+514-11+4-5+14$，证明Chase野兽先辈说成立是朴素的。$\blacksquare$

考虑到 524 = (1+1)*4+514-11+4-5+14 ，证明Chase野兽先辈说成立是朴素的。\blacksquare
考虑到 $524 = (1+1)*4+514-11+4-5+14$ ，证明Chase野兽先辈说成立是朴素的。$\blacksquare$

英文就没有这个问题：

Considering the fact that 524 = (1+1)*4+514-11+4-5+14, the proof of the theory which asserts Chase is Yaju Senpai is simple.
Considering the fact that $524 = (1+1)*4+514-11+4-5+14$, the proof of the theory which asserts Chase is Yaju Senpai is simple.

$524 = (1+1)*4+514-11+4-5+14$を考慮すると、「Chaseは野獣先輩である」という命題が成立することを証明するのは明白である。\blacksquare

同理

@uscreditcardguide 不知道这是Discourse上游的问题还是论坛设置的问题？

看起来是Discourse的问题，测试里似乎只考虑了$$紧接中文、日文、阿拉伯文标点前后的时候：

github.com

discourse/discourse-math/blob/686736d3c2221b18b8c103b57e08964329c83c33/spec/pretty_text_spec.rb#L41-L51

it "can handle inline math with Chinese punctuation" do
cooked = PrettyText.cook("这是一个测试，$a^2 + b^2 = c^2$，这是另一个测试。")
html = '<p>这是一个测试，<span class="math">a^2 + b^2 = c^2</span>，这是另一个测试。</p>'
expect(cooked).to eq(html)
end

it "can handle inline math with Japanese punctuation" do
cooked = PrettyText.cook("これはテストです、$a^2 + b^2 = c^2$、これもテストです。")
html = '<p>これはテストです、<span class="math">a^2 + b^2 = c^2</span>、これもテストです。</p>'
expect(cooked).to eq(html)
end

我本来想二分答案，然后算三维空间里平面 \ln(2)x+\ln(3)y+\ln(5)z\leq \ln(m) 和 xy, yz, xz 围成的simplex内的整数格点。但是发现这个多面体不适用三维的Pick’s Theorem，最后就只能乖乖队列了。

这个二分可以呀，因为(x,y,z)的取值至多是(log n)^3的，爆算可过。

今天倒的确是一眼数论

主要是本来以为有什么神奇公式（

https://leetcode.com/problems/2-keys-keyboard

我是数论想了半天没想到因数分解，就 O(n^2) 递推做了，我数学基础真的好差

然后发现打表才是归宿：
int minSteps(int n) {
array<int, 1003> dp = {0,0,2,3,4,5,5,7,6,6,7,11,7,13,9,8,8,17,8,19,9,10,13,23,9,10,15,9,11,29,10,31,10,14,19,12,10,37,21,16,11,41,12,43,15,11,25,47,11,14,12,20,17,53,11,16,13,22,31,59,12,61,33,13,12,18,16,67,21,26,14,71,12,73,39,13,23,18,18,79,13,12,43,83,14,22,45,32,17,89,13,20,27,34,49,24,13,97,16,17,14,101,22,103,19,15,55,107,13,109,18,40,15,113,24,28,33,19,61,24,14,22,63,44,35,15,15,127,14,46,20,131,18,26,69,14,23,137,28,139,16,50,73,24,14,34,75,17,41,149,15,151,25,23,20,36,20,157,81,56,15,30,14,163,45,19,85,167,16,26,24,25,47,173,34,17,19,62,91,179,15,181,22,64,29,42,36,28,51,16,26,191,15,193,99,21,18,197,19,199,16,70,103,36,24,46,105,29,21,30,17,211,57,74,109,48,15,38,111,76,20,30,42,223,17,16,115,227,26,229,30,21,35,233,21,52,63,82,26,239,16,241,24,15,65,19,46,32,37,86,17,251,17,34,129,25,16,257,48,44,22,35,133,263,20,58,28,92,71,269,16,271,25,23,139,21,30,277,141,37,18,281,52,283,75,27,26,48,16,34,36,100,77,293,19,64,43,20,151,36,17,50,153,104,27,66,25,307,22,106,38,311,22,313,159,18,83,317,58,40,17,110,32,36,16,23,165,112,47,54,21,331,87,43,169,72,18,337,28,116,26,42,27,21,49,31,175,347,36,349,19,22,21,353,64,76,93,27,181,359,17,38,183,25,24,78,66,367,31,47,44,60,38,373,30,18,53,42,18,379,28,130,193,383,17,23,195,49,101,389,23,40,20,134,199,84,21,397,201,29,18,401,72,44,105,17,38,48,26,409,48,140,107,66,31,88,23,142,32,419,19,421,213,53,59,27,76,68,111,27,50,431,17,433,40,37,113,42,78,439,22,20,32,443,44,94,225,152,19,449,18,52,117,154,229,25,28,457,231,26,32,461,23,463,37,39,235,467,23,74,54,160,65,54,84,29,28,59,241,479,18,50,243,33,26,102,17,487,67,166,21,491,48,46,34,22,39,78,88,499,19,170,253,503,19,106,36,29,131,509,27,80,18,28,259,108,50,58,46,176,24,521,37,523,135,20,265,48,22,46,60,65,30,54,94,112,73,182,271,25,18,541,273,184,27,114,25,547,141,67,23,48,32,86,279,45,143,557,39,56,20,31,283,563,54,118,285,19,77,569,29,571,28,194,50,33,18,577,36,196,38,90,102,64,79,24,295,587,21,50,66,200,45,593,22,29,153,202,38,599,19,601,52,73,155,27,106,607,29,39,68,60,27,613,309,49,24,617,108,619,40,32,313,96,24,20,315,33,161,54,20,631,85,214,319,132,60,27,42,77,19,641,112,643,34,51,38,647,18,70,25,41,167,653,114,136,49,79,56,659,23,661,333,33,89,31,45,52,171,226,74,72,20,673,339,19,30,677,118,104,28,230,44,683,29,142,23,232,51,66,33,691,177,24,349,144,38,58,351,236,21,701,24,56,23,55,355,108,66,709,78,85,95,54,29,29,183,242,361,719,19,110,40,244,185,39,27,727,26,18,80,60,68,733,369,22,33,78,49,739,46,35,62,743,40,154,375,89,32,114,20,751,55,254,44,156,20,757,381,37,30,761,132,116,195,28,385,72,19,769,25,260,197,773,51,41,103,47,391,60,25,82,42,38,22,162,136,787,201,266,86,120,23,74,399,61,203,797,31,64,20,95,403,84,74,35,46,272,107,809,19,811,40,274,50,168,28,62,411,26,50,821,142,823,109,24,68,827,33,829,90,280,25,31,144,172,34,40,421,839,21,58,423,284,215,31,55,29,61,286,29,60,78,853,70,30,113,857,29,859,52,51,433,863,19,178,435,37,42,90,39,80,115,103,44,22,80,877,441,296,24,881,22,883,34,67,445,887,46,134,96,23,227,66,154,184,21,39,451,60,20,70,54,53,119,186,156,907,231,107,27,911,30,94,459,69,233,138,28,919,34,310,463,84,25,47,465,109,39,929,41,33,237,314,469,33,25,937,76,316,56,941,162,64,67,21,56,947,86,86,31,320,30,953,61,196,243,43,481,144,20,62,52,113,245,198,35,967,28,39,104,971,19,146,489,26,69,977,168,100,23,115,493,983,50,202,48,57,36,66,24,991,41,334,80,204,90,997,501,46,21};
return dp[n];
}

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

这样着没意思

https://leetcode.com/problems/stone-game-ii

minimax dp，一开始TLE结果发现只是@lru_cache开得不够大

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

https://leetcode.com/problems/strange-printer

DP写不出来，玉玉了，其实转移方程很简单

（LC英文版的题解就是一坨屎）

ok，黑神话启动

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\\ \color{orange}送我黑神话DLC}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

你这广告真的可以

https://leetcode.com/problems/number-complement

可以用全1的掩码：
int findComplement(int num) {
int mask = 1;
while (mask < num) mask = mask * 2 + 1;
return (~num) & mask;
}

或者bitset?
int findComplement(int num) {
std::bitset<32> bs {static_cast<unsigned>(num)};
bool flag {false};
for (short i = 31; i >= 0; --i) {
if (!flag && bs[i]) flag = true;
if (flag) bs[i] = ~bs[i];
}
return bs.to_ulong();
}

有没有什么更巧妙的解法

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

掩码可以不用循环，branchless地来计算
pub fn find_complement(num: i32) -> i32 {
let mut v = num;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
!num & v
}

int findComplement(unsigned num) {
return ~0u>>countl_zero(num)&~num;
}

intrinsic大法

我觉得后端应该同时编译三个平台四个cpu，都通过才开始跑，阻止作弊

说得好，但是这个函数已经进标准了

https://leetcode.com/problems/generalized-abbreviation

爆搜，没什么好说的

https://leetcode.com/problems/fraction-addition-and-subtraction/

解析字符串然后求LCM，难点在于解析字符串

力扣 LeetCode

3145. 大数组元素的乘积 - 力扣（LeetCode）

3145. 大数组元素的乘积 - 一个非负整数 x 的 强数组 指的是满足元素为 2 的幂且元素总和为 x 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明，x 对应的强数组是独一无二的。

数字 二进制表示 强数组 1 00001 [1] 8 01000 [8] 10 01010 [2, 8] 13 01101 [1, 4, 8] 23 10111 [1, 2, 4, 16]

我们将每一个升序的正整数...

不会，再见

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

image1179×667 53.1 KB

手机屏幕窄没有自动换行，你的latex需要改进

这题还是没啥难度哒，求一下前缀和就完了

1e16，存前缀和会MLE吧，还是我的姿势水平太低了

【引用自 ATF】:
富婆大姐姐请大力送我
请富婆大姐姐对我大力输出

我觉得是这样

首先只需要会算big_nums[1..n].product() % MOD，big_nums[i..j] % MOD可以通过计算big_nums[1..j] 和 big_nums[1..i-1]，加上一点中国剩余定理和逆元算出来。
big_nums[1..n].product() 其实就是统计1, 2, 4, 8在1…n里用了多少次，用一些取模和除法运算很容易算出来，然后快速幂就行了。

【引用自 ATF】:
存前缀和会MLE吧
当然不是存前缀和，前缀和log就能算出来。
【引用自 YoumuChan】:
big_nums[1..n].product() 其实就是统计1, 2, 4, 8在1…n里用了多少次，用一些取模和除法运算很容易算出来，然后快速幂就行了。
不错，所谓的乘法就是数2的个数，直接转化成了求和。应该都用不上CRT，因为 10^{15} * 64 * 64 < 10^{18} 。

我想到了logn求前缀序列长度，但是完全没有意识到用幂运算求和，我还是太菜了

%%%%%%%一下大佬们

每一步都看得懂，连起来就看不懂了，暂时跳过这题，我是sb

感觉是个二分计数集大成题。首先得注意到 powerful array就是一个数的二进制表示。接下来可以考虑如下几个简单的分解问题：

给定 n,k，由 1,2,\cdots ,n 生成的big_num数组有多少项 2^k?
给定 n，由 1,2,\cdots, n 生成的big_num数组有多少项?
给定 r，big_num [1,\cdots,r] 是从 1,\cdots, n 中产生的？这里可能会多出来几项，是从n+1里来的。
如果我们能知道big_num [l,\cdots,r] 中有 a_0 2^0, a_1 2^1, a_2 2^2,\cdots，那我们最后要求的就是 \prod (2^i)^{a_i}\mod (mod)=2^{\sum_i i\cdot a_i}\mod (mod)。问题2本质上是在求 \sum_i a_i，但其实稍微改改就能求 \sum_i i\cdot a_i，就做完了。

这么多聪明坛友 压力好大

聪明坛友给这条点姚明 感觉压力更大了

我不点姚明，我是笨逼

你可以点哭哭

又是一道脑筋急转弯傻逼毒瘤题

https://leetcode.com/problems/find-the-closest-palindrome

陆老师的账号快要变成ATF的形状了

image422×592 23.4 KB

image440×597 24.3 KB

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

https://leetcode.com/problems/binary-tree-postorder-traversal

用递归写应该是小学级别的题目，用迭代不会

https://leetcode.com/discuss/general-discussion/5686582/weekly-contest-412

扭老师评论过操别人的老婆，古人总结出的智慧估计也包括“别人的女朋友可以站起来蹬”；很可惜，作为一名处男从来没有体验过这种感觉；

今天发现用别人的账号打比赛或许能让我体验到类似的感觉：打完一盘Apex进比赛就发现迟到了，T1T2轻松搞定后可以直接下号，随便WA、TLE、爆零都无所吊谓，太爽了

（这，就是我作为男的证明，大家在日批我却做题都不利索）

T1可以用栈轻松解决，T2最后我用的字符串，T3我觉得肯定不是写高精度直接复制思路，可能有什么神奇的数学思路我不懂

T4看都没看

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

T3可以先把数字都转成multiplier进制的数，然后用T1先把他们都变成位数一样的。假如剩下次数 k, 一共有 n 个数字，那么现在最小的 k % n 个数会在最后被乘 （k / n) + 1次，其余的数被乘k / n次，快速幂就行了。

【引用自 ATF】:
用别人的账号打比赛
是我的账号吗

是的陆老师，忘记切号了

懂了，用T1模拟做到某个状态以后剩下的操作就是纯绕圈乘了，可以快速幂

我是这个帖子里智商最低的SB

【引用自 ATF】:
T4看都没看
LeetcodeCN AK的老哥亲测，T4靠暴力+哈希是可以过的

我是 \Huge傻逼

你居然敢
【引用自 ATF】:
站起来蹬
陆老师

的账号

不要恶意删节

这题确实太恶心了，卡人的点在于六位数做两次操作，最多是 6\cdot 5\cdot 4\cdot 3=360 种办法，这个比5000小太多，而5000 * 360就可过了。

https://leetcode.com/problems/n-ary-tree-postorder-traversal

ez，打卡下班
vector<int> postorder(Node* root) {
if (root == nullptr) return vector<int>();
vector<int> result;
stack<Node*> st;
Node* last = nullptr;
st.push(root);
while (!st.empty()) {
Node* current = st.top();
if (current->children.size() != 0 && last != current->children.back()) {
for (auto it = current->children.rbegin(); it != current->children.rend(); it++) {
st.push(*it);
}
} else {
result.push_back(current->val);
last = current;
st.pop();
}
}
return result;
}

我哪敢啊水老师

要断章取义，节选自不要断章取义

https://leetcode.com/problems/path-with-maximum-probability/

虽然显然没有负环，但是男友算法比Dijkstra好写

F-W会TLE

震惊了，BF都能跑那么快，LC都怎么写的

image2527×788 102 KB

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

https://leetcode.com/problems/count-sub-islands/

这题应该用并查集做，但是我暂且双重dfs一条道走到黑了

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column

一开始以为是贪心，看了标签是并查集就懂了，对元素 Si=(x,y)， \forall n, S_j=(x, n) 和 \forall n, S_k=(n, j) 属于一个集合，我注意力涣散，但可以注意到

每个并查集 D_i=\{d_{i,1}, \cdots, d_{i,n}\} 总有一种办法选择一个 d_{i, k} 并按规则删除所有 \forall j, j \neq k, d_{i, j}\in D_i
对于任意两个元素 \forall i, j, x, y; i\neq j \implies d_{i, x} d_{j, y} 必定永远不能相互删除

也就是说线性搜索一遍以后并查集的数量就是最后留下的石子的数量

这道题不难，但对我这种注意力涣散的人非常不友好

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

我的并查集模板，一坨屎但是性能也一般：
struct UF {
std::vector<int> p;
std::vector<int> s;
DisjointSet(int maxSize) {
p.resize(maxSize); s.resize(maxSize);
for (int i = 0; i < maxSize; ++i) {
p[i] = i; s[i] = 1;
}
}

int f(int v) {
if (v == p[v]) return v;
return p[v] = find(p[v]);
}

void u(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
if (s[a] < s[b]) std::swap(a, b);
p[b] = a; s[a] += s[b];
}
}
};

今天这个两遍最短路好有意思啊，感觉是两个月以来遇到的最有意思的题。

大佬牛逼，这是一道CF黄名级别（2300分段）题，只不过LC数据变弱了

https://codeforces.com/problemset/problem/715/B

https://codeforces.com/blog/entry/47169

跑两遍最短路是用的修改版最短路算法吗

我反反复复看了好几遍题解的总思路才想出一个暴力做法，当然因为数据弱很神奇地过了

https://leetcode.com/problems/modify-graph-edge-weights

我最后的思路和CF的题解1类似（证明最短路可能包含可变边后跑最多n遍Dijkstra/SPFA），LCCN题解1的思路和CF的题解2类似，但都需要跑多遍Dijkstra，但是考虑到图比较稀疏，应该问题不是非常大？

考虑到这种做法可以AC掉CF的数据，我释怀了

哎，我好笨啊，做这种题一点也不开心

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

用玩解谜游戏的说法来说的话，这题好就好在游戏的引导做得非常好，完全可以一步一步做出来

看到题的第一个疑问就是，在什么情况下无解？很容易想到两种情况，不考虑能改的边和考虑能改的边

i. 如果完全不考虑能改的边的时候最短路小于目标，那么无论我怎么改边，都不会让这个值变大，那么无解。（第一遍最短路）

ii. 如果能改的边全部都是1的时候最短路大于目标，那么无论我怎么改，都不会让这个值变小，那么无解。（第二遍最短路）
接下来自然的问题是，如果1.i那个值等于目标怎么办？把边改成无穷大（2x10^9）就行了。
剩下的情况就是第一遍最短路比目标大，第二遍最短路小于等于目标了。那么这时第二遍最短路用到的路径里必然有能改的边（不然违反第一遍最短路找到的长度），大概能想到改改这条路径里能改的边是不是就能凑出目标。不在这条路径里的边可以直接改成无穷大。
接下来的问题就是如何修改这条路径。我们要防止的是把一条边改得太小导致一条更短的最短路出现，那也就是说，我们需要维护最短路的不变量，对于修改后的最短路 s 的每一条边 (s_i, s_{i+1}), 我们希望 d(s_0, s_{i+1}) = d(s_0, s_i)+w(s_i,s_{i+1}) 其中 d 是最短路距离， w 是边长。

假设第一遍最短路求得的最短路距离是 d_0 , 我们只需要保证 d_0(s_0, s_i)+w(s_i, s_{i+1})+\dots+w(s_k, dest)\geq target ，就可以防止把 w(s_i, s_{i+1}) 改得太小被其他的路偷鸡。

所以倒着遍历路径，遇到一条能改的边 (s_i, s_{i+1})，算一下 target - d_0(s_0, s_i) - (w(s_{i+1}， s_{i+2})+\dots+w(s_k， dest)) 这个值就是这条能改的边最少需要改的长度，我们把这条边就改成这个长度（当然如果这个值是非正的就改成1）。

考虑一下最短路上正着数的第一个能改的边（一定存在）加上最短路性质，就会发现这么改改出来就会正好是目标长度。

两遍最短路证明有解是朴素的，如何
【引用自 YoumuChan】:
我们要防止的是把一条边改得太小导致一条更短的最短路出现
我是真没想出来，拜读一下大佬的答案

更新：

我最最最开始的思路也是这样的，找一条可行的最短路，然后轮流更新里面可以改的边权重保证最短路不会被偷鸡（不可变边不会偷鸡因为本身没有），但是我实在是没法证明正确性，所以就暴力了

我现在还没搞懂的就是类似这种情况：

3->5这段如果在最短路里是不能>2的（不然会被3-4-5偷鸡），一开始算以0为源的最短路用无穷大求出的这个权重确实是1，但是我想不出怎么证明正确性

我们只需要考虑边长的下界，不用考虑上界，因为有解的性质（EDIT：更严谨地说是距离函数的三角形不等式）保证了下界小于等于上界，所以只要永远赋值下界就行了。

你这图假如target=6，目标最短路0-2-3-5

因为目标dist[5]=6，dist_0[3]=inf，所以我们需要dist[3]+w(3,5)=dist[5]并且dist[3]<=dist_0[3]就行了，那么w(3,5)的取值其实没啥限制，所以下界是1，那就赋值1

现在目标dist[3]=dist[5]-w(3,5)=5，dist_0[2]=2，我们需要w(2,3)=dist[5]-dist[3]>=dist[5]-dist_0[3]=3，所以下界是3，赋值3

现在目标dist[2]=2，所以w(0, 2)赋值2

nb，%%%%%%%%%%%%%%%

你们这都能找到，发现我竟然做过，感觉挺恶心一题

然后今天也

Leetcode今天每日是27号的题导致一直无法签到，他们修复方法好像是把27号的题改成了2sum

image437×620 37.2 KB

https://leetcode.com/problems/path-sum-iv/

SB模拟题，明天歇一天去放松一下

广告：

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

超讨厌这些binary search over answer 的题目，这不就是应试教育吗，现实里哪会有这种情况

（不引用上面的具体题目）

我觉得会这个思路很重要，但是二分查找面试这么火大概真的是纯纯的cjb

在工程上“单调”这个保证太奢侈了

轮子哥，求一个微软内推

clear 不就行要不然怎么记得下来

【引用自 ATF】:
求一个微软内推
你求到多少了

1 YOE 羡慕死了

感觉dfs没啥问题吧，真的需要UF?

刷了题对工作/学习有帮助吗

【引用自 ATF】:
求一个微软内推
blind上说又要freeze headcount折腾了

哦我日

前几天刚一口气申了十几个

全聚德

0个，轮子哥给就是1个

当然是背啊，好记性不如烂键盘，多WA几遍就背过了

ATF的解答和评论之类的写得太好了

有三哥顺着ATF的解答兔子洞人肉我了

并且想connect

根据他的枚举，他发现了我在互联网上所有非纯中文的活动站点

【引用自 Lunasol】:
三哥
???

我就忘记切号骂了一下LC啊陆老师

而且@ ctzsm @ YoumuChan @ Sleepless 这三位才是真神
【引用自 Lunasol】:
根据他的枚举，他发现了我我在互联网上所有非纯中文的活动站点
这就是为什么要每个平台用不一样的ID，打一枪换一个地方（逃

倒不完全是id一样

我每个网站都留指向下一个站点的指针了

而且留得比较明显
【引用自 ATF】:
@ ctzsm @ YoumuChan @ Sleepless
偷偷假艾特也太坏了
【引用自 ATF】:
忘记切号
第二次忘记切号 有理由怀疑是故意忘记切号

我会故意留下链接到别的网站的假信息增大盒武器使用难度
【引用自 Lunasol】:
偷偷假艾特也太坏了
惊扰了巨佬是要杀头的
【引用自 Lunasol】:
第二次忘记切号 有理由怀疑是故意忘记切号
这不是要给陆老师刷个八月全勤吗，全勤出了bug肯定是要狠狠斥责lc

T3强行状压DP+剪枝，一个样例让我难逃TLE命运

image1061×301 9.92 KB

我日，为什么C++状压DP就能过，气抖冷

哦，原来应该状压行

T4可以暴力过，我其实规律都找出来了

难受，黑马楼启动

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

https://leetcode.com/problems/add-two-polynomials-represented-as-linked-lists/

挺有意思的题

https://leetcode.com/problems/find-missing-observations/

弱智模拟

https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array

没啥意思，明天暂停一个周末，去尝试找一把五六半

python 那个 x in list 的实现会tle 呃 好蠢

dfs和验证写一起，TLE了

https://leetcode.com/problems/linked-list-in-binary-tree/

不知道为什么一定要分开写

【引用自 ATF】:
为什么一定要分开写
什么是分开，我暴力过了，数据量那么少，虽然性能很差
bool isSubPathCannotSkip(ListNode* head, TreeNode* root) {
if (!head) return true;
if (!root) return false;
if (root->val == head->val)
{
if (isSubPathCannotSkip(head->next, root->left)) return true;
if (isSubPathCannotSkip(head->next, root->right)) return true;
}
return false;
}

bool isSubPath(ListNode* head, TreeNode* root) {
if (!head) return true;
if (!root) return false;
if (isSubPathCannotSkip(head, root)) return true;
if (isSubPath(head, root->left)) return true;
if (isSubPath(head, root->right)) return true;
return false;
}

看了第一名的代码，区别是先test后call还是先call后test，快了但是不DRY

如果同时dfs和验证就会TLE

tree is about DP

我最喜欢jeff在讲dp的时候说的这句话。把在复杂的数据结构上执行的算法抽象成dp状态图的话，会舒服一些。

DP is about 有向无环图中的爆搜

当年一个CTSC选手给我们讲的，后来我就就豁然开朗，龙场悟道

yes, that’s what Jeff said

and you can abstract it to “whatever-first-search”

你们俩这尬聊一看就不是一波人

https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list

昨天的题，这真没啥可说的吧，随便写写就秒了

上代码看看？（以及其实可以KMP，也是一种dfs和验证写一起）

我觉得可能是会重复遍历一些节点，但是我注意力涣散看不出来：
bool recurse(ListNode* head, ListNode* lst, TreeNode* tre) {
if (lst == nullptr) return true;
if (lst != nullptr && tre == nullptr) return false;
if (lst->val == tre->val) {
bool l = recurse(head, lst->next, tre->left);
if (l) return true;
bool r = recurse(head, lst->next, tre->right);
if (r) return true;
}
bool l = recurse(head, head, tre->left);
if (l) return true;
bool r = recurse(head, head, tre->right);
if (r) return true;
return false;
}

假如root匹配list第一个元素但是root.left不匹配下一个

你的代码会dispatch这几个搜索

(head, head, root) → (head, head.next, root.left) → (head, head, root.left.left)

(head, head, root) → (head, head, root.left) → (head, head, root.left.left)

注意到(head, head, root.left.left)在两种不同情况下都被查询了，估计是个指数复杂度。

压行怪来了
bool isSubPath(ListNode* head, TreeNode* root,bool start=1) {
if(!head)return 1;
if(!root)return 0;
if(root->val==head->val&& (isSubPath(head->next,root->left,0)||isSubPath(head->next,root->right,0)))return 1;
return start?isSubPath(head,root->left)||isSubPath(head,root->right):0;
}

还可以再压成一行

又来这招是吧
【引用自 ATF】:
NG找工投简历记录贴
ll _(ll $) {
ll $$; return (!$ || !($->next)) ? $ : (($$=_($ -> next)), ($->next->next=$), ($->next=0), $$);
}

【引用自 YoumuChan】:
注意到(head, head, root.left.left)在两种不同情况下都被查询了，估计是个指数复杂度。
难怪会TLE
【引用自 YoumuChan】:
以及其实可以KMP
Yet another大家津津乐道但是从来没用上过的算法

【引用自 YoumuChan】:
KMP
我这辈子是默写不出来了。但是我会默写AC自动机。

毕竟大佬是自动AC机

https://leetcode.com/problems/count-the-number-of-consistent-strings/

没什么好说的，普及组签到级别的题目

https://leetcode.com/problems/xor-queries-of-a-subarray/

注意到 a\oplus b\oplus b = a 且 a \oplus 0 = a，计算以0为首的前缀和即可

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

\Huge\color{purple}求\color{olIve}内\color{blue}推

https://codeforces.com/stream/693

看tourist和ecnerwala写kotlin

tourist给kotlin打了那么多年广告了，平时自己写题还是C++

毕竟JB是金主爸爸，面子还是要给的

Kotlin 刷签到题蛮好的，可惜 WF 没有签到题

水老师你的头像已经不是本人了

【引用自 未知】:
Amex在Walmart花50返10(三次) 信用卡
来凑头像颜色的热闹
[image]
晚些时候换回去

ICPC WF 开始了，有人看直播么……

打算看个开头。东部时间看直播是真的勇

不看，反正我也看不懂

Problemset

Scoreboard

看到签到题前半部分，还以为给一个order of numbers输出order of completing。然后最后看到probability，我：

其实只要关心最后一个被叫到的数字就好了……

笑死了，MIT 不会写 binary search

image1088×536 76 KB

unsigned long long 搞人心态

真的难绷……

第二时间想到了，第一下完全蒙了

笑死，MIT C题考虑了闰年，题目明确说了不考虑

Swarthmore College是哪位啊？这能NA第一的？

挂在 assert 上也是醉了……

image1920×646 62.4 KB

image1920×1100 184 KB

北大赢了

东亚（含 MIT）几乎一统天下了……

对了，北大在埃及拿了一个第一一个第二，这回还是同一拨人么？

话说一年三次 WF 也是活久见了……

不知道啊，才知道今年有3场，前两次都没关注

前年的因为疫情，去年的因为战争，都挪到今年了……埃及那场真是盛况空前，直接把人家神庙包场了……

虽然我知道l+((r-l)>>1)，但是我进不了MIT……

怎么感觉独联体大拉特拉啊

早就没落了

总算遇到一次可ak周赛了

又是做不出题摆烂的一天，该看题解了

T4虽然我知道是双指针但就是写不出来，操了都

最近周赛很喜欢出这种，比如https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-ii/description 感觉出题人的知识储备就到这了。

最近在忙研究+投简历，做题暂时耽搁一会

这轮CF被骂得好惨

Codeforces

Tutorial for Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 - Codeforces

Codeforces. Programming competitions and contests, programming community

三队人是完全不同的。北大这几年 WF 队都没有连打两年的。

毛子这几年太拉了，不知道是不是因为战争训练跟不上了。

这也太厉害了……

【引用自 Scape】:
不知道是不是因为战争训练跟不上了。
会不会是为了防止被拉壮丁都不在俄罗斯高校读书了

其实我更好奇的是 sjtu 为什么这几年也没落了……

【引用自 aqua】:
sjtu
斯人已逝，会+1s导致TLE（逃

钻的lab全体加起来，竟然占了这图中不少学校

要不然娃志不在此，要不然（俞勇）老师不管了吧

不太清楚具体发生了啥。我觉得之前毛子们垄断奖项是因为他们有质量非常好的训练营，不知道现在还在不在办了。

其实我觉得ICPC成绩不行反而是一件好事，这玩意大一打打差不多了，再往后挤占别的时间了。

确实，北美正经人谁打ICPC啊，直接刷题进大厂

FB hackercup round 1 Meta Hacker Cup - 2024 - Round 1

趁着国内小年轻半夜起不来可以试试偷鸡一波

完了，看都看不懂

C如果没有sample的话感觉挺难的，但有sample可以直接猜

一开始以为是个markov chain stoptime，后来发现不对啊，稍微算了下发现竟然有简单close form。

一个是uiuc一个是noi

t2 暴力

t3 dp+剪枝 两个样例疑似被卡常了

Problem C: Bunny Hopscotch | Meta Hacker Cup - 2024 - Round 2 明明有分类讨论的思路，但是时间不够写不出来了，难受

今天好多FST的，10分钟写个A1的暴力就能拿T shirt了

手快点A1A2都做出来甚至能进下一轮。后悔莫及啊

我又开始做题了，t1t2都不难，t3发现了规律（math.comb()算杨辉三角形->组合数递推公式）发现一直tle（python10个样例过不去，c++出了高精的问题），考虑到mod10，肯定没法简单直接套mod，然后就感觉是不是需要逆元或者卢卡斯定理？数学题我都不会，产生了一种深深的无力感

t4这种几何题就更不会了

等下看看题解，会不会常熟优化就可以过

我想问kattis应该怎么刷？

我刚开始接触算法竞赛

【引用自 SuKi2cn】:
我刚开始接触算法竞赛
洛谷试试？

有点经典了

不会做 摸了

泥潭有人今年去阿塞拜疆么

水老师要去带队吗

这次周赛第四题感觉是很适合llm的那种，sliding window median + best-time-to-buy-and-sell-stock，组装一下就好。

我看第三题卡住了不少llm，这个题是真有意思，我用hash + 二分错了一个case，不知道他怎么卡住我的，换了几次multiplier才凑巧过去。

我看直播

今天这t2t3真毒瘤吧

t2t3都是并查集，幸亏我会并查集

t4死活想不出来，看了题解发现原来可以秒，破防了

我的并查集模板
struct UF {
vector<int> size;
vector<int> parent;
int sets;

explicit UF(size_t _size) : size(_size, 1), parent(_size), sets(_size) {
iota(parent.begin(), parent.end(), 0);
}

int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}

void unite(int a, int b) {
int x = find(a);
int y = find(b);
if (x == y) return;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
sets--;
}
};

a老师好努力 还在刷题

因为被天竺人搞了 要失业了啊

https://www.uscardforum.com/t/topic/402930/2

不存在or不公开 你们lounge的吧

哦确实zs

陆老师怎么还没加入

什么失业帖子居然要放进lounge。并查集是少数几个我还能随手写的玩意 我打lc从来不用模板，都是现场在网页上手写，真实模拟面试环境。

听我谷歌的同学说L3L4可以和面试官说"let’s assume we have access to an efficient union-find implementation…"

放进钛金一是因为没写完，二是因为被管理员点草了

图片773×118 19.2 KB

图片784×187 13.6 KB

能不能偷偷发给我和c老师看

T1：暴力

T2：二分找连通分量数量

T3：正难则反，反推加入k的那个操作

T4：中心扩散+剪枝回溯，但没有用状压，最后状态爆炸了

531 / 537 个通过的测试用例，距离AK最近的一次

羡慕四题大佬

T4一直TLE，问了三个llm agent都没用，安老师帮我看看好不好

import functools

class Solution:
def maxLen(self, n: int, edges: List[List[int]], label: str) -> int:
neigh = {i: set() for i in range(n)}
for edge in edges:
u = edge[0]
v = edge[1]
neigh[u].add(v)
neigh[v].add(u)
@functools.cache
def dfs(l: int, r: int, visited: int):
max_len = 0
for l_child in neigh[l]:
for r_child in neigh[r]:
# 剪枝：确保不会往左/往右搜索两次
if l == r and l_child > r_child:
continue
if l_child == r_child:
continue
if label[l_child] != label[r_child]:
continue
if (visited >> l_child) & 1 == 1:
continue
if (visited >> r_child) & 1 == 1:
continue
new_visited = visited
new_visited = new_visited | (1 << l_child)
new_visited = new_visited | (1 << r_child)
max_len = max(max_len, dfs(l_child, r_child, new_visited) + 2)
return max_len
maxmaxlen = 0
for i in range(n):
visited = 0
visited = visited | (1 << i)
rv = dfs(i, i, visited)
maxmaxlen = max(maxmaxlen, rv + 1)
for edge in edges:
u = edge[0]
v = edge[1]
if label[u] == label[v]:
visited = 0
visited = visited | (1 << u)
visited = visited | (1 << v)
rv = dfs(u, v, visited)
maxmaxlen = max(maxmaxlen, rv + 2)
return maxmaxlen

出门右转力扣中文版 找0x3f题解

【引用自 ATF】:
T4
看完题：怎么这么神，根本不会做啊 qaq

再看到n <= 14：这不是
【引用自 ATF】:
状压
随便搞一下就完了。看了下你的代码你也是随便搞了一下，不过我应该不会记忆化搜索，我应该直接填表了。

我给你再加了个剪枝过了。
import functools

class Solution:
def maxLen(self, n: int, edges: List[List[int]], label: str) -> int:
neigh = [[] for i in range(n)]
for edge in edges:
u = edge[0]
v = edge[1]
neigh[u].append(v)
neigh[v].append(u)
@functools.cache
def dfs(l: int, r: int, visited: int):
max_len = 0
for l_child in neigh[l]:
if visited & (1 << l_child) > 0:
continue
for r_child in neigh[r]:
if l_child == r_child or (visited & (1 << r_child) > 0):
continue
if label[l_child] != label[r_child]:
continue
lc, rc = l_child, r_child
if lc > rc:
lc, rc = rc, lc
new_visited = visited | (1 << lc) | (1 << rc)
max_len = max(max_len, dfs(lc, rc, new_visited) + 2)
return max_len
maxmaxlen = 0
for i in range(n):
rv = dfs(i, i, 1 << i)
maxmaxlen = max(maxmaxlen, rv + 1)
for edge in edges:
u = edge[0]
v = edge[1]
if label[u] == label[v]:
if u > v:
u, v = v, u
rv = dfs(u, v, 1 << u | 1 << v)
maxmaxlen = max(maxmaxlen, rv + 2)
return maxmaxlen

T1随便秒

T2被卡常了，sb leetcode不给tle限制谁知道会不会卡常，没办法问了claude怎么O(n)算组合

T3线段树不会写了，超时

T4完全不会，计算几何是我爹

【引用自 ATF】:
计算几何
都不做学生了，弄这个干什么

计算几何确实太恶心了。不过T2和组合没关系吧？枚举(x,0)直线应该就行

我是我们队里专门做
【引用自 ATF】:
计算几何
的

看了下
【引用自 ATF】:
T4完全不会
都不算什么正经的计算几何。就枚举两个点求斜率，然后按斜率和b排序瞎搞就完了，斜率记得用分数表示，记得平行四边形要去重，还要处理有四点共线。

【引用自 ctzsm】:
我是我们队里专门做
爷，给您跪下了

【引用自 ctzsm】:
我是我们队里专门做
爷，他给您跪下了

因为队友是打oi过来的，oi不怎么整计算几何。留给菜的我的只能是特化专攻一些专项。

T1: 瞪眼贪心

T2: 贪心+暴力，注意到如果加入L一定在最左边好，T同理

T3: 暴力BFS，就是需要提前质因数分解，不然会TLE（我是先找质数再找因数，不行）

T4: 完全不会，看了题解才知道确实完全不会

问下大佬们觉得现在的周赛是什么难度？学艺不精，本以为刷到1000题可以挑战第4题了，然而现在是解第3题都越来越吃力了

T1: 前后缀暴力

T2: 模拟

T3: 本来以为是贪心，做完WA才发现是DP

T4: 看了才知道是差分，这个真不会
【引用自 Simplylovely】:
本以为刷到1000题可以挑战第4题了
主要取决于你有没有做过类似的题以及能不能读出题目考点，我写过不少模板但经常看不出来题在考察什么

WA是什么？

t3我也是想了好久，贪心 滑窗 栈都了下才想到dp

【引用自 ATF】:
差分
差分约束系统吗？真是有点久远的记忆了
【引用自 Simplylovely】:
WA
Wrong Answer

【引用自 ctzsm】:
差分约束系统吗？真是有点久远的记忆了
不就是差分数组，线段树平替那种？

纪念人生第一次AK，虽然我也不知道T4是怎么写对的，中间ADHD发作，被沙雕视频硬控了半个小时

image1942×150 26.6 KB

T1：模拟+线性扫描

T2：贪心

T3：本来以为是DP，然后悟过来应该是二分，上限可以用倍增（AC以后在想怎么更好地算上限，感谢 提醒我可以用倍增）

T4：使用了和T3 第 472 场周赛 - 讨论 - 力扣（LeetCode） 这个题解差不多的思路，但我并不知道为什么是对的，只知道AC了（吃罚时是忘记处理边界条件了）

无效打码

还真是，自欺欺人了

【引用自 ATF】:
上限
感觉上限6*(d_1+d_2)还是挺显然的

我去我看不出来啊大佬

首先判定条件是

x - floor(x/r1) - floor(x/r2) + floor(x/lcm(r1,r2)) >= max(d2-(x//r1-floor(x/lcm(r1,r2))),0)+max(d1-(x//r2-floor(x/lcm(r1,r2))), 0)

这你肯定已经知道了

然后左边大于x(1-1/r1-1/r2)，右边最多是d1+d2

如果(r1, r2) != (2,2)， 那么左边至少x/6.如果(r1, r2) = (2,2)，那么左边至少 x - floor(x/2) >= x/2.

无敌了，膜，让我消化一下

t123秒了，t4一看就不会 感觉是DP，但转移方程都不知道怎么写

【引用自 ATF】:
DP
这里有详细教学

俺也败北了，想了一个铁超时的dp

结束以后问了问chatgpt说要单调性+滚动数组优化，是我完全不会的内容捏

力扣 LeetCode

第 475 场周赛 - 讨论 - 力扣（LeetCode）

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】3 分 - 三个相等元素之间的最小距离 I 4 分 - 三个相等元素之间的最小距离 II 5 分 - 网格中得分最大的路径 8 分 - 循环划分的最大得分

这思路无敌了，我好笨

怎么这么卷

草泥马leetcode卡我常，不做了

图片622×355 7.22 KB

这题也是狗屎，怕吃罚时想了半天思路

图片2053×588 45.3 KB

笑死 今儿赛后我听很多人说被卡了

让我赶紧有机会读读题

今天题很简单，再次AK T123都是模拟 T4简单的建图最短路，SB Leetcode卡常

我看他们都说今天周赛很难 吓得我都没敢参赛了

我还没做，今早的双周赛不难…

哎 你们全他喵的是金牌佬吧 哎 被降维打了 很难受哎

安老师你看看题就知道了，对你肯定小意思…

你们两个肯定是随便AK

如果我不会做 你们会把套桑的IG发给我 安慰我一下吗

做了下Q4，确实不难，睡了

羡慕，几何老师估计3分钟AC吧