ACM的记忆-CSDN博客

原创【Learning】适妞来学插头 dp

极其仰慕邝斌巨巨！！！！！！ Orz资料http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710343.htmlProblem Listhttp://acm.hust.edu.cn/vjudge/contest/view.action?cid=23691#overviewStep By StepA - Eat

2013-05-09 20:20:15 2488

原创【Learning】适妞来学SA

Contesthttp://acm.hust.edu.cn/vjudge/contest/view.action?cid=23305#overviewTemplate sa[i]=j表示str+i这个字符串在所有后缀中第j小rank[i]=j表示后缀中第i小的是str+j const int N = 5e4 + 9;namespace Suffix_array{

2013-05-02 22:19:15 1906 2

原创 ACM and String

字符串理论, 多串匹配与AC自动机例题http://acm.hust.edu.cn/vjudge/contest/view.action?cid=21239#overviewA HDU 2222木板题，统计包含个数#include #include #include #include #include using namespace std;const int

2013-03-22 23:11:47 1845

原创 To do list

The Most Important 图论你妹妹A 动态维护凸包 / mutiset / 离线树状数组 / 平衡木http://acm.nbut.cn/Problem/view.xhtml?id=1348http://blog.csdn.net/c3568/article/details/8549325From Ac：#include#include

2013-03-02 23:52:24 1624 2

原创 [Learning] SAM

From cxlove资料http://fanhq666.blog.163.com/blog/static/8194342620123352232937/题目http://www.spoj.pl/problems/NSUBSTR/ 这题基本上就是套个木板T_T 。借鉴的cxlove 和 UESTC 神奇的后缀三兄弟 Orz cxlove mua ~

2013-02-27 19:44:25 1518

转载 Template extends xiaodao @version1.0

/** Header .. **/ //{#define LOCAL#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #in

2013-02-12 17:28:13 1187

原创【主席树】跟岛娘学主席树

A http://www.spoj.com/problems/DQUERY/岛娘的资料：http://paste.ubuntu.com/1426159/http://paste.ubuntu.com/1426225/题意：给一个序列，求某段区间内的不同元素个数。解法：1、离线 + 树状数组将询问按照左端排序，维护元素第一次出现位置，树状数组。const in

2013-01-30 03:51:45 6497 3

原创【数位dp】 Step by Step

看到诸位神牛的代码和Blog，我也来班门弄斧学一下数位dpStep0：找木板和资料向ftiasch 和 edward_mj （窃笑，师父们T_T）求了资料，得到一个好板子——BUPT 某神的BlogStep1：撸水题HDU 2089 直接暴力就可以，不过还是老老实实地数位dp一把，基本是板子题目。HDU 3555 同上的数位DPUESTC 1307 前导0 建立状态原来

2013-01-25 03:38:23 4576 2

原创 codeforces 214 E [Prob 366 E] 一朝不做题，回到解放前。

题目叙述http://codeforces.com/problemset/problem/366/E其实就是找 n * m 矩阵中数字 x 和数字 y 的最远距离。算法n * m 的。不知道 cf 上面那些人为啥都好慢。。。这题说白了就是求最远哈密顿距离。那为啥不用武森的论文呢。http://www.cppblog.com/sonicmisora/archive/2009/09/14/9

2013-11-25 16:24:58 3171 3

原创回看大学这四年 ACM

新生大一来的时候还是一个毛头小子，什么都不会。打个校赛，依稀记得第一题是给一个矩形和一个半径 r ，问能不能放进两个圆。当时wa了26发有余才过掉，成为历史奇迹。。。由于 NOIP 的阴影，大学便开始从事 ACM 的事情。渐渐从以 ACM 为乐到最终爱上 ACM 。一切以 ACM 为重，走火入魔到感觉世界上除了 ACM 没有啥东西了。KeepItSimpleStupid校赛之后组了个队伍

2013-11-19 12:43:48 6367 3

原创【MZ】CF 363E #211 (Div. 2)

problem：给一个n*m的矩阵，每个cell有个值。定义一种cricle，半径为r(这个我就不解释了。。)。选两个没有公共cell的circle使其和最大，并输出有多少中选择。think1.预处理每个circle的值。n^3. 这个先存一下每一列sum(a(i,1) + a(i,2) + …… + a(i,j))。然后找到圆心为(i,j)这个circle的第ii行时，可以O(1

2013-11-12 02:16:57 2514

原创 2013 ACMICPC Hangzhou Ants

Ants题目描述给一棵边权树，一直蚂蚁从一个节点爬到另一个节点获得的分数是路径上的所有边异或和。m 个询问，求第k大。解法首先求出根节点到所有节点的异或和，那么节点-> 节点的异或和就是两个根到节点的异或和的异或和。将所有的节点插入 Trie 树中，然后对于 n 个节点维护一个优先队列——就是这 n 个节点在Trie 树中的位置和当前的异或值。还是把询问离线从小到

2013-11-11 00:42:54 3670

原创 2013 ACMICPC Hangzhou Rabbit Kingdom

Rabbit Kingdom题目描述给一个N个数的序列，M个询问，每个询问两个数L , R 。问 [L , R] 中有多少个数和区间中所有数（除了自己都互质）解法首先肯定要O(N * sqrt(N)) 预处理出每个数互质的话左右分别能延伸到什么地方，记为l[i] , r[i].接下来就有两种解法了Solution Of cxlove 她是爱酱，喵~ http:

2013-11-11 00:05:22 4321 8

原创【MZ】CF 356A - 356D #207 (Div. 1)

A. Knight Tournamentproblem输入 n m 和 m 行每行 l r x 表示把区间[l, r]中除了x还没有值的变成x问最后每个n的值分别是多少，没有就是0think线段树codeint val[333333<<2];void update(int l, int r, int k, int L, int R, int x){ i

2013-11-07 22:53:04 2650

原创【MZ】CF 358D - 358E #209 (Div. 2)

D. Dima and Haresproblem输入n (1 ≤ n ≤ 3000) a1 a2 ... an. b1, b2, ..., bn. c1, c2, ..., cn. n只兔子，每只兔子喂一遍，abc分别是旁边两只都饿着一直饿着一直饱着两只都饱着的joy值，按照某种顺序喂，求最大joy和。think两边的情况太模糊。。我纠结了很久。。d

2013-11-07 22:33:17 2548

原创【MZ】CF 359C - 359E #209 (Div. 2)

C. Prime Numberproblem:输入 n and x (1 ≤ n ≤ 105, 2 ≤ x ≤ 109) a1, a2, ..., an (0 ≤ a1 ≤ a2 ≤ ... ≤ an ≤ 109). x是素数1/(x^a1) + 1/(x^a2) + …… + 1/(x^an) 可以变为 t/s 其中 s = x ^ (a1 + a2 + …… + an)

2013-11-07 21:50:28 2647

原创【MZ】hdu 4117 AC自动机DP + 线段树优化

problem:给你N个字符串， N(1 4), 所有穿的长度加一起不超过 3 * 105.每个串有个值。这个值[-1000， 1000].问不打乱字符串顺序，从中取若干个字符串，使得前一个串是后一个串的子串，求满足前面调条件的字符串值得和最大，求这个值。think:建立AC自动机。后面检查取了以每个字符串是最后取的串的最大值。那么检查第i个字符串的时候，就是这个字

2013-10-28 22:11:30 2585

原创 2013 ACM-ICPC 成都总结

Boardhttp://winguse.cloudapp.net/现场题目情况A37/160B44/355C3/14D40/286E1/2F122/424G3/52H165/189I0/46J105/434真实回放上来 SM 读A ， zxa 读 B，我这个英

2013-10-23 17:47:48 2409

原创【MZ】hdu 2243 AC自动机 + 矩阵加速

problem:给你 n 个病毒，问长度为 [1, m] 的，包括病毒的有多少。全都是小写字母。think:和 poj 2778 有点像。不一样的是：1) 这个是求包括的，我这么做的，加一维用来表示已经包括了病毒的状态。2) 求长度是 [1, m] 的。在矩阵里面维度变成二倍。[A 1][1 0] 左下面的 1 就是最后所求。A是矩阵的话，就把 1 变成 I

2013-10-19 12:52:26 2029

原创【MZ】ZOJ 3494 BCD Code AC自动机+数位DP

problem：给你 n 个由 01 串组成的病毒。(0一个数的 BCD 编码为每个数字变成四位的二进制(如127 would be:0001 0010 0111)。问从x到y有多少个数其BCD编码中没有病毒。（0think:用 AC 自动机得到每个状态，每个状态是否已经构成一个病毒，每个状态后面加一个数字后转移到哪个状态。有了这些处理，就是个简单的数位 DP 了。

2013-10-17 02:03:18 2067

转载【字符串】转自小岛

【专题】字符串理论（建设中。。）Posted on November 20, 2012 by xiaodao课文http://www.cppblog.com/mythit/archive/2009/04/21/80633.htmlhttp://hi.baidu.com/htwvlmsfqsnpswr/item/497be6079be1b668d45a11afht

2013-10-14 15:40:58 2286

原创【DP】

题源：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27634题意：三个数，第一个数N， R， Q。 1N < 101, 000, 0R Q1, 000。找出最大的没有前导零的由 N 的若干位不打乱顺序构成的数，设这个数%Q==R. 如果不存在输出Not found思路：复杂度1000(N长度)*1000

2013-10-10 19:42:10 1962

原创 ACMICPC 2013 长沙 F 题Curve in Circle

题目链接http://acm.zju.edu.cn/changsha/showProblem.do?problemId=27题目大意一个半径为 R 的洞里面有一个半径为 r 的圆盘，圆盘内部有个凸包，每个点给你。用一支笔画住洞和圆盘连线延长线的凸包上点，在凸包上转一圈，问形成的路径长度是多少。Tag计算几何·凸包、点数值积分·自适应辛普森、路径积分求导解法

2013-09-25 02:03:42 3719 3

原创 2013-ACMICPC Nanjing Online 05 Polygon

Polygon题目大意给一个简单多边形和一条抛物线，问抛物线在简单多边形内部的长度和是多少。Tag积分·辛普森计算几何·点，线解析几何解法给一个例子——多边形 ABCDEF和抛物线我们算出抛物线和多边形的焦点 GHIJ。那么就能很简单确定我们需要的积分区间 G->H 和 I -> J于是我们要做的事情就简单了——1.算出来每条线段与抛物线

2013-09-21 22:17:07 3855 4

原创 2013多校九1003-HDU4688-DP+计算几何

不讲题意了。思路：状态就是DP(i, j)表示i前面的切好了，j后面的切好了，求i到j这一节的答案。DP思想就是这样。计算几何真心不会写。计算几何是抄师傅的。const int N = 222;const double eps = 1e-10;int vis[N][N];//这个状态求过double res[N][N];double to[N][2];

2013-08-21 01:13:34 3117 1

原创补一个简单的数据结构——带权并查集

讲解http://www.cnblogs.com/wally/archive/2013/06/10/3130527.htmlCodeint fa[N];LL dist[N];void init() { for (int i=1;i<=n;++i) { fa[i]=i; } RST(dist);}int find(int x){ int y =

2013-08-11 19:27:01 2119

原创【Learning】跟着kuangbin巨巨学概率dp

资料http://www.cnblogs.com/kuangbin/category/417528.html虐题http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28939#overview

2013-08-11 17:33:14 2036

转载 FFT

Module#define L(x) (1 << (x))const double PI = acos(-1.0);const int N = 17, Maxn = L(N + 1);double ax[Maxn], ay[Maxn], bx[Maxn], by[Maxn]struct FFT{ private : int revv(int x, int bits)

2013-08-04 21:40:13 1807

原创【Learning】跟 Hime 混 Splay

模板题http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=13565Code

2013-07-14 13:35:38 821 1

转载 [Open Ural FU Personal Contest 2013]E.Pear Trees wuyiqi's method

1965. Pear TreesTime limit: 1.0 secondMemory limit: 64 MB题目链接http://acm.timus.ru/problem.aspx?space=1&num=1965题目叙述给一个 n 个数的排列n 问是否可以将这个排列拆成两个子序列使得子序列严格递增 | 递减比如63 5 1 2 6

2013-06-23 18:32:24 1584

原创 [Open Ural FU Personal Contest 2013]J. 皇后像廣場

很赞的一个模拟题目！我能写出来说明我结构十分清晰！！J. 皇后像廣場题目链接http://acm.timus.ru/problem.aspx?space=154&num=10题目大意给 9 个 4 * 4 的数字矩阵。要求拼接成 10 * 10 的矩阵。保证有解。要求输出一组。题目解法肯定是一个暴力题目，关键就是暴力的姿势问题。一共有 9！种排

2013-06-22 20:50:07 1450

原创 [2013 Codejam Round 1B Problem B] 呵呵。。。

题目叙述(version xiaodao):就是有一个水晶从无线高往下坠落如果有障碍会等概率向两边滑现在往下扔 n 个水晶问某个位置有水晶的概率。解法按照如下方法，按照从低往高的顺序三角形两条直角边分层那么(X , Y) 所在位置的层号也就是 (abs(X) + abs(Y)) / 2我们可以看出每层的方块个数是 1 ， 5 ， 9 。。。。 4

2013-05-05 03:03:08 1064

原创【MZ】CF #180 (div1)

A. Parity Gameproblem：在一个01串中。可以去掉最前面的一个字符；可以在后面加一个字符，若该串有奇数个‘1’则末尾加字符‘1’否则加‘0’。问能否把a串变为b串。think：如果偶数个‘1’则‘0’可以在结尾任意加。又因为前面随便去掉，所以可以在想要的位置去掉前面的‘1’然后结尾加‘1’。所以偶数(n)个‘

2013-04-23 00:14:31 1769 1

原创 [数论]中南大学 2013 校赛 G 题解题报告

Balls and Boxes题意N 个盒子，原本有一些球；每次可以向 M 个不同的盒子里面各放一个球，问最少要多少次操作能让盒子里面的球数量相等。不可以输出 -1.解法：一开始写了一个姿势 wa了，换了一个姿势就过了方法是——记录所有盒子的最大值 Max ，和 Sum ，最小值 Min。那么如果最后能够达成，高度为H ，那么肯定满足以下三个条

2013-04-14 23:58:59 1266 1

原创 [操作系统实验] Todolist

typedef struct SimpleCmd{ int isBack; char **args; char *input; char *output}以上是原来的改为typedef struct Cmd{ int isBack; //时候为后台任务 int cmdCount; //单个命令的数目，就是以管道分隔符‘|’分割开来的命令的数目 cha

2013-04-07 13:25:59 841

原创 [操作系统实验] Todo - list

typedef struct SimpleCmd{int isBack;char **args;char *input;char *output}以上是原来的改为typedef struct Cmd{int isBack; //时候为后台任务int cmdCount; //单个命令的数目，就是以管道分隔符‘|’分割开来的命令的数目

2013-04-07 13:24:32 871

原创不太常见的 C++ 库函数

Math#include / #include erf(x) 累积分布函数是指随机变量小于或等于的概率，用概率密度函数表示为可以化作标准正态分布函数累积密度：可以化作fmod(x , y)原型：extern float fmod(float x, float y);功能：计算x/y的余数说明：返回x-n*y，符

2013-04-01 16:34:02 1117

原创 ubuntu 12.10 x64 下编译新内核 + 系统调用方法

吐槽：一个小东西弄了好几次不成功，x64就是要special judge 啊。。。sad download老师给的地址有点儿慢，推荐给力的 https://www.kernel.org/ 这个地址。下载最新的稳定 3.8.4 版本复制kernel到/usr/src中 sudo cp linux-3.8.4.tar.xz /usr/src然后在图形界面

2013-03-31 22:13:45 1692

原创 [ACdream原创群赛の数树]解题报告

比赛地址ACdream原创群赛の数树A 递推数题目叙述求递推数列的a[a[a[a[n]]]]解法方法是暴力。。。一开始用一个暴力的代码（复杂度 O(n)）跑 1min 左右跑出来 a[n] 对于 1e9+7 的循环节 222222224LL ，然后继续跑出来 222222224LL 的循环节 183120LL 然后跑出来 183120LL 的循环节 240

2013-03-15 22:36:24 2410 3

原创 SRM 572 Div 1 500 题解

Mark这题难在细节上啊！不是TLE时间上啊！不要太关注一个题目的难点因为有可能判断错误T_T原题描述Problem Statement Elly and Kristina play a game called "Bulls". Initially each of them thinks of a non-negative integer w

2013-03-07 01:22:45 1320

空空如也

空空如也