- 博客(166)
- 收藏
- 关注
RSS订阅原创 Spring Security登录认证【前后端分离】
1. 导入依赖<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-security</artifactId></dependency><dependency> <groupId>org.springframework.security</groupId
2020-08-31 11:42:22
4476
5
原创 JAVA网络编程 -UDP篇（简单实现网络聊天）
通过UDP实现网络聊天多线程实现UDP网络聊天1. 编写UDP发送线程UdpSendThreadimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.net.*;public class UdpSendTread implements Runnable{ DatagramSocket datagramSocket = null;
2020-08-23 21:44:38
409
原创 TCP发送实现
网络编程 TCP实现TCP和UDP区别：TCP相当于打电话，双方需要同时在线连接，UDP相当于发邮件，一方发送，接收方不要求在线，在线即可接收发送方发送的消息1. 编写发送方实体类 TcpSender（客户端）import java.io.IOException;import java.io.OutputStream;import java.net.InetAddress;import java.net.Socket;public class TcpSender { public
2020-08-18 16:52:19
348
原创 Spring JPA环境搭建
导入依赖spring核心依赖<!-- https://mvnrepository.com/artifact/org.springframework/spring-beans --><dependency> <groupId>org.springframework</groupId> <artifactId>spring-beans</artifactId> <version>5.2.8.RELE
2020-08-17 18:00:05
166
原创 Codeforces Round #550 (Div. 3) E 【数学】
题目链接：http://codeforces.com/contest/1144把字符串当作26进制数，通过 (L+R)/2 ，取中间值再转成字符串就是答案。因为字符串的长度很大，算出来的数会溢出，所以需要一些技巧。假设有两个字符串 abc, efg那么就有 通过不断的 % 26得到每个位的数字。我们可以发现的是，我们其实只需要对括号内的数字 %26 就能得出结果了。...
2019-04-01 22:59:47
1581
原创 POJ 1062 昂贵的聘礼 【最短路】
题目链接：http://poj.org/problem?id=1062假设一个起点0，根据题目给出的权值构图，答案就是从0到1之间的最短路。这里要注意的是这个等级限制的问题。首先等级限制不是相邻点之间的限制，而是整体路径的。等级的限制可以通过假设一个点为最低点求最短路，我假设某个点是最短路中等级最低的，然后求最短路。每枚举一个点就求一次最短路，取最小的值。因为你枚举的点已经是等...
2019-04-01 17:07:54
104
原创 POJ - 2502 Subway 【最短路】
题目链接：http://poj.org/problem?id=2502所有点用走路的速度连接，相邻站点用地铁速度连接，跑最短路。注意输出用 %.0f，取其他精度会WA#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include &...
2019-04-01 10:51:12
185
原创 HDU Taotao Picks Apples 【二分】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6406先离线记录从左到右的单调递增数列，记为h[]下面分几种情况：修改的点x不在h里面：1，值减少，答案不变；2，值增加，二分h数组，答案减去点x右端比修改值小或者等于的个数。修改的点x在h里面：1，值减少；(1) x的值小于或者等于左端的值，答案加上x和x右端之间的最...
2019-03-30 18:26:37
86
原创 codeforces 1010D 【二分+交互】
题目链接：http://codeforces.com/problemset/problem/1011/D题目让你在1到m之间猜一个数x，你每猜一个数，会得到三种回复，-1(x < y) ，0(x == y), 1 (x > y)。而且每次回答都不一定是正确的回答，会根据一个序列p，0为错误回答，1为正确回答，的规律回复你。首先需要确定序列p，这里的方法是问n次数字1来...
2019-03-27 13:41:11
182
原创 POJ 2018 【二分答案+dp求最大区间段】
题目链接：http://poj.org/problem?id=2018从0到2000000(2000*1000) 枚举平均值，让数组统一减去枚举的平均值，如果存在区间和大于等于0的，就说明答案是成立的。关键是如果求最大的区间和。假设不限制区间的长度，求某一个数组的最大区间和应该怎么求？如果dp[i]表示的是某左界到右界 i 的最大区间和，那么dp[i+1] 应该如果求？因为要求...
2019-03-25 21:08:19
251
原创 HDU - 2546 饭卡 【01背包+排序】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546题目问的是最小容量，而且容量可能会负数，我们可以换个角度解决问题，比如题目允许的容量是 5~m，我们可以把容量设置成m~2*m-5，这样做的好处是能把可能为负数的结果变成正数，那么就可以用01背包求解问题(dp[容量])，求的是最大值。另外需要给价格排序，比如下面这个两个数据，自己可以...
2019-03-21 14:06:33
248
原创 Codeforces Round #546 (Div. 2) D. Nastya Is Buying Lunch 【思维】
题目链接：http://codeforces.com/contest/1136/problem/D让所有能和最后一个点交换的点尽可能多且连续的排列在尾部，才能让最后一个点尽可能的排在前面，这个应该比较好理解。这里我们假想存在这么一个队列P，最初的时候，队列P的个数为0，那么就有下面这种假想的情况存在。a1, a2, a3, a4, [P], a5首先存在这么一个判断，a4是否能和a...
2019-03-18 20:29:24
107
原创 HDU - 2888 Check Corners 【RMQ（二维线段树 / ST）】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2888第一种方法是二维线段树，注意的地方在代码注释的部分。第二种方法是 ST算法，在后面。#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#i...
2019-03-08 21:10:04
122
原创 Codeforces Round #538 (Div. 2) C. Trailing Loves (or L'oeufs?) 【数论】
题目链接：http://codeforces.com/contest/1114/problem/C一个十进制数的二进制展开式中，次幂最小的那个数就是这个二进制数中末尾0的个数，所以题目的问题可以改成求某进制数的展开式中最小的那个次幂，也就是 n! % (b^r) == 0，满足这个式子的情况下，r能取的最大值。这道题有一个结论非常重要，如果你不知道的话，是做不出来的。假设n！= p1...
2019-03-07 12:21:59
160
原创 HDU - 3486 Interviewe 【ST表】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3486ST表模板题。这里把题目的问题改一下。给N个面试的人分组，每一个组安排一个面试官，每一组的人数要相同，每一组只选价值最高的，每一组价值最高的加起来要大于K，让你求出至少需要多少组才能满足题目的要求(也就是要求面试官尽可能的少)，这里要注意，假设我给N个面试的人分了5组，如果前几组价值最...
2019-03-06 13:53:23
209
原创 UVA - 11478 Halum 【二分答案+spfa】
题目链接：https://cn.vjudge.net/problem/UVA-11478这道题有两点收获。1，stack的spfa的确要比queue的spfa快很多，如果发现queue的spfa超时的话，可以试试用stack。2，之前的spfa模板给记错了，我以为松弛的次数是边的数目，今天才发现松弛的次数应该是点的数目，在搞错这个的情况下，我用stack就AC了，之前一直T，我是和别人...
2019-03-02 16:34:10
242
原创 POJ - 3159 Candies 【向前星+dij】
题目链接：http://poj.org/problem?id=3159差分约束问题，下面把要注意的地方讲下。首先这道题是卡队列的，如果你用的是spfa，要把queue换成stack才能过，至于为什么就不是很清楚了（可能是因为题目的数据是稠密图，每次队列的插入和删除开销大，和下面要用向前星一样，vector比较适合用来存储稀疏图的边，而稠密图最好用向前星），要么就是dij的堆优化。如果你...
2019-03-01 14:10:14
199
1
原创 POJ - 2983 Is the Information Reliable 【spfa解决差分约束问题】
题目链接：http://poj.org/problem?id=2983原理在上篇博客已经讲过了，这里把要注意的讲下。1，因为差分约束问题都是不等式约束，以不等式为基础给题目建图，但是如果题目给出的约束条件是 d[u] - d[v] == w，怎么处理？w <= d[u] - d[v] <=w，这样就能表示d[u] - d[v] == w这个条件，一条正向正权值，一条反向负...
2019-02-28 15:17:11
99
原创 POJ - 2019 Cornfields 【二维线段树】
题目链接：https://vjudge.net/problem/POJ-2019我写的这个二维线段树没什么技巧，就是直接开一个 node[cur][cure]，cur代表的是x轴的一维线段树，cure代表的是y轴的一维线段树。初始化：先从x轴开始做线段树的操作，当x轴到达叶节点时，再对y轴做线段树的操作，x轴返回到父节点时，一样要对y轴从1到N重头做一次线段树的操作，这是初始化的过程，...
2019-02-27 20:53:46
148
原创 Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) Toy Train 【贪心】
题目链接：http://codeforces.com/contest/1130/problem/D2贪心的策略还算比较容易找的，但是会比较难写。贪心策略是每次都取离当前车站最远的一颗糖，这样能多经过几个车站多取几颗糖，省时间。但是写起来特别麻烦。但是如果你能把这道题的问题写成一个公式，那么会简单很多。假设5个车站，只有一个车站有3颗糖，并且这3颗糖都不是当前车站的。这个时候我们...
2019-02-26 18:46:14
261
原创 POJ - 1201 Intervals 【spfa解决差分约束问题】
题目链接：http://poj.org/problem?id=1201题目的意思是一个序列在数字上满足约束条件，值在a和b之间的数至少出现c个不同的数，输出满足条件的最短长度。可以先参考下这个博客：https://blog.csdn.net/godleaf/article/details/87907527首先要注意的是给出的a和b中，a要-1，为什么？因为 [ a, a ] 可以出...
2019-02-25 22:51:29
95
原创 POJ - 3169 Layout 【spfa解决差分约束问题】
题目链接：http://poj.org/problem?id=3169根据给出的样例，我们能得到下面几个不等式。(d表示离点1的距离)d[2] - d[3] <= 10d[4] - d[2] <= 20d[3] - d[2] >= 3第三个不等式通过移项能得到 d[2] - d[3] <= -3 再来看看spfa的松弛不等式 d[v] > d[...
2019-02-24 21:54:33
263
原创 POJ - 3255 Roadblocks 【次短路】
题目链接：http://poj.org/problem?id=3255如果是求最短路，直接套模板就能AC，但是次短路怎么求。其实仔细分析一下就能知道，如果我每一个路径都保证是最优的走法，那么得到的就是最短路径，但是如果我有一步走错了，后面又继续走最优的走法，那么得到的路径就会比最短路长，当然如果走错两步，总路径也一定比最短路径长，但是只要我走错之后又继续走最优的走法，那么走错两步的情况一定...
2019-02-23 17:41:40
126
原创 Codeforces Round #539 (Div. 2) Sasha and a Bit of Relax 【DP】
题目链接：http://codeforces.com/contest/1113/problem/C这道题的难点不在DP而在等式。这个等式我当时有想到，但是给我自己给推掉了。题目要求的是 a(l) ^ a(l+1)^.... == a(mid+1)^...^a(r) 这种情况的个数有多少。这个等式要结合异或 xor的运算法则才能做。首先是 A^B^C^D == A^B^(...
2019-02-18 17:09:05
101
原创 HDU - 3001 Travelling 【三进制状态压缩+BFS】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3001状压DP也能做，这里用的是BFS从搜索的思路来看，这道题的难点就是状态重复访问的情况比较多，到现在我也没明白会有哪些重复访问的状态。首先题目给出的是10个城市，每个城市都只能被访问两次，所以每一个城市可能访问的次数有0,1,2，三种，所以所有的状态数是3^10，这个数不会很大，而且起点...
2019-02-16 17:16:43
280
原创 HDU - 2102 A计划 【BFS】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2102有两个要注意的地方1，走到传送门是强制传送的。2，如果传送到另一层又是一个传送门，会死循环，直接排除掉这个点。#include <iostream>#include <queue>#include <cstring>#include &l...
2019-02-15 18:08:50
93
1
原创 HDU - 1067 Gap 【BFS+字符串压缩状态】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1067一开始看题目的时候，最苦恼的就是题目存在的状态数太多，空格可能存放的数字有28个，那么可能的状态就有 28！种，这个数目显然很大，所以不知道如何做。但事实上并不用都遍历一遍，虽然我知道，只要四个空格左边的数都是个位数为7的数，那么就可以肯定无解，这样能减少不少耗时，但是我没想到能减这么多。...
2019-02-15 17:05:16
193
原创 ZOJ - 2477 Magic Cube 【迭代加深+模拟】
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2477从接触acm到现在，一直很抵触ZOJ的题目，我做过的很多ZOJ的题目大部分题意都很模糊，阐述不清楚。这道题的难点不在搜索，光看题目的问法都应该知道是用迭代加深，但是真正让人崩溃的是什么地方？首先是立方的展开图，如果没指名哪一面是正面或者背面，对应的...
2019-02-13 19:15:58
343
原创 HDU - 1560 DNA sequence 【迭代加深】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1560关于迭代加深，可以参考这篇博客 https://blog.csdn.net/hzaukotete/article/details/81226556迭代加深是在dfs的基础上，枚举深搜的深度 dep。比如说 我一开始规定 dep == 1，当dfs深搜到深度为 1的时候就回溯，如果dep...
2019-02-12 18:42:06
164
原创 HDU - 3533 Escape 【BFS】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3533需要注意的点：1，人不能去有城堡的地方2，子弹不能穿过城堡，遇到城堡子弹不会继续向前射，即使城堡在途中也不行，比如说子弹从(0, 0) 向 (0, 3)射，如果(0, 1)有城堡，子弹会消失。3，子弹是从时间 t 开始射击的，不是从0开始。思路就是人先走，然后遍历每一个城堡的射...
2019-02-12 14:28:19
120
原创 HDU - 3567 Eight II 【bfs打表+映射+康托展开】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3567这道题比较容易想到的就是双向bfs，在时间上是比较理想的，但是在内存上就比较紧张。网上看到有人用映射的技巧做这题。假设我知道起点是 12345678x这个状态到其他状态的所有路径。对于所有起点是 ********x这个状态到其他状态的所有路径我也能够知道。假设我知道12x34567...
2019-02-11 13:31:31
260
原创 Educational Codeforces Round 59 (Rated for Div. 2) D Compression 【dp】
题目链接：http://codeforces.com/contest/1107/problem/D这道题只要把主要问题找出来就有思路了。题目的矩阵是 n*n的，要想压缩成 n/x *n/x 的矩阵需要满足一个条件，假设x == 2，那么这个矩阵将会被分成4小块矩阵，如果这四个小矩阵每一块要么全是1要么全是0，那这个矩阵就能压缩成n/2 *n/2的矩阵。因为题目给的n比较大，如果暴力求小...
2019-02-10 15:10:47
244
原创 HDU - 1043 Eight 【反向BFS打表】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043因为状态不多，在样例不多的情况下，直接bfs也是能过的（POJ），但是对于样例多的HDU，需要把所有可能的结果都预处理一遍存起来，要的时候直接输出结果，就能快很多。网上很多代码都有用康托展开做空间优化，不用康托展开优化，用一个map存结果，也是能过的，下面写了两个。要注意的是，你bfs...
2019-02-09 17:30:12
220
原创 康托展开原理
康托展开结合组合数学会比较容易理解。假设有 {1， 2， 3} 这三个数，那么全部的排列组合有 6种，按从小到大的顺序有 123, 132，213， 231， 312， 321。而康托展开能以n^2的时间复杂度求出比某个排序组合小的个数。比如说 比 213 小的数有2个，比312小的数有4个。原理：假设有 {1，2， 3， 4} 这4个数，根据组合数学的知识，一共有 4*3*2*1...
2019-02-09 17:13:37
849
原创 POJ - 3279 Fliptile 【枚举+模拟】
题目链接：http://poj.org/problem?id=3279题意：0代表白色，1代表黑色，每翻一个瓷片，上下左右的瓷片会跟着一起翻，要求翻动次数最小并且答案的字典排序最小。答案是一个矩形，代表的意思是对应位置的瓷片翻动几次，如果不存在就输出IMPOSSIBLE。思路：因为翻动一个瓷片会影响四周的瓷片，所以要一层一层的完成翻动，比如说我要把第一层的全部翻成白色，最好的办法是翻动...
2019-01-30 14:09:20
396
原创 UVALive - 5012 Rescue 【二分答案+数学公式】
题目链接：https://vjudge.net/problem/UVALive-5012因为题目的答案有单调递增的特点，所以很容易想到用二分答案来做，难得地方就是check函数要如何写，也就是说，如果给你一个p，要如何在规定的时间范围内判断这个p能否满足题目的要求(摧毁所有的石头)。因为只能向左丢球，所以丢球的顺序肯定是从右向左丢的，比如说最右边的石头要想摧毁的话，你只能站在这个石头上向左...
2019-01-29 17:47:33
189
原创 HDU 3642 Get The Treasury 【线段树+扫描线（相交体积）】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3642题目要求的是覆盖超过2次的总体积。线段相交的长度，面相交的面积，物体相交的体积，这三种类型题使用的线段树方法都是差不多的。唯一不同的就是扫描线的扫描方式，这里求相交体积最重要的部分就是怎么扫才比较合适。网上大部分都是以Z轴，也就是从下到上的顺序扫描的，只要离散化过后，从下到上，从左到右...
2019-01-27 15:05:24
96
原创 HDU - 1255 覆盖的面积 【线段树求相交面积】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1255这题的方法在之前的博客有比较详细的描述，这里把需要注意的重点说一下就行了。https://blog.csdn.net/godleaf/article/details/86608855如果题目只是问覆盖至少一次的话，代码基本上不用变，只需要把ans累加的公式改一下就行了，就是两个相邻的垂...
2019-01-24 15:27:04
194
原创 HDU 1828 Picture 【线段树+离散化+扫描线】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1828题意要注意的是，周长不仅仅包括外周长，还包括内周长。用扫描线从左向右扫一次，计算图形竖直部分的周长，用扫描线从下向上扫一次，计算图像横线部分的周长。我们每次扫到一条边的时候，只取没和之前重叠的部分。类似这种求区间覆盖的问题，可以用线段树来解决，除此之外，我们还需要考虑把覆盖的区间还原回...
2019-01-23 14:58:10
167
原创 HDU - 4553 约会安排 【线段树区间合并】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4553需要3个标记，分别是左区间连续长度，右区间连续长度，中间区间的最大连续长度(最大可以通过更新回溯的过程中，pushup中更新)。题目的难点是如何找合适的连续区间。因为题目要求的是最左边的符合题目要求的区间，所以找区间的时候要先看左区间的连续长度，其次是中间区间的连续长度(因为中间可能会...
2019-01-18 18:51:20
156
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人