天使v之翼-CSDN博客

原创 TCP/IP网络编程，一个简单的TCP server

用TCP协议编写一个简单的服务器，客户端，服务器一直监听本机的6666端口。server.cpp代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<errno.h>#include<sys/types.h>#include<sys/socket.h...

2018-04-05 15:27:48 19666

原创 C++如何连接redis

首先C++要连接redis,我们先要去官网下载hiredis.那么接下来用一个简单的例子来演示如何来连接redis.//redistest.cpp#include <stdio.h>#include <hiredis/hiredis.h>int main(){ redisContext* conn = redisConnect("127.0.0.1",6379...

2018-04-09 23:39:57 2108

原创 Liunx多线程pthread初探

一、线程标识线程有ID, 但不是系统唯一, 而是进程环境中唯一有效.线程的句柄是pthread_t类型, 该类型不能作为整数处理, 而是一个结构.下面介绍两个函数:头文件: 原型: int pthread_equal(pthread_t tid1, pthread_t tid2);返回值: 相等返回非0, 不相等返回0.说明: 比较两个线程ID是否相等. 头

2017-12-19 15:45:22 316

转载高并发解决方案（二）负载均衡

1,什么是负载均衡？当一台服务器的性能达到极限时，我们可以使用服务器集群来提高网站的整体性能。那么，在服务器集群中，需要有一台服务器充当调度者的角色，用户的所有请求都会首先由它接收，调度者再根据每台服务器的负载情况将请求分配给某一台后端服务器去处理。那么在这个过程中，调度者如何合理分配任务，保证所有后端服务器都将性能充分发挥，从而保持服务器集群的整体性能最优，这就是负载均衡问题。

2017-12-09 21:04:31 1672

转载高并发解决方案（一）页面静态化

一、什么是页面静态化：简单的说，我们如果访问一个链接 ,服务器对应的模块会处理这个请求，转到对应的jsp界面，最后生成我们想要看到的数据。这其中的缺点是显而易见的：因为每次请求服务器都会进行处理，如果有太多的高并发请求，那么就会加重应用服务器的压力，弄不好就把服务器搞down 掉了。那么如何去避免呢？如果我们把对 test.do 请求后的结果保存成一个 html 文件，然后每次用户都去

2017-12-09 21:02:56 1827

转载 Redis简介（四）高可用分布式集群

一，高可用高可用（High Availability），是当一台服务器停止服务后，对于业务及用户毫无影响。停止服务的原因可能由于网卡、路由器、机房、CPU负载过高、内存溢出、自然灾害等不可预期的原因导致，在很多时候也称单点问题。（1）解决单点问题主要有2种方式：主备方式这种通常是一台主机、一台或多台备机，在正常情况下主机对外提供服务，并把数据同步到备机，当主机宕机后，

2017-12-09 20:59:44 360

转载 Redis简介（三）面试常见问题

1. 使用redis有哪些好处？(1) 速度快，因为数据存在内存中，类似于HashMap，HashMap的优势就是查找和操作的时间复杂度都是O(1)(2) 支持丰富数据类型，支持string，list，set，sorted set，hash(3) 支持事务，操作都是原子性，所谓的原子性就是对数据的更改要么全部执行，要么全部不执行(4) 丰富的特性：可用于缓存，消息，

2017-12-09 20:55:33 376

转载 Redis简介（二）数据类型

Redis常用数据类型详解1.Redis最为常用的数据类型主要有以下：StringHashListSetSorted setpub/subTransactions在具体描述这几种数据类型之前，我们先通过一张图了解下Redis内部内存管理中是如何描述这些不同数据类型的：首先Redis内部使用一个redisObject对象来表示所有的key和

2017-12-09 20:51:20 249

转载 Redis简介（一）概述

首先，分布式缓存框架可以看成是nosql的一种（1）什么是redis?redis 是一个基于内存的高性能key-value数据库。 (有空再补充，有理解错误或不足欢迎指正)（2）Reids的特点Redis本质上是一个Key-Value类型的内存数据库，很像memcached，整个数据库统统加载在内存当中进行操作，定期通过异步操作把数据

2017-12-09 20:45:24 4073 3

转载 NoSQL介绍

NoSQL，泛指非关系型的数据库。随着互联网web2.0网站的兴起，传统的关系数据库在应付web2.0网站，特别是超大规模和高并发的SNS类型的web2.0纯动态网站已经显得力不从心，暴露了很多难以克服的问题，而非关系型的数据库则由于其本身的特点得到了非常迅速的发展。NoSQL数据库的产生就是为了解决大规模数据集合多重数据种类带来的挑战，尤其是大数据应用难题。（一）NoSQL数据库的四

2017-12-09 20:43:04 171

原创 CSU 1922 Irony Ring 类似单调栈的瞎搞或者线段树

题意：有n个铁环,内外半径和高度已知,问这些铁环最多能叠多高,外径必须非减,上面的铁环的外径必须大于下面铁环的内径，才能保证不掉下去。用一个栈维护能叠在一起的铁环，如后面一个不能放上去，则一直pop，直到能放上去，在这个过程中维护一个高度的最大值即可。线段树貌似也能实现，把[r,R]看做一个区间，两个区间有交叉则答案+1，再维护一个答案最大值即可。#include#in

2017-05-09 17:08:26 431

原创 HDU 2089 不要62 数位DP

题意：给出一个区间，求区间内满足不包含4和不含连续的62的数的个数。dp[pos][state]表示当前第pos位，前一位是否是6的状态，这里state只需0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。#include#include#includeusing namespace std;int a[20];int dp[20][2];int df

2017-05-03 17:32:56 800

原创 CSU 1911 Card Game 快速沃尔什变换（FWT）模板题

题意：给你两个二进制数的集合，给出q次询问，输出两个集合之间元素或的值等于查询值的种数。 #include#include#includeusing namespace std;#define LL long longconst int maxn = 1LL a[maxn],b[maxn];int n,m;char s[20];void FWT(LL a

2017-04-29 23:15:53 1329

转载快速沃尔什变换（FWT）讲解解决集合卷积的方法

能看到这篇博客的人，一定知道FWT是干什么的。（什么？你不知道？）没事，这里有picks讲FWT的一篇博客。先点进去看一看。如果你看懂了，那么恭喜你。如果你跟我一样看不懂，那么请继续往下看。这里的A和B都是什么呢？其实它们是一个多维的向量（如果你不知道向量是什么，就把它当成数组），下标从0开始。其中，A=<a0,a1,...,a2k−1>B=<b0,b1,...,b2k−1&...

2017-04-29 23:11:20 12846 5

原创 POIJ 1149 PIGS 最大流建图是关键

题意：某猪场由M个猪圈，N个顾客来买猪，每个猪圈有一定数量的猪，每个顾客有一个卖猪数量的最大值，每个顾客有某些猪圈的钥匙，打开相应猪圈后顾客挑选猪，在猪圈关闭前，打开门的这些猪可以任意分配到当前打开门的猪圈，买完关闭猪圈。下一个顾客重复以上操作。将每个顾客当做一个节点来表示，再加入超级源点和超级汇点。1. 对于每个猪圈的第一个顾客，从源点向他连一条边，容量为猪圈里的猪的数量。2

2017-02-17 16:16:22 660

原创 HDU 5965 扫雷 CCPC合肥

比赛现场没做出来，调了2小时。赛后一下想明白了，今天交了一发AC。枚举第一列放的个数，后面的便可以有前面的列确定。#include#include#includeusing namespace std;const int maxn=10010;const int mod=1e8+7;char str[maxn];int a[maxn],m[maxn],ans[3];

2016-11-05 18:10:30 1310

原创 POJ 3140 Contestants Division 简单树形DP

注意到题目说每两个点之间有且仅有一条路径，由此可得是一棵树。那么接下来就简单了，直接dfs即可。#include#include#include#include#includeusing namespace std;#define LL long long#define INF 0x3f3f3f3f3f3f3f3fconst int maxn=1e5+10;vecto

2016-11-02 15:53:30 459

原创 CF 219D Choosing Capital for Treeland 树形DP

首先我们可以将有向图转化为无向图，即正向边权值为0，反向边权值为1。那么接下来求某个点到剩下所有点的距离最小值。首先我们可以选择一个点为根，求出其到剩下所有点的距离。那么接下来选择其它点为跟的情况可以由上面计算的值递推出来。假设root有son1和son2, root到其他所有点, 都是先到son1, son2, 再接着往下走.那么求son1到所有点的时候, son1到son1子树的计数情况和

2016-11-02 14:31:09 393

原创 HDU 2196 Computer

树形DP第二题。题目要求出每个节点能够到达的最大距离。考虑最大距离只有两种情况。第一，通过子树达到最大；第二，通过父亲节点达到最大。而第二种通过父亲节点达到最大可能就经过了此节点，那么我们就还得记录一个从其它儿子节点过来的次短距离。#include#include#include#include#includeusing namespace std;const int maxn=1

2016-10-26 17:06:23 314

原创 HDU 1520 Anniversary party

树形DP第一题。首先定义dp[i][0]表示不选i号节点i子树能获取的最大值，dp[i][1]表示选i号节点i子树能获取的最大值。那么很容易的可以写出状态转移方程：dp[i][0]+=max(dp[v][0],dp[v][1]);dp[i][1]+=dp[v][0];#include#include#include#include#includeusing names

2016-10-26 16:51:08 313

原创北京网赛 F题 hiho1388 Periodic Signal

首先式子可以化为Ai^2+Bi^2-2*Ai*Bi;显然前面两项是一个定值，那么只需要求后面的最大值即可，但是枚举是O（n^2）的时间复杂度，超时是无疑的，那么对于这种卷积的形式，可以用到FFT，但是考虑到Ai,Bi数据很大，FFT精度就不够了，那么改用NTT。把A复制一遍放到末尾，B反转，构造多项式，这样多项式乘积指数[n,2n)的系数就是各个位置的结果了。再取一个最大值即可。#in

2016-09-25 15:52:48 439

原创沈阳网赛1003 HDU 5894 hannnnah_j’s Biological Test

考虑每两个人之间隔了几把椅子。可以发现，一共有m个数，和为n-m，且每个数都>=k.将每个数都减去k-1，即得到：m个正数之和为n-k*m，方案数为C(n-k*m-1,m-1).需要乘以圆排列的N，同时每个方案被算了M次，再除以M。这种组合数预处理阶乘可以做，直接Lcaus也行。#include#include#includeusing namespace std;#define

2016-09-18 20:37:43 1568

原创沈阳网赛1010 HDU 5901 Count primes

求前n个数中质数的个数。这里要用到Meisell-Lehmer的n^(2/3)的方法，借用了一大牛的板子。//Meisell-Lehmer#include#includeusing namespace std;#define LL long longconst int N = 5e6 + 2;bool np[N];int prime[N], pi[N];int getp

2016-09-18 20:10:33 1887

原创青岛网赛 1006 HDU 5883 The Best Path

可以将问题转换为求欧拉路径，欧拉回路。#include#include#includeusing namespace std;const int maxn=100010;int a[maxn],degree[maxn];int main(){ int t,n,m,u,v,cnt,ans,MAX; scanf("%d",&t); while(t--)

2016-09-17 20:13:49 634

原创青岛网赛1005 HDU5882 Balanced Game

水水水！#include#include#includeusing namespace std;#define LL long longconst int maxn=2016;int main(){ int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); i

2016-09-17 19:35:02 452

原创青岛网赛1002 HDU5879 Cure

首先题目要求保留小数点后5位，那么当n大到一定程度，前5位是不会再改变了。对于会变的情况直接打表预处理，大于则直接输出不变的结果。题目很坑，没说n的范围，需要用字符串读入。#include#include#includeusing namespace std;#define LL long longconst int maxn=1000010;const int c=130

2016-09-17 19:32:11 626

原创青岛网赛1001 HDU5878 I Count Two Three

可以知道在int范围内,满足2^a*3^b*5^c*7*d的数不会太多，直接打表然后二分查找即可。#include#include#include#include#includeusing namespace std;#define LL long longconst int c=1e9;int p=0;LL a[10000],f2[32],f3[32],f5[32],f

2016-09-17 19:26:41 791

原创 51nod 1358 浮波那契

构造新数列f(n)=f(n-10)+f(n-34),n>40,f(n)=1,n<=40,则FB(n)=f(10n)#include#include#includeusing namespace std;#define LL long longconst int p=1e9+7;struct Matrix{ LL a[35][35]; Matrix(){memse

2016-09-13 00:34:40 615

原创大连网赛 1010 HDU5877 离散化+树状数组

#include#include#include#include#includeusing namespace std;#define LL long long#define lowbit(x) x&(-x)const int maxn=100010;int t,n,u,v,a[maxn],c[maxn],q[maxn],rd[maxn];vector G[maxn];map

2016-09-11 16:29:11 542

原创大连网赛 1009 HDU5876 稠密图的最短路

#include#include#include#includeusing namespace std;const int maxn=200010;int n,m,s,u,v;int d[maxn];set::iterator it;set t1,t2;vector G[maxn];void bfs(int s){ queue q; t1.clear(),t

2016-09-11 01:43:24 752

原创 51node 1419 最小公倍数挑战

几天以前，我学习了最小公倍数。玩得挺久了，想换换口味。我不想用太多的数字，我想从1到n中选三个数字（可以相同）。使得他们的最小公倍数最大。（n首先考虑n为奇数，显然n,n-1,n-2这三个数互质，结果为三者乘积；再考虑n为偶数，结果为max( (n-1)*(n-2)*(n-3),n*(n-1)*i ) i为最大的与n和n-1都互质的数。最后特殊处理一下n#include#in

2016-09-05 23:30:08 537

原创 51node 1678 lyk与gcd

这天，lyk又和gcd杠上了。它拥有一个n个数的数列，它想实现两种操作。1：将 ai 改为b。2：给定一个数i，求所有 gcd(i,j)=1 时的 aj 的总和。n，Q(1<=n,Q<=100000)ai(1<=ai<=10^4)刚开始还以为可以用线段树维护，想了好久都不知道怎么维护，好像压根就维护不了。对于统计gcd(i,j)=1的和比较难，

2016-09-04 16:44:08 858

原创 51node 1537 分解

问(1+sqrt(2)) ^n 能否分解成 sqrt(m) +sqrt(m-1)的形式如果可以输出 m%1e9+7 否则输出no刚开始看这题的时候是一脸懵逼，之后便暴力跑了几组数据出来瞅瞅，瞅了有一会儿发现一个递推式，即F(n)=7*F(n-1)-7*f(n-2)+f(n-3),那么接下来构造一个3*3矩阵便迎刃而解了。A完之后又想了想，只要是(sqrt(x)+sqrt(x

2016-09-04 16:25:30 556

原创数组模拟实现邻接表

之间都是用vector模拟邻接表，但是后面发现vector时间复杂度有点高，所以写了份用数组模拟链表的方法实现邻接表#include#include#includeusing namespace std;/******************/#define LL long longconst int maxn=100010;templatestruct Gr

2016-09-04 16:06:33 1222

原创 2015年湖南省省赛E题简单的图论问题 CSU1780

题意很简单，写两个优先队列的bfs即可，dis小的排在前面即可，第二个bfs开一个变量记录每次从当前位置转移到下一个位置的方向即可。#include#include#include#include#define INF 0x3f3f3f3fusing namespace std;const int maxn=512;int n,m,sx,sy,ex,ey;int a[m

2016-08-21 17:29:42 956 1

原创 SGU 275 高斯消元

#include#include#include#include#define LL long longusing namespace std;const int maxn=110;int a[64][maxn];int n;LL x;LL gauss(){ int row,col; row=64-1; LL ans=0; for(;row>=

2016-08-17 16:21:34 387

原创 POJ 1830 开关问题高斯消元

题意：给你N个开关，其中某些开关之间是相互影响的，即一个开关控制多个，那么每个开关操作与否为一个变元，有N个变元，开关之间相互影响的系数设为1，否则为0，对模2高斯消元求解自由变元个数。#include#include#include#includeusing namespace std;const int maxn=30;int n,m;//有n个方程,m个未知数int

2016-08-16 10:59:31 304

原创 HDU 5833 高斯消元

首先，一个完全平方数的每个质因子的幂一定是偶数。对每个数进行质因数分解，令其中幂为奇数的系数为1即可。#include#include#include#includeusing namespace std;#define LL long longconst int mod=1000000007;const int maxn=305;int n,m;//有n个方程,m个未知数i

2016-08-15 18:30:01 437

原创高斯消元原理

高消一直是ACM中高层次经常用到的算法，虽然线性代数已经学过，但高消求解的问题模型及高消模板的应用变化是高消的最复杂之处。先介绍一下高消的基本原理：引入互联网czyuan的帖子：高斯消元法，是线性代数中的一个算法，可用来求解线性方程组，并可以求出矩阵的秩，以及求出可逆方阵的逆矩阵。高斯消元法的原理是：若用初等行变换将增广矩阵化为，则AX = B与CX = D是同解方程组。所

2016-08-15 16:30:30 4739

转载 ACM必学知识点清单

训练过ACM等程序设计竞赛的人在算法上有较大的优势，这就说明当你编程能力提高之后，主要时间是花在思考算法上，不是花在写程序与debug上。下面给个计划你练练：第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来。 1.最短路(Floyd、Dijstra,Bellm

2016-08-09 11:01:29 12181

空空如也

空空如也