sqyon-CSDN博客

原创 [bzoj]-1901-Zju2112 Dynamic Rankings-可持久化线段树

动态查询区间第K大值，单点修改，树状数组套可持久化线段树，线段树中每个代表的相同区间的节点组成了一个树状数组，这样就可以logn的查询前缀和了。写了好长时间，调了好长时间，毕竟蒟蒻 #include #include #include #include #define maxn 110086 using namespace std; struct node { int l, r, s;

2015-03-03 11:06:54 649 2

原创 [poj]-2104-K-th Number-可持久化线段树

区间静态查找第K大值，无需修改，先离散化。马上省选了就没时间详细写了╮(￣▽￣)╭ #include #include #include #define maxn 100010 using namespace std; struct node { int l, r, s; }t[maxn * 20]; struct A { int n, i; }in[maxn]; int n, m,

2015-03-02 13:59:43 518

原创你好CSDN

博客搬家了http://sqy_on.jd-app.com/现在开始停止更新，谁让京东突然说不干了，哼！

2015-02-16 20:36:19 875 1

原创 Happy New Year!!

你好！2015！还在CH上写着题突然发现2015已经悄悄的来了，一年这么快就过去了，现在我还觉的去年寒假培训只是昨天的事情。一年来我从刚刚熟练语法的蒟蒻到现在能拿省一的蒟蒻，变化真的很大。这也是我生命中最劳累最痛苦的一年，但也是我生命中最令我印象深刻的一年。踏入二中的校门，就被门口往年竞赛保送生们的照片吸引了，我于是对竞赛产生了无比崇敬的心。计算机竞赛，我刚

2015-02-16 20:33:55 501 1

原创 [Poj]-1679-The Unique MST-N久没写代码的后果╮(￣▽￣)╭

NOIP后好久没写代码了，恶补了一个月的文化课感觉自己萌萌哒ˉ﹃ˉ 翻了翻暑假的PPT，都™的是省选++的题，丧心病狂 QQ上和zrt大神和gmh大神聊了聊，感觉自己差的东西好多╮(￣▽￣)╭ =====再扯就写不完了=====分割线===== 原题链接题意就是给你一个图，判断最小生成树是否是唯一的很容易想到的就是看看是否存在非严格次小生成树，就可以判断最小生成树是否唯

2015-02-16 20:31:40 500

原创 Poj-1330-Nearest Common Ancestors-倍增LCA

代码很好理解（我觉得是）好吧，这么渣的代码根本就是我自己写的(ノ=Д=)ノ┻━┻ LCA倍增代码 #include #include #include #include #include #include #include #define maxn 10010 #define lg 20 #define inf 0xefffffff using namespace s

2015-02-16 20:30:16 464

转载 [搬运]关于扩展欧几里得与同余方程

什么是GCD？ GCD是最大公约数的简称（当然理解为我们伟大的党也未尝不可）。在开头，我们先下几个定义： ①a|b表示a能整除b（a是b的约数） ②a mod b表示a-[a/b]b（[a/b]在Pascal中相当于a div b） ③gcd(a,b)表示a和b的最大公约数 ④a和b的线性组合表示ax+by（x,y为整数）。我们有：若d|a且d|b，则d|ax+by（这很重要！）

2015-02-16 20:28:28 534

原创 [USACO]-4.2-完美的牛栏-二分图匹配

描述农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。给出奶牛们的爱

2015-02-16 20:26:44 1209

原创 [SPOJ]-1481-寻找素数项-miller rabin

【题目描述】设数列{an}满足如下递推式： ai=(ai-1+1234567890) mod 2^31，其中i>=2. 给定a1，判断a1，a2，…，a100000是否是素数。若是输出1，否则输出0。【输入格式】一行一个正整数a1，在int范围内。【输出格式】一行，一个长度为100000的01串。第i项个字符对应ai是否为素数。若是则为1，不是则

2015-02-16 20:25:49 641

原创 [Cogs]-693-Antiprime数

693. Antiprime数 – COGS. //部分引用自byvoid.com，代码原创如果一个数X是反质数，则它的约数的个数大于所有Y(X>Y)的约数的个数。也就是说反质数是最小的具有相同个约数的数。寻找不大于N的最大反质数问题可以转化成，寻找不大于N的约数个数最多的最小正整数。求一个数的约数个数可以用乘法原理，例如75=3^1×5^2，则75有(1+1)(2+

2015-02-16 20:21:17 836 1

原创 [Cogs]-1032-最小交换排序

奇♂怪的题，我用了丧心病狂的方法，有必要写下题解最小交换排序【问题描述】小x最近切了一道很水的排序题，但是在AC之后，他想到了一个问题：给定n个不相等的整数，将其按从小到大排序，你每次可以对任意一对数进行交换，问最少的交换次数是多少？【输入】第一行：一个整数n 第二行：n个用空格隔开的正整数ai，-2^31 【输出】一

2015-02-16 20:13:48 669

sqyon的算法博客BnK&BF^2tp%T