Hexo

枚举，二分，前缀和 前缀和 ABC181E: Transformable Teacher 1200 题意 \(N \le 2 \times 10^5\) (奇数)个小朋友，第 \(i\) 身高为 \(H_i\) ，老师的身高可以变换，共有\(M \le 2 \times 10^5\) 种形态，第 \(i\) 种身高为 \(W_i\) . 现在小朋友和老师一起做游戏，两个人一组。配对花费为 \[ \sum_{i=1}^{(N+1)/2}|x_i-y_i| \] \(x_i,y_i\) 是第 \(i\) 组两个人的身高 求最小的的配对花费。 分析 老师必定要匹配一个小朋友。那么可以枚举小朋友和老师匹配，剩下的小朋友自己匹配。自己匹配的最优解一定是排序后两个相邻的匹配。小朋友和老师匹配，就是老师选一个和小朋友最接近的升高来匹配。这个可以排序后用二分 \(O(logM)\) 实现。小朋友两两匹配可以用前缀和预处理好, 枚举的时候 \(O(1)\) 查询. 代码 1234567891011121314151617181920212223242526272 ...

动态规划习题 (R1000-R2300) 状态压缩动态规划 ABC180E: Traveling Salesman among Aerial Cities R1200 题意 有 \(N \le 17\) 个城市的坐标是 \((X_i,Y_i,Z_i)\) , 从坐标 \((a,b,c)\) 到 \((p,q,r)\) 的距离是 \(|p-a|+|q-b|+\text{max}(0,r-c)\) , 求从 \(1\) 号城市出发，访问完所有城市回到 \(1\) 的最小距离 分析 数据量提示较为明显，考虑状压dp. 用一个Bitmask \(S\) 记录访问过的城市。因为从 \(1\) 号城市出发，还要回到 \(1\) 号城市。可以不妨设开始的时候，\(1\) 号城市没有访问，然后访问完一圈之后回到 \(1\) 正好访问完所有的城市. 设 \(f[S][i]\) 是你访问完 \(S\) 集合中的所有城市，现在的位置在 \(i\) ,那么可以写出下面的方程： \[ f[S][i] = \infin \ ,\ f[0][1] = 0\\ f[S][i]= mi ...

Analysis 数学分析 实数 数集 \[ \Z=\{所有整数的集合\} \\ \R = \{所有实数的集合\} \\ \Q = \{所有有理数的集合\} \\ \N=\{x\in Z:x\ge 0\} = \N_0 \\ \N_{>0}=\{1,2,3,4,...\}=\{x\in N:x>0\} \] 定义 1.1 子集 \(B\) 是 \(A\) 的子集， \(B \subseteq A\) ， 若 \(\forall x \in B \Rightarrow x\in A\) 定义1.2 映射 一个函数 \(f: A\rightarrow B\) 是 injektiv 若 \(\forall_{x \neq y \in A} f(x) \neq f(y)\) surjektiv 若 \(\forall_{y \in B} \exists_{x \in A} f(x)=y\) bijektiv 若 \(f\) 同时 injektiv 和 surjektiv 集合的模 Kardinalität 如果两个集合 \( ...

Codeforces Round #680 (Div. 2) 传送门 A. Array Rearrangment 数学 题意 给定 \(A,B\) 数组和一个数 \(x\), 将 \(A\) 数组和 \(B\) 数组匹配，使得 \(A_i + B_i \le x\) 分析 \(A\) 的最大值 \(A_{max}\) 必须要找一个 \(B\) 数组的元素匹配。那么如果最小的 \(B_{min}\) 都无法满足，那么无解。否则存在解。 考虑假如存在一个解，那么它是不是一定也存在 \(A_{max}\) 与 \(B_{min}\) 匹配的解. 如果有一个满足的解 \(A_{max}\) 和 \(B_i\) 匹配，\(B_{min}\) 和 \(A_j\) 匹配. 那么 \(A_{max}+ B_i \le x\) 且 \(B_{min} + A_j \le x\) 其不是最大值与最小值匹配的情况. 那么交换 \(B_{min}\) 与 \(B_{i}\) . 可以证明 \(A_{max} + B_{min} \le A_{max} + B_i \le x\) ...

LaTeX 安装 打开这个网页 image-20201016171058010 安装这个即可 然后安装个 TexMaker 1winget install texmaker 然后可以配置一下，在选项里面配置，可以把编译器改一下来支持中文 image-20201016171147980 LaTeX文档 12345678910111213141516171819202122232425\documentclass{article}\usepackage{ctex}\usepackage{graphicx}\usepackage{booktabs}\usepackage{multirow}\title{Use \LaTeX to make presentation}\author{Fyind}\date{\today}\begin{document} \maketitle ...

QT编程 下载QT http://download.qt.io/official_releases/qt/5.12/5.12.0/ image-20200913175437819 下载那个exe，然后安装好. image-20200913180336560 image-20200913180400705 新建项目 左上角文件-> 新建项目 image-20200913181029681 然后这里用Dialog image-20200913181212608 配置链接 点那个配置链接的图标，然后从slidebar 拖拽到dial组件，就可以生成一个信号 image-20200913181812844 文档 在开始搜索assist，打开assistant MinGW 就可以打开Qt的文档 image-20200913183304138 程序发布 首先设置成release版本 image-20200913183934227 然后构建，打开构建的目录 ...

引入 如果不使用数据库系统，会有很多问题，如数据的损失，多用户同时访问，安全问题，高昂的开发成本等。 数据库的结构 下面是一个数据库的示意图。最底层的是物理层，数据和数据结构(B树) 就存在这里。然后上面一层逻辑层是比如说放表格这些的位置。然后上面是不同的人相对于数据库不同的视角，因为权限不一样所以可以访问的也不一样 image-20200919100827092 更为具体的是下面这张图 image-20200919104235467 数据建模 类似我们在程序设计的时候要建模，在设计数据库的时候也要对数据建模，对于数据的概念模型有： Entity-Relationship-Modell (ER-Modell) Unified Modeling Language(UML) 逻辑层面的模型有 Relationales Modell 同过关系来建模 比如在大学的范围里，我们可以建立下面的数据模型 image-20200919104540233 下面是对应的数据表 image-202009191046 ...

网络安全 Vmware Workstation 桥接网络配置 image-20200919203643934 打开虚拟网络编辑器，发现没有桥接网络，点设置 image-20200919203722602 让桥接模式解上正确的网卡 image-20200919203838977 然后主机和虚拟机就可以互相ping通了 image-20200919204116816 环境搭建 Kali Linux 镜像下载 https://www.kali.org/downloads/ 安装完虚拟机后，更新一下源 123apt updateapt upgradeapt dist-upgrade 源列表位置 /etc/apt/source.list 设置开机启动软件 12update-rc.d ssh enableupdate-rc.d postgresql enable 重启网络服务 1service networking restart 开启网卡 12ifconfig eth0 upifup eth0 Win ...

Javaweb 安装 IDEA, 可以先用 -Ss 搜索intellij 来确定后面的版本号 1sudo pacman -S intellij-idea-ultimate-edition-2020.2.1-1 IDEA 使用技巧 别打开老项目 settings 里面 system settings了里面别勾选 Reopen image-20200906194355077 Ctrl + 鼠标左键可以查看源代码 Alt + Shift + v 新建局部变量 Tomcat 安装 1sudo pacman -S tomcat9 最好要去官网下载, 这样用户有执行权限，pacman 下载的运行要家sudo, 在idea里会报错 启动 可以在zshrc里面加入 12alias tomcat="sudo zsh /usr/share/tomcat9/bin/startup.sh"alias ctomcat="sudo zsh /usr/share/tomcat9/bin/shutdown.sh" 然后可以 ...

前缀和和差分 https://ac.nowcoder.com/acm/contest/19483 普通前缀和 前缀和数组 对于数组 \(A\) 的前缀和数组 \(s\) 是 \[ s[x]=\sum_{i=0}^{x}A[i] \] 递推公式 \[ s[x]=s[x-1]+A[x] \\ s[0]=0 \] 广义前缀和 把求和看成某种操作的累加。 维护dp矩阵 DP转移用矩阵表示，然后可以用前缀和维护 求 \[ dp(l,r) = dp(1,r)-dp(1,l) \] 设初始列向量为 \(\textbf{v}\), 转移矩阵为 \(mat[i]\) 然后 \[ dp(l,r) = mat[r] \cdot mat[r-1] \cdot mat[r-2]...mat[l+1] \cdot \textbf{v} \] 所以我们维护一个左乘矩阵前缀和 \[ sum[i] = mat[i] \cdot mat[i-1] ... mat[2] \cdot mat[1]\\ sum[i]=mat[i] \cdot sum[i-1] \] 维护好之后计算 ...