水厂日志

UESTC 2370

发表于 2020-05-05 更新于 2025-04-29 分类于 ICPC训练，数据结构，栈

关键字：栈；贪心；

leetcode 1081差不多，但是有一点区别。这题直接给出了元素的种类，也就是$k$，而leetcode上那题并不直接给出元素种类，但最多是26（小写字母），而这题的$k$高达1e6…

leetcode社区中的题解主要有两种方法：

栈+贪心
寻找第一个元素的位置+贪心

我在写本题的时候用的第一个方法，第二个应该也可以，但是有点麻烦，它需要$o(1)$的复杂度确定从$i$到最后共有多少种元素，leetcode那题因为最多26种，所以直接位运算就完事，而本题的$k$高达1e6，位运算显然不现实，也可以用前缀和去判断，但是我懒得写，直接第一种完事。

题解

参照这个题解。

上面链接的那个幻灯片就很直观了。首先从输入读取一个数字，如果栈是空的则入栈，如果非空则判断能否进入，首先先确定栈内是否存在这个数字，我的做法是用一个marked数组保存已经入栈的数字，如果存在则不处理，不存在则进行下一步，判断栈顶元素是否大于输入的数，如果大于而且栈顶元素还存在于之后的输入中，则出栈并重复这一步骤，直到栈为空或者栈顶小于输入的数，然后入栈，此时就能保证字典序是最小的。

要判断栈顶元素是否还存在于之后的输入中，我的做法是保存每个数字最后出现的位置，这样直接判断当前位置是否小于最后的位置即可。

代码

AC代码

// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;
const int MAX = 1e6 + 5;
int lastPos[MAX];
int seq[MAX];
int origin[MAX];
bool marked[MAX];

int main() {
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    int n;
    int k;
    int tmp;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        // cin >> tmp;
        scanf("%d", &tmp);
        origin[i] = tmp;
        lastPos[tmp] = i;
    }
    // stack
    int stackIter = 1;
    for (int i = 1; i <= n; i++) {
        if (stackIter == 1) {
            // insert anyway
            seq[stackIter] = origin[i];
            marked[origin[i]] = true;
            stackIter += 1;
        } else {
            if (seq[stackIter - 1] == origin[i] || marked[origin[i]]) {
                continue;
            }
            while (true) {
                if (stackIter != 1 && seq[stackIter - 1] >= origin[i] && i < lastPos[seq[stackIter - 1]]) {
                    // pop
                    marked[seq[stackIter - 1]] = false;
                    stackIter -= 1;
                } else {
                    // insert
                    seq[stackIter] = origin[i];
                    marked[origin[i]] = true;
                    stackIter += 1;
                    break;
                }
            }
        }
    }
    if (stackIter <= k) {
        cout << "Kanade";
        return 0;
    }
    for (int i = 1; i < stackIter; i++) {
        //cout << seq[i] << " ";
        printf("%d ", seq[i]);
    }
    return 0;
}

测试例生成（Python3）

import random
def k(n,k):
     a = [str(random.randint(1, k)) for i in range(n)]
     f = open('in', 'w')
     f.write("{} {}\r\n{}\r\n".format(n, k, " ".join(a)))
     f.close()

彩蛋

吐个槽，我在本机上测试1e6的数据量，默认编译器是clang++ 11.0.3 with LLVM，跑了两秒多，换成g++9瞬间提升到0.08秒，绝了。

破案了，macOS上的clang++默认使用libc++，这个库无法通过一般方法关闭流同步，而g++使用的是libstdc++，就没有这个问题。

UESTC 2361

发表于 2020-05-05 更新于 2025-04-29 分类于 ICPC训练，数据结构，并查集

关键字：并查集；

快慢指针法

这个方法来自于判断链表中是否存在环，原理很直观，就是加入一个移动较慢的指针（一般是快指针速度的一半），如果链表中有环的话，就会导致两个指针出发了一段时间后“撞”在一起。所以只要在出发后判断两个指针是否相等即可确定链表中是否有环。

题解

并查集模板题，快慢指针法判断是否成环，再加个路径压缩就完事。复杂度$o(n)$，这题限时是200ms，太极限了。

代码

AC代码

// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

int a[1000000];
int isLoop = 0;

int findSet(int fast, int slow, bool moveSlow = false, int step = 0) {
    if (fast == a[fast]) {
        isLoop = 0;
        return fast;
    } else {
        fast = a[fast];
        if (moveSlow) {
            slow = a[slow];
        } else {
            if (step && fast == slow) {
                // loop
                isLoop = 1;
                return fast;
            }
        }
        return findSet(fast, slow, !moveSlow, step + 1);
    }
}

void mergeSet(int x) {
    if (x == a[x]) {
        return;
    }
    int t = a[x];
    a[x] = x;
    mergeSet(t);
}

int main() {
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        //cin >> a[i];
        scanf("%d", a + i);
        if (a[i] == i) {
            ans += 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) {
            continue;
        }
        findSet(i, i);
        if (isLoop) {
            // new loop
            ans += 1;
        }
        // compress
        mergeSet(i);
    }
    cout << ans;
    return 0;
}

其中的findSet函数用于查找根结点，成环的话会返回环上某一点，具体是哪个这里不展开说，同时会标记isLoop变量。

mergeSet用于路径压缩，如果我们只关心一个结点的根结点，在findSet完成之后直接把根结点设为它的父结点，这样如果以后还有结点在findSet过程中路过这个结点就可以快速找到根结点了，再引申一下，如果将路径上所有的结点都重新设置父亲结点，就可以加快经过那些结点的findSet。再优化一下，ans+=1之后，这个结点的根结点其实也不重要了，它的子结点必然不需要ans+=1，所以直接把路径上每个结点都设为根节点，速度又能提升一些。

树状数组的一个优雅实现（C++）

发表于 2020-04-29 更新于 2025-04-29 分类于数据结构，树状数组

废话不多说，直接上代码：

class BIT {
private:
    vector<int> tree;
    int n;
public:
    BIT(int _n) : n(_n), tree(_n + 1) {}

    static int lowbit(int x) {
        return x & (-x);
    }

    // 查询前缀和
    int query(int x) {
        int ret = 0;
        while (x) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    // 更新
    void update(int x, int v) {
        while (x <= n) {
            tree[x] = v;
            x += lowbit(x);
        }
    }
};

从leetcode的一个题解里面抄的，构造函数接受一个参数_n表示数组长度，并初始化（为0），做了一些改动，感觉非常舒适。

TODO

从数组或者迭代器中初始化
使用模板，不局限于int类型

UESTC 2360

发表于 2020-04-25 更新于 2025-04-29 分类于 ICPC训练，数据结构，栈

关键字：括号匹配；栈；

题解

括号匹配，直接上栈就完事了。首先判断输入的符号是(还是)，如果是前者则入栈，后者先判断栈是否为空，空则ans+=1，不空的话出栈，最后栈内剩余的是没有被匹配的，所以答案是ans加上栈内元素数量。时间复杂度$o(n)$。

代码

AC代码

// @author: hzy
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    stack<char> st;
    while (t--) {
        int n;
        int ans = 0;
        cin >> n;
        char c;
        while (n--) {
            cin >> c;
            if (c == '(') {
                st.push(c);
            } else {
                // ) matches a (
                if (st.empty()) {
                    ans += 1;
                } else {
                    st.pop();
                }
            }
        }
        cout << ans + st.size() << endl;
        while (!st.empty()){
            st.pop();
        }
    }
    return 0;
}

后记

其实不用STL的stack也可以，只需要记录有多少个(，应该会更快，毕竟栈内只会有着一种符号，我以为这样写会TLE，没想到居然过了，可能是训练题比较水吧。如果是多种括号的匹配，比如()[]{}的组合，那应该只能用栈。

ldap-python基本使用

发表于 2020-04-20 更新于 2025-04-29

因为StarSSO这个项目，我不得不专门补了下LDAP的有关知识和概念，这里记录一下。

LDAP基本概念

LDAP(Lightweight Directory Access Protocol，轻型目录访问协议)是一个协议，但是我们一般认为它用于存储用户数据，比如手机号、电子邮箱、密码（当然是加密后的）、用户名之类的信息。

和大多数数据库一样，它有服务端和客户端，服务端存储，客户端查询。

从名字我们就知道它是一种目录结构，典型的比如一般文件系统的文件夹就是一种目录，每个目录下可以存放多个条目（entry），一般来说一个条目就是一个用户或者组织，条目中可以存放多个属性（attribute），这些属性就是上面提到的用户名（一般是cn，即common name）、密码（一般是userPassword）、电子邮箱、手机号等等。一般一个条目必须拥有的属性是objectClass，用来表示条目的类型，比如person或者orgnizationalUnit，可以认为不同的objectClass可以拥有不同的属性。

每个条目都有一个唯一的dn（distinguished name，专有名称），比如说cn=admin,dc=example,dc=com就是一条dn，它表示在com这个dc下的example这个dc下有个cn为admin的条目，通常LDAP在安装之后的管理员账户就是cn=admin,dc=nodomain。

关于LDAP的更多知识可以在这个网站找到，这里就不展开了。

python-ldap

如果我们使用的编程语言是Python，可以使用python-ldap这个包来访问LDAP，Linux下安装需要编译，可以安装openldap或者openldap-dev（取决于发行版）来获得相应的头文件和链接库。

然而这个包的文档十分简单粗暴，它本身只是对LDAP的C语言接口做了简单封装，所以各种C语言的函数比如add/add_s都完美继承了下来，大量的函数都带有_s/_ext/_ext_s，我也是看了C语言接口的文档才知道_s的意思是同步（Synchronize），也就是说会阻塞知道执行完成，而不带_s的函数是异步执行，返回一个消息，然后通过另一个函数来获得执行的结果。

使用这个包看文档是不够的，更多时候应该关注官方仓库里的Demo和调试器窗口，因为文档里根本不会告诉你返回值是个什么东西。

下面介绍一些常用的操作：

ldap.initialize

连接LDAP数据库，返回一个LDAPObject，用于后续的各种操作。

明日不再来，观众不再有

发表于 2020-02-21 更新于 2025-04-29 分类于灌水，日常

前天刷到有什么让人听了背脊发凉的恐怖故事？ - 知乎，开局很有意思就一直读下去了，看完回答的时候作者提到后续内容在豆瓣阅读，名字是《恶脑》。根本停不下来，马上下了豆瓣阅读买完整版（6块多），一口气看完，看完的时候已经是晚上十一点。虽然小说有点悬疑和推理，但并不着重于此，看了分类才知道是奇幻。

它让我想起了高中时候看过马广《明日不再来》，当时它在《萌芽》上连载。高中时我浪得很，除了自习课，有时上正课也会看闲书，最初是《读者》《意林》《青年文摘》这样的文摘，然后是《收获》《萌芽》《当代》《人民文学》。我当然没有钱去订阅那么多，所有的这些都感谢柳高读书馆，图书馆里的杂志是三期钉到一起，借一次可以爽差不多一星期。

刘慈欣说他是在值班的时候写小说，有种占便宜的感觉，我那时候应该也是差不多的心理。那是我阅读量突飞猛进的一段时光，现在失去了那种状态，也提不起读文字的兴趣了，每天想的都是写代码或者打游戏，怎么可能会去读书呢？

以上是背景，看完《恶脑》第二天又翻了翻kindle，恍然想起《明日不再来》，《明日》也是带着点悬疑和推理的小说，但是它的情节要更丰富，结局更自然，各个方面都比《恶脑》成熟多了。既然我能看完《恶脑》，为什么不重新看一遍《明日》呢？手贱点开样章，才六块钱，买。

于是一天就没了。

虽然已经知道结局，也多多少少记得一些内容，再看一次还是很有意思。

男主角杜鸣的女朋友董佳萌失踪，六天里杜鸣和佳萌的弟弟董佳世到处寻找佳萌。故事并不长，只有六天，却充实得可怕。虽然说艺术来源于生活而高于生活，但还是不自然地会去对比现实，想想自己这个寒假，太颓废了。我没有女朋友，但是如果我有而且她失踪的话，我想我是一定还是每天该吃吃该喝喝，报个警就完事了，大概不会到处去找线索。

最后放个kindle版的购买链接。

樱花动画的webgl实现

发表于 2020-01-13 更新于 2025-04-29 分类于 Web ， WebGL

来自LUG的MC网站，感觉很不错，我删掉了一些代码，只保留了canvas的部分。如果看不到的话可以点这里。

小记1

发表于 2019-11-21 更新于 2025-04-29

最近头有点胀，主要体现在上课/做题/写代码等需要集中注意力的时候，因为这个导致经常不想做事情，甚至连这篇文章都不太想写，但还是想着要留下点什么。

今天搞了一天的CDN，现在在用的腾讯云，访问博客应该是没啥问题了。

kase基本上完工。

萌生杯那边队友还在拖，算了反正也不指望什么。

最近咖啡喝的有点多，以后还是节制一些，虽然上课确实没什么打瞌睡的想法了，但是总感觉这玩意就是我头胀的罪魁祸首。

明早第一节没课，今晚大概可以睡得比较舒服了吧，而且明天只有一节课，我甚至可以睡上一天。

好久没有真正意义上的看小说，也许明天可以看一篇短篇。

泰坦不想打了，头晕，眼睛花，也不想玩其他游戏。

我自己

发表于 2019-09-14 更新于 2025-04-29

不知道是什么时候开始，情绪变得不敏感，在上大学之后达到了质变，既不关心自己也不关心别人，如果是懒得回复的消息，甚至都不想打开看一下。

我曾经很喜欢编程，也喜欢刷算法题，但是现在一打开IDE就本能地想逃避，严重的时候看代码就头晕。

曾经玩泰坦陨落2玩得风生水起，失败了很气馁，胜利就很开心，能开心到叫出来，现在虽然胜率已经超过50%，但是也失去了那种感觉，输了笑一下，赢了也笑一下，好像再平常不过。

高中时候上课看小说，能从上课看到下课，现在有了kindle，也不过是每个月拿出来充下电，真正成了盖泡面神器。

还有好多好多呢，甚至懒得一一列举了。我到底是为什么会失去兴趣、热情的呢？

现在连一些长句子都懒得看下去，知乎上刷到一篇文章如果没有断句，就直接放弃了。

用iphone之前用的是小米4，整天折腾来折腾去，时不时刷个机，或者用公测版系统，每天看有没有更新，又有哪些新功能。到后来也放弃了，直接用稳定版系统，推更新了也懒得去处理，当然现在用iphone就更懒了。

windows10刚发布的时候就给家里电脑装过双系统去体验，甚至还到处帮微软推广来着，现在想想真是可笑呢。换mac之前主力是一台戴尔笔记本，也曾长期使用win10，也有各种魔幻操作去优化，禁用自动更新之类的，在一些“大神”眼里是基本操作的事情。后来也还是因为懒，重装win7一直用到换mac，当然win7确实稳定，没有什么自动更新，系统更新也会明确列出，只是快到服务期限了，所以换mac。

我还记得以前经常会很期待一些东西，比如电影、游戏、数码产品之类的，期待到晚上睡不着觉，想的都是现在能拿到多好啊。有时候确实拿到了，反而有些失望，和自己的期望差太多吧。

大概这就是所谓的佛系青年？或许这是个贬义词，我也懒得去反对了吧。当然这也导致我在选择上更着重于稳定，比如选择完成度较高的产品，github上没有几百个commit的开源软件都不太敢用。现在只觉得，那些折腾来折腾去的事情，其实没有也罢。但是这似乎又陷入了一个矛盾，其实就我个人来说，学习的各类“旁门左道”都是折腾出来的，比如Linux，比如单片机，其实基本都没有系统学习过。

虽然我大概搞清楚了变得佛系的原因，但是看起来我并没有能解决它的方法。有个学长现在在用一系列时间统计工具，对自己各项指标做量化，我觉得没必要，自己的情况自己再清楚不过了，成绩差难道不是因为没听课、没复习、没刷题么？听起来很可笑，但确实是这样，大多数时候我们走错道路，不是因为选择错了，而是我们在知道哪条路正确的时候，同样也知道那条路实在太难走而放弃。

在PX4Flow上使用HC-SR04

发表于 2019-07-14 更新于 2025-04-29 分类于航模，飞控，光流

参照https://blog.csdn.net/hxudhdjuf/article/details/79671892

因为上面那个文章写的很乱，代码也不怎么规范，这里记录一下，顺便给后人排坑。

在校队的时候申了一块PX4Flow，260多不带超声波，真特么贵，超声波要260多，原版的超声波型号是MB1240（这里给出Datasheet），但不得不说效果真的很好，精度和测距范围都很棒。当然当时我是不知道的是PX4Flow如果不带超声波基本没法工作，代码的话我也看得不是很懂。淘宝上可以搜到300不到的PX4Flow，顺便校队里有一个用Pixhawk的无人机就是用的那个光流模块，当时真TM后悔。

好吧闲话不多说，先给出修改原理。HC-SR04的驱动方法相当简单，就是在Trig引脚给一个脉冲，然后等待Echo引脚电平两次变化读取时间，就是发送和接收到超声波的间隔，根据空气音速就能算出距离。所以这里的思路就是用PX4Flow上的STM32F7单片机GPIO引脚来做驱动。

连接方法如下，Trig接4脚（RX），Echo接2脚（PW），GND和VCC供电，分别可以接7脚和6脚，后面应该有GND和VDD的丝印。

需要修改官方的代码，这里提供我修改之后的代码，具体改了哪可以看commit log，这里就不在描述了，修改的部分是超声波的驱动src/modules/flow/sonar.c，以及在src/modules/flow/module.mk和CMakeLists.txt中加入exti和syscfg。