Code--Dream-CSDN博客

原创搬家了-博客园

搬家了：新家：http://www.cnblogs.com/coded-ream/

2017-07-28 17:36:18 541

### 题目意思数三角形的数量### 思路这道题一眼看去有一个非常显然的想法，那就是先用组合数算出任选三点出来的方案数，最后再减去三点共线的情况即可。那么关键就在于如何求三点共线的数目。我们要用到一个公式：设两个整点分别为$$(x1,y1)$$，$$(x2,y2)$$，那么两点之间连线上的整点数目为 $$gcd(|x1-x2|,|y1-y2|)$$接下来我们对直线在x轴 ,y 轴的射影长度进行枚举...

2018-05-25 14:32:25 266

原创 hdu 6035(Colorful Tree)

参考题解做的！思路+题意在代码中藏着呢。 1 #include 2 #include 3 #include 4 #include string.h> 5 #include 6 #include string> 7 8 9 using namespace std; 10 typedef long long int LL; 11 const

2017-09-27 17:57:15 384

原创 Splay模板(序列终结者)

我只是一个存模板的，详细的请看这里 http://blog.csdn.net/whai362/article/details/47298133 题目链接：http://www.codevs.cn/problem/4655/ 1 #include 2 #include 3 #include 4 #include 5 #include set> 6 #incl

2017-09-27 17:55:37 394

转载 splay tree

类别：二叉排序树空间效率：O(n)时间效率：O(log n)内完成插入、查找、删除操作创造者：Daniel Sleator和Robert Tarjan优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。注：所有图片来自wiki。http://blog.csdn.net/cyberzhg/article/details/8058208Tree R

2017-07-19 17:28:06 481

原创树堆（Treap）

平衡树简介：平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点

2017-07-17 08:41:25 529

原创 bzoj1556 (DP)

bzoj 1556 点这里打开题目题目是求 a^2 求和；原问题可以转化为：两个人在玩这个东西，问这两个人弄出来的序列相同的有多少种情况，操作方式不同即为一种不同的情况。就这个问题，参考大佬的DP思想。DP[t][i][j] 分别表示两人同时第t次取小球，第一人在上面管道取了i个，第二个人在上面管道取了j个所出现相同情况的个数：我们假设：某一个状态为 DP[t][i][

2017-07-06 10:32:11 611

原创 DFS序+线段树(bzoj 4034)

题目链接题目就不多说了。本题目，可以用dfs序+线段树做：题目给定了一棵树，树上节点告诉了权值。我们可以先将这棵树进行dfs将一棵树变成线性结构：如图变成这样后，然后就可以用线段树。操作1：也就是将某两个点+a；操作2：区间更新操作3：查询起始区间到某点的和我们建线段树，需要统计 +，- 抵消后的个数，因为要知道该区间的和，需要知道+a；简单插线问线。代

2017-07-04 21:23:22 607

原创在线判题系统hustoj的搭建

摘要:ACM/ICPC程序设计竞赛,越来越受到各个高校的重视,是程序设计竞赛中的奥林匹克。Hustoj是搭建在linux系统上的判题系统。能够判断代码的正确性。会及时返回通过或者不通过，如果不通过会返回具体原因。所以这个系统很适合ACM队员在上面做一些练习。每个学校有必要有自己的OJ，hustoj虽说是开源，有搭建教程。但是在搭建过程中还是会有一些问题。所以针对这些问题，给出了我的解决办法。

2017-06-26 12:51:48 11275 2

原创 deepin软件中文乱码

如图所示，deepin软件，会有这种情况，中文全是乱码，口口口。这表示很讨厌，学长给出的解决办法，将系统换成英文语言，这样确实解决了乱码，但是还是有问题，比如在写中文注释，又变成这样了。去deepin的bbs找了解决办法。将系统字体换一下，换成这样，软件上字体就不会乱码了，但是编辑框里面还是乱码，那就需要到软件设置那里去选择这个字体了。这个软

2017-06-26 12:46:08 7401

转载 QQ通信原理

转载自http://blog.csdn.net/li_xiao_ming/article/details/8106857下面有4个基本的问答：问题一：为什么只要可以连上互联网的计算机都可以用QQ相互建立通信，而不需要固定IP?也就是这个QQ用户端是怎样找到另一个QQ用户的，而用户在每次使用时他可能用的是不同的计算机，有着不同的IP地址。服务器端不会以qq

2017-06-26 12:44:12 1253

原创 .vimrc

" This line should not be removed as it ensures that various options are " properly set to work with the Vim-related packages available in Debian. " debian.vim " Uncomment the next line

2017-06-26 12:42:33 374

原创值域线段树 (玲珑OJ 1117)

点击打开题目链接题目意思很简单:1、插入x2、把小于x的数变成x3、把大于x的数变成x4、求集合中第x小数5、求集合中小于x的数个数思路: 线段树,节点是值的分数,你可以离散,也可以不离散,直接标记;我的写法是: 看代码注释>>>据说数组改为指针会快点;代码比较挫.存一个;#include #include #include #i

2017-05-19 17:12:14 1161

原创线段树-矩形面积求并

题目链接题目描述: 给定很多个矩形,给定方式是对角线坐标点.求面积的并。大致思路: 扫描线+线段树;#include <stdio.h>#include <iostream>#include <algorithm>#include <string.h>#include <string>#include <stdlib.h>#include <math.h>#inc

2017-05-16 18:26:30 513

原创值域线段树 bzoj 4627

0.0

2017-05-16 14:10:55 710

原创简单数位DP

https://cn.vjudge.net/problem/HDU-4722懒得写看，代码注释吧;主要存板子#include #include #include #include #include #include #include #include #include #include #include #include #include #include

2017-03-17 14:48:50 571

原创主席树学习--入门

本篇文章，讲讲主席树入门，以及区间第K大，或者区间第K小。学习主席树前提是要学习线段树，主席树也就是多棵线段树，每次更新都需要记录之前的线段树，如果每次新建一棵线段树。比较浪费空间时间。因为每次更新一个点只会修改一条树链。其他的树节点信息不改变，所以可以公用一些节点。这就是可持久线段树思想。大致思路我就不再重复了，整理了一些学习资料。算法讲堂-主席树，这个视频是UESTC某位大佬讲解的。很

2017-03-15 23:38:34 892

原创归并排序--小白写的

归并排序排序算法，最好实现的一种算法之一啊。学习该算法只需要了解递归就好了。首先给出一个问题，给出两个有序的数列，让你把它合成一个有序的数列，那么我们只需要两个同时从前往后看，小的数放到一个临时数组（当然这样是从小到大的排序），这样这个数组里面就是一个有序的了。然后再把这个有序的数组放回原来的位置。所以，会递归，归并排序写起来就很简单了。#include #include #i

2017-03-13 16:21:09 423

原创 Power Strings--KMP

https://cn.vjudge.net/problem/POJ-2406上面是比赛链接。题目意思很明确，问最多是多少个子串连接而成的？这个需要用到KMP，很好的理解KMP的Next数组。Next数组里面存了当匹配失败时应该跳到的位置，prefix（Next）=当前位置为末尾的长度相同的子字符串。n,代表字符串长度,那么Next[n]代表 prefix(Next[n])==长度等

2017-03-04 11:08:39 449

原创 blog.codedream.ren

博客将转到 CodeDream ,新的链接是 http://blog.codedream.ren

2017-02-28 15:15:11 876

原创数学题--On Sum of Fractions

题目链接题目意思:定义v(n)是不超过n的最大素数, u(n)是大于n的最小素数。以分数形式"p/q"输出 sigma(i = 2 to n) (1 / (v(i)*u(i))), pq为互质整数且q > 0。通常会想到这个裂项。公式一写发现约掉了许多。最终是：所以：AC 注意乘的过程会爆int。#include #include #include

2017-02-22 14:50:36 479

原创 Manacher 算法

原因:之前会这个算法,过了很久忘了。所以又得重新学习。如果留下自己的笔记，复习起来会很快。所以决定写一写自己的理解。我学习Manacher看的是这一篇博客。首先这个算法是解决最长回文子串问题的。算法解释：将字符串之间插入同一个特殊字符，然后从前往后开始，p[i]数组代表以i为对称中心的字符串的长度（算上中心那个字符）。下面计算P[i]，该算法增加两个辅助变量id和mx，其中id表示最大

2017-02-21 17:02:55 451

原创后缀数组--经典题型

后缀例题转自--后缀数组---处理字符串的有力工具例1 ：最长公共前缀问题描述：给定一个字符串，询问某两个后缀的最长公共前缀。算法分析：问题可以转化为：height数组的区间最小值。所以加上一个 RMQ+倍增算法模板。可以O(1)查询。例2：可重叠最长重复子串问题描述：给定一个字符串，求最长重复子串，这两个子串可以重叠。

2017-02-21 15:18:16 579

原创 Sports

题目链接 : http://acm.hpu.edu.cn/problem.php?id=1184 或者 http://acm.nyist.net/JudgeOnline/problem.php?pid=1319 题目意思 : 给定三个整数N，M，K，在1=a=N和1=b=M的约束下，存在多少个不同的整数对(a，b)使得a∗b可以被K整除？

2016-12-04 15:42:46 476

转载 OJ提交题目中的语言选项里G++与C++的区别

一、OJ提交题目中的语言选项里G++与C++的区别http://www.th7.cn/Program/cp/201405/199001.shtml首先更正一个概念，C++是一门计算机编程语言，G++不是语言，是一款编译器中编译C++程序的命令而已。那么他们之间的区别是什么？在提交题目中的语言选项里，G++和C++都代表编译的方式。准确地说，选择C++的话，意味着你将

2016-11-30 22:02:22 1117

原创 hpuoj 1193: Interval

Interval [STL、双指针、二分]题目链接 http://acm.hpu.edu.cn/problem.php?id=1193 或者题目链接 http://acm.nyist.net/JudgeOnline/problem.php?pid=1316 看了题解有点迷,标程很厉害,很巧妙。先求出前缀和 presum[MAXN]，

2016-11-29 14:40:30 572

原创数学题-计算相交圆的公共部分面积

参考学长的模板;数学能力差就要看公式模板;数学知识不懂画图推一下就出来了。高三同学做这种题应该特别厉害。double abss(double a,double b) //两数作差绝对值{ return a-b>=0?(a-b):(b-a);}struct circle{ double x,y,r;} a,b;double get_dis(double x1,

2016-11-26 21:15:37 1518

原创 2016-浙江理工新生赛-部分题解

巴比伦花园 link :http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4239 对于新生还是比较难;我是用 RMQ + 二分写的; 因为 fi[i] 数组代表从i开始最长到哪里,因为要求最长,所以第一个一定是1, i 是单调的,fi 数组也是单调的,所以可以二分;二分找刚刚在区间的,完全在区间用

2016-11-22 23:30:17 1041

原创 poj-3666

http://vjudge.net/problem/POJ-3666 题目是dp 题目; 简单dp 离散一下就好. 我们先来讲一讲不离散的,简单的懂了,其他的也很容易. dp[i] 代表这个数列以i 结尾的最小花费; 假设现在要求前n个数组成的数列,那么dp[i]= 前 n-1 的 min(dp[i]~dp[0])+ (当前这个数-i);#include

2016-11-17 00:03:59 496

原创 HDU-2255(KM算法)

KM算法

2016-11-14 21:20:04 548

原创字典树-水题

Hat’s Words题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1247 字典树题目: 建字典树,然后将一个单词分两个部分在字典树中查找!!用结构体封装一下,感觉还行~~>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>水水更健康#include#include#include#include

2016-11-12 18:02:35 409

原创树链剖分-入门题目

Query on a tree题目链接: http://vjudge.net/problem/SPOJ-QTREE题目大致意思就是: 给你一棵树,有连个操作: ● 第一个是查询任意两个不同节点上的最短路径上的最大权边! ● 第二个操作修改某一条边的权值;对于一棵树,数的深度如果很大,那么每次查询两个叶子节点,时间复杂度还是很高的。所以我们就把树分成一

2016-11-12 16:37:59 1332 1

原创线段树-题解

模板

2016-11-05 13:51:06 407

原创 Relocation POJ-2923

题目链接题目意思: 有 n 个货物，并且知道了每个货物的重量，每次用载重量分别为c1,c2的火车装载，问最少需要运送多少次可以将货物运完。分析：本题可以用二进制枚举所有不冲突的方案，再来dp 一下,一开始dp数组初始化为正无穷,dp[0]=0,代表什么都不运送需要多少趟,对于每个不冲突的选择方案；假设有 5 个物品, 就是更新 dp 数组 00000~11111 的状态的趟数。每次需要用不

2016-10-26 23:00:16 491

原创 ACM2016级新生第三周训练赛

弱校题解!高手莫笑话.

2016-10-23 11:51:30 3084 1

原创 nyoj 86 --位标记

nyoj 86 --位标记点击打开题目链接 : 找球号(一）这道题目很多解法,其他解法请参考 http://www.cnblogs.com/playboy307/p/5273737.html我参考最优代码写了一下,思路就是标记,一个数除以32会得到商(a) 和余数(b) ,那么已知a,b就可以确定一个数。那么我们可以用一个数组的

2016-10-16 16:53:21 535

原创 AC自动机-题目集合

AC自动机-题目集合模板题目链接: hdu-2222#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;t

2016-10-10 21:50:36 1662

原创 codeforces-724

题目链接: http://codeforces.com/contest/724/problem/B思路: 先把一步能够到达有序的情况枚举存在一个二维数组a里面。然后输入每一行对每一行进行两两交换，交换后把对应的 a数组的状态加一。最后看是否存在到达n的状态。#include#include#include#include#include#include#include

2016-10-09 13:56:57 573

原创有多少个不同的子串？-- 后缀数组

点击打开题目链接题目大意：给你一个字符串问你有多少个不相同的子串？InputT- number of test cases. ToutputFor each test case output one number saying the number of distinct substrings.ExampleInput:2CCCCCAB

2016-09-28 14:08:02 664

原创后缀数组-入门学习

后缀数组论文链接——处理字符串的有力工具_百度文库后缀排序DescriptionTim正在自学《数据结构》，他刚刚学会如何比较两个字符串大小。书上是这么说的（和Pascal语言中的比较规则相同，学习过Pascal语言的同学可以跳过这段）：比较两个不同字符串s1=’p1p2p3…pN’和s2=’q1q2q3…qM’的大小，设N若s1是s2的前缀，则s1qi，且i最小；若pi

2016-09-26 19:34:19 669

空空如也

Count primes ---ACM 题目