AC_Arthur-CSDN博客

原创 Grafana浅探

最好的资料还是官方文档官方文档：http://docs.grafana.org/安装启动以MAC系统为例尽量使用包管理工具，或者搞一个虚拟环境，防止环境乱掉brew updatebrew install grafana// startbrew services start grafana// stopbrew services stop grafana...

2020-04-20 13:29:33 327

原创 thymeleaf模板之href属性

用thymeleaf模板编写前端时， href属性的方法如下：它的写法与th：src一样一般写法为th:href="@{值}"如果是需要从model中取值的话，写法为th:href="@{${model中的name值}}"。有的时候我们不止需要从model中进行取值，还需写字符串与model中的值进行拼接，写法为th:href="@{'字符串'+${model中的nam值}}"例子：...

2018-03-04 15:14:30 7650

原创 manacher算法

ACM退役很久了，不过仍然喜欢解决一些很酷的算法。至此之后，这里将会是一个纯净的算法讨论阵地，和比赛无关，但是希望能将算法的原理和做法讲解明白。很后悔在做ACM的时候没有这么做。博客推荐这个，可以很快了解一下这个算法的做法：点击打开链接那么我还是简单说一下。我们从左往右扫描字符串枚举中点。算法维护了一个最右边的点，这个是当前存在的回文串的最右边能到

2017-09-05 19:37:02 884

原创 CR, LF, CR/LF 回车换行

在文本处理中, CR, LF, CR/LF是不同操作系统上使用的换行符.Dos和windows采用回车+换行CR/LF表示下一行, 而UNIX/Linux采用换行符LF表示下一行，苹果机(MAC OS系统)则采用回车符CR表示下一行.CR用符号’r’表示, 十进制ASCII代码是13, 十六进制代码为0x0D; LF使用’n’符号表示, ASCII代码是10, 十六制为0x0A

2017-05-19 10:30:38 736

原创 Python多线程爬虫

实现了一个简单的多线程爬虫，爬取百度贴吧某个帖子的回帖用户、回帖内容和回帖时间。1. 使用pool.map实现一个简单的多线程效果。2.使用xpath，代替查找正则表达式的方法。# -*-coding:utf-8-*-import reimport timeimport requestsimport jsonimport sysreload(sys)sys.setd

2017-03-20 16:48:40 889

原创 Codeforces Round #404 (Div. 2) 题解

题目链接：点击打开链接这次比赛AC了4个水题，然而我zz了Ｅ题写了个ｂｕｇ调了很久没时间写Ｄ啦。A. Anton and Polyhedrons水题，加一加就行了。B. Anton and Classes排序就行了，我们肯定是在一个区间集合中找一个右端点最小的，在另一个集合里找一个左端点最大的。C. Anton and Fairy Tale我们可以发现，

2017-03-16 05:46:10 1361

原创网页爬虫获取课程信息

Github链接：点击打开链接用Python学习制作一个简单的网页爬虫：1. 安装pycharm是一个非常好用的IDE~，安装地址在：点击打开链接2.学习一些常用的正则表达式符号和方法。3.运用正则表达式，观察网页源代码，并提取想要的信息。4.安装requests插件本来一直顺风顺水，但是用到这个套件时提示我python没有安装，我费劲千辛万苦，终于在命令

2017-03-15 16:58:19 1434

原创 Codeforces Round #396 (Div. 2)D. Mahmoud and a Dictionary（带权并查集）

题目链接：点击打开链接思路：带权并查集水题。带权并查集可以知道在一个集合里的两点间距离。那么这种同义反义关心恰好对应距离的奇偶。附上一图：这就是合并的过程。细节参见代码：#include #include #include #include #include #include #include #include #include #includ

2017-02-09 01:46:48 469

原创 Codeforces Round #395 (Div. 2) 题解

比赛链接：本次比赛解决3题（好水呀QAQ）A. Taymyr is calling you水题暴力代码：#include #include #include #include #include #include #include #include #include #include #include #include #include #inc

2017-02-03 00:48:54 848 1

原创 HackerRank Even Tree（树dp）

题目链接：点击打开链接思路：简单证明了一下，贪心不可行，那么我们考虑树形dp。用d[u]表示以u为根的子树的最优解。 u的儿子v，如果以v为根的子树数目为偶数，那么可以考虑选择断掉u和v的边（决策1），也可以不断，递归下去（决策2）。细节参见代码：#include #include #include #include #include #include

2017-01-26 16:18:29 726

原创 HDU 1007 Quoit Design（分治）

题目链接：点击打开链接思路：经典的分治法，网上讲解很多我就不多说了，这是nlognlogn复杂度，大多数情况是够用的。。优化了一下排序函数，跑了780ms细节参见代码：#include #include #include #include #include #include #include #include #include #include #inc

2017-01-17 22:23:37 497

原创 BNUOJ 27935 我爱背单词（FFT）

题目链接：点击打开链接思路：该题暴力当然可以过，如果数据量加大，我们还有一种nlogn的算法：FFT仔细观察这个复习单词量的累加方式可以发现，这是一个卷积，可以用FFT加速算法。细节参见代码：#include #include #include #include #include #include #include #include #includ

2017-01-12 23:16:15 959

原创 Codeforces Good Bye 2016（部分题解）

本次比赛一共AC了前4题...A. New Year and Hurry水题。#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #incl

2016-12-31 19:29:48 881

原创 Codeforces Round #389 Technocup 2017 E. Santa Claus and Tangerines（二分+DP）

题目链接：点击打开链接思路：我们二分答案，那么这就变成了一个二分求下界的问题了。关于判定我采用了一种记忆化搜索的递归方式，简单证明了一下应该可以达到log的复杂度。细节参见代码：#include #include #include #include #include #include #include #include #include #include

2016-12-25 21:07:07 666

原创玲珑杯 1074 - Pick Up Coins（区间DP）

题目链接：点击打开链接思路：用d[l][r]表示这个区间的最大值。那么我们枚举区间的某个数，表示这个数是区间内最后一个选的数。所以他的临近元素是a[l-1]和a[r+1]。14年北京赛区原题...细节参见代码：#include #include #include #include #include #include #include #include

2016-12-24 16:13:34 818

原创玲珑杯 1072 - Capture（DFS序+线段树）

题目链接：点击打开链接思路：不难发现，这是一棵树，把树先建立好，跑dfs序，然后就变成了线段树区间修改、单点修改、区间最值。细节参见代码：#include #include #include #include #include #include #include #include #include #include #include #include

2016-12-24 15:22:02 839

原创 Codeforces Round #388 (Div. 2)D. Leaving Auction（水题呀？）

题目链接：点击打开链接思路：我们只要把每个人竞价的最大值存起来，并且把每个人的所有竞价维护在一个有序数组（方便二分），对于一组询问，我们从大到小遍历这k个数，把不在这k个数的最终竞价最大的两个人找到（复杂度O(K)），然后在竞价最大的那个人的set里二分第二大的人的竞价最大值就行了。细节参见代码：#include #include #include #include

2016-12-20 22:02:50 934

原创 Codeforces Round #384 (Div. 2)D. Chloe and pleasant prizes（树DP）

题目链接：点击打开链接思路：比较简单的树DP，用dp[u][id]表示当前以u为根的子树还已经找到几个子树的最大值。转移比较多，一方面可以转移到某一个儿子，表示问题在以后解决，一方面如果id==1说明还要找1个子树，可以直接用val[u]更新， val[u]表示该子树的和。如果id == 0说明还要找两个子树，我们用两个最大的儿子值更新即可。细节参见代码：#in

2016-12-19 20:20:09 836

原创 POJ 3237 Tree（树链剖分）

题目链接：点击打开链接思路：对于树上的路径更新操作，我们通常把他hash到线段上，也就是树链剖分，大概完全理解了吧，存个代码。对于该题的反转操作，可以里用异或操作的性质来做标记。细节参见代码：#include #include #include #include #include #include #include #include #include

2016-12-08 21:20:17 427

原创 Codeforces Round #200 (Div. 1) D. Water Tree（dfs序+线段树）

题目链接：点击打开链接思路：dfs序其实是很水的东西。和树链剖分一样，都是对树链的hash。该题做法是：每次对子树全部赋值为1，对一个点赋值为0，查询子树最小值。该题需要注意的是：当我们对一棵子树全都赋值为1的时候，我们要查询一下赋值前子树最小值是不是0，如果是的话，要让该子树父节点变成0，否则变0的信息会丢失。细节参见代码：#include #in

2016-12-07 19:04:09 490

原创 Codeforces Round #383 (Div. 2)C. Arpa's loud Owf and Mehrdad's evil plan（dfs&lcm）

题目链接：点击打开链接思路：很简单的一道题， dfs之后求n个数的lcm就行了，从网上扒下来一个lcm，mdzz死循环了。。不对的代码你贴个XX细节参见代码：#include #include #include #include #include #include #include #include #include #include #include #

2016-12-07 11:49:19 702

原创 Codeforces Round #383 (Div. 2) D. Arpa's weak amphitheater and Mehrdad's valuable Hoses（DP）

题目链接：点击打开链接思路：在宿舍打CF不敢使劲敲键盘，最后没交上D也怨不了别人。挺水的DP，就是个背包。细节参见代码：#include #include #include #include #include #include #include #include #include #include #include #include #include

2016-12-07 11:23:37 577

原创 CDOJ 1292 卿学姐种花（分块）

题目链接：点击打开链接思路：由于是一个区间更新问题，而且更新的值不一样，所以我们考虑分块。对于一个块，我们维护第i块的第一个元素被加了多少了sum[i]，第i块被更新了多少次cnt[i]，那么对于一个块内，元素依次增加sum[i]递减cnt[i]，这是一个等差数列。细节参见代码：#include #include #include #include #inc

2016-12-06 17:53:16 694

原创主席树

附上主席树代码，以示我完全理解了主席树：#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define Max(a,b)

2016-12-05 21:01:29 563

原创 51NOD 1640 天气晴朗的魔法（二分+最大生成树）

题目链接：点击打开链接思路：我们二分最大的边，这显然是符合二分性质的，然后使得边权和最大用最大生成树就行了。细节参见代码：#include #include #include #include #include #include #include #include #include #include #include #include #include

2016-11-30 21:20:08 562

原创 51NOD 1272 最大距离（线段树）

题目链接：点击打开链接思路：问题简化一下就是，求任意一个数后面大于等于它的数中距离它的最远距离。因为有两个特征：“大小”， “距离”，我们可以用线段树下标表示数的大小，距离作为值，就变成了求区间最大值的问题了。细节参见代码：#include #include #include #include #include #include #include #in

2016-11-30 14:18:49 549

原创 51 NOD 1521 一维战舰（并查集）

题目链接：点击打开链接思路：倒着用并查集合并就行了，一边合并一边统计，当能放置的船数大于等于k就停止。细节参见代码：#include #include #include #include #include #include #include #include #include #include #include #include #include #

2016-11-28 22:48:52 633

原创 HDU 4366 Successor（分块）

题目链接：点击打开链接思路：把题目转化一下就是：求一个区间内所有大于能力值v的人中忠诚度最大的是哪个人。我们考虑分块，对于一个块内的人，我们另开一个数组维护，将块内的人按照能力值排序，二分这个能力值，之后还要维护一个左端点变化的区间最大值，预处理即可。细节参见代码：#include #include #include #include #inclu

2016-11-11 12:29:17 579

原创 E. XOR and Favorite Number（莫队算法）

题目链接：点击打开链接思路：莫队算法适用于无修改操作的区间问题。关键是，需要能够用O(1)时间从[l, r]转移[l+1, r], [l-1, r], [l, r+1], [l, r-1]。该题需要观察异或和的特点，它是满足区间加减的。区间[l, r]的异或和等于[1, r] - [1, l-1]。那么我们用莫队算法维护每个点的前缀异或值，就是可以完美解决这个问题

2016-11-09 15:41:43 785

原创 Vijos P1988 自行车比赛（treap）

题目链接：点击打开链接思路：如果我们判断第i个人是否能第一，只需要把尽量小的分值给分数最大的人，如果有人超过了他，就不能得第一。我们可以把n个人排序，让2~n个人分别加上n-1~1，用treap维护最大值。转移到下一个人的时候，只需要把下一个人的加分加到当前这个人上就行了。PS：用treap的原因是set被卡了。吐槽：set太慢了。细节参见代码：#inclu

2016-11-03 21:31:15 772

原创 Vijos P1987 游戏（DP）

题目链接：点击打开链接思路：类似背包，很容易想到用d[i][j][s]表示前i个数字选了j个和为s的情况是否存在，复杂度略高，考虑到这是个布尔类型，可以用bitset转移，复杂度/6，这样就可以过掉全部数据了。细节参见代码：#include #include #include #include #include #include #include #inc

2016-11-03 17:25:29 620 1

原创 HDU 5945 Fxx and game（DP+单调队列）

题目链接：点击打开链接思路：用d[i]表示从i变到1的最小花费，那么如果i % k == 0，转移到d[i/k]，还可以转移到min(d[i-t, i])，我们可以发现这是一个区间最小值，用线段树维护即可，但是该题时间卡的很严，线段树会TLE，那么我们还可以用单调队列搞一搞。复杂度O(n)。细节参见代码：#include #include #include

2016-11-01 16:09:29 648

原创 ZOJ 3216 Compositions（矩阵优化DP）

题目链接：点击打开链接思路：ZOJ挂了，理论AC一下。用d[i]表示数i的拆分方案。转移是个难点，我们可以考虑转移到d[i-1]表示对于当前这个拆分出的数进行+1修改，转移到d[i-k]表示之前拆分的数不变了，新增加一个拆分数k。然后构造矩阵就很简单了。

2016-10-21 20:27:46 778

原创 UVA 10779 - Collectors Problem（网络流）

题目链接：点击打开链接思路：我们以1~m建立一列结点，表示Bob的物品，以2~n建立一列结点，表示其他的人。源点和1~m相连，容量为Bob的初始数量；汇点也和1~m相连，容量为1，表示最终种类的限制，如果有一个人i有物品j，那么i向j连容量为i拥有的个数-1，表示只会给他重复的物品；否则， j向i连容量为1的边，表示最多给i一个（不要重复的）。细节参见代码：

2016-10-21 16:05:40 517

原创 UESTC - 1251 谕神的密码（DP）

题目链接：点击打开链接思路：根据数据范围，很容易确定用d[i][j]表示前i位和为j是否能组成符合要求的数字。用path[i][j]表示下一个状态的j值， hehe[i][j]表示当前状态选了哪个数字。特判n == 1 && s == 0。细节参见代码：#include #include #include #include #include #include #

2016-10-19 20:28:18 597

原创 POJ 3373 Changing Digits（DP）

题目链接：点击打开链接思路：用d[i][j]表示前i位余数为j的最小修改次数， DP的过程中用path[i][j]表示相同状态下的下一个余数，目的是记录路径，用hehe[i][j]表示相同状态下该位最终的值是多少。细节参见代码：#include #include #include #include #include #include #include #inclu

2016-10-17 22:12:02 672

原创 UVA 11261 - Bishops（杂题）

题目链接：点击打开链接思路：象可以沿着对角线走任意距离，直接枚举保存复杂度n*m*log(nm)，肯定超时，考虑到数学方法：同主对角线上y-x的值相同，同一副对角线上x+y相同，且连续分布。所以我们考虑枚举主对角线的值，如果这个值出现过，那么这一个对角线的所有点都会被攻击，否则，我们维护这个区间的副对角线被占有的值的个数。复杂度O(nlogn)细节参见代

2016-10-13 16:41:53 615 2

原创 Ural 1542. Autocompletion（二分）

题目链接：点击打开链接思路：因为单词最长15，我们把每个单词不同长度的前缀存起来，排序之后二分即可，复杂度O(nlogn)细节参见代码：#include #include #include #include #include #include #include #include #include #include #include #include

2016-10-11 16:05:03 488

原创 UVA 1221/HDU 2413/POJ 3343 Against Mammoths（二分+二分图匹配）

题目链接：点击打开链接思路：由于人类星球和外星球是一一对应的，自然想到二分图匹配，但是如果匹配，必须是某人类星球能打赢某外星球才连边。因为星球上的飞船数量随时间变化，所以先考虑把时间固定，然后就可以分类讨论求出在T时间内的最大匹配。由于在T时间内能胜利，那么大于T时间也一定能，二分即可。细节参见代码：#include #include #includ

2016-10-10 12:39:59 863

原创 POJ 3538 Domestic Networks（DP）

题目链接：点击打开链接思路：选一些边，使得任意两点都可以相互到达且花费最小，这显然是最小生成树，将边挑选出来之后，如果贪心选取的话，有可能导致无解，所以我们考虑用动态规划。根据数据量，用d[i][j]表示前i个边，第一种颜料用了j单位长度下的最小花费，因为没条边都选，那么用总和减去j就是第二种颜料的花费。用path[i][j]表示改状态下从哪一个状态转移过来

2016-10-03 16:33:09 980 2

空空如也

空空如也