ZHLin_Blog

牛客2025秋季算法编程训练联赛3-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A 牛牛的DRB迷宫I 对于这个题目，我上来想到的就是用DFS来暴力求解（因为我当时并不清楚DFS的时间复杂度），导致TLE。现在，我需要对DFS在二维矩阵中的时间复杂度做个总结： 对于本题，最坏情况就是所有位置都是’B’，也就是每个位置都有两种选择。 路径长度：从（1,1）到（n,m）需要走(n-1)+(m-1)=n+m-2步 路径数量： $2^{n+m-2} $ 时间复杂度：$O(2^{n+m-2})$ 当n=m=50时： 路径长度 = 98步 路径数量 ≈ 2^98 ≈ 3.17 × 10^29 超过了10^8的时间复杂度，必然会TLE 总结：DFS在二维矩阵中时间复杂度为$O(路径数量)$ = $O(2^{路径长度})$ ​ 在n+m>40时完全不可行。 随后，我又想到以前写过一道动态规划基础题和这个类似，概括下就是从（1,1）开始只能向右或向下走，问走到终点一共有几种方法。有用了这个题的思路，就把本题给写出来了。 B 牛牛的k合因子数 看到这题时候，我本想着直接顺着题目的意思模拟，但是因为时间复杂度...

牛客2025秋季算法编程训练联赛4-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ C 子段乘积 比赛时思路（没写出来OvO）： 本题一开始想到了一个方法，简单来说就是先乘上一个数然后除掉结尾的数每次运算进行取模，但是发现0这个数处理比较复杂，于是就一直纠结在处理0的问题上。怎样选择k个数，其中不包含0呢？ 我想到了状态记录，将0位开始的k个数所对应的状态记录为1，其余为0，那就将以这个数据结尾的k个数相乘再取最大值就可以了。但是我忽视了时间复杂度，状态记录需要两层循环，时间复杂度是$O(nk)$超时了。 我又想到了个方法，就是用last记录上一次0出现的下标，如果当前非0数离上一个0距离>k,那就将以这个数据结尾的k个数相乘再取最大值，但是我想了好久都没有实现。 AC思路： 思路1：尺取法，l代表左端点，r代表右端点。l先不动，r往前扫描，如果成功扫到，有k个非0元素的子段就累成起来，最后把最左端的元素除了，左端点往前移动，l++，再继续扫描。再未达到k个非零元素的子段前，如果遇到0，当前的区间就废了 ,左端点直接到0的下一个位置。继续扫描。 ...

2025年香港城市大学（东莞）新生程序设计个人排位赛正式赛（同步赛） ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛 牛客竞赛OJ F 优香数列 观察出来了，需要将公差为 1 的等差数列的和与 n 作比较，但是没有想出来要用二分答案。 答案有序 一部分满足条件，一部分不满足条件 #include <bits/stdc++.h>using namespace std;typedef long long LL;LL t, n;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> t; while (t--) { cin >> n; LL l = 1, r = 10000000000; while (l < r) { LL mid = l + r >> 1; if (mid * (mid + 1) ...