.mjpage .MJX-monospace {
font-family: monospace
}
.mjpage .MJX-sans-serif {
font-family: sans-serif
}
...
PAT冲冲冲——甲级
PAT甲10级练习题 ——PAT (Advanced Level) Practice
PAT甲级(Advanced Level)真题
柳婼 の blog经验
saquarius’s blog
PAT甲级题目及分类总结
pat甲级题解目录
PAT考试经验总结（甲乙级均适用）想满分的请看这里！——前人经验
▲报名费256，可以刷牛客网的题来获得-50的优惠券，该练习场下的所有题目只要通过都算
甲级练习题
由于甲级题目较多，也较难，因此决定还是将两者分开写两篇文章了。
1001 A+B Format (20 分)
看似很简单的一道题，但坑点确实不少， ...
高性能问题：
Q：需求：（老板给你分了台2GHz单核，内存500M的服务器然后让你写程序）程序每秒会收到一组数据，每组数据包含10万条命令，总共会有100万个仓库，每个仓库库存没有上限且可为负，库存初始为0。你需要在一秒内完成全部的命令，然后将查询结果按顺序得出后传回，命令如下：
Add i j，i和j为正整数，表示第i个仓库增加j个库存（j不超过220）
Sub i j，i和j为正整数，表示第i个仓库减少个库存（j不超过220）
Query i j，i和j为正整数，i<=j，表示询问第i到第个仓库的总库存；End 表示结束，这条命令在每组数据最后出现；
思路一：用array去存储每 ...
PAT冲冲冲——乙级
PAT甲级练习题 ——PAT (Advanced Level) Practice
PAT甲级(Advanced Level)真题
柳婼 の blog经验
saquarius’s blog
PAT甲级题目及分类总结
pat甲级题解目录
▲报名费256，可以刷牛客网的题来获得-50的优惠券，该练习场下的所有题目只要通过都算
乙级练习题
NowCoder数列
没想到第二题就是考了个数据范围，由于0≤n≤1000000，所以F(n)必然比long long大，而判断3的倍数可表示为===> F(n) % 3 —> (F(n-1)%3 + F(n-2)%3 ...
MinMax-极小极大算法——2048
算法介绍
MinMax
大家在编程的时候应该或多或少都接触到过这样的写法:min(max(xxx,yyy))，MinMax算法的表达形式就是如此，不过其中的Min和Max都是具有对应含义的。
一般解决博弈类问题的自然想法是将格局组织成一棵），树的每一个节点表示一种格局，而父子关系表示由父格局经过一步可以到达子格局。Minimax也不例外，它通过对以当前格局为根的格局树搜索来确定下一步的选择。而一切格局树搜索算法的核心都是对每个格局价值的评价。Minimax算法基于以下朴素思想确定格局价值：
Minimax是一种悲观算法，即假设对手每一步都会将 ...
sshpass
ssh登陆不能在命令行中指定密码。sshpass的出现，解决了这一问题。即sshpass可以用于非交互SSH的密码验证，一般用在sh脚本中，无须再次输入密码。
sshpass允许用-p参数指定明文密码，然后直接登录远程服务器。(支持密码从命令行、文件、环境变量中读取)
1.安装sudo apt install sshpass
2.使用说明
12345678910111213141516171819# -p 直接指定密码sshpass -p '123456' ssh user_name@host_ip# -f: -f filename #后跟保存密码的文件名，密码是文件内容 ...
Hungarian algorithm匈牙利算法
主要用来解决不带权的分配问题，O(V*E)
首先，需要明白二分图（又名二部图）的概念
二分图Bipartite Graph
二分图是图论中一种特殊模型。设G=(V,E)是一个无向图(当且仅当图中不存在长度为奇数的环。)，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
注意：如果一图是二分图，那么它一定没有奇环。如果一图没有奇环的话，那么它可以是二分图。(没有奇环是二分图的必要条件)
▲通常被用来解决分配、匹配 ...
安装系统镜像:
官网下载镜像，解压下载好的Zip文件会得到.img镜像文件。下载win32DiskImage
方式:
SSH
VNC
Xrdp
系统设置:
$ sudo raspi-reconfig
1.安装字体
默认安装的是英文字体，如果时区选择中文，将会乱码，因此需要安装中文字体进行汉化。
sudo apt-get install ttf-wqy-zenhei
2.安装中文输入发
3.修改键盘布局
键盘布局默认是英标的，需要将其改成美标
输入sudo dpkg-reconfigure keyboard-configuration后选择通用的104键PC键盘(Generic 10 ...
KM(Kuhn-Munkres)算法
带权二分图最佳完美匹配，O(n^3)，（运用匈牙利算法辅助求解），同时也是完备匹配
只适用于带权最大匹配一定是完备匹配的情况，实践中建议用费用流来解决。
完全二分图一定是偶数个点
可行顶标（Feasible Labeling）：结点函数（x），任意边（x，y）：1（x）+l（y）≥w（xiy）。
相等子图：G的生成子图，包含所有点以及满足l（x）+I（y）=w（x，y）的边（x，y）
如果EL有完美匹配为PM，则该M是原图的最大权匹配：
PM的权和等于所有点的顶标之和SV。
G的任一个最大权匹配M，边满足w（xy）≤l（x）+（y）→M边权和≤S ...
二分图的判定：
染色法1：假设DFS初始点A涂黑色，与它相邻的点就涂白色。如果搜到某一个点u的相邻点v已经涂色并且与u同色，就不可能是二分图啦~
染色法2：就是给每个点进行标号，标为-1，1如果存在一条边连接的两个点标号相同，那么就是存在一个奇数环…
热身题：
判断无向图是否有环
用DFS遍历图g，如果访问到已经访问过的顶点，那么有环
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 ...
最大流
FF算法
最基本找増广路的算法
dinic实现(基础的FF算法)
反边：我们知道，当我们在寻找增广路的时候，在前面找出的不一定是最优解，如果我们在减去残量网络中正向边的同时将相对应的反向边加上对应的值，我们就相当于可以反悔从这条边流过。
技巧：flow[u]正边，flow[u^1]反边
建边的时候是同时建的，比如1的反边为2，2的反边为1，▲边不能从0开始
主要思路：
求增广路
分层图
dinic的优化
当前弧优化(作用不明显)
12345678910111213141516171819202122232425262728// 最原始int dfs(int no ...
网络知识——Websocket
TCP ：面向连接—> 打电话(相互回复,一来一回)，客户端向服务器端 拨号 , 三次握手 ,
UDP : 面向无连接 --> 寄快递(寄出去就不管了) e.g.直播
UDP四层结构
网络访问层(链路层): 物理连接设备(网线)、MAC地址（物理地址）
互联网层： IP地址（定位设备）
传输层： port (端口号) : 表示通信进程,将数据交给哪个应用处理
应用层： 自己定义的协议（处理字符串消息的方法）
套接字(socket) ： 特殊的设备文件 ， 写网络应用程序的接口，写入后就是发送，接收就是读取。 类似于 esp8266 ...
PIL的Image学习
transpose和rotate
transpose
1234from PIL import Imageimg = getCaptcha()# 对称反转img.transpose(Image.FLIP_LEFT_RIGHT)
rotate
123456from PIL import Imageimg = getCaptcha()# expand默认为False时,超出原有尺寸的部分将用黑色填充,不会拓展尺寸img = img.rotate(45)# expand为True时,会根据图片大小,拓展尺寸img = img.rotate(45,expand=Tru ...
2019年8月23号运维笔记
docker
docker stop containerID，以后再重新启动时报错
1Error response from daemon: driver failed programming external connectivity on endpoint app (3c0c01ac6b42b7a420644fc2b4debfbbcc0e1d2e74e6294155c28aca82f794c4): (iptables failed: iptables --wait -t nat -A DOCKER -p tcp -d 0/0 --dport 12345 ...
app测试
命令
adb shell monkey 500随机执行500次
adb shell pm list packages -3 查看第三方包
adb shell monkey -p tv.danmaku.bili指定在某个软件中随机压力测试
adb shell monkey -p tv.danmaku.bili -p com.umaman.laiyifen 500会先执行来伊份
▲.在测试应用程序某些选项的同时，也会进行系统级功能的测试，如截图、调音量等
adb shell monkey [-options] times
参数说明
1234567-s seed种子值：种子相同时， ...
2019-9月7号C++编程笔记
auto
定义变量时放在变量前，无需知道具体变量类型，系统可自行推断类型，减少编程工作，特别是在模板使用时，使用更方便。
123456789101112131415161718auto a=1;auto b='a';auto s="abdc";auto c;//这样使用时错误的，系统无法自动推断出变量类型//下面为迭代指针使用，很方便vector<int> vec;auto it=vec.begin();/**模板使用案例*/template<typename InputIterator> TreeNode *creatTre ...
MinMax和Alpha-beta剪枝分析[转]
一般解决博弈类问题的自然想法是将格局组织成一棵），树的每一个节点表示一种格局，而父子关系表示由父格局经过一步可以到达子格局。Minimax也不例外，它通过对以当前格局为根的格局树搜索来确定下一步的选择。而一切格局树搜索算法的核心都是对每个格局价值的评价。Minimax算法基于以下朴素思想确定格局价值：
Minimax是一种悲观算法，即假设对手每一步都会将我方引入从当前看理论上价值最小的格局方向，即对手具有完美决策能力。因此我方的策略应该是选择那些对方所能达到的让我方最差情况中最好的，也就是让对方在完美决策下所对我造成的损失最小。
Mini ...
第二十八届“和巨耀通杯”NOJ邀请赛
三人团队赛， 正好最近在刷PTA， 于是一个人报名尝试了一下。
一共AC了三题， Rank28
C. Battle game
签到题
Description:
You are playing a game which you will battle with an enemy. As you don’t want to lose, your total power can’t be lower than your enemy’s. Your power is simply added by the power of your soldiers, ...
软件测试笔记
移动应用测试
appnium使用
安装的是appnium-desktop,没有教程中所说的Appium/node_modules/.bin/路径，使用命令行输入appnium和appium-doctor也都没啥反应，后来索性没管，直接跑代码
真机测试
使用的时候报错Build info: version: 'unknown', revision: 'unknown', time: 'unknown'，以为是appnium版本的问题，第一次安装的是1.13，后来换成了1.9，其实没多大区别，只不过据说要保证版本在1.6以上。
更换版本后，发现还是Build info: ...
玩玩Stm32
文件结构
12345678910111213141516G:.├───CORE # startup_stm32f10x_hd.s汇编编写的启动文件| # core_cm3.c底层函数├───HARDWARE # 相关外设的初始化代码├───OBJ├───STM32F10x_FWLib # 固件库包: GPIO/i2c/...│ ├───inc│ └───src├───SYSTEM # 正点原子提供的常用、通用模块│ ├───delay│ ├───sys│ └───usart└───USER # stm32f10x_it.c 中断管理文件 | ...