YoungForest's blog

因为洗澡迟到了8分钟，否则应该可以进前500的。
本次的双周赛是变相的手速场，141人作出4题。剩下的比拼前3题的手速。
我花10min很顺利地做完了前三题，Q4却思考了一个小时也并未有重大突破。
虽然有些许眉目，觉得是个DP，但事后发现问题早已超纲，没做出来也实属正常。

比赛链接

之前LC-CN举办的春季赛和秋季赛我都没参加，因为实验室之前每周六下午开组会，时间完美冲突。现在老板改为平时开小组会，一月开一次大组会，终于有机会参加2021年的春季赛了。
周一清明节参加了个人赛，总结博客于此.
周六和 佛系刷题群 的 老赖 还有 George 组队一起佛系出征，最后的结果果然很佛系，2题结束。我第一题，George第二题（还是我提供思路，帮忙 review + debug). 不得不说，跟2个人组队打比赛还不如我一个人效果好。怪不得ACM比赛的队伍都要磨合好久。

LCP 33. 蓄水

签到题。虽然是Easy，不过作为竞赛第一题，本题的难度还是相当大的。

观察 + 暴力。

操作共分为 升级 和 蓄水 2种。显然 蓄水操作应排在升级之后.
一个朴素的暴力方法是，我们先枚举所有可能的蓄水次数，升级次数就因之而定，然后在其中选最小的。枚举蓄水次数也存在剪枝的过程。先试小的，如果已经比全局最小总次数大了，就直接结束了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        // time: max(buckets[i]) * buckets.size() = 10^4 * 100
        int ans = numeric_limits<int>::max();
        const int n = bucket.size();
        if (accumulate(vat.begin(), vat.end(), 0) == 0) return 0;
        auto check = [&](const int x) -> int {
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                const int need = vat[i] - bucket[i] * x;
                if (need > 0) ans += (need + x - 1) / x;
            }
            return ans;
        };
        for (int x = 1; x <= 1e4; ++x) { // 蓄水次数
            if (x >= ans) break;
            ans = min(ans, x + check(x));
        }
        return ans;
    }
};

时间复杂度: O(max(vat[i]) * buckets.length) = O(10^4 * 100),
空间复杂度: O(1).

LCP 34. 二叉树染色

1822. Sign of the Product of an Array

签到题。多少负数，是否有0。

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        x = 1
        for i in nums:
            x *= i
        if x > 0:
            return 1
        elif x == 0:
            return 0
        else:
            return -1

时间复杂度: O(N),
空间复杂度: O(1).

1823. Find the Winner of the Circular Game

经典的约瑟夫环问题。随便Google了一个: 约瑟夫环——公式法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    int cir(int n,int m)
    {
        int p=0;
        for(int i=2;i<=n;i++)
        {
            p=(p+m)%i;
        }
        return p+1;
    }
public:
    int findTheWinner(int n, int k) {
        return cir(n, k);
    }
};

时间复杂度: O(N),
空间复杂度: O(1).

1824. Minimum Sideway Jumps

比赛链接

LCP 28. 采购方案

签到题。可以看到总共2750名选手签到。

二分搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    const int MOD = 1e9 + 7;
public:
    int purchasePlans(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        // 1 2 4 5 6/
        // target = 5
        // 2
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            const int x = nums[i];
            auto it = upper_bound(nums.begin(), nums.begin() + i, target - x);
            ans = (ans + distance(nums.begin(), it)) % MOD;
        }
        return ans;
    }
};

时间复杂度: O(N log N),
空间复杂度: O(1).

LCP 29. 乐团站位

一开始很简单想到模拟填数，时间复杂度为 O（N^2), 因为n 最大 10^9. 显然已经超时了，我们需要考虑更优的解法。

观察发现，数字填写的规律十分明显。我们其实只需要计算其离起点的位置即可。通过计算目标点距离四周的距离，我们可以得到外侧总共有多少层，再通过等差数列求和，可以快速计算出外侧有多少数。然后，问题简化为目标点一定再最外圈的情况。分4种情况（上边，右边，下边，左边）分别计算目标点与左上角的距离。

1816. Truncate Sentence

签到题。再次强调一遍，字符串问题适合用Python做，真的只需要描述题目就可以了。

1
2
3

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return ' '.join(s.split(' ')[:k])

时间复杂度: O(s.length),
空间复杂度: O(s.length).

1817. Finding the Users Active Minutes

暴力。以ID为统计每个用户的动作时间序列，然后排序去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        // brute-force:
        // logs.length + k
        unordered_map<int, vector<int>> actions; // userId -> actionMinute
        for (const auto& v : logs) {
            actions[v[0]].push_back(v[1]);
        }
        vector<int> ans(k, 0);
        for (auto& p : actions) {
            auto& v = p.second;
            sort(v.begin(), v.end());
            auto it = unique(v.begin(), v.end());
            const int d = distance(v.begin(), it);
            if (d >= 1 && d <= k) ++ans[d - 1];
        }
        return ans;
    }
};

时间复杂度: O(logs.length * log(logs.length) + k),
空间复杂度: O(logs.length + k).

1818. Minimum Absolute Sum Difference

最近因为放松了刷题，自己竞赛水平也有所降低。不过这算是我刻意为之的。之前疯狂刷题刷了1k+，后来遇到瓶颈，改为每天刷3题（国服每日一题，美服每日一题，残酷群每日一题。分别有积分和红包奖励），现在已经基本每日0题，只是坚持打周赛维持手感和获得快乐。
诚然刷题和比赛是很快乐的，让人上瘾，我早已欲罢不能。
但是因为面临毕业和毕业论文的压力，我刻意控制了自己刷题的时间和投入。
不知道你能不能理解，在写论文的时候，什么东西都能成为诱惑。而刷题这种我平日里就很喜欢的活动更是成为了巨大的诱惑和逃避之地。究其根本，写论文和做实验真的是太痛苦了。
甚至不需要是刷题，别的什么阻止我都足够了。比如 看书，看电影，刷论坛。
没办法，论文总是要强迫自己投入主要精力去做的。我不是一个意志力足够坚强的人。
因此，刷题被我刻意远离了。仅仅品尝每周竞赛的快乐就足够了。

因为水平的降低和自己国服rating太高（2400+），我现在已经基本转战美服了。美服账号rating不到2200，尚且有不小的上升空间。打起来压力也不会太大。
之前打国服，连跌2次，险些跌出2400俱乐部。
我打算先把美服也打上2400. 这样不把鸡蛋放在一个篮子里，自己的rating也更稳定些。

Auto daily health report solution for BUAA.

又要打卡了，已经连续5周残酷打卡了。而且确实自己本次做题没觉得多简单，WA5次，心态爆炸，但是排名却不理想。感觉还是LeetCode越来越卷了。

动机

接上篇解决台式机Ubuntu VPN访问公网资源的问题后，我尝试了配置跳板机访问杭研院机器。

在科研工作中，MAC笔记本无法连接OpenVPN，从而访问杭研院机器。我的台式机Ubuntu已经配置好了VPN，可以访问服务器。我现在想通过台式机Ubuntu中转，从而实现MAC“直接”访问杭研院。抽象一下问题为：

• A可以访问B
• A不可以访问C
• B可以访问C
• 我现在想A访问C

由于工作中主要使用SSH，因此，问题简化成A通过SSH直接登陆C。
我经过不屑的网上搜索和尝试，总结了2中技术和方法实现我的目的。

• SSH 代理
• SSH 隧道

周末，整整耽误了3场比赛。
双周赛没参加，周赛迟到半小时，紧接着参加KickStart，人已经废了。
以后打比赛还是要养精蓄锐，好好打才行。

第四题我最后其实是有思路的，无奈时间不够了。之前做过类似用Trie处理异或问题的题目，印象还挺深刻的。