效果展示

最终效果视频

监控+差值+黑白二值图像

代码

• 该程序计算量要求较低，可以部署在树莓派类的物联网设备上

python包配置

1
2
3
4

sudo pip install argparse #用于解析参数
sudo pip install imutils #用于修改图片格式大小
sudo apt-get install libopencv-dev  
sudo apt-get install python-opencv  #安装opencv

python代码

代码写的相当详细，注释的极其详细，不再赘述。（python版本2.7）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#coding:utf-8
#必要的包
import argparse
import datetime
import imutils
import time
import cv2

#创建参数解释器并解析参数
ap = argparse.ArgumentParser()
ap.add_argument("-v", "--video", help="path to the video file")
ap.add_argument("-a", "--min-area", type=int, default=1000, help="minimum area size")
args = vars(ap.parse_args())

#如果video参数为None, 那么我们从摄像头读取数据
if args.get("video", None) is None:
    camera = cv2.VideoCapture(0)
    originaltime = time.time()#记录时间
else:
    camera = cv2.VideoCapture(args["video"])
#初始化视频流的第一帧
firstFrame = None
num=0
#遍历视频的每一帧
while True:
    if time.time()-originaltime <= 2:  #等待摄像机开启并稳定
        (grabbed, frame) = camera.read()
    else:
        (grabbed, frame) = camera.read()
        #调用camera.read()返回一个２元组。元组第一个值是grabbed，表明是否成功从缓冲中读取frame。元组第二个值为frame本身
        text = "not exist"
        #表明正在监控的房间“没有被占领”。如果确实有活动，就更新该字符串
        if not grabbed:
            break
        #调整该帧的大小，转换为灰阶图像并且对其进行高斯模糊
        frame = imutils.resize(frame, width = 500)
        gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)#灰阶图片
        gray = cv2.GaussianBlur(gray, (21, 21), 0)#高斯模糊

        #如果第一帧是None, 对其进行初始化
        if firstFrame is None:
            firstFrame = gray
            continue

        #计算当前帧和第一帧的不同
        frameDelta = cv2.absdiff(firstFrame, gray)#两幅图的差的绝对值输出到另一幅图上面来

        thresh = cv2.threshold(frameDelta, 25, 255, cv2.THRESH_BINARY)[1]#黑白二值化

        #扩展阈值图像填充孔洞，然后找到阈值图像上的轮廓
        thresh = cv2.dilate(thresh, None, iterations = 2)#图像膨胀
        (cnts, _) = cv2.findContours(thresh.copy(), cv2.RETR_EXTERNAL,
                                     cv2.CHAIN_APPROX_SIMPLE
                                     )#findcontours函数会“原地”修改输入的图像,只检测的外轮廓，仅保存矩形４个顶点


        #遍历轮廓
        for c in cnts:
            #如果轮廓太小，忽视轮廓
            if cv2.contourArea(c)<args["min_area"]:
                continue

            #计算轮廓边界，在当前帧中画出该框，并更新text
            (x, y, w, h) = cv2.boundingRect(c)
            cv2.rectangle(frame, (x, y), (x + w,y + h), (0, 255, 255), 2)
            text = "exist"

        #在当前帧上写文字以及时间戳
        cv2.putText(frame, "room stats:{}".format(text), (10, 20),
                    cv2.FONT_HERSHEY_SIMPLEX, 0.5, (0, 0, 255), 1)
        cv2.putText(frame, datetime.datetime.now().strftime("%A %d %B %Y %I:%M:%S%p"),
                    (10, frame.shape[0] - 10), cv2.FONT_HERSHEY_SIMPLEX, 0.4, (0, 0, 255), 1)

        #显示当前帧
        cv2.imshow("二值化图像", thresh)
        cv2.imshow("差值图像", frameDelta)
        cv2.imshow("监控", frame)
        cv2.waitKey(10)

        #对环境渐变的适应
        flag = True#标记是否值得更新（第一帧）背景帧
        for c in cnts:
            if cv2.contourArea(c)>args["min_area"]//4:
                flag = False
        if  flag is True:#新背景＝旧背景＊(1-0.618)＋当前无物体背景＊(0.618)
            firstFrame = cv2.addWeighted(firstFrame, 1-0.618, gray, 0.618, 0.0)
        #cv2.imwrite("Security Feed.png", frame)
        #cv2.imwrite("Thresh.png", thresh)
        #cv2.imwrite("Frame delta.png", frameDelta)
        #cv2.waitKey(0)
#清理摄像机资源并关闭打开的窗口
camera.release()
cv2.destroyAllWindows()

前段时间的，新生工程体验课上，两人一组，靠厂家提供的元器件和烧录代码，焊接了了一台智能小车。

最进，碰巧手头有空闲的一块树莓派，本来打算用树莓派去实现远程控制空调，但发现空调的红外编码带有逻辑控制，只能退而求其次，试试远程控制小车，大体框架结构如图。

2017-07-03更新，已经实现对空调类带逻辑编码设备的简单控制。

烧录系统

几乎所有的新手教程都使用Win32DiskImager作为系统安装工具——中文的、英文的、官方的、eLinux wiki的，不一而足。 但是这个工具不支持中文目录名（文件或目录有中文，会出现123错误），不支持压缩，必须先插好SD卡，再开软件。 而USB Image Tool，就是Win32DiskImager的一个更方便的替代品。

写SD卡：直接读取zip压缩包

USB Image Tool可以直读.zip压缩包。网上下载的zip格式系统镜像，下完直接可以烧录。 点击Restore，选择.zip文件即可。注意打开对话框中默认看不到.zip文件，在“文件类型”处选择“All Files (.)”即可。

SSH无法连接问题

自从2016年11月开始，树莓派官方推荐 Raspbian 系统镜像关闭了默认ssh连接，重新开启也很简单，把SD卡拔下来，进入到根目录，新建一个名为ssh的空白文件(无后缀)就可以。

好了然后再把卡插回树莓派，就可以使用SSH了。

• 初始用户名：pi
• 初始密码：raspberry

将红外接受管和发射管连接至树莓派GPIO接口

材料：

红外接受管（3pin），红外接受管（2pin）,杜邦线若干。

根据不同树莓派版本，查看GPIO的引线图，该实验采用B+版，具体实物对应图和GPIO与pin对应图如下图：

硬件连接

红外接收器

• vcc 连 pin1 (3.3v)

• gnd 连 pin6(ground)

• data 连 pin12(gpio18)

红外发射器

• gnd 连 pin25(ground)

• data 连 pin11(gpio17)

红外接受器规格见图，左引脚为data，中为接地，右为3.3V供电

红外发射器规格见图，长脚为data,短脚为接地

接收器和发射器通过杜邦线跟树莓派相连，最后的连接实物图

预先解析控制码

修改 raspbian 仓库默认源

1. 修改apt源

1

sudo nano /etc/apt/sources.list

例如使用大连东软信息学院软件源镜像，修改之后的内容如下：

1

deb http://mirrors.aliyun.com/raspbian/raspbian jessie main contrib non-free rpi

其他可用源如下：

• 中国科学技术大学 Raspbian http://mirrors.ustc.edu.cn/raspbian/raspbian/

• 阿里云 Raspbian http://mirrors.aliyun.com/raspbian/raspbian/

• 清华大学 Raspbian http://mirrors.tuna.tsinghua.edu.cn/raspbian/raspbian/

• 华中科技大学 Raspbian http://mirrors.hustunique.com/raspbian/raspbian/ Arch Linux ARM http://mirrors.hustunique.com/archlinuxarm/

• 华南农业大学（华南用户） Raspbian http://mirrors.scau.edu.cn/raspbian/

• 大连东软信息学院源（北方用户） Raspbian http://mirrors.neusoft.edu.cn/raspbian/raspbian/

• 重庆大学源（中西部用户）

  Raspbian http://mirrors.cqu.edu.cn/Raspbian/raspbian/

2. 更新软件源和软件

1
2
3
4

# 更新软件源
sudo apt-get update
# 更新软件
sudo apt-get upgrade

更换vi文本编译器为vim

因为vi在insert模式下，方向键会变为ABCD，故用vim进行替换

1
2
3
4

#卸载vi
sudo apt-get remove vi-common
#安装vim
sudo apt-get install -y vim

安装lirc

LIRC (Linux Infrared remote control)是一个linux系统下开源的软件包。这个软件可以让Linux系统接收及发送红外线信号。

1

sudo apt-get install lirc

配置硬件

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

# sudo vim /boot/config.txt #在文件结尾添加
# 修改一下内容
dtoverlay=lirc-rpi
gpio_in_pin=18
gpio_out_pin=17

# sudo vim /etc/lirc/hardware.conf  #编辑LRIC的配置文件
# 修改以下内容
LIRCD_ARGS="--uinput"
DRIVER="default"
DEVICE="/dev/lirc0"
MODULES="lirc_rpi"

# 重启生效
sudo /etc/init.d/lirc restart

注意：配置gpio_in_pin和gpio_out_pin时，编号为GPIO号，并非pin号

启动测试

1

sudo mode2 -d /dev/lirc0

红外接收器已经打开，处于监听状态。这个时候，利用任何红外发射器（可以是电视遥控器或其他遥控器）对红外接收模块按任意按钮，就可以在树莓派终端上看到类似如下的代码

看到这个代码便证明红外接收模块是正常工作的。

如果没有看到，请检查你的接线、电压、以及通过lsusb查看是否加载了相应模块。

1
2
3
4
5
6

pulse 1681
space 4816
pulse 1695
space 4784
pulse 1333
space 3638

录制解析控制码

1. 开始录制

1

irrecord -d /dev/lirc0 ~/lircd.conf #按照提示操作即可,录制完后会让你输入按键名

2. 查看可用键名列表

1

irrecord --list-namespace

3. 将已录制的编码加载进 lirc 配置参数

1

sudo cp ~/lircd.conf /etc/lirc/lircd.conf

通过树莓派发射红外编码

1. 启动lircd服务

1

sudo lircd -d /dev/lirc0

2. 查看录制好可以使用的键名

1

irsend LIST /home/pi/lircd.conf ""

3. 发送红外编码

1

irsend SEND_ONCE /home/pi/lircd.conf KEY_XXX

演示效果

关于录制带逻辑编码的红外编码

一个比较令人兴奋的消息，谢谢博客http://blog.just4fun.site/raspberrypi-lirc.html的帮助，直接发送raw原始码就可以实现简单的控制程序。😘

注意：其只能使用raw原始码，记录是通过mode2命令实现。

1. 制作模版（不设置按键，初始化玩直接跳过）

1
2

sudo /etc/init.d/lirc restart
irrecord  -f -d /dev/lirc0 ~/lircd.conf

2. 录制需要实现的按键

1
2
3
4
5
6
7
8
9

mode2  -d /dev/lirc0 > /tmp/temp.code  
cat /tmp/temp.code | sed -n '2,$p' | grep -o  -E "[0-9]+" | xargs echo  # 移除第一行,之后把所有数字取出

# 把上述指令写入 ~/lircd.conf 的 KEY_OPEN里
# 值得注意的是 ~/lircd.conf文件里的空格十分重要

sudo cp ~/lircd.conf /etc/lirc/lircd.conf
sudo /etc/init.d/lirc restart
# irsend LIST /home/pi/lircd.conf "" #列出指令

3. 最后一个参考格式的lircd.conf文件（保证空格正确）

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

begin remote

  name  /home/pi/lircd.conf
  flags RAW_CODES
  eps            30
  aeps          100

  gap          8015

      begin raw_codes

          name KEY_POWER
               8927 4522 531 1711 551 1706 559 598 549 599 551 600 551 598 551 597 552 1719 558 597 549 1715 549 1724 540 614 535 592 559 597 550 599 551 610 551 602 549 598 553 1706 558 598 549 601 549 599 550 601 548 614 551 593 557 1717 545 598 551 598 552 598 552 599 549 598 553 1720 556 597 563 589 549 600 549 601 549 607 545 593 555 599 551 614 548 598 551 598 551 600 550 594 604 548 555 597 551 599 551 597 573 7967 558 597 549 598 548 603 548 601 554 598 550 599 550 600 545 619 549 600 545 599 556 598 551 600 549 611 541 597 551 599 551 609 548 601 555 598 552 596 554 598 550 598 563 587 551 600 543 615 556 598 550 598 551 599 576 574 552 596 552 598 552 613 538 612 551 595 552 597 553 598 552 599 552 596 552 1720 545 596 552 610 551 599 551 599 575 575 551 593 559 595 553 598 552 598 549 612 552 598 551 1705 559 597 574 1689 550 1724 540 598 552 592 559 609 553 599 548 598 552 1711 551 1705 560 1708 553 1711 550 599 553 1716 563 7970 559 597 551 600 573 578 550 599 551 600 575 573 565 589 575 586 552 1710 554 597 556 596 553 597 549 604 552 600 550 599 551 614 551 598 552 599 552 599 548 602 553 598 550 1713 552 599 552 613 593 558 545 604 564 586 552 598 552 598 554 595 554 601 546 617 546 607 550 597 551 611 541 597 553 598 553 598 580 572 548 615 552 599 554 596 552 599 551 598 554 598 547 614 536 604 552 609 554 1714 548 598 556 597 548 599 553 601 553 1711 553 598 553 593 549

      end raw_codes

end remote

4. 启动服务，运行指令

1
2

sudo lircd -d /dev/lirc0
irsend SEND_ONCE /home/pi/lircd.conf KEY_POWER

本人常用Mi5s,伴随着MIUI9（7.0）内测，实在等不急官网放MIUI的包（其实是不想使用MIUI，设计风格跟原生差异太大）。

这几天就靠着以前的所积累的刷机经验，并且刷上刚适配的lineage os (CM14.1)，以此为基础，替换AOSP（Android Open-Source Project）编码的应用。

再加 上pixel launcher 谷歌“亲儿子”的美化和Nougat的优化，对原生的安卓顿生好感。

当然，刷机过程也是比较曲折的，但总算没有白费精力，为了以后类似操作便捷，特地记录一下。

Step1: 小米官网解锁fastboot

​ 小米自从mi4后，为了增强安全性（防止大家乱刷机），至底层加入bl锁，导致刷入第一步需解锁，但刷机有风险，一旦解锁，就失去保修机会，且修改不可逆，小米会将设备解锁信息在服务器上保存，谨慎操作！

• 解锁网址：http://www.miui.com/unlock/index.html
• 解锁步骤：https://jingyan.baidu.com/article/29697b9103205dab20de3c33.html

Step2: adb刷入第三方recovery(TWRP)

1. 去https://twrp.me/下载最新的TWRP(我当时最新版本3.1.1.0)，为之后刷第三方系统做准备，并用adb(Android Debug Bridge)工具包刷入TWRP

ADB下载地址：http://adbshell.com/downloads 选择ADB Kits

2. 手机关机进入fastboot模式（音量键下+电源键），USB连接电脑，装上驱动（用官方驱动或者第三方驱动安装软件）

powershell 刷入命令

1

.\fastboot flash recovery XXX.img

• XXX.img代表TWRP所下载的文件名

3. 最后输入命令重启，再关机，按住 音量键上+电源键 进入recovery模式

1

.\fastboot reboot

Setp3: 刷入lineage os(with root)

去lineage os官网下载rom包和root包，在recovery模式下，用TWRP依次刷入两个包

网址：https://download.lineageos.org/

注意：根据设备cpu类型选择root包（我的是arm64,安卓7.1）

Step4: 刷入openGapps（aroma）

网址：http://opengapps.org/

根据设备类型选择包

• aroma ： 图形化安装版本，可以自定义所需刷入的应用。（但有些机型会由于recovery的原因无法使用）。

• super ：最为完备的版本，该有的和不该有的都有了（比如日语输入法、注音输入法、等大陆用户基本上不会需要的应用）

• stock ：包括 nexus 出厂所具备的所有应用，在安装好 CM 、魔趣等系统后，刷入该包会自动替换掉 Aosp 的应用 ，比如 Google 相机、Gmail、Google Now 桌面、Google 相册分别替换掉 Aosp所带的 相机、 邮件、桌面、相册等，当然 Google全家桶的其他软件如 Gooele Play、Youtube、地图、Gooele keep等也会随之刷入你手机。

• full ：与 stock 唯一区别就在于不会替换掉 Aosp 应用。

• mini、micro、nano、pico ：依次减少应用，但都具备 Google service 和 Play

推荐nano包，但下载时需要一个稳定的梯子，建议用chrome直接下载，最后用TWRP刷入既可。

Step5: 精简部分不需要系统应用+修改hosts

该布操作最简单，但比较繁琐，用root删除掉内置的一些不需要使用的google应用，比如其他语言输入法，删除完后重启手机一次。

用go hosts APP替换掉原始hosts，使设备能直接访问谷歌（该操作并不完美，但可以用做备用）

Step6: 刷入Magisk框架并接入viperfx音效

因为手机并不自带音效改善软件，且不带HIFI模块的手机插手机的音效很差，所以这里刷入现在口碑最好的viperfx音效，但直接刷入时会存在I/O报错，root报错等原因，所以这里借助Magisk框架修改系统API接口实现同等功能

Magisk 下载网址：https://forum.xda-developers.com/apps/magisk/official-magisk-v7-universal-systemless-t3473445

1. 先TWRP刷入Magisk ；
2. 再开机安装Magisk Manager apk；
3. 最后在magisk中安装viperfx即可。

最终效果图

题目描述：

小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。

现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, … AN。

小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？

输入：

第一行包含两个个整数N和K。

第二行包含N个整数A1, A2, … AN。

对于30%的数据，1 ≤ N ≤ 10​

对于100%的数据，1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000, 0 ≤ K ≤ 100000

输出：

一个整数，代表答案。

样例输入： 5 1 2 3 1 2 4 2 5 5 3

样例输出： 6

再比如，

样例输入：

10 1

2 1 1 1 1 4 4 3 4 4

样例输出： 8

资源约定：

峰值内存消耗 < 256M

CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0

注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。

注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。提交时，注意选择所期望的编译器类型。

问题分析：

​这题就相较于前几题就有难度提升，不在依靠于单一基础算法就能较好的解决问题。

​比赛时，我一开始就认为搜索能解决问题，纸上推演的半个小时才发现有问题，始终是一个NP问题。后来经过分析：这样的策略可能达到解决问题的目的：

1. 因为当K>0时，若选值为m的点，则应该选上值为m的所有点，依照桶排序的思想，进行优化

2. 当K=0时，最大选择数=不同值的点的类别数

3. 依照K值，形成关系链（可以为多条关系链）

4. 单一关系链中，选择类数和并且不关联的最大一个或几个点，该算法应为动态规划

如图所示：

输入：

1
2

22 2  
2 1 1 1 1 4 4 3 4 4 6 7 7 8 8 8 8 9 11 11 12 13

• 第一条链最大个数和：4
• 第二条链最大个数和：8
• 第三条链最大个数和：2
• 第四条链最大个数和：2
• 第五条链最大个数和：1

最大个数和：4 + 8 + 2 + 2 + 1 = 17

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

const int N = 100000;
int n, k;
std::array<int, N> num{0};
std::vector<int> link[N];
int node[N];
int num_node = 0;
int num_link = 0;   // 关系链数
std::array<short, N> vis{0};    // 1代表已访问，0代表未访问，-1代表点不存在
std::array<int, N> F{0}; // dp F[i]=max(F[i-1],F[F-2]+num[i])
long long tot = 0;

void init() {
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int t;
        std::cin >> t;
        num[t]++;
        vis[i] = -1;
    }

}

void work() {
    for (int i = 0; i <= N; i++)
        if (num[i] != 0) {
            node[num_node++] = i;
            vis[i] = 0;
        }
    for (int i = 0; i < num_node; i++) {
        if (vis[node[i]] == 0) {
            vis[node[i]] = 1;
            link[num_link].push_back(node[i]);
            int next = node[i] + k;
            while (vis[next] == 0) {
                link[num_link].push_back(next);
                vis[next] = 1;
                next = next + k;
            }
            num_link++;
        }
    }
}

void dp() {
    for (int i = 0; i < num_link; i++) {
        F.fill(0);
        for (int j = 0; j < link[i].size(); j++) {
            if (j >= 2)
                F[j] = std::max(F[j - 1], F[j - 2] + num[link[i][j]]);
            else if (j == 0)
                F[j] = num[link[i][j]];
            else if (j == 1)
                F[j] = std::max(F[j - 1], num[link[i][j]]);
        }
        // std::cout << F[link[i].size() - 1] << std::endl;
        tot += F[link[i].size() - 1];
    }
}

int main() {
    init();
    work();
    dp();
    std::cout << tot;
    /*
    for (int i = 0; i < num_node; i++)
        std::cout << node[i] << "->" << num[node[i]] << " ";
    std::cout << std::endl;

    for (int i = 0; i < num_link; i++) {
        for (int j : link[i]) {
            std::cout << j << " ";
        }
        std::cout << std::endl;
    }
    */
    return 0;
}