无向秃

原创 mit s0681 lab2 Trace系统调用实现

xv6操作系统内核trace系统调用实现

原创 SpringMVC的执行流程图例

原创 html解析Model与ModelandView测试

解析关于html解析这个的话我使用的是thymeleaf解析模板，这里贴上ssm引入thymeleaf的代码Maven导入 <dependency> <groupId>org.thymeleaf</groupId> <artifactId>thymeleaf</artifactId> <version>3.0.11.RELEASE</version> </depe

原创 Navicat连接远程服务器失败(2003)

Navicat连接远程服务器失败（2003）的问题一般有一下几种：数据库未开启网络安全组未开启防火墙未关闭数据库可访问ip未设置(可能不是，但是可以试试)防火墙的关闭命令第一种//停止systemctl stop firewalld.service//禁止开机启动systemctl disable firewalld.service第二种//这里发现防火墙是开启的，再来查看防火墙控制的端口systemctl status firewalld//查看防火墙控制的端口，发现我想

原创 网页打开的实现

一个类似的网络结构，由客户机H1(HTTP)访问服务器H2(域名为：www.abcde.com)时TCP/IP协议体系的经过分析传输过程1. 应用层：DNS协议: 首先访问DNS服务器，DNS 运行在 53 号端口，于是浏览器会创建一个 UDP 套接字，标识该套接字的二元组分别是『目的 IP 地址』和『目的端口』。而套接字本质上就是为了唯一标识应用层进程，就是为了让响应报文能够找到目的地。HTTP/1.1协议：由于域名为www.abcde.com，由于是对于万维网的网点访问，所有使用的是HT

原创 Git使用命令

命令初始化本地git仓库git init声明远程仓库路径git remote add origin (你的远程项目地址)查看仓库地址git remote -v如果结果是正确的则跳过下面的代码。git remote rm origingit remote add origin xxxxx.git查看全局配置信息git config --global --list检测是否连接上远程仓库git fetchE:\workspace\go-xxx>gi

原创 http使用post提交后服务器显示乱码

首先我们要了解到浏览器的发送形式：把表单的数据经过规定的编码格式进行编码（没有特殊声明，一般就是网页规定的格式，特殊声明方式是 accept-charset）成urlencode的格式。一般来说，中文都转义成%xx的形式然后发送时使用该编码发送数据，在服务器端接受字节流以后得到的就是urlencode的编码格式，我们要正常显示的话，还要将其按照urlencode的形式来改。另tomcat9已经是默认utf-8编码了...

转载 String、StringBuffer和StringBuilder的区别

一篇写的非常容易理解的博客收藏等于不看，还是转载好。

原创 Java调用百度地图API实现经纬度转详细地址。

我们在百度地图获取ak以后打开逆地理编码查看服务文档。我们采用Java的Java.net来调用API。直接看demo吧package BDS;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.UnsupportedEncodingException;import java.net.MalformedURLException;i

转载 Javaio流

io流关于Java的io流一般按照数据操作类型可以分为字节流与字符流首先来说一下字节流字节流字节流的方法都是以stream结尾的。字节流的用途：转换图片为二进制。转换音频，视屏为二进制。字符串等也可以转为二进制。字节流常用于图片，音频等二进制的传输。方法字节流FileInputStream 从文件系统中的某个文件中获得输入字节。FileOutputStream 文件输出流是用于将数据写入 File 或 FileDescriptor 的输出流。文件是否可用或能否可以被创建

原创 最小费用最大网络流

要打网络赛了，抓紧时间复习。这里我先介绍一下费用流全名：最小费用最大网络流。所以我先介绍最大网络流。最大网络流就是给定一个图，每一条边都有一个上限，表示这条边的最大流量，求从源点流到汇点的最大流量。对于这种题目，我们一般采用dinic算法(复杂度n2∗mn^2*mn2∗m).dinic对于dinic算法，每次增广前，我们先用 BFS 来将图分层。设源点的层数为 0 ，那么一个点的层数便是它离源点的最近距离。分层：确定每一个点的层数，那么只要每一次都走到下一层，则在寻找增广路时保证搜索深度最

原创 CF1341D

题目链接题意的话给出了n个01串，1代表该位置是亮的，我们必须把m个位置变亮后且都是数字。求能组成的最大数字。每个位置代表的地方看题目给的图吧。思路明显的dp题，我们假设dp[i][j]dp[i][j]dp[i][j]表示前iii个数字花费jjj次机会后能形成具体数字。那么其状态转移方程为：dp[i][j]=dp[i+1][j+val[k]]dp[i][j]=dp[i+1][j+val[k]...

原创 codeforces1343F

这道F题说句实在的，题意能把人看蒙了，看懂了倒是挺简单的，反正我一开始把题意看难了。题目题目大意存在一个长度为nnn的排列aaa，然后给出n−1n-1n−1个子排列，其中每个子排列的元素为[al,al+1,...,ar][a_l,a_{l+1},...,a_r][al​,al+1​,...,ar​]，其中rrr是由2−n2-n2−n里面的数字，每一个数字必将出现一次。求原来的排列。思想看...

原创 差分约束zoj2770

题目链接题意大概就是给我们nnn个营地，c[i]c[i]c[i]表示第iii个营地最多的人数，第uuu-第vvv个营地一共有www个人。问最少有多少人。对于这种题型，我们一般做法是首先确定一个数组表示前面iii个营地的总人数挖掘隐藏条件，每一个营地的人数不可能为负数，所以a[i]−a[i−1]≥0a[i]-a[i-1]\geq0a[i]−a[i−1]≥0每个营地最多有iii人，我们可以知...

原创 树状数组+二分查询第K大(经典应用)

题目链接按题意每一次查询和最大的p个数的最小字典序中第q个位置的数字；首先我们可以把所有数字的按从大到小进行一级排序，位置按从前往后进行二级排序，那么在排序以后p个数的最大和且最小字典序就是前p个数，那么我只要输出前面按照位置从小到大的第q个数就行了。显然，问题转化后就是求前p个数中的第q大值；树状数组维护数字x是第几大，然后在有单调性的情况下选择二分第q大值就好了。#include&l...

原创 差分约束

差分约束hhh，这几天病毒感染，真的不敢乱溜达，干脆狂写blog算了，hhh一般形式差分约束题一般是给出大量的一些不等式ai−bi≤x→ai≤x+bia_i-b_i\leq x \rightarrow a_i\leq x + b_i ai​−bi​≤x→ai​≤x+bi​由上面这个不等式我们应该可以联想到最短路的不等式dis[u]≤dis[v]+x(u→v)dis[u]\leq di...

原创 迪杰斯特拉堆优化

迪杰斯特拉算法的堆优化性能使得最短路算法时间复杂度再次加快了一个档次变成了n∗log⁡2nn*\log_2 nn∗log2​n，让人更加头秃原理来说原理的话我建议可以讲一下迪杰斯特拉的算法思想，利用贪心，每一次走距离当前点uuu最近的点vvv，那么我们由原点到vvv一定会是最近的，因为uuu一开始就是最近的，那么dis[u]+min(u→v)≤dis[u]+!min(u→v)dis[u]+...

原创 codefores 817B

题目链接题意：给定一个数列 a 包含 n 个正整数。现在可怜想要统计三元组 (i,  j,  k) (i < j < k)的个数，满足 ai·aj·ak 是整个数列所有三元组中最小的。题解：显然就是简单的排个序然后计算一下前3个数字的个数就好了，具体操作见代码！代码#include<stdio.h>//#include<windows.h>#in...

原创 codeforces 466c

题目链接题意给定一个序列，问有多少种方案可以将此序列分割成3个序列元素和完全相同的子序列。（子序列不能为空）。即问有多少个点对（i,j）满足a[1]+…+a[i-1]=a[i]+a[i+1]+…+a[j]=a[j+1]+a[j+2]+…+a[n]题解已知如果能分成三段相等的数据，那么把整个数组相加的和（sum值）一定可以被3整除，不能整除就是0个。每当遇到第i个元素之前的所有数字之和为s...

原创 图论存图

存图方式今日份复习一下大概已知的存图方式：矩阵存图：很容易理解的一种存图方式，开一个矩阵，在其中假设一个数字（inf）为无穷大,，也就是不连通，那么不是这个数字的全是连通的，例如：a[i][j]=1；可以看成从点i到点j距离或者代价为1！优点：容易理解，操作方便；缺点：空间浪费率过高，不能表示很大的比如2e5的点！点的大小在1000以内可以使用前向星没学过的点这个优点：一个非常重...

原创 poj 2912

并查集+扩展域好题题意有点模糊，意思是这里有三种人和一个判官在猜拳，每一种人只能出一种手势，这里面有一个判官可以随意改变自己的手势！给定m个回合判断，问判官是谁。能知道就输出最快能在第几回合清楚，如果多了就输出“Can not determine”，或者不存在就是“Impossible”。分析：数据很小，可以暴力枚举每一个人，如果n个人里面除开这个人以外，其余所有人都不冲突，则这个人就可能...

原创 manacher(马拉车算法)

manacher用法O(n)求最长回文子串对于回文串有两种情况：对于中间一个元素对称；对于中间一个空格对称；为了两种情况的适应性，我们可以把他们总结归纳以下，对于第二种的我们直接加入一个不存在的元素表示空格，对于第一种显然是没有影响的，而且可以发现，这时候回文串的长度等于当前元素能扩展到的最长距离，因为对于i的左边一共有len/2个元素，右边一共有len/2个空格，即证；思想利用回文...

原创 图论选手的自闭之路

1.单源最短路：1.1 迪杰斯特拉：1.2 贝尔曼佛德：1.3 分层图：2. 判环：2.1 floyd算法：2.2 dfs：3.欧拉图：3.1 无向图：对于一个无向图来说，当且仅当所有点的度为偶数时该图为欧拉回路，当有两个点度为奇数时，该图存在欧拉路径3.2 有向图：在一个图中，除了两个端点以外其余顶点的出度都等于入度，那么存在欧拉路径，如果全部点的出度都等于入度，则该...

原创 最小生成树cf1245D

传送门简单讲解一下题意：在一个二维坐标上有n个城市(坐标表示)，每个城市可以选择自己供电花费b[i]，也可以选择来自其他城市的电花费c，求最小花销，每一个供电的城市序号以及连接路径！赛时脑子：我会了，快写，赶紧的！手：不，你还不会，需要冷静。。。一个比较好的思路：我们可以构建一个虚点0，每一个直接与0相连的城市都是自己供电的，其他的都是通过连接来得到电。克鲁斯卡尔算法注意合并两个点的时...

原创 cf596D(质数分解)

传送门说下题意，给1e5个数和一个K，求里面两个数之积为x的k次方有多少组，x为任意值。解题思路：首先根据算术基本定理对于，对每一个数进行质因数分解a=p1e1+p2e2+…+pnen，因为两个数之积为一个值的k次方，那么这两个数的每一个质因数的次方之和一定为k的倍数。然后计算贡献，每一个值对于后面的贡献是每一个质因数的次数对k取模后的积，同时计算这个值还缺多少个数字变成k次方，加上这个值在前...

原创 扩展欧几里得入门

青蛙的恋爱经典扩欧板子题，稍微注意一点就可以A了，之所以要写呢，是因为发现这题在洛谷上的数据比较强，让人自闭。方程大家应该都找的到吧，我也就不提了，直接说坑点，就是如果gcd之中如果有一个参数为负数的话，最后的结果符号会出现问题，不确定是否为正还是负，这一题里面很明显的出现了，如果（m-n）为负数的话，那么gcd可能为负数，那么**ans= (ans % f + f) % f;（f=l/gcd...

原创 2019徐州icpc网络赛A题

请看题面一个板子题，不过说起来我貌似连板子都不会。。。菜啊简单说下题意：给t个数对（a，b）求一个最小的n符合n%a=b；一开始没看过扩欧，罪过，搞了半天；讲下思路吧：a1x1+b1=a2x2+b2<==>a1x1-a2x2=b2-b1转化以后很明显的线性同余方程；解方程就不说了，直接得到x的通式为x=x0+a2/gcd；(x0为最小正整数解)这时n=a1(x0+a2...

原创 简单的容斥原理

容斥原理：奇加偶减hdu2588本以为只要求一下GCD就行了。。。结果果然是我天真！由题可知两个数里面有一个已经被固定了，那么他的gcd一定是n的一个因子，所以我们可以把n的所有因子全部找出来，排序以后直接找大于m的所有因子，由于可能出现因子之间有倍数关系，因此再去重，然后直接使用容斥原理就行了！！容斥原理：使用一个二进制数字1表示使用过，0表示不用，然后枚举每一位是否为1直接可得每种方案...

原创 无向图最小环——Floyd解法

题目链接简单讲一下题意：给n(<=1e5)个数，数字范围(1e18)任意两个数字之间如果经过与运算以后不为0则可以判为两点相连，给出最小环大小，如果没有则输出-1；第一步将1e5变小，可以发现只要二进制的任意一位上面出现过3个乃至以上的1则只需输出3，大致算一下那么只有100个数字左右了可以跑Floyd了！！由Floyd算法可以知道，在它运行到以k做中间节点时，前面经过所有点都比k小...

原创 2019杭电多校第二场6009（树状数组）

题面在这里题意是在前m个数中删去m-1中的一些数字总和小于给定值，问最少删除多少个数字。很容易想到每一次删除前m-1个数中最大的数字直到之和小于给定值就是答案，这个方法虽然可行但是明显是个暴力复杂度太高，那么换个思路每一次加上前面的最小值，这里还是比较大，那么离散化以后使用树状数组呢？考虑到树状数组的单调性，每一次二分一个数字n去树状数组求和表示前n小的数字之和直到和为给定值的小于等于的第一个...

原创 第k大值 HDU2639

背包变式——能装的第K大值hdu2639先吐槽坑点：n大于题目所讲100！！！说下题意，给一个背包和一些物体的体积与价值求所能放的第K大价值。很明显的是一个01背包变式，至于如何求一个第K大价值就是这一题的最大难点了。首先讲一下第K大值的核心思想：第K大值必然出现在每一次的最大的前K个数字之间打一个比方也就是让你找全国第三大富翁怎么找？一个一个的？当然是把每一个省前三的富翁全部找出来比较一...

原创 二分实数总结

总结二分这个算法就不说了，直接上一个题目吧，二分实数看算法竞赛指南上的题解勉强看懂，这题主要是让我求一个一个数组之中大于L长度的最大平均数。书上大概都有，我就简单说下单调性吧。任意数列减去自己的平均数后总和为0如果一个数字小于平均值的话，减去这个数字后总和将会大于0，而如果大于平均值的话总和将会变成一个负数，由此可以看出平均值的单调性。#include<stdio.h>#inc...

原创 素数判定 欧拉筛

欧拉筛欧拉筛是一种线性筛法，能将1~n以内所有质数全部筛出来，是已知比埃氏筛法快的筛选1到n以内质数的办法！欧拉筛基于算术基本定理：任意大于1的数字都能唯一分解为有限个质数的乘积也可以解读为任意一个大于1的数字至少可以分为一个质数乘以一个合数而欧拉筛正是利用了这一点，每一次标记当前值x与1到x的最小质因子之间的所有质数之积也就是合数，这样标记每一个合数都只会标记一次，对时间复杂度有极大的优化。...

原创 IncDec序列 差分数组

差分数组实例题目链接请点击此处大致讲一下题意，给一个数组，让我用最少的次数将这个数组重置为相同的值，也就是数组内所有数字大小必须相同，而每一次操作仅允许对一个区间进行+1或者-1的操作。区间修改，而且是修改相同的值，就让我想到了差分数组，差分数组不熟悉的请点击让每一个值都相同其实就是让差分数组从第二个开始都为0！当从第二个开始都为0时那么整个数组都会变成第一个值的大小。那么首先就先将这一题...

原创 洛谷P4568 分层图最短路

分层图最短路入门洛谷P4568 分层图板子首先讲一下题意吧，首先给n个点，m条边，然后再给两个点p,q,要求从p点走到q点时在最多省k条边的情况下所要走的最短的路程。分析很明显就是最短路的一种变式，但是由于有k条边可以改成路程为0，就成了这一题的难点。本蒟蒻一开始看了后不会，看了n位大佬blog后有所感悟了。我的想法就是使用dp思想，把dis数组开成二维dis[i][j]，第一维表示...

原创 差分数组

纯属个人理解，如有错误，欢迎各位大佬斧正

转载 链式前向星入门

第一次写blog，如有不足，请指正，谢谢。