只玩三国的程序猿-CSDN博客

原创 IDEA用maven创建springMVC项目和配置（XML配置和Java配置）

这段时间在学习javaweb的一些知识，然后接触到了springmvc框架。框架的创建和配置一直是新手入门的一个难题，所以我就写一下我的配置过程，以供参考，另外因为spring4的新特性可以用java来配置，网上相关资料较少，所以我参考了很多博文后，把xml和java两种配置方式都试了一下。工具准备：IDEA2016.3 Java jdk 1.8 1、DEA创建项目新建一个

2017-03-02 14:12:32 39329 31

原创 VSCODE codeforces 插件

VSCODE codeforces 插件选择插件CodePalCodeforces BotCodeforeces （没错，有个插件就叫这个名字）Catalyst、ICIE、acmX最后选择插件目前vscode已经有一些帮助codeforces写题的插件，但是由于本来这方面就是比较小众的，所以更新动力不强，bug挺多，大部分都不是很好用。截图里面的这些插件都是相关的，但是我挨个试了一下，大部分都不是很好用，我就说一下几个能用的。CodePal这个是首选，再几个电脑上都测试过，可以用，他的主要功

2021-06-08 17:50:19 5894 3

原创 'utf-8' codec can't decode byte 0xb5 in position : invalid start byte

看一下文件的编码就可以了，然后选择对应的编码

2019-11-26 09:49:17 9275 3

原创 thinkPHP5 session和cache的区别问题

之前用thinkPHP5开发接口的时候，碰到这么一个问题，用浏览器测试的api再用postman或者是脚本去访问就会出现重新登录的问题，后来看了一下session里面的内容，发现脚本和postman没有办法访问到对应的session，这样就很难受，最后经过大佬指点，才知道了thinkPHP5里面的session就是给浏览器用的，非浏览器的方式是没有办法访问到那个session的，只能用cache的方

2017-06-11 14:11:26 4167

原创 HDU 5732 Subway(树同构)

题意：给你两个树，让你判断是否同构。分析：这个题目还是挺好的，主要考验了Hash的技术，如何能够把两颗树Hash出来是难点之一，题解给出了一个办法，就是把每个子树的Hash值乘以一个小质数累乘然后模一个大质数，但是只要是这种hash肯定会出现重复的情况，所以我们需要对重复的hash值进行多次检验，另外，要把这个树变成有根树，可以选择中心或者是重心，这二者是不同的，但是都是可以做的。具体

2017-02-02 21:48:16 663

原创 HDU 5412 CRB and Queries(整体二分 | CDQ分治)

2017-02-02 21:47:25 619

原创 HDU 5313 Bipartite Graph(bitset + DP)

题意：给你一个二分图，问你最多可以添加多少条边，让这个图变成完全二分图。分析：可以知道的是，完全二分图的边数就是两边的点数相乘，为了让这个值能够最大，我们要让两边的点数尽量相等，所以先预先处理处每一个小二分图的两边的个数，然后dp一下就好了，但是n^2的dp肯定是过不了的，所以我们用bitset来优化一下就好了。bitset的每一位存的是前i个二分图，最多可以让两边的点往n/2靠近的值

2017-02-02 21:46:34 421

原创 HDU 5036 Explosion (bitset + DP)

题意：给你一张图，每个图都可以到达另一个节点，当然你也可以选择炸开者结点来进入这个图，问你炸开节点的期望次数是多少。分析：因为每个点是独立的，我们考虑每一个点的单独的期望，到这个点要炸的次数其实就是到这个点的节点数的倒数，所以我们需要把可以到达每个点的点数处理出来，直接求的话，用floyd来求闭包，复杂度不够，所以用bitset来优化。代码：//// Created by CQ

2017-02-02 21:46:02 601

原创 Codeforces 701C They Are Everywhere (滑动窗口)

2017-02-02 21:45:18 399

原创 Codeforces 700B Connecting Universities(树的中心)

题意：给你树上的一些点，问你如何把他们两两分组，是的每组的距离总和最大。分析：很显然的就是，如果能够让这些点都经过最远的点，甚至是根的话，那么答案肯定是足够大的，仔细想想之后可以联想到树的重心，但是这个重心不是整个的重心，而是根据那选定的点的重心，找到之后一次dfs就好了。代码：//// Created by CQU_CST_WuErli// Copyright (c) 2

2017-02-02 21:44:44 475

原创 Codeforces 700A As Fast As Possible(机智)

2017-02-02 21:43:35 423

原创 Codeforces 698B Fix a tree （模拟）

题意：给你一个在某一个特定根下，书中每一个节点的父亲，问你如何修改，能够使得形成一棵树。分析：主要还是怎么机智的实现这些东西，因为是在某一个根的情况下，所以对于所有的p[i] == i的点，都可以算是不符合要求的点（出了根节点），随意我们标记出所有的这种点，然后选择其中一个为根，其他的全部链接过来即可。比赛的时候没想到这个，写的太复杂，还没过样例。。。结果集训队大神几十行就搞定了（ra

2017-02-02 21:43:00 368

原创 Codeforces 698A Vacations(线性DP)

2017-02-02 21:41:57 452

原创 Codeforces 696C PLEASE(数论)

题意：给你三个杯子，一开始中间的杯子里有钥匙，每一次把中间的杯子和左右两边中的一个杯子交换，每次选择是等概率的，问你n次操作之后，钥匙在中间杯子的概率是多少，并且用分数形式表示出来。解法：这题有两个需要处理的，一个就是因为n会很大，所以给的n的各个因子，不过这个没啥困难的，价格矩阵快速幂就能算，另外dp的方程很好推，就是dp[i] = (1 - dp[i - 1]) * 0.5。然后他

2017-02-02 21:41:16 527

原创 Codeforces 696B Puzzles(期望+树形dp)

题意：对树做dfs的时候，每一个点都有一个时间戳，问你如果每次选择子节点都是等概率的情况下，每个点的期望时间戳是多少。解法：一看就是典型的树形dp求期望的题目，我们考虑的是其他的点对某一个点的贡献度，最后的出的转移方程就是dp[v] = dp[u] + 1 + (sz[u] - sz[v] - 1]) * 0.5。得到这个方程有两个方法，第一种很好理解，首先子节点最起码比父节点

2017-02-02 21:40:29 457

原创 Codeforces 696A Lorenzo Von Matterhorn(LCA)

题意：给你一棵树，其实就是按照线段树的方法建的树，有两种操作，将u到v的路径上的边权全部加w，然后询问从u到v的路径上的边权和。解法：因为节点的编号很大，所以不能直接建树，但是可以知道，这棵树的最大深度也就是62层，所以我们可以用map来保存边权，或者把边权放在点权上，就像树链剖分那样，每次操作时就可以暴力的向上更新，因为最多1000次操作，哪怕每次都是最深的节点，也最多向上63次，总

2017-02-02 21:39:14 419

原创 Codeforces 687D Dividing Kingdom II (图论+并查集)

题意：给你一张图，其中边按照序号排好，每次给你一个 l和r，让你用给定区间范围内的边生成一张图，然后把这个图中的点分成两边，在所有使用的边中，使得两边端点在同一个部分的边的最大值最小。解法：我们可以很快的看出，如果是二分图的话，那么所有的边的两个端点都不会再同一个部分，那么也就是说如果生成的图不是二分图，那么才会存在这样的边，于是问题就转变成了如何找到所有的奇环的最小边的最大值。这里可

2017-02-02 21:38:21 541

原创 Codeforces 685E Travelling Through the Snow Queen's Kingdom(DP)

题意：给你一张图，每一条边都有一个编号i，经过每条边的时间为1，如果当你到达这条边的时间小于i的话，就必须等到i才能走出这条边，如果大于i，就走不出去了，也就是不通了。然后给你一些询问l, r, s, t，问你是否可以从s出发，时间为l，在r时间之前到达s。解法：我们假设动态规划的状态为dp[s][t]表示从s到t要花费的最少时间，我们考虑倒叙添加边，这样的话每当新添加一条边(u,v)

2017-02-02 21:37:19 614

原创 Codeforces 685D Kay and Eternity (扫描线)

题意：给你nn个点，再给你正方形边长，问你在整个无限大的网格中，包含有1,2,3..n1,2,3..n个点的正方形有多少个解法：因为整个网格是无限大的，而且点的坐标范围也很大，所以需要离散化，既然用到了离散化，而且又是这种覆盖的问题，就可以考虑扫面线，我们用cnt[y]来辨识y这个坐标被覆盖了多少次，因为确定一个正方形只需要确定左下的点就好了，所以只需要统计左下被覆盖多少次。我们把每一

2017-02-02 21:35:57 756

原创 Codeforces 685B Kay and Snowflake(树的重心)

题意：给你一棵树，问你每一颗子树的重心是哪一个节点。解法：树的重心有一个性质，当把两棵树合并时，新的树的重心肯定在两颗树重心之间的路径上，所以我们只需要看当前节点到他重儿子重心之间的路径中是否有满足条件的点就可以了，（重儿子请去看树链剖分）因为重儿子是最大的，不在这个路径上找，会让重儿子单独出来，肯定不满足条件。//// Created by CQU_CST_WuErli//

2017-02-02 21:33:43 597

原创 Codeforces 679C Bear and Square Grid(滑动窗口)

题意：给定一个网格图，其中有的有的是可以走的点，有的是障碍，定义连通块和无向图中连通块是一样的。如果把一个k*k大小的区域内的点都变成联通块，那么这个网格图中最大的连通块是多大解法：这个如果用暴力枚举的话，是O(N4)O(N^4)的，但是我们可以用滑动窗口来优化，我们首先把每一个连通块的大小求出来，然后枚举y，先把窗口内的点全部变为联通，并且从他所在的连通块分离出去，那么我们只需要检测

2017-02-02 21:32:19 415

原创 Codeforces 677E Vanya and Balloons(暴力+转换) category:

题意：给定一个矩阵，让你其中有1,2,3,0，让你在里面寻找一个十字，是的这个十字所包含的数字的乘积最大。解法：这个完全可以预处理处八个方向的前缀，然后暴力枚举中心即可，要注意的是，十字的四条边长是一样的，另外因为数字太大，所以用log把乘变成加，就可以比较大小了，不然直接模是无法比大小的。代码略长。。。//// Created by CQU_CST_WuErli// Co

2017-01-18 16:19:40 476

原创 Codeforces 677D Vanya and Treasure(DP+分治) category:

题意：一个图上有一些宝箱，每一个级别的箱子里有搞一个级别箱子的钥匙，而最高级别的里面有宝藏，每次从(1,1)出发，问你拿到宝藏所要走的最短距离是多少。解法：这题如果直接来暴力更新的话，复杂度要炸，但是我们可以发现，每一次更新的时候，之和当前级别和前一个级别有关，所以如果两个级别的数量加起来大于m*n的话，我们就直接bfs就好了，这样可以把复杂度降到mnsqrt(nm)。话说这个方法我以

2017-01-18 16:17:53 609

原创 Codeforces 677C Vanya and Label(二进制)

2017-01-18 16:15:44 331

原创 Codeforces 676E The Last Fight Between Human and AI (数论)

题意：给定一个参数不确定的多项式，电脑和人类轮流确定系数的大小，可以使任意实数，使得这个多项式能够除以x-k，判断如果人类选择最优的方法，是否可以胜利。解法：这题要分类讨论，如果k=0的话，只要a[0]=0，那么就可以整除，所以我么你只需要判断a[0]是否已经被赋值且是否为0，这个好判断。然后是k不等于0时，那么就有两种情况，一种是所有的系数都被赋值了，判断k是否是这个多项式的

2017-01-18 16:12:16 337

原创 Codeforces 676D Theseus and labyrinth(最短路)

题意：给定一个迷宫，起点和终点，每一个可以走的格子上都有不同的门的情况，每次都可以选择到达周围符合条件的格子或者是让所有格子的门顺时针旋转一下，问你从起点到重点的最短距离。解法：因为每次都是转90度，所以对于每个格子来说，都有四个状态，所以建立一个分层图，每层都代表个点的一种状态，然后直接BFS即可。代码：//// Created by CQU_CST_WuErli// C

2017-01-18 16:08:10 458

原创 Codeforces 671B Robin Hood (二分搜索)

题意：给定一个数列，每次让最大值-1，最小值+1,问你k次操作之后，数列中的最大值和最小值的差值是多少。解法：不管结果是怎样的，我们可以确定的是，最后的最大值和最小值肯定是固定的，但是我们不能确定到底是多少，所以我们需要尝试，而且随着操作次数的增加，最大值会越来越小，最小值会越来越大，所以我们采用二分搜索来找最后的值。值得注意的是，寻找最大值和最小值的边界是不一样的，具体在代码中。代

2017-01-18 16:05:26 476

原创 Codeforces 689E Mike and Geometry Problem（组合数学）

题意：给你n个x轴上的线段，在其中选k个线段，对于所有的可能方案，总共有多少点次被覆盖，也就是说同一个点如果被不同的方案所覆盖还是要被算在答案里的。这个题首先我们要把线段的端点离散化，用map就可以，对于某一段，我们可以算出被多少条线段覆盖，假设这个值为p，如果这一段被大于等于k个线段覆盖，那么ans+=Ckp∗numans +=C_{p}^{k} * num，num是这一段点的个数。

2016-07-08 17:28:52 584

原创 Codeforces 689D Friends and Subsequences（二分+RMQ）

题意：给你两个数列a和b，问你其中有多少对l和r使得maxri=lai=minri=lbimax_{i=l}^{r}a_{i} = min_{i=l}^{r}b_{i}。这个题有一个很正宗要的性质：假设我们固定l，那么对于l到r这个区间内的maxri=lai−minri=lbi≤maxr+1i=lai−minr+1i=lbimax_{i=l}^{r}a_{i} - min_{i=l}^

2016-07-08 17:18:58 513

原创 Codeforces 678C Mike and Chocolate Thieves（二分）

2016-07-08 17:06:03 673

原创 Codeforces 678B Remainders Game（数论）

题意：给你一个k，再给你一个数组c，让你判断对于任意的非负整数x，知道了xmodcifori:=1tonx mod c_{i} \quad for\quad i := 1\quad to \quad n的值，问你是否能够知道xmodkxmodk的值。作为一个数学渣，完全没有想法。其实我们可以从反面来考虑这个问题。假设有两个x1和x2是的上述的条件不成立，依旧是说对于每一个数字

2016-07-08 16:59:51 712

原创 Codeforces 689 C The Values You Can Make（dp）

题意: 给你一些硬币，让你选出一个子集的总价值和为k，然后对于一个选出的子集，除了可以组成k以外，还可以在选出的子集中选出一些其他的价值。问你所有的选出的子集一共可以得到多少种价值。对于这个，因为tag是动态规划，所以就往上面思考，但是找不到一个一个可行的状态。看过题解才明白，一个很机智的状态。 dp[i][j][k]dp[i][j][k]表示前ii个硬币组成了价值为jj的一个子集

2016-07-08 16:11:41 867

原创 HDU 1435 Stable Match(稳定婚姻问题|盖尔沙普利算法)

2016-03-09 23:33:18 1436

原创 HDU 3031 ToBe Or Not To Be（模拟）

题意：给你一堆牌，再给你5种操作牌，两个人轮流抓操作牌，并且按照操作来执行，最后谁手里的牌多谁就赢。明明是左偏树的题目，但是我用priority_queue水过去了。。。代码：#include <queue>#include <math.h>#include <stdio.h>#include <string.h>#include <algorithm>#include <

2016-03-09 23:31:27 965

原创 HDU 4085 Peach Blossom Spring（斯坦纳树+dp）

题意：给你一些点和边，让你选择一下边，是的前k个点和后k个点连通且代价最小，但是除了这2k个点，好友一些其他的点。一开始我以为是MST，后来发现不行，然后就是网络流乱搞，然并卵，就是因为有其他的点可用可不用。后来一看才知道原来是斯坦纳树。。。。如此高级的东西。斯坦纳树的定义：斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点

2016-03-08 23:06:08 1012

原创 HDU 3062 Party（2-SAT入门+学习）

2016-03-07 23:20:03 447

原创 HDU 1575 Tr A（矩阵快速幂）

2016-03-05 00:23:29 413

原创 POJ 2823 Sliding Window（单调队列||线段树）

题意：让你不停的查询区间长度为k的最小值和最大值一开始用set模拟，发现常熟太大，T了，然后开始学单调队列，看了一会儿还是好理解的，所以就写了，发现G++会T，只能交C++，后来发现有人线段树也能过，于是就写了一发，还真行，只不过就是吧查询的答案用全局变量来存，减少return的时间消耗，还是只能交C++。单调队列：//// Created by CQU_CST_WuE

2016-03-05 00:21:32 406

原创 HDU 1878 欧拉回路

题意：欧拉回路的判断条件，一、无向图每个顶点的度数都是偶数，则存在欧拉回路。二、有向图（所有边都是单向的）每个节顶点的入度都等于出度，则存在欧拉回路。以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。三、混合图（有的边是单向的，有的边是无向的。常被用于比喻城市里的交通网络，有的路是单行道，有的路是双行道。）找到一个

2016-03-05 00:16:54 457

原创 UVA 11324 The Largest Clique（SCC+dp）

2016-03-05 00:14:14 401

SpringMVC两种配置的Demo

我的tomcat无法连接到Oracle数据库