- 博客(545)
- 资源 (1)
- 收藏
- 关注
RSS订阅
转载 WJMZBMR在成都赛区开幕式上的讲话
各位选手，各位教练，大家好，我是来自清华大学交叉信息学院的陈立杰，今天很荣幸站在这里代表全体参赛选手发言。对于我来说，这是我第一次正式参加ACM的比赛。不过我跟ACM之间的缘分，大概在很早的时候就已经存在了。 我还依稀记得，在我初三的时候，晚上我的一个好朋友在用手机跟妹子聊天，而我在用手机看OI和ACM的题目。自习课上我的那个朋友跟妹子一起学习，而我则翘课想去机房，有时候机房老师不让
2014-10-31 10:55:03
1778
原创 hdu 4846 Big Barn【dp】
http://acm.hdu.edu.cn/showproblem.php?pid=4846求矩阵中最大的仓库正方形#include <cstdio>#include <cmath>#include <algorithm>#include <iostream>#include <cstring>#include <vector>#include <string>#include <ma
2016-09-28 16:07:25
452
原创 hdu 5889 Barricade【最小割】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5889解法：求最短路图上的最小割，先在图上源点和终点分别求一遍最短路。再在最短路图上求最小割。 最小割==最大流定理代码：#include <stdio.h>#include <math.h>#include <algorithm>#include <iostream>#include <str
2016-09-18 09:49:06
514
原创 内存分配函数（C语言）
C 标准函数库提供了许多函数来实现对堆上内存管理 malloc函数：malloc函数可以从堆上获得指定字节的内存空间（必须初始化） free函数：释放内存，防止内存泄露 calloc函数：与 malloc类似，但不需要初始化 realloc函数：重新分配内存头文件stdlib.hmallocmalloc函数可以从堆上获得指定字节的内存空间，其函数原型如下：void * malloc(int
2016-09-18 02:10:47
3999
原创 RDB和AOF持久化
RDB持久化直接保存数据库的键值对。是二进制文件存储。指定的时间间隔内生成数据集的时间点快照两个命令:1 SAVE 会阻塞进程 2 BGSAVE 创建子进程处理文件，不会阻塞。父进程继续处理client请求，子进程负责将内存内容写入到临时文件。由于os的写时复制机制（copy on write)父子进程会共享相同的物理页面，当父进程处理写请求时os会为父进程要修改的页面创建副本，而不是写共享的页面
2016-09-17 23:52:14
509
原创 哈希表VS红黑树
HashHash，也可以称为“散列”，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出（也就是多对一的关系）。哈希表的构造在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决
2016-09-16 23:49:26
956
原创 Linux生产者消费者模型--基于线程条件变量
生产者和消费者之间用中间类似一个队列一样的东西串起来。这个队列可以想像成一个存放产品的“仓库”，生产者只需要关心这个“仓库”，并不需要关心具体的消费者，对于生产者而言甚至都不知道有这些消费者存在。对于消费者而言他也不需要关心具体的生产者，到底有多少生产者也不是他关心的事情，他只要关心这个“仓库”中还有没有东西。这种模型是一种松耦合模型。C代码：#include <stdio.h>#include
2016-09-13 02:01:35
606
原创 虚函数实现原理(转)
虚函数表（Virtual Table），简称为V-Table。在这个表中，主是要一个类的虚函数的地址表，这张表解决了继承、覆盖的问题，保证其容真实反应实际的函数。这样，在有虚函数的类的实例中这个表被分配在了这个实例的内存中，所以，当我们用父类的指针来操作一个子类的时候，这张虚函数表就显得由为重要了，它就像一个地图一样，指明了实际所应该调用的函数。在类的对象地址空间中存储一个该虚表的入口，占4个字节虚
2016-09-10 00:04:04
320
原创 SWAR算法：计算Hamming Weight
统计数组里面非0二进制位的数目： 比如a[] = {1,0,1,0,0,1,1,0}统计非0数目为4。Hamming Weight，即汉明重量，指的是一个位数组中非0二进制位的数量。比较常规的方法，按位统计，算法复杂度O（n）。redis里实现用到了两种算法：1.查表法 比如 0000 0001 ： 1 0110 0001 ： 3
2016-09-09 22:40:50
1178
原创 内存分配算法
（1）首次适应算法。使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。 该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断
2016-09-09 11:14:24
1604
原创 跳跃表 SkipList【数据结构】原理及实现
为什么选择跳表目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率
2016-09-06 22:35:07
9235
1
原创 基于Socket的网络聊天室
from asyncore import dispatcherfrom asynchat import async_chatimport socket, asyncorePORT = 5005NAME = "ChatRoom"class EndSession(Exception):passclass CommandHandler: def unknow(self, session, c
2016-08-30 22:41:04
2477
1
原创 Nagle算法
纳格算法是以减少数据包发送量来增进TCP/IP网络的性能。它是由约翰．纳格任职于Ford Aerospace时命名。纳格的文件描述了他所谓的“小数据包问题”－某个应用程序不断地提交小单位的数据，且某些常只占1字节大小。因为TCP数据包具有40字节的标头信息（TCP与IPv4各占20字节），这导致了41字节大小的数据包只有1字节的可用信息，造成庞大的浪费。这种状况常常发生于Telnet工作阶段－大部分
2016-08-03 16:26:00
393
原创 VIM配置
ubuntu系统下打开终端，输入vim就进入vim了。配置方法是输入 vim ~/.vimrc (这样是用vim编辑配置文件，或者用 gedit ~/.vimrc 就是用gedit编辑了)配置的话，按照自己习惯加几句配置文件就可以使用了。一般配置下面几个：syntax onset nuset tabstop=4set shiftwidth=4colo eveningset mouse=a
2016-05-12 15:27:10
583
3
原创 Linux 进程间通信
1 pipe管道子进程写，父进程读。 pipe(fd[2]) fd[1]写，fd[0]读#include <unistd.h>#include <stdio.h>#include <string.h>#define MAXSIZE 100int main() { int fd[2],pid,line; char message[100]; if (pipe(f
2016-05-12 14:20:33
339
原创 Linux 进程控制
进程1 进程创建fork()函数创建子进程。 “调用一次，返回两次”#include <stdio.h>#include <sys/types.h>#include <unistd.h>#include <stdlib.h>int main(){ pid_t pid; if ((pid = fork())<0) { printf("error\n")
2016-05-11 18:36:10
440
原创 wustoj 1593: Count Zeros【线段树】
题目：http://acm.wust.edu.cn/problem.php?id=1593&soj=0解法：线段树维护因子2 5存在的个数。并判断是不是存在0代码：#include <stdio.h>#include <iostream>#include <string>#include <cstring>#include <cmath>#include <cstdlib>#includ
2016-04-25 17:17:35
433
原创 Leetcode 151. Reverse Words in a String
题目：https://leetcode.com/problems/reverse-words-in-a-string/代码：class Solution {public: void reverseWords(string &s) { string ans; ans.clear(); for (int i = 0;i != s.siz
2016-04-23 22:49:29
299
原创 循环有序数组查找值
循环数组，即有序的数组进行移位后的数组。 如：4，5，6，7，8，0，1，2，3查找值是否存在时，利用二分的思想。步骤：while(L<R)如果 a[mid] == key,return mid。如果a[mid] > ａ[L],说明L-mid是有序的，mid+1 - R是循环的 如果key<a[mid] && key >= a[L]，则key在L - mid-1之间，
2016-04-22 22:20:30
582
原创 hdu 3294 Girls' research【manacher】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3294代码：#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <fstream>#include <algorithm>#include <cmath>#include <queue
2016-04-19 16:07:35
329
原创 Codeforces Round #346 (Div. 2) ABCDE
题目：http://codeforces.com/contest/659/problems A:#include <iostream>#include <string>using namespace std;int n, a, b;int main(){ while (cin >> n >> a >> b) { int ans; ans = (a
2016-04-03 17:10:56
360
原创 认识与学习bash
变量的显示与设置变量的显示: echo $[变量名] 修改变量名： 用等号“＝” 变量名只能由字母数字组成，且只能字母开头。取消变量： unset 变量名 环境变量功能： env查看环境变量及说明 随机数变量RANDOM set查看所有变量（包括环境变量） 如果想在子进程使用自己定义的环境变量，使用”export 变量名“。显示语系变量：locale 变量的读取，数组和
2016-03-30 21:55:47
705
原创 K-means聚类算法
K-means算法是一种无监督的机器学习算法。全自动分类，将相似对象归到同一个簇中。用户预先给的K个簇，每个簇通过“质心”来描述。伪代码：创建K个点作为起始质心（一般随机选择）任意一个点所属簇的结果发生改变时 对数据集中每个点 对每个质心 计算数据与质心间的距离 将数据划分到与它最近的簇 对于每个簇，重新计算质心（所有点的均值
2016-03-22 22:02:33
629
原创 LightOJ 1067 - Combinations【Lucas定理】
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1067题意： 组合数求模，Lucas定理代码：#include <stdio.h> #include <math.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include
2016-03-14 08:46:07
588
原创 LeetCode 2. Add Two Numbers
题目：https://leetcode.com/problems/add-two-numbers/class Solution{public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if (l1 == NULL) return l2; if (l2 == NULL) return
2016-03-12 01:24:51
409
原创 sizeof 计算原则
sizeof()计算类大小的一些基本原则： (1)类的大小为类的非静态成员数据的类型大小之和，也就是说静态成员数据不作考虑； (2)类的总大小也遵守类似class字节对齐的，调整规则；(参考５分钟搞定内存字节对齐) (3)成员函数都是不会被计算的； (4)如果是子类，那么父类中的成员也会被计算； (5)虚函数由于要维护虚函数表，所以要占据一个指针大小，也就是4字节。总结即：一个
2016-03-08 19:55:29
660
原创 最小堆
最小堆:所有父亲节点的值都小于儿子节点。 插入操作:首先在末尾添加元素，再不断向上（父亲节点）调整位置 删除操作：把末尾的元素值赋给根，并且删除末尾项，并且从根向下（儿子节点）不断调整位置。最大堆与最小堆类似。操作反过来即可。代码：const int MAXN = 1010;int heap[MAXN], sz = 0;void push(int x){ int i = sz++;
2016-03-03 18:42:26
482
原创 LightOJ 1050 - Marbles【概率】
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1050题意就不解释了思路： dp[i][j]表示i个红球j个蓝球的获胜概率。 初始化：dp[0][i] = 1 没有红球全是蓝球则获胜概率是1 转移：dp[i][j] = 我取得红球的概率*dp[i-1][j-1] + 我取得蓝球的概率*dp[i][j-2]代码：#inclu
2016-03-02 21:11:12
492
原创 LightOJ 1025 - The Specials Menu【区间DP】
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1025题意：给你一个字符串，可以删除任意多个字符使之组成回文串，问你最多有多少种方法。思路： dp[i][j]表示i到j组成回文串的方法数目。 首先初始化dp[i][j] = 1，就是不删除任何字符的方法。若s[i] != s[i] dp[i][j] = dp[i+1][j
2016-03-02 19:47:28
372
原创 poj 1463Strategic game【树形dp】
题目链接：http://poj.org/problem?id=1463题意：给你一棵树， 求用最小的点覆盖所有的边。思路： 树上的dp,对于一个节点i，dp[i][1]表示以i为根节点选择i点的最优解,dp[i][0]为不选择i的解，对于所有的j是i的儿子节点，dp[i][0] += dp[j][1],dp[i][1] += min(dp[j][1],dp[j][0]);代码：#include <
2016-03-01 20:36:32
360
原创 LightOJ 1044 - Palindrome Partitioning【dp】
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1044题意：给你一个字符串，问最少分为几个回文串？思路：dp[i]表示从开头到位置 i 的最优解，若[j,i]是回文串，则dp[i] = min(dp[i],dp[j-1] +1)代码：#include <iostream>#include <cstdio>#include <
2016-02-29 20:59:10
463
原创 LightOJ 1079 - Just another Robbery 【背包问题】
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1079题意： 给你一些银行的存储金钱的数目及被抓的概率，若被抓总概率不超过p的话，问不被抓的条件下最多可以抢多少钱？思路： 对于一个银行，可以抢或者不抢，于是想到了背包。代码：#include <iostream>#include <cstdio>#include <alg
2016-02-29 19:46:22
501
原创 LightOJ 1031 - Easy Game【区间dp】
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1031题意: 给一个序列，两个人轮流在序列的两边取任意个数的number，但每次只能从选定的那一边取，问取得数字的和的较大者比较小者多多少？思路： dp[i][j]表示i-j区间的最优解，然后枚举区间。代码：#include <cstdio>#include <cstring
2016-02-28 16:58:40
787
原创 小Z的袜子【莫队算法】
[2009国家集训队]小Z的袜子(hose)Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5259 Solved: 2426 [Submit][Status][Discuss] Description作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听
2016-01-28 02:39:07
608
原创 Codeforces Round #340 (Div. 2) A B C D
http://codeforces.com/contest/617 A 尽量选择数值较大的#include <iostream>#include <stdio.h>#include <string>#include <string.h>#include <cmath>#include <queue>#include <vector>#include <map>#include <
2016-01-24 15:22:25
419
原创 Redis主从同步
全量同步Redis全量复制一般发生在Slave初始化阶段，这时Slave需要将Master上的所有数据都复制一份。具体步骤如下： 1）从服务器连接主服务器，发送SYNC命令； 2）主服务器接收到SYNC命名后，开始执行BGSAVE命令生成RDB文件并使用缓冲区记录此后执行的所有写命令； 3）主服务器BGSAVE执行完后，向所有从服务器发送快照文件，并在发送期间继续记录被执行的
2016-01-21 12:23:48
592
原创 hau 3037 Saving Beans【Lucas定理】
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=3037代码：#include <iostream>#include <cmath>#include <cstdio>using namespace std;long long pow(long long a, long long b, long long c){ long long tm
2016-01-14 16:26:23
335
原创 Java-高精度
1002 http://acm.hdu.edu.cn/showproblem.php?pid=1002import java.io.*;import java.util.Scanner;import java.math.BigInteger;public class Main{ public static void main(String[] args) {
2016-01-13 18:04:08
446
原创 机器学习实战 第2章 k-近邻算法
简单的分类器：from numpy import *import operator def createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group,labelsg,la = createDataSet()def cl
2015-12-21 14:57:10
511
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人