_Wilbert-CSDN博客

原创 Codeforces-620d Professor GukiZ and Two Arrays

题目大意：给你两个数组，一个长度为n，一个长度为m，第一个数组各个元素的和为suma，第二个数组各个元素的和为sumb，现在想要通过交换两个数组元素的方式使Abs(suma - sumb)最小，但是交换的次数不能超过两次。让你输出Abs(suma - sumb)的最小值，并输出这个值发生的时候的交换次数和交换元素在两个数组中的下标。解题思路：首先看到这题我们需要明确一下数据大小

2017-08-27 22:48:53 531

原创 vector详解

引言emmm…这篇博客写作的缘由其实就是我在日常使用vector的时候发现对vector并不怎么了解所以决定写这篇博客的。写这篇博客，我参考了vector - C++ Reference中的内容，及侯捷先生的《STL源码剖析》一书，所实验的环境是CentOS7，g++4.8.5，所查看源码是SGI STL v3.3。这个版本的STL发布于2000年，而且是最新版。所以不包含C++11后的内容，所

2017-08-14 23:06:41 11051 3

原创网络编程入门

Linux和Windows下网络编程入门...

2017-07-10 00:53:06 627

原创随便写点什么

2017年6月30号快结束了，按月份来算，2017年的上半年要结束了。回想起去年的这个时候，我还在寝室玩着剑三，想着第二天开始要好好刷题争取在秋天拿下一块银牌。今年的这个时候，依旧类似去年，在寝室无所事事，却又想着明天开始要好好学习争取在秋天拿到个好offer，只是啊，付出多少努力，才会有多少收获啊。去年侥幸拿到的铜牌，今年还能够侥幸拿到好的offer么？自身的缺点，自身性格的缺陷，在这今年暴

2017-06-30 20:02:35 517 1

原创机器学习-决策树 ID3算法

今天用了一晚上把决策树的ID3算法撸出来了。首先推荐一发博客，说的感觉挺靠谱的...传送门一、信息熵高中化学里面有个概念讲的是分子的混乱程度(大概是这个...)。而信息熵就是香农借鉴了热力学的概念，将信息熵定义为“离散随机事件出现的概率”。加入对于随机变量X={xi}，每个xi的概率为pi，那么信息熵可以定义为：二、信息增益对于一个数据集S来说，其信

2017-04-24 23:10:47 538

原创 51nod-1040 最大公约数之和

解题思路：这题感觉dalao们会说这题是个水题....虽然这题确实挺简单的...思路很好想，求最大公约数之和嘛，对于n，从1-n与n之间的最大公约数，必然不可能有n个，也就是必然出现再n的因子中，那么其实可以求sum(a * b),a表示n的因子，b表示最大公约数为a的个数。那更进一步，gcd(n, m) = k,那么必然会有gcd(n / k, m / k) = 1，那么就可以根据这

2017-04-24 11:37:32 458 1

原创 Hihocoder-1514 偶像的条件

解题思路：其实就是随意搞下就行。求|a - b| + |b - c| + |c - a|的最小值显然枚举a，然后二分整个{b}找到离a最近的b，再二分整个{c}找到离a最近的c和离b最近的c比较一下谁最近，就可以O(nlogn)搞出来了。代码：#include #include #include #include #include #include #i

2017-04-24 11:30:31 691

原创 Hihocoder-小Hi的烦恼

解题思路：其实题目自带的题解已经交代的比较清楚了。但是如果完全按照题目自带的解法来计算，肯定是会超时的。因为无论如何还是O(n^2)的解法，当然也可能是彩笔我比较菜只能写出这样的。所以需要一些转换。这个题目给的内存空间为1024M，显然我们要用空间换时间了。就以单个科目为例吧。假设a[i]表示第i个学生在语文这个科目上的排名，index[a[i]] = i表示语文排名为a[i]的是

2017-04-24 11:25:44 554

原创 Hihocoder-1286 子矩阵求和

解题思路：看到这个题目的时候是很懵逼的= =矩阵是无限的但是其实没那么刚，只需要巧妙的转换下就可以得到结果。对于矩阵：1 1 1 1 1 1 1 11 2 2 2 2 2 2 21 2 3 3 3 3 3 31 2 3 4 4 4 4 41 2 3 4 5 5 5 51 2 3 4 5 6 6 61 2 3 4 5 6 7 71 2 3 4 5 6 7 8对于这样的矩

2017-04-24 11:09:31 1019

原创 Goodbye 2016

2016最后一个小时。先把昨晚的Codeforces Goodbye 2016题解xjb写一下吧。第一题是水题。只要能看到题目应该能很快写掉。第二题有点意思。不过依旧是水题。可能有点坑点。在北极只有一个方向就是南，在南极只有一个方向就是北。不存在在南极或北极能向东向西这样的情况。如果从当前点向南向北走超过使得超过南极或北极，也是不合法的，因为在北极会有向北的方向，在南极有向南的方向。然

2016-12-31 23:59:28 793 3

原创杂

本来想着每天一题hihocoder，然后写博客总结的。不过看起来选的时候不是很好。作为学渣的我还是要好好学习应对期末考试的。等期末考试后再继续吧~最近一周计划：now -> 12月30日 xjb复习（预习）12月30日晚上22:05 codeforces GoodBye 201612月31日数值分析期末考试期末加油了我....立个flag：期末不挂

2016-12-26 21:16:02 366

原创入门动态规划问题

hihocoder这周欠了三题，于是今天一波结束了。然后发现这三个题目似乎都很简单，并且还是一类问题里面的。所有就写成一次的吧。动态规划问题，说起来，理论上是每个搞ACM的人都会学的，而且应该是最开始就学的。因为动态规划问题是各种各样比赛的宠儿啊，几乎每次比赛必出动态规划。楼教主的“男人八题”里面就有几个动态规划问题，是需要结合数据结构和动态规划才能解决的问题。不过不在这次范围内。

2016-12-18 15:38:21 475 1

原创 AC自动机

本来这篇...我是不想写了的...以及比计划晚了三天...虽然是因为考试的原因....不过主要还是由于AC自动机这个算法我也不过是上周日的时候才学会怎么写。原理性东西有点了解而已。所以既然还是决定写了，那就写吧。AC自动机算法（Aho-Corasick算法）是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，在均摊情况下，具有近似于线性的时间复杂度

2016-12-18 14:02:07 396

原创 KMP算法

KMP算法(Knuth-Morris-Pratt Algorithm)是一种非常高效的字符串匹配算法，是由Knuth,Morris和Pratt三位与1977年发布的算法。最坏复杂度为O(n+m)首先我们用一个例子来演示这个算法：原串为babababcbababababb模式串为bababb模式串的失配数组为0,1,1,2,3,4当i = 6, j = 6时，出现

2016-12-15 13:13:47 447

原创 [OpenGL]用鼠标拖拽图形移动

今天做计算机图形学实验。题目布置了写程序使图形移动，于是我就写了这个程序。使用的环境是Code::Blocks + GLUT，Code::Blocks配置GLUT实现OpenGL的教程可以看这篇：http://blog.csdn.net/yang_7_46/article/details/24674849想要实现用鼠标拖拽使图形移动，首先需要考虑两个问题：1.如何接受鼠标产

2016-12-14 23:29:05 11647 4

原创 HDU-2222 Keywords Search

题目大意：给你一个最长为1e6的字符串，再给你一个字典，问你在这个字符串里面有多少字典中国的字符串出现过。解题思路：AC自动机模板题。这道题目，有两个坑点。大概是两个坑点吧。第一个就是要被匹配的串可能会匹配字典中的字符串多次。第二个就是字典中的字符串可能会重复，可能会被多次匹配到。比如一个数据：13sheshesheshesheshe

2016-12-13 15:00:56 434

原创 Trie

今天照例，写了一发hihocoder，是关于Trie字典树的，于是顺便再复习下字典树吧。Trie是一种树，非常实用的一种树，使用Trie还可以写AC自动机。在字符串处理上面有非常好的效率。首先介绍下字典树的定义。在使用C++的时候，可以这么定义字典树#define N 26 //字典树中的字母数量typedef struct node{ int num;

2016-12-13 10:24:51 556

原创 Manacher算法

最近发生了很多事。博客本来准备用自己搭（想要看的可以访问www.wilverain.com）的，后来发现不管是wordpress还是hexo都不是很喜欢，于是就又回到csdn了。等以后成为全栈再自己写一个吧（划掉最近开始刷hihocoder里面的题目了，就是跟着hiho一下里面来做，预期是每天做一题。毕竟已经是退役狗了。所以对于每一个hihocoder应该都会写一个博客来记录自己的思路或者学习

2016-12-12 15:43:23 402

原创 HDU-1588 Gauss Fibonacci

题目大意：有两个函数，g[i] = k * i + b，另外一个函数f[i] = f[i-1] + f[i-2]，问你从0到n-1的f(g[i])的和。解题思路：斐波那契数列有种递推的思路是：{f[i+1], f[i]; f[i], f[i-1]} = A ^ i其中A = {1, 1; 1, 0}这样的话，我们可以利用这样的特性，另f[i] = A^i，这样可以把这个问题

2016-10-17 17:24:02 438

原创 Codeforces-713C Sonya and Problem Wihtout a Legend

题目大意：给你一个序列，让你把它变成一个严格递增的序列。对每个数字，无论+1或者-1都消耗1，问你把它变成严格递增的序列的最小cost解题思路：DP首先根据题目，a[i+1] >= a[i] + 1，两边同时减去i+1，就得到a[i+1] - (i + 1) >= a[i] - i设b[i] = a[i] - i，则b序列是不降序列，那么问题就变成了将序列变成一个不降序列所

2016-10-10 21:05:20 455

原创 Codeforces-713A Sonya and Queries

题目大意：+ x表示向一个mutiset里增加一个数x- x表示向一个mutiset里面减少一个数x？ x表示询问这个mutiset里面能够与x匹配的数的个数，匹配规则是x只由01组成，0表示偶数，1表示奇数。当x比要匹配的数长度短的时候，在x前面补0，当x比要匹配的数长度长的时候，在待匹配的数前面补0解题思路：乍一看觉得应该用字典树写。其实不然。直接设一个长度为2^18的

2016-10-10 20:52:40 488

原创 HDU-5895 Mathematician QSC

题目大意：已知f[0] = 0, f[1] = 1, f[i] = f[i-1] * 2 + f[i-2]，且g[n] = g[n-1] + f[n] * f[n]，现在给出n，y，x，s，问你x^(g[n*y]) mod (s + 1)的值为多少。解题思路：首先可以得到的是g[n] = f[n] * f[n+1] / 2证明方式就是xjb打表加上猜加上数学归纳法，别问我怎么猜到的

2016-09-20 20:38:52 667

一、引言在平时做题目或者进行运算的时候，素数的出现次数总是十分频繁。这里总结了一些常见的判定素数和计算某个范围内素数个数的一些算法。部分代码来源于 kuangbin 的模板，嗯毕竟都是跟着这个学的...二、朴素判断素数算法就判断素数而言，事实上是非常简单的了。根据定义，判断一个整数n是否是素数，只需要去判断在整数区间[2, n-1]之内，是否具有某个数m，使得n % m == 0。代码可以这么写：...

2016-09-19 21:23:00 29307 8

原创 HDU-5900 QSC and Master

题目大意：有n对二元组(key, value)，两个相邻的元组间如果key的不互质，那么可以被移除，并获得两个元组的value值之和的分数，问你最多能有多少分数。解题思路：区间DP按照最裸的区间DP模型用记忆化搜索写是要超时的...本题的模型可以参考POJ-2955 Brackets题解这里有~设dp[i][j]表示区间[i, j]能获得的最大分数状态转移就可以写成dp

2016-09-19 18:25:33 671

原创 HDU-5889 Barricade

题目大意：给你n个点，有m条边，让你求出这个图的最短路上的最小割，这个最小割。解题思路：直接求出最短路图然后dinic跑最小割就行。我遇到的一些错误点：1、用dinic算法求解最小割需要使用当前弧优化，否则会TLE2、最短路图注意求最短路的时候，每个边都是长度为1，也就是说可以bfs求。千万不要把权值当成边长3、构造最短路图注意不要重复构造代码：#include

2016-09-18 21:44:35 521 1

原创 HDU-5884 Sort

题目大意：给你n个长度为ai的序列，让你把这n个序列合并，每次合并需要一个cost，值为合并的序列的长度之和，每次最多可以合并k个序列。现在问你，给出cost最大为T，最小的k是多少。解题思路：显然，可以用优先队列水一发，复杂度为nlognlogn二分枚举k，然后每次取最小的k个加在一起，加入队列，然后判断，加和是否比T大。其实就是一个k维哈夫曼树的优先队列优化，来篇博客，传送

2016-09-17 22:54:00 459

原创 HDU-5876 Sparse Graph

题目大意：给你一个完全图让你删除给出的这些边形成新的图，问你在新的图上的s点到其它所有点的距离。解题思路：BFS乱搞...补图的BFS的问题虽然很经典= =不过确实还是第一次做。很方。用一个map来保存邻接的信息。因为最多20000，很坑的是比赛时候题面给的是5000然后先从s来遍历所有点，如果邻接信息里面含有s到i的边，那么将i插入到set里面，并将dis[i]置为-1，

2016-09-13 12:56:32 432

原创 BZOJ-1010 [HNOI2008]玩具装箱toy

解题思路：斜率优化DP这道题= =嘛算是斜率优化的入门题目了。还是非常经典的感觉。首先考虑，这道题目有经验的小伙子一眼就可以想出来状态转移方程是什么。显然是 dp[i] = min(dp[i], dp[j] + pow(sum[i] - sum[j] + i - j - 1 - L, 2));但是想出来之后，想都不用想就知道这个题目，显然是不会是这么简单就能解决的了。因为n

2016-09-13 12:39:42 560

原创 POJ-2955 Brackets

题目大意：给你一个只由'('、')'、'['、']'组成的字符串，问你这个字符串的子串能够匹配的最长长度是多少。能够匹配的意思是这样的：1.如果s是个空串，那么它是匹配的。2.如果子串是(s)或者[s]，那么它也是匹配的，其中s是匹配的3.如果s是匹配的，s'也是匹配的，那么ss'也是匹配的解题思路：标准的区间DP直接按照上面3个定义来考虑区间DP就好。代码：

2016-09-07 11:26:19 619

原创 BZOJ-1177 [Apio2009]Oil

解题思路：一种非常神奇的枚举策略...不过这种枚举策略...是需要DP来完成的嘛...这种神奇的题目我独立肯定是做不来的...所以我是看着这篇博客写的...传送门嘛...这篇博客好就好在...你必须要想通了你才知道这个代码是怎么回事...太可怕了%%%首先，因为题目说了，必须要是三个k*k的矩形，那么其实相对来说比较容易的想法就是一个个去枚举，但是肯定会超时。那么考虑一个问题

2016-09-04 14:37:41 600

原创 BZOJ-1001 [BeiJing2006]狼抓兔子

解题思路：这道题目是关于最小割的一道题目。最小割的经典算法是根据最大流最小割定理，将最小割化成最大流然后用dinic算法求解不过这题比较特殊，即使转换成最大流求最小割依旧不可能通过。因为时间和空间的双重限制，所以这道题的解法需要利用这个图的特殊性质。给出的图是一个平面图无疑，那么利用平面图的特殊性质解决这个问题会简单很多。将平面图转换成其对偶图，然后计算新的源点到新的汇点的

2016-08-31 15:28:45 554

原创 POJ-3734 Blocks

题目大意：有n个blocks，让你用红，蓝，绿，黄四种颜色染上色，其中红色和绿色的block都是偶数个的方案有多少个。解题思路：其实这是个DP...啊一脸狗血...其实模型很像这题....HDU 1143 Tri Tiling首先，假设dp[i][0]表示当涂了前i个blocks之后，红色和绿色都是偶数个的方案个数，dp[i][1]表示当涂了前i个blocks之后，红色和绿色只

2016-08-30 20:17:09 435

原创 UVAlive-3363 String Compression

题目大意：给你一个字符串，让你把它压缩，比如gogogo可以压缩成3(go)，letsgogogoletsgogogo可以压缩成2(lets3(go))，然后问你压缩后的最短长度。解题思路：区间DP。一开始我以为是个基础的DP。没想到在第二个样例过不去，才发现这不是个基础的DP，也不是...这应该算是基础的区间DP吧。首先设dp[i][j]表示从i到j这个区间内的字符串能压缩的

2016-08-27 21:12:24 626

原创 UVAlive-4643 Twenty Questions

题目大意：有m个问题，n个人，给出这n个人对这m个问题的回答，只有“Yes”和“No”这两种回答，所以用1表示yes，0表示no，然后问你最少用几次询问问题能分别出所有人。一个例子，比如3 4001011100000用两次即可，先问第3个问题，如果是1则问第2个问题，如果是0则为第1个问题，得到的答案是2而不是3！解题思路：状态压缩动态规划+记忆化搜索

2016-08-27 20:56:45 672

原创 UVA-10817 Headmaster's Headache

题目大意：有s个学科，现在在学校有n个教师在教书，这些教师必须要被雇佣，现在还有m个教师正在应聘。现在给出这n个在职教师的工资和能教的科目，给出m个应聘教师的工资和能教的科目，现在希望这s个科目，每个都有至少两个教师教授，问你最少需要支付的工资是多少。解题思路：动态规划。状压DP。dp[i]表示i这个状态需要支付的最少工资。因为每个科目至少两个教师，且最多只有8个科目，所以很明显状

2016-08-24 11:47:26 535

原创 Codeforces-710E Generate a String

题目大意：有三个操作，插入删除和复制。其中插入和删除均耗费x时间来插入或删除一个字符，复制耗费y时间将当前文件内所有字符复制并粘贴（就是字符*2），现在需要生成n个字符，问你最少需要的时间。解题思路：DPdp[i]表示生成i个字符需要的最少时间，那么状态转移方程就是dp[i] = min(dp[i-1] + x, dp[i+1] + x, dp[i / 2] + y);代码

2016-08-23 13:06:44 842

原创 POJ-2762 Going from u to v or from v to u?

题目大意：给出一个有向图，这个图，是否存在任意两点a,b可达，这里的任意两点a,b可达是说，只要从a能到b或者只要能从b到a就算是可达的。解题思路：先求出这个图的强连通分量，然后缩点建图，只要这个图是一条链状的，那么就可以满足任意两点都可达，否则不满足。原因是只要这个缩点建图之后的图是链状的，那么必然从链的头到尾，任意两点都可达。一旦不是链状，要么出现分叉，要么某个点入度>=2，这

2016-08-22 22:05:18 381

原创 HDU-5269 ZYB loves Xor I

题目大意：给出一个长度为n的数组A，让你求出lowbit(A[i]^A[j])的和对998244353取模的结果，其中i和j都属于[1,n]。lowbit(x)表示的是满足x xor 2^k > 0最小的2^k解题思路：因为数据规模很明显是5e4这样的规模，直接暴力搞必然超时，那么我们可以考虑一个问题，对于异或，如果x xor 2^k > 0的话，k一定是x二进制表示中最小的一位为1的

2016-08-21 22:31:59 377

原创连通图问题入门小结

每次到了晚上都无法静下心来写题目，不如写篇博客，总结一天的学习。今天一天，首先回顾了昨晚Codeforces的几道题目。恕本蒟蒻太菜，实在无法写出来后面两道题目。然后偶然发现很久之前的一道题目还没写，就顺手写了。然后便开始了今天的学习。今天主要学习的问题是连通图的一些问题。第一个问题就是强连通分量的求解。这一部分事实上我看了挺多的博客还有资料都没有看的太懂，最后跟着某篇博客

2016-08-21 22:22:20 1655

空空如也

空空如也