a2520123-CSDN博客

原创后缀数组实现

先贴这里,免得忘了program sa;type int=longint;var i,j,k,m,n,l,max:int; a,b,c,d,x,r:array[0..1000000]of int; ch:char;procedure main;begin l:=1; repeat

2013-03-17 09:48:49 859 2

原创 [网络流]matrix题解

以下的描述中可能会把行和列弄反,请不要过于纠结.[题目描述] 给你2个n*m的矩阵A和B,求一个矩阵C,满足:Ai,j[题解] 这道题还是很好想的,只要有一点线性规划的基础知识就行了. 没有的可以看一下我上一篇文章. 显然,我们先令Di,j=Ci,j+k,其中k是一个充分大的数使得Di,j的下界非负. 然后,我们二分这个ans,原问题变为:求一个矩

2013-03-11 12:42:16 933

原创线性规划入门

最近好像没怎么动这个blog了,不能这么堕落了...也就是一时兴起想写一下,看不懂别怪我...首先明确一下线性规划的定义,就是所有约束条件以及目标函数中未知数的次数都是1,因此线性规划的一个约束条件表示在n维空间上是"平"(自己意会一下吧)的.接着,线性规划的可行域在n维空间上看起来是"凸"的(因为约束函数是"平"的),我们把这个东西叫做单纯形.求解线性规划的算法,一般用单形法或者

2013-03-09 17:17:57 1179

转载复数与矩阵,一个有趣的东西

原文地址:http://www.math.hmc.edu/funfacts/ffiles/30001.1.shtml截图:简单的说就是将负数a+bi用一个2*2的矩阵来表示,这样负数的运算就可以变成矩阵的运算.一个好处是:用矩乘优化旋转操作不要推矩阵了.

2013-03-03 21:52:02 1157

原创单纯形的实现

烧卖好像要讲,所以我就先讲了,免得到时候写了没人看.烧卖的代码在这里:http://blog.csdn.net/jarjingx/article/details/8565910首先我要吐槽一句:做最大流不要初始化可行解,不要判无解,不要判解无限,不要怕死循环(出题人不会卡你),怎么写都可以过.推荐这道题目:https://icpcarchive.ecs.baylor.edu/ext

2013-02-17 12:05:14 1051 2

原创 [orz]一道题的神做法....

题目描述:Squirrel Liss lived in a forest peacefully, but unexpected trouble happens. Stones fall from a mountain. Initially Squirrel Liss occupies an interval [0, 1]. Next, n stones will fall an

2013-01-20 22:34:55 729

原创 SDOI2012最近最远点对

[题目描述]给你n个点,求最近点对和最远点对,n[题解]计算几何裸题,由于本沙茶不会最近点对的二分算法,加上ws的出题人卡住了随机算法,于是苦B的打了一个2-d树交上去....用2-d树做最近点对的应该就只有我这个若b了吧好心酸TAT,幸好没卡2-d树,不然白打了140行的代码啊...代码量骤增(虽然我不知道二分的代码量怎么样,但这个140行的程序代码量算是很大的了)这个代

2012-12-05 22:50:29 911 3

原创旋转卡壳

算法请自行百度,本文专门用来贴代码,想学算法的请直接无视tyvj的某题Code:type int=longint; real=extended; point=record x,y:real; end; line=record a,b,c:r

2012-11-25 22:33:49 503

原创 [HNOI2012]archery

题意:略思路:略实践证明:单纯形法比裸半平面交(nlog^2n)略快!!!!!!半平面交(nlogn)的code:program std;uses math;type int=longint; real=extended; point=record x,y:real; end;/

2012-11-24 10:20:21 572

原创标记永久化的线段树

本文纯属自娱自乐. 前些日子考了一道叫classroom的题目,大意是这样的:给你一个序列a,每次将l到r的元素-k,问你哪次操作后会开始出现负的元素. 正解是二分+差分.很多人打的带标记的线段树.我考场上打的二分,后来有人说线段树常数太大,我告诉他们标记不下放可以提高速度,战神则坚持认为标记一定要下放,于是就有了这篇蛋疼的文章. 直接贴代码,最裸的线段树

2012-11-19 21:52:19 2270

原创 [noi2009]植物大战僵尸

[题目描述] 略[分析]略没什么好说的,一道裸题罢了.NOIP前一周还是温习一些知识吧,虽然NOIP一定不会考...唯一需要注意的是对环的处理,一遍拓补排序即可.最大流的模板是自己YY的,感觉上跟以前写的完全不一样(以前主要是模仿盾盾的),看来这几个月还是有进步的.Code:program pvz;type int=longint;const max=maxlongin

2012-11-04 20:55:49 674

原创 POI EST 题解

[题目描述] 我们手中一共有n个句子，现在要按顺序排成若干行，同一行相邻两句子用一个空格空开，任一行的长度不允许超过m，定义一个不和谐度为相邻两行长度的绝对值之差，我们的目标是使不和谐度最小。[题解] 显然,这道题是一个经典的DP模型.状态有几种设计方法,我设计的状态是F[i,j]表示从1到j,第i+1个到第j个合并的最小代价. DP方程:F[i

2012-10-30 15:47:17 680

原创 CF101E Candies and Stones题解

[题目描述]Little Gerald and his coach Mike play an interesting game. At the beginning of the game there is a pile consisting of n candies and a pile consisting of m stones. Gerald and Mike move in t

2012-10-29 17:06:51 914 1

原创 sequence题解(贪心)

[题目描述] 给你一个序列,你可以给某个数*2或给所有数-1,求最短的把所有的数都变成0的操作序列.[题解] 这道题原本是北京集训的题目,被某某人邪恶的蒯来做noip模拟题. 这道题奇特的地方是,操作中有*2,但又不能直接用二进制搞(因为还有个-1). 一个显然的结论是,在变换的过程中所有的数都不能超过原来的最大的数(如果你看不懂,就继续

2012-10-27 16:20:09 774

原创单队优化DP

[题目描述]略[题解]如果忽略掉K的限制,单队优化是很显然的.加上k后,我们要"延迟"元素进队的时间,在适当的时候再把元素进队.另外,考场上没想到直接用单队维护maxmin,打了个线段树,再加上方程推错,交上去各种WA,最后终于被众人碾压.为了维护maxmin,再开2个队列.以max为例,维护一个元素单减的序列,队首的删除与决策队列同步.(Orz考场上想出来的CCL大神犇)

2012-10-26 15:13:24 8451

原创统计逆序对--函数式线段树

[题目描述]众所周知，lyp喜欢以用各种方式折磨别人为乐，这次，他趁 wars不在时在他的电脑上挂了一把神奇的锁，这把锁需要一串巨长无比的数字密码才可以解开，这个密码由 lyp 自己保管，这样 wars 就没法 Kingdom Rush 了。但 wars 设法从 lyp 的脑袋中挖出了有关密码的信息，这些信息是一列非负整数{An}。而解开密码锁的方式是首先输入这列这数的逆序

2012-10-25 14:50:58 929

原创对fibonacci数列的分析

首先,为了方便描述,我们进行如下定义: (1)我们用Fi(有时为了避免歧义,需要在i的两边加上中括号,而在一般情况下,为了简便起见就不加括号了)表示fibonacci数列的第i项,fibonacci数列是这样的一个数列:F1=1,F2=1,Fn=Fn-1+Fn-2,n为任意的整数.(注意,fibonacci数列是有负数项的).[一]fibonacci数列的组合意义

2012-10-18 20:31:33 905 2

原创数论中的一些性质

(1)关于取模(a+b)%c=(a%c+b%c)%c(a*b)%c=((a%c)*(b%c))%c(a-b)%c=(a%c-b%c+c)%c(a/b)%c=(a%c)*b'(b'表示b的逆元)(a^b)%c=((a%c)^b)%c(a^(p-1)-1)%p=0,p为素数(2)关于gcdGcd(a,b)=Gcd(a-b,b)Gcd(a,b)=Gcd(a%b

2012-10-17 16:57:40 922

原创 pudding题解--链表的启发式合并

[题目描述] 现在有n个布丁排成一排，每个布丁都有一个正整数颜色。有m个操作：第一种操作1 x y 将所有颜色为x改为颜色y。第二种操作2 询问当前有多少段颜色。[数据范围] n,m[题解] 考试时只想到每个颜色建一棵平衡树,进行启发式合并,写的时候各种蛋疼. 知道正解之后发现自己对数据结构和复杂度分析真的是

2012-10-17 15:56:50 765

原创 [奇葩方法]三元环题解

[题目描述]给你一个包含n个点,m条边的无向图,求三元环个数.[数据范围]n,m[题解] 这个方法是lypYY出的一个奇葩方法.ORZlyp,YY都能YY出这种方法. 将所有点分成两类:度数sqrt(m)的. 先求包含第一类点的三元环个数. 由于边很少,所以枚举2条边即可.由于一个点的度不超过sqrt(m),所

2012-10-16 21:26:16 2790

原创 [斜率优化的dp]storage题解

[题目描述]L公司有N个工厂，由高到底分布在一座山上。工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。

2012-10-15 14:54:50 627

原创 [apio2010]特别行动队(斜率优化的dp)

[题目简述] 给你一个序列,你要将他们分成连续的若干份.每一份带给你的收益是ax^2+bx+c,其中x是这一份的和,a[题解] 对于这道题,我们可以很容易的写出方程:f[i]=max(f[j]+a*(s[i]-s[j])^2+b*(s[i]-s[j])+c);因为数据范围是100W,所以我们猜测这个dp要用斜率优化或单调队列优化. 现在

2012-10-15 08:53:47 10675

原创 [hnoi2008]玩具装箱题解(斜率优化的dp)

[题目描述]P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说

2012-10-14 22:16:36 783

原创 [题解]和

[题目描述]给定一个长度为n的序列，你每次可以合并相邻两个元素，新的元素为这两个元素的和。你需要使得若干次合并之后的序列非降，求最小合并次数。[数据范围]n[题解] 这道题的标程用的是n^2log(n)的dp,所以才会有奇葩的1500的范围. 然而,这道题完全可以在O(n^2)的时间内解决. 考虑前i个数的决策.如果我们要合并成合法

2012-10-14 19:34:13 1097 8

原创 [位运算+搜索]下棋

[题目描述]【问题描述】学习之余，小秋秋还喜欢进行棋类活动。。。现在，小秋秋迷上了一个叫tic-tac-toe的游戏。。（这种诡异的名字？原题如此）。这个游戏是两个人轮流在4*4的格子中放棋子，一个人放满了一行或一列或一个对角线就算赢。现在，小秋秋用X先手，已经下过许多步了。他想知道自己现在是否有必胜策略，以及最小的字典序走法。【输入文件】输入有多

2012-10-11 17:45:31 798 2

原创 [遗传算法]冰与火之歌

[题目描述]在著名游戏“冰与火之歌”中英雄们亲自参战了！英雄一开始有HPH点生命值与MPH点魔法值，英雄们能够使用不同的技能，你的英雄会三种技能：雷霆之怒、混沌转移和天使之心。英雄要打一群怪兽，每只怪兽一开始有HPM点生命值，这一群怪兽一开始有NM只，它们的总生命值就有HPM×NM点，随着战斗的进行，怪兽群的总生命值减少。假设当前怪兽群有H点总生命值，那么还存活的怪兽个数为H/HPM取

2012-10-09 15:24:13 1588 5

原创 apio2009 atm题解

题目请自行百度. 这道题和sort很像,甚至比sort还水.在此再次吐槽noip模拟题的难度,完全跟noip不是一个级别. 先缩点,求最长路即可.又打了一遍tarjan,应该不会忘了吧.Code:{$M 10000000}program main;type int=longint;var i,j,k,m,n,high,ans:int

2012-10-04 19:38:27 874 1

原创 sort题解

题目描述有N个数A1..AN，已知一些它们之间的大小关系，形如某个数不小于某个数。Your Task 把这N个数分成尽量少个集合，使得每个集合内的任意两个数的大小关系都是未知的。输入文件第一行 N M 表示有N个数，M个大小关系。接下来M行，每行 i j 表示Ai>=Aj。输出文件一行包含一个整数，最少要分成多少个集合。样例输入4 4 1

2012-10-04 15:29:50 647 2

原创 [10.3]

今天真的是被呸残了,不过也是该呸. 先说上午吧,考了一套模拟题,结果第二题少一个特判,第三题先是输出文件出问题,hash时还没有比较字典序,最后连200都没上,真是愧对向总.考完之后不过几十分钟就A掉了3道题,要是考试时细心一点多好.另外还有一道代码题至今没有动手,自己真的是懒.要是一直这样下去,省选怎么办,noi怎么办,都是一个问题.在大赛当中手贱已经不是第一次了.我们这一届很特殊

2012-10-03 21:57:20 600

原创 [三元组]题解

题目描述: 给出n个形如（i,j,k）的三元组定义一组三元组之间的差为: D(Ta, Tb) = max{Ia−Ib, Ja−Jb, Ka−Kb}−min{Ia−Ib, Ja−Jb, Ka−Kb} 求所有对三元组的差的总和（算了D(Ta, Tb)就不用算D(Tb, Ta)了）数据范围: n时限1s[题解]

2012-09-29 14:18:52 1292 3

原创第k大区间和问题的树状数组实现

问题描述：给定一个整数序列a[1..N]，定义sum[i][j]=a[i]+a[i+l]+……+a[j]，将所有的sum[i][j]从小到大排序（其中i，j满足1输入格式(ktm.in) 第一行有两个整数N，k，其中0 接下来N行每行一个整数。顺序给出序列a的元素。输出格式(kth.out) sum序列

2012-09-28 20:08:50 2228

原创关于导弹拦截问题

这里要讲的是导弹拦截的第二问，即：给定一个序列，求它的最小链覆盖。经典的做法是对每两个可以搞到一起的点连边，用之前讲的h-k算法求一遍最大匹配，但是，这种方法的复杂度可能会退化到O(n^2)。一种有效的解法是利用dilworth定理求一遍最长反链，其复杂度为O(nlog(n))。先介绍一下偏序关系：对集合A中的两个元素，引入一个序的概念，设为R，很明显，要么R（x,

2012-09-23 10:19:38 710 2

原创二分图匹配的H-K算法

算法的具体描述请看http://chenhaifeng.blog.edu.cn/2007/91117.html，我只是来贴代码的。 http://blog.csdn.net/emoizhang/article/details/8004502这里讲的比我详细（虽然都是废话），但他的代码比我的慢。【题目描述】给一个有向无环图，求最小链覆盖【输入格式】第一行两个

2012-09-21 16:42:55 2529

原创【棋盘制作】题解

【题目描述】国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。

2012-09-17 20:03:11 2336

首先，我是要检讨的，因为这个礼拜还是没有完成原来的目标，把sequence和智慧珠A掉。至于其中的原因，除了这个礼拜各种奇葩的状况以外，还有我自己高估了我的能力了。splay和dlx会倒是会了，但要把那两道恶心题A掉，没有百来行的代码是不行的。昨天晚上就花了大半的时间来debug了。结果今天过来看原来的程序，发现自己非重打一遍不可。另外原来说要贴的单旋splay还没贴，因为常数太大了，比邓毛慢1.

2012-09-16 21:47:06 533

原创【9.8】

今天又被虐了，尤其不能忍受的是，竟然连高一的都能虐我了。其实今天的题目不算很难。这次倒不是有什么奇葩算法没搞，是因为第一题拖的时间太长，第二题又太急了，没设计好算法，不断的修改，改了2个小时还没A，至于第三题根本没时间细看，虽然以前看过，但最后连打暴力的事件都没有，于是乎今天就悲剧了。今天的题没有让我想改的欲望，所以先放在这里，以后搞dp时再说吧。晚上研究了一下

2012-09-08 21:09:17 395

原创【9.7】第一篇日志

这是我的blog上的第一篇日志，昨天我们考了noi2005的三道题目，我是各种被虐，唯一有把握拿一些分数的第一题也爆空间了。考完之后，看了题解，第一题是以前就搞过的单调队列，考试时没想到优化，还爆了空间。第二题是裸的splay，很早以前就想学，但一直死抱着treap没学。第三题是要转化成精确覆盖，以前也看过dlx的论文，但一直没有编程实现。总之，自己暑假浪费了太多时间，几乎没有什么收获

2012-09-07 20:14:54 660 1

原创线性筛法的应用

线性筛法最基础的功能就是求[1,n]中的素数,以此为基础,可以对他进行一些变形。变形后的线性筛法可以实现许多其他的功能。(下文中的tot均指一定区间内的质数个数) 先看一道简单的问题：求[1,n]中的m个数的最大质因子的序数(hdoj2136) 这个问题可以利用线性筛法打一个质数表,然后二分答案,复杂度为O(n+mlog(tot))。

2012-08-25 10:55:12 1227

原创一个左偏树的经典应用

以后写文章前先Orz Jerrydeng. 之前讲过左偏树在dispatching中的应用,但是那还不够经典.左偏树最经典的应用,就是黄源河大牛05年论文中的那道例题. 题目是这样的:给一个序列a,要求你构造一个长度与a相同的非降序列b,使sigma(abs(ai-bi))最小黄源河对这个问题进行了细致的讲解,但是里面的证明略显学术了,一般的人(比如我)看了一半

2012-08-23 14:29:56 1005

空空如也

空空如也