varinic-CSDN博客

原创 ecnu 电话送报贪心

在一条直线上分布着 n 户人家，你是邮局的送报员（邮局的坐标为 0），你的工作是每天早上要给所有人送报。一种方案是你亲自去给人家送，你要走过去并且走回来，可以在沿途上送多户人家的报纸，需要花费一定的（骑车）时间；另一种方案是你打电话让人家来拿，但打电话也需要花费一定的时间，并且你不能同时给多户人家打电话，打完电话后该户的报纸可以被视为已经送完。求你需要花在这份工作上的最短时间。假设自行

2017-06-30 12:47:09 747

原创 ecnu 核反应控制数学

著名物理学家 Daffy Duck 提出了核反应控制的关键理论。该理论的（玄学）表述是：在一个原子堆中有很多原子量不同的原子，如果原子 A 的原子量和原子 B 的原子量之和，恰好等于原子 C 的原子量，那么核反应控制难度将急剧增大。该理论的（数学）表述是：有集合 A={a1,a2,…,an}，如果存在 i,j,k(i≠j,i≠k,j≠k) 使得 ai+aj=ak，则输出 NO；否则

2017-06-30 12:24:28 547

由于你瞬间解决了小强多年以来的烦恼，小强十分高兴，于是他给大家讲了一个故事：“ 传说从前有个叫舍罕的印度国王，因为他的宰相发明了国际象棋，打算予以奖赏一番。国王问宰相想要什么，宰相对国王说：‘ 陛下，请您在这个棋盘的第一个格子里赏给我 1 粒麦子，在第二个格子里给 2 粒，第三个给 4 粒，以后每一个格子都比前一个多 1 倍，请您将这个棋盘上的 64 个格子全部摆满。’ 国王没宰相会算账，所以当即

2017-06-29 20:13:20 529

原创 C++ 11 thread join detach move swap

刚自学了thread发现网上的资料比较分散，现在这里统一整理一下，不是很深入，只介绍一般用法。首先创建thread对象：一般某一线程B是由其主进程A创建的。除了创建，A还要负责B的回收，回收的操作就是join()，意即B加入到A中被回收，可以推测join()操作只有一次。如果A在程序某处有B.join()，则A进程会阻塞，直到B进程结束，A才继续执行。如果线程A既希望被创建的线程

2017-03-28 20:30:04 1255 1

原创 hihocoder 1479 三等分树型dp

描述小Hi最近参加了一场比赛，这场比赛中小Hi被要求将一棵树拆成3份，使得每一份中所有节点的权值和相等。比赛结束后，小Hi发现虽然大家得到的树几乎一模一样，但是每个人的方法都有所不同。于是小Hi希望知道，对于一棵给定的有根树，在选取其中2个非根节点并将它们与它们的父亲节点分开后，所形成的三棵子树的节点权值之和能够两两相等的方案有多少种。两种方案被看做不同的方案，当且仅当形成方案的2个节

2017-03-17 20:30:51 772

原创 hihoCoder 1478 水陆距离

描述给定一个N x M的01矩阵，其中1表示陆地，0表示水域。对于每一个位置，求出它距离最近的水域的距离是多少。矩阵中每个位置与它上下左右相邻的格子距离为1。输入第一行包含两个整数，N和M。以下N行每行M个0或者1，代表地图。数据保证至少有1块水域。对于30%的数据，1 对于100%的数据，1 输出输出N行，每行M个空格分隔的整数。每个整数表示该位置距

2017-03-17 19:47:45 971

原创 ACM 利用位运算枚举所有子集

给集合里的元素一个顺序，那么就可以用整数表示集合，某一位为1表示对应元素被选取。设x为表示集合的整数，那么这个整数有如下性质： x的子集整数y在数值上不会比x大。因为x的子集y只是保留了x某些位置上的1，所以y总可以加上一个非负的整数z等于x，相当于把没选的1补上。根据这个性质可知，可以通过枚举所有比x小的数p并判断，p是否只含x对应位

2017-03-10 17:00:08 5413

原创 Raft动画演示

分享一个Raft动画演示网站： http://thesecretlivesofdata.com/raft/包括选举（Leader Election）、复写（log replication）、分区（partition）

2017-01-17 19:46:02 2412

原创总线仲裁之计数器定时查询

总线仲裁中集中式仲裁有一个计数器定时仲裁，看书的时候没弄懂。网上看了公开课算弄明白了。其实很简单，我们来看看它的工作过程：假设总线仲裁器中计数初值为0，这时设备2、4都通过BR线发出请求，如果设备不忙既BS为0，计数器开始从0计数。并通过设备地址线查看该设备是否发出请求，如果是，则响应否则继续计数。这里设备0没有请求，继续计数直至2，发现设备2有请求则响应，并将BS线设为1

2016-12-31 11:38:08 13611 4

原创 hihoCoder - 1116 - 计算（线段树区间合并）

线段树区间合并的题目套路就是每一段维护1.当前段的答案data[k]，2.当前段所有前缀Left[k]3.当前段所有后缀Right[k]合并时由当前段的左右子节点的data转移当前段，还有左子节点的后缀与右子节点的前缀合并形成的区间对当前段的贡献。然后维护当前段Left,Right就ok了。现在很少看见用vect或者map维护每一段前后缀的了（我会说是跑的太慢了吗）

2016-09-25 15:32:31 635

原创 hdu 5884 Sort k叉哈夫曼树+双队列优化

Problem DescriptionRecently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.Alice will give Bob N sorted sequences, and the i-th sequence includ

2016-09-17 20:17:21 1058

原创 HYSBZ 1067 RMQ

题意很清楚，坑点就是l或是r不存在时，要二分去找临近位置，然后统计这之间的max。#include #include #include #include #include #include #include using namespace std;const int maxn=2e5;map mp;/*数组下标从1到n，询问[l,r]最小值*/int a[ma

2016-09-16 15:44:09 438

原创 poj 3368 统计区间出现次数最多数个数 RMQ

对上升序列如：1 1 2 2 2 3 3 4 5 5 ....... 统计区间出现次数最多数个数。我们可以构造一个b[]数组，if（a[i]==a[i-1]）b[i]=b[i-1]+1;else b[i]=1;这样对上述例子，b[]数组有1 2 1 2 3 1 2 1 1 2那么对询问区间[l,r]，如果l在数与数交界处，那么直接查询l,r区间最大值。否则要知道与a[l]相

2016-09-16 14:08:09 2714

原创 hdu 5875 Function 二分+rmq

按照题意每次到当前点右边找比当前点小并且最接近当前点的点p。如果你能在O（1）的时间里查询[l,r]区间最小值，那么就可以二分查找p。#include #include #include #include #include #include using namespace std;const int maxn=100000+5;int a[maxn];int dp

2016-09-13 18:52:49 408

原创 hdu 5869 Different GCD Subarray Query 离线+树状数组

题意：给你n个数，每次查询[l,r]区间里所有子区间不同gcd的个数。我们先来看如何查询区间不同数的个数： spoj D-query 区间不同数个数主席树||离线+树状数组上面这道题讨论的是单个点，既对答案有贡献的是单个点，而这里是子区间要怎么处理。同理，对每个gcd有多个子区间，定义子区间左端点为子区间大小，那么只有最大的那个子区间才是有效的。这里还要用到gcd性质

2016-09-13 16:38:00 474

原创 varinic的模板

这里是varinic的模板字符串处理1.KMP/*pku3461(Oulipo), hdu1711(Number Sequence)这个模板字符串是从0开始的Next数组是从1开始的*/#include #include using namespace std;const int N = 1000002;int next[N];char S[N], T[N

2016-09-06 21:48:34 949

原创 poj 3667 Hotel 线段树区间合并

至此，扫描线，线段树区间修改更新，可持久化线段树，线段树区间合并等线段树题目全部过了一遍。接下来还有好多高级数据结构等着我去学。trick：线段树区间合并时，cover只需一个，因为一段区间只能处于一种状态，我作死开了两个cover分别对应两种情况，好处是一目了然，坏处是更新完一个cover还要更新另一个，（因为一段区间只能处于一种状态） QAQ #include

2016-09-02 13:40:15 421

原创 hdu 5790 prefix 主席树

这道题目其实和 spoj上的d-query 差不多 http://blog.csdn.net/mtrix/article/details/52335617，本质都是统计连续区间不同数个数，本来有离线+树状数组和在线主席树两种做法，这里强制在线那就主席树，对每个前缀要判断它有没有出现过可以用hash也可以字典树。#include #include #include

2016-09-01 18:07:07 813

原创 spoj D-query 区间不同数个数主席树||离线+树状数组

把区间统计转化为前缀和，这里的前缀和不是普通的前缀和，对相同的ai，只有最右边那个才是有效的。举个栗子：1 2 2 1 3 这样一个序列有效是这个样子 * * 2 1 3 ，因为1在后面出现过所以前一个无效，同理 2。前缀和则是0 0 1 2 3 ，那么对区间[1,5],[2,5],[3,5],[4,5],..[x,5] 我们都可以用sum[5]-sum[x-1]来求。这里的一个问题是前缀

2016-08-27 16:45:25 2234

原创主席树 poj 2104 K-th Number

主席树又名可持久化线段树。我们先撇开可持久化看看主席树是怎么实现的。维护一个长度为n的序列，我们可以建一颗线段树来维护，最上的根节点代表的区间是[1,n]。我们知道线段树的形态由你给的[l，r]，既维护的区间长度决定，现在我要为这个序列的每一个前缀建一棵线段树，每一棵线段树最上的根节点代表的区间依然是[1,n]，所以这n棵线段树的结构是一模一样的。这里的线段树不是普通的线段树而是权

2016-08-26 17:55:45 616

原创 poj 2777 Count Color 线段树区间更新

题目大意：给你两种操作：1、给一段连续区间涂颜色。2、统计某一区间有多少种不同的颜色。分析：线段树区间更新，区间查询。略坑的一点是要用二进制优化，开始用的vector TLE到死。。。#include #include #include #include #include #include #include #include #define lson k<<

2016-08-25 16:43:49 461

原创 hdu 4027 Can you answer these queries? 线段树区间修改区间查询

题目大意：对线段树有两种操作，对连续一段整体开根号，对连续一段整体求和。分析：这里开根号数会越来越小，到1后根号1==1，不变，可以利用这一点。某段maxv还有一种优化就是某一段maxv==minv，既这一段全都相等，那么开根号后值一样，可以用lazy优化。我第一种，两种结合起来试了一下，第二次跑的比第一次还慢，不知道是数据原因还是我代码写挫了。。附代码：#includ

2016-08-25 10:08:24 393

原创 hdu 5861 Road 线段树区间更新

考虑每一段最早出现的时间和最晚消失的时间，在这之间这段路都是要打开的，然后将2*n个时间点放到m个查询，对每个查询，可知道当前查询有哪些点进入，哪些点出去，统计它们对答案的贡献。#include #include #include #include #include #include #include using namespace std;typedef long l

2016-08-24 09:30:38 498

原创 hdu 5834 Magic boy Bi Luo with his excited tree 树形dp

题目大意：给你一棵树，每个点都有权值，每条边也有权值，从一个点出发，获得点值，走过一条边付出边值，点值只能获得一次，边值走一次付出一次。问从每个点出发，可以获得的最大价值。每个点记录从这个点出发又回来的最大值re[x]，以及从这个点出发最终往一个方向走的最大值ans[x][0]。第一次dfs还要记录下最优值ans[x][0]、次优值ans[x][1]，以及最优值是往那条边走的f[x][0]。第

2016-08-22 10:35:05 525

原创 hdu 5862 Counting Intersections 坐标离散化+树状数组

题目大意：给你与坐标轴平行的线段，问相交点有多少。我们将与x轴平行的线段分成两个点，左端点与右端点，与y坐标平行的线段取它的x坐标作为一个点，排序。那么一遍扫过去，遇到左端点，对应的y坐标++，遇到右端点对应的y坐标--，遇到第三种点，就是统计当前这个点对应y1，y2坐标之间出现过多少点。支持单点修改，区间求和，线段树树状数组都可以高效求解。#include #include #inc

2016-08-20 14:17:53 561

原创 FOJ 有奖月赛 2016-8 C Problem C Daxia & Suneast's problem

Problem Descriptiondaxia和suneast玩起来取石子游戏,现有n堆石子放成一排,每堆石子颗数为a1,a2,...,an.然后开始m轮游戏,每轮游戏之前,suneast先把第i堆的石子改成x颗,然后双方开始在第j堆到第k堆之间进行取石子游戏.取石子规则如下:1. daxia先取,然后双方轮流,每次取的数量不得超过该堆的一半;2. 当轮到某一方,而其不能

2016-08-17 18:08:14 990

原创 hdu 5784 How Many Triangles 极角排序计算锐角直角钝角

题目大意：给你n个点，计算有多少个锐角三角形。锐角三角形个数=(图中锐角个数-钝直角个数*2）/3转化为计算图中有几个钝直角，锐角。枚举角的顶点，然后再枚举该顶点引出的边，可以用向量表示。对这些向量进行极角排序，枚举起始边，用尺取的方法，算得与该边成锐角，钝直角的边的条数。统计，最后输出答案。#include using namespace std;const double pi

2016-08-10 13:44:10 1592

原创 hdu 5818 Joint Stacks 静态链表+栈

题目大意：有两个栈支持push，pop操作，还可以把两个栈合并，合并时元素push的时刻大的在栈顶。#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef

2016-08-09 17:22:40 512

原创 codeforces 364 div2 D As Fast As Possible

题目大意：一群小学生从起点走到终点，期间雇了一辆车来载学生，但车可能坐不下那么多人，问所有学生到达终点最短时间。最优方案是把第一批学生运到离起点x远的地方，然后车子返回运第二批，装着第二批人的车子追上第一批小学生，让第二批人下车和第一批人一起走，注意从头到尾整个过程小学生都是走着的而不是在原地发呆。。然后运第三批人重复这一过程，最优解就是最后一批人追上前面的人也就刚好到达终点了。然后我们来看一

2016-08-07 19:38:27 497 2

原创 poj 2406 Power Strings kmp next数组

求字符串最小循环节个数。有后缀数组，kmp的next数组两种求解方法，这两种方法的证明过程刚好是互逆的，证明了一种另一种也就证明了。先看后缀数组，假设循环节为k，那么s[0]与s[k]表示的后缀它们的最长公共前缀为n-k，既s[k]这个后缀刚好是s[0]这个后缀的前缀（有点绕233）。那么把s数组每k长为一段，分成n/k段（如果能整除的话）记为x1,x2,x3,......x n/k ，那么s[k

2016-08-05 10:33:46 318

原创 poj 3261 Milk Patterns

求重复至少k次的最长子串。后缀数组排序，那么sa[]里面连续的k个，求k个的最长子串长度。这里用到height[]数组求，k个的最长子串长度就是height[]里面连续k-1个的最小值，那么这些最小值里面取个最大值就是ans了。#include #include #include #include #include using namespace std;const int ma

2016-08-04 20:36:48 326

原创 hdu 5795 A Simple Nim

题意：n堆石子，每次从一堆取若干个，或者把一堆分成非空的三堆（这时不能取）。求sg，如果一堆有x个，那么对取来说它能转移到的状态为0，1，2，.... x-1 ，如果分三堆，可以类比剪纸的博弈游戏（poj 2311 http://poj.org/problem?id=2311），只要对分成的三部分取异或，就代表x所能转移到的下一状态。然后打表找规律就可以了。#include

2016-08-04 17:11:54 658

原创线性回归之梯度下降（附代码）

这几天看了知乎上子楠大神的机器学习笔记（地址：http://zhuanlan.zhihu.com/p/21340974），其中线性回归讲到梯度下降法求解function，我就自己实现了一下。文字讲解笔记里已经讲的很详细了，这里直接上效果，图，代码：代码：#include#include#include#i

2016-08-03 11:17:38 1591

原创 hdu 5792 World is Exploding 树状数组

计算像a，b这样上升的有la对，像c，d这样下降的有lb对，ans=la*lb。这样是有重复的，重复的就是a与c重合，a与d重合，b与c重合，b与d重合这四种情况。那么减去这四种情况就ok了。可以用树状数组预处理出每一位i的左边比a[i]大的有多少La[]，少的有多少Li[]，右边比a[i]大的有多少Ra[]，少的有多少Li[]。最后ans减去Ri[i]*Ra[i]; Li[i]*La[i]

2016-08-02 17:59:50 553

原创 poj 1743 Musical Theme 后缀数组

首先，连续的一段可以同时加减k值，不好直接求解，但是相邻两个数同时加减k 它们的差值却是不变的，所以s[]中存的不再是题目直接给的数而是它们的差值。比如：n=66个数为：1 2 3 1 2 3s[]数组中存的则是 1 1 -2 1 1这就转化成求不重叠最长重复子串，我们来看看这个问题怎么求解，设不重叠最长重复子串长度为len，显然长度为0至len的不重叠重复

2016-08-02 09:06:54 358

原创后缀数组之高度数组

加了一点自己对高度数组的理解：height 数组：定义 height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。那么对于 j 和 k，不妨设rank[j]则有以下性质：suffix(j) 和suffix(k)的最长公共前缀height[rank[j]+1],height[rank[j]+2], heigh

2016-08-01 13:58:49 2245 1

原创最优比例生成树

原文：http://www.cnblogs.com/lotus3x/archive/2009/03/21/1418480.html 概念：有带权图G, 对于图中每条边e[i], 都有benifit[i](收入)和cost[i](花费), 我们要求的是一棵生成树T, 它使得 ∑(benifit[i]) / ∑(cost[i]), i∈T 最大(或最小).解法：设x[

2016-07-31 20:46:18 1548

原创 hdu 1809 sg函数

这道题目我一定要好好吐槽一下，二维char数组表示成一维string，用来表示状态，然后求sg函数值用记忆化搜索，然后就一直WA，心好累差点怀疑人生，QAQ。后来发现记忆化搜索代码加上 if(vis[str])return sg[str]; 就WA，所以肯定这里出问题，后来一想，这种状态表示有毒，例如5x4与4x5的矩阵显然不同，但是展开成一维string时显然可以得到相同string，所以二维展

2016-07-30 11:34:04 494

原创 hdu 5769 Substring 2016 多校第四场

原题：后缀数组求不同子串个数。比赛时看着bin神博客http://www.cnblogs.com/kuangbin/archive/2013/04/24/3039634.html YY了两个小时，莫名A掉。我的做法就是算出包含X字符的所有子串数，再减去其中重复的就是答案。#include #include #include #include typedef long long

2016-07-30 11:20:44 356

原创博弈论合集

hdu 1847#include #include #include #include using namespace std;int dp[1003];int main(){ int p[30]; p[0]=1; for(int i=1;i<20;i++){ p[i]=p[i-1]<<1; } memset(dp,0,si

2016-07-24 22:17:19 776

空空如也

空空如也