• avatar just_sort 2017-01-13 16:38:57

    poj 2891 (一般模线性方程组)

    一般模线性方程组裸题,记录下模板。模板来源:http://www.cnblogs.com/Missa/archive/2013/06/01/3112536.html #include <stdio.h> typedef long long LL; const int maxn = 1e

    来自 just_sort
    00
  • avatar just_sort 2017-01-13 15:57:52

    Fighting For 2017 Season Contest 1 题解

    题目过于简单,就不在线讲题了,看这个题解即可。 A: 签到题1,记录个id和val,然后再结构体排序,然后用两根指针,一个在前一个在后边输出边移动输出即可,直接计算位置也可以。 #include <bits/stdc++.h> using namespace std; struct

    来自 just_sort
    00
  • avatar just_sort 2017-01-13 15:28:55

    POJ 1006 Biorhythms 中国剩余定理学习

    题意: 生理周期 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 132804 Accepted: 42455 Description 人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和

    来自 just_sort
    00
  • avatar just_sort 2017-01-13 14:05:15

    紫书 例题10-18 概率 UVa 11346

    题意:在[-a,a]*[-b,b]区域内随机取一个点P,求以(0,0)和P为对角线的长方形面积大于S的概率(a,b>0,S≥0)。例如a=10,b=5,S=20,答案为23.35%。 分析: 根据对称性,只需要考虑[0,a][0,b]区域取点即可。面积大于S,即xy>S。xy=S是一

    来自 just_sort
    00
  • avatar just_sort 2017-01-13 13:15:53

    紫书 例题10-18优惠券 UVa 10288

    题意:大街上到处在卖彩票,一元钱一张。购买撕开它上面的锡箔,你会看到一个漂亮的图 案。图案有n种,如果你收集到所有n(n≤33)种彩票,就可以得大奖。请问,在平均情况 下,需要买多少张彩票才能得到大奖呢?如n=5时答案为137/12。 分析:设f[i]代表还有i个优惠券没有收集到的期望开箱次数

    来自 just_sort
    00
  • avatar just_sort 2017-01-13 12:00:25

    紫书 例题 10-17 UVa 1639

    题意:有两个盒子各有n(n≤2*10 5 )个糖,每天随机选一个(概率分别为p,1-p),然后吃一颗糖。直到有一天,打开盒子一看,没糖了!输入n, p,求此时另一个盒子里糖的个数的数学期望。 分析: 根据期望的定义,不妨设最后打开第1个盒子,此时第2个盒子有i颗,则这之前打开 过n+(n-i)

    来自 just_sort
    00
  • avatar just_sort 2017-01-12 21:36:50

    紫书例题10-16 UVa 12230 过河

    题意:你住在村庄A,每天需要过很多条河到另一个村庄B上班。B在A的右边,所有的河都在 中间。幸运的是,每条河上都有匀速移动的自动船,因此每当到达一条河的左岸时,只需等 船过来,载着你过河,然后在右岸下船。你很瘦,因此上船之后船速不变。 日复一日,年复一年,你问自己:从A到B,平均情况下需要多长

    来自 just_sort
    00
  • avatar just_sort 2017-01-12 21:10:28

    紫书例题 10-15 杆子的排列 UVa1638

    题意:有高为1, 2, 3,…, n的杆子各一根排成一行。从左边能看到l根,从右边能看到r根,求有多少种可能。 分析: 设d(i,j,k)表示让高度为1~i根杆子排成一行,从左边能看到j根,从右边能看到k根的方 案数。为了方便起见,假定i≥2。如何进行递推呢?首先尝试按照从小到大的顺序按照各个

    来自 just_sort
    00
  • avatar just_sort 2017-01-12 20:20:21

    hdu 6000 Wash 贪心

    题意:L堆衣服,N台洗衣机,M台脱水机,给出每台机器的每次工作的时间 Wi,Di。一台机器一次只能给一堆衣服工作,求洗完衣服最少需要多少时间。 分析:2016 ccpc/final的一个题,这个贪心这是好难想到啊。看了这篇题解:见这里,思想就是最小洗完时间加最大脱水时间取大,仔细想想这个贪心确实是

    来自 just_sort
    00
  • avatar just_sort 2017-01-12 11:14:11

    紫书 例题 10-13 危险的组合

    题意:一个栈中只能放入U和L,问存在连续3个以上U(危险组合)的个数为几个 分析:这个题的解法有多种。 解法1: 用总组合数-安全组合=危险组合。d[i]表示第i个位置以L结束的序列,所以就有d[i] = d[i - 1] + d[i - 2] + d[i - 3]。 解法2:设答案为f(n)

    来自 just_sort
    00
  • avatar just_sort 2017-01-12 10:36:12

    例题 10-12 纸牌游戏 UVa 1637

    题意:36张牌分成9堆,没堆4张,每次可以拿走某两堆顶部的牌,但需要的点数相同,如果有多种拿法就等概率随机拿,问拿完所有牌的概率。 分析:直接用9元组表示当前状态,即每堆剩余的牌数,状态数为5^9=1953125。设d[i]表示状态i对应的概率,则根据全概率公式,d[i]为后继状态的成功概率的平均

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 21:12:55

    紫书 例题 10-11 UVa11181

    题意:n个人去购物,要求只有k个人买东西。给你n个人每个人买东西的概率,然后要你求出这n个人中有k个人购物并且其中一个人是ni的概率pi。 分析:设B是n个人中选择k个人。设Ai是除了第i个人外选择k - 1个人。那么P = P(Ai)∗ pi / P(B);所以用dfs求出B,和Ai的概率,然后

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 20:39:55

    紫书 例题10-10 奶牛和轿车 UVa10491

    题意:见紫书326页翻译。 分析:本题其实就是一道数学题,计算出最终的概率计算公式输出即可。使用全概率公式来计算。打开c个牛门后,还剩a-c头牛,未开的门总数是a+b-c,其中有a+b-c-1个门可以换(称为“可选门”)。那么换到轿车的概率就是可选门中含有含有车的门数除以总的可选门数。分两种情况:

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 20:25:09

    紫书 例题 10-9 决斗 Uva1636

    题意:你和人决斗。决斗规则如下:用一把有n个弹槽的左***,对着自己脑袋来一枪,孰生孰死看天意。现在对方已经装了若干发子弹,并随机转了一下转轮,子弹呢用一个01序列表示,0表示这个弹槽无子弹,1表示有子弹。对方先对着自个脑袋开了一枪,嗯,你只听到了一声’click’,人还好好的,是空枪。现在轮到你了

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 15:51:28

    紫书例题 10-8 Uva 1262

    题意:给出两个6行5列的字母矩阵,一个密码满足:密码的第i个字母在两个字母矩阵的第i列均出现。然后找出字典序为k的密码,如果不存在输出NO 分析:来自紫书题解, 解法1:我们先统计分别在每一列均在两个矩阵出现的字母,然后从小到大排好序。 对于第一个样例来说,我们得到ACDW、BOP、GMOX、

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 15:23:07

    紫书 例题 10-7 UVa10820 欧拉函数

    题意:求1~n之间共有多少对互质的数 分析:如果用普通方法一个一个判断,时间复杂度是O(n^2),会超时。但是可以利用欧拉函数和筛法在O(nloglogn)时间内把50000内与每个数互质的正整数的个数求出来。当求有多少对时,只需令sum[n]*2 —1即可。 解题方法: // //Creat

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 15:18:57

    紫书 例题10-6 无关的元素 UVa1635

    题意:给定n个数a1,a2····an,依次求出相邻两个数值和,将得到一个新数列,重复上述操作,最后结果将变为一个数,问这个数除以m的余数与那些数无关?例如n=3,m=2时,第一次得到a1+a2,a2+a3,在求和得a1+2*a2+a3,它除以2的余数和a2无关。1<=n<=10^5,

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 13:12:28

    例题10-5 GCD等于XOR UVa12716

    题意:输入整数n,(1<= n <= 30000000),有多少队整数(a, b)满足: 1<=b<=a<=n,且gcd(a, b) = a XOR b。例如 n = 7时,有4对:(3, 2), (5, 4), (6, 4), (7, 6)。 分析:本题看上去难得找

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 11:08:20

    紫书例题 10-4 Uva10791 唯一分解定理

    题意:分解质因子的一个题,将最小公倍数分解质因子,最小的和sum便为各个质因子的相应次方数之和。 此题难点在于几个特殊的情况的处理: (1)当N = 1时,应输出2(1*1=1,sum=1+1=2); (2)当N是素数的时候,输出N+1(N*1=N,sum=N+1); (3)当只有单质因子时

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 10:39:54

    SWUST OJ 2540 少女输出问题

    题目链接:见这里 题意: 中文题目, FFT裸题。 代码如下: // //Created by BLUEBUFF 2016/1/11 //Copyright (c) 2016 BLUEBUFF.All Rights Reserved // #pragma comment(linker,&qu

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 10:03:23

    紫书例题10-3 Uva10375 唯一分解定理

    题意:已知C(m,n)=m! / (n!*(m-n!)),输入整p,q,r,s(p>=q,r>=s,p,q,r,s<=10000),计算C(p,q)/C(r,s)。输出保证不超过10^8,保留5位小数 分析:初步分析,本题时间上基本上没有太大的限制,可以暴力求解C(m,n);

    来自 just_sort
    00
  • avatar just_sort 2017-01-11 09:33:48

    紫书 例题 10-2 不爽的裁判 UVa12169 ex_gcd

    题意:已知xi=(a*xi-1+b) mod 10001,且告诉你x1,x3………x2*t-1,让你求出其偶数列 分析:枚举a,然后通过x1,x3求出b,再验证是否合适 1.设a, b, c为任意整数。若方程ax+by=c的一组整数解为(x0,y0),则它的任 意整数解都可以写成(x0+kb’

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 23:42:34

    Letter-moving Game 1月8日

    题目链接:见这里 题意:给出两个只包含小写字母的字符串S 和 T ,S 和 T的字母组成一样但字母顺序可能不同。每次操作可以将 S 中的任意一个字母移到 S的开头或者末尾,求将 S 变成 T的最少操作数。n <= 1000。 分析:下面题解描述来自Wannafly每日题解: 首先我们先得

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 23:19:25

    例题10-1 巨大的斐波拉契数 Uva 11582

    题意:让你求斐波拉契数列的第a的b次方项模n的结果。 分析:由于是每一项都对n取模,所以不同的n值都会对应一个周期,只要循环一下。当前项等于f1,前一项等于f0时就可以跳出循环了。a的b次方,可以用幂取模的知识,快速分治求出。注意第二个样例a要先模一下周期,不然会有溢出。刚开是long long

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 21:50:52

    ZOJ 3537 Cake (区间DP6)

    题目链接:见这里 题意:求将一个凸n多边形分成n-2个三角形的最小费用 分析:这个题首先要判是不是凸包,如果是凸包,那么从逆时针开始枚举分割的起点,和终点,注意起点从n - 3开始,确定起点和终点之后,枚举中间点转移。 dp[i][j]代表将凸包的子多边形i j分成(j−i

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 20:17:30

    POJ 3280 Cheapest Palindrome (区间DP5)

    题意: 给出一个由m中字母组成的长度为n的串,给出m种字母添加和删除花费的代价,求让给出的串变成回文串的代价。 分析:我们知道添加最少的字母让其回文是经典的DP。可以转化为LCS来解,即枚举中间点,计算前后的最长公共子序列长度MAX,最后总长度减掉2倍MAX就可以了。那么这个题多了一个价值,我们不

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 17:39:13

    nyoj746 整数划分 (区间DP4)

    题意:给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号,将n分成m段,求出这m段的最大乘积 分析:根据区间dp的思想,我们定义dp [ i ] [ j ]为从开始到 i 中加入 j 个乘号得到的最大值。 那么我们可以依次计算加入1—-m-1个乘号的结果 而每次放入x个乘号的最大

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 17:02:22

    POJ 1141 Brackets Sequence (区间DP3)

    题意:给出一串由‘(‘)’‘ [ ’ ’ ] ‘组成的串,让你输出添加最少括号之后使得括号匹配的串。 分析:那么假如我们知道任意 i 到 j 从哪儿插入分点使得匹配添加括号最少。那么我们定义ans[i][j]表示 i 到 j 从哪儿分开使得匹配添加括号最少,如果i和j匹配我们可以让ans[i][j

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 16:40:09

    POJ 2955 Brackets (区间DP2)

    题目链接:点击打开 题意:给出一串的只有‘(’ ‘)’ ‘[‘ ‘]’四种括号组成的串,让你求解需要最少添加括号数让串中的所有括号完全匹配。 分析:定义dp [ i ] [ j ] 为串中第 i 个到第 j 个括号的最大匹配数目 那么我们假如知道了 i 到 j 区间的最大匹配,那么i+1到 j

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 14:36:52

    NYOJ 737 石子归并问题 (区间DP1)

    题目链接:见这里 题意:中文题目 解题方法:基础区间DP。要求n个石子归并,我们根据dp的思想划分成子问题,先求出每两个合并的最小代价,然后每三个的最小代价,依次知道n个。定义状态dp [ i ] [ j ]为从第i个石子到第j个石子的合并最小代价。则有: dp[i][j]

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 14:10:21

    CodeForces 663E - Binary Table FWT

    【题目链接】见这里 【题意】 给出一个n(n≤20)行m(m≤105)列的01矩阵。每次操作可以将某一行取反或者将某一列取反。要求操作后的矩阵中的1的个数最少,求最小个数。 【解题思路】 由于行比较少,我们考虑状压。状压每一列的状态,sta第i位为1,代表第i行为1,否则为0。现在我们有一个

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 10:41:41

    HDU 5909 FWT 加速集合异或

    【题意】 Byteasar有一棵nn个点的无根树,节点依次编号为11到nn,其中节点ii的权值为v_iv​i​​。 定义一棵树的价值为它所有点的权值的异或和。 现在对于每个[0,m)[0,m)的整数kk,请统计有多少TT的非空连通子树的价值等于kk。 一棵树TT的连通子树就是它的一个连

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 09:57:29

    Fast Walsh-Hadamard Transform (快速沃尔什变换)

        这两天在学FWT,找到了一些比较好的学习资料,分享出来。     第一个: http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform     第二个: (主要是觉得这个BLOG里的模板比较好),感觉以现在的智

    来自 just_sort
    00
  • avatar just_sort 2017-01-10 09:18:44

    Educational Codeforces Round 9 E. Thief in a Shop

    【题目链接】点击打开链接 【题意】给定N, K, N种物品每种的价值为Ai,必须装满K个物品的背包,求所有能装的价值,从小到大输出。 【解题方法】其实就是长度为1000的价值向量的k次幂, 存在该价值就为1,否则为0。然后用FFT求K维卷积,用bool数组可以降低精度误差,同时长度不要直接设为1

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 21:01:17

    FFT uoj34 多项式乘法

    【题目链接】 点击打开链接 【题意】告诉两个多项式的系数,求多项式乘法后,每个的系数,多项式长度<=1e5。 【解题方法】 FFT模板题。 【AC代码】 // //Created by BLUEBUFF 2016/1/9 //Copyright (c) 2016 BLUEBUFF.A

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 20:15:42

    例题7-9 万圣节后的早晨 UVa1601

    【题目链接】点击打开链接 【题意】w*h(w,h <= 16)网格中有n(n<=3)个小写字母(代表鬼),要求把它们分别移动到对应的大写字母里。每一步可以有多个鬼移动(均为往上下左右4个方向之1移动),但每一步结束之后,任何两个鬼不能占用同一个位置,也不能在一步之内交换位置。 【解题

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 16:43:28

    HDU 4609 3-idiots FFT 求解计数问题

    【题目链接】 点击打开链接 【题意】 其实题目是给了n条线段。问随机取三个,可以组成三角形的概率。 【解题思路】 下面解题方法摘抄自 kb大神blog 其实就是要求n条线段,选3条组成三角形的选法有多少种。   首先题目给了a数组, 如样例一: 4 1 3 3 4 把这个数组

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 15:55:31

    HDU 1402 A * B Problem Plus FFT

     【题目链接】点击打开链接 【题意】 计算2个大数A*B的值,FFT入门题。记录一下FFT的模板,FFT的学习资料看这里:点击打开链接 【AC代码】 // //Created by BLUEBUFF 2016/1/9 //Copyright (c) 2016 BLUEBUFF.All Rig

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 14:52:27

    FFT算法学习笔记

    【PS】非常详细的FFT总结,适合入门的同学、 【链接】点击打开链接

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 13:55:17

    Atcoder Xor Sum 1月5日

    【题目链接】点击打开链接 【题意】   题意   给定一个整数N,求出有多少对u, v (0 <= u, v <= N),满足存在两个非负整数a和b使得a xor b = u 且 a + b = v。xor为异或操作。   数据   (1 <= N <=

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 12:21:08

    分块法 hdu4858 项目管理 1月5日

    【题目链接】点击打开链接 【解题思路】qwb巨BLOG: 点击打开链接 【AC代码】 // //Created by BLUEBUFF 2016/1/9 //Copyright (c) 2016 BLUEBUFF.All Rights Reserved // #pragma comm

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 10:05:55

    VK Cup 2015 - Finals, online mirror D. Restructuring Company 并查集 set 二分

    【题目链接】点击打开链接 【题意】   题意   给出 n 个元素,q 次操作,操作类型有三种 1 x y :将x 和 y 合并到一个集合 2 x y : 将x,x+1,x+2,...,y 合并到一个集合 3 x y : 询问x 和 y 是否处于同一个集合   数据  

    来自 just_sort
    00
  • avatar just_sort 2017-01-09 09:39:35

    Codeforces Round #204 (Div. 1) B. Jeff and Furik 1月7日

    【题目链接】点击打开链接 【题意】 Jeff和Furik玩游戏。对于一个长为n的序列,为1-n的排列,两个人交替操作。Jeff先手,他会选择一对相邻的数交换。 Furik会先投硬币,如果是正面,他会随机选取一对相邻的数i,i+1,且Pi > Pi+1,进行交换。如果没有可以操作的数对,他

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 21:35:01

    SPOJ Interesting Game 1月6日

    【题目链接】 点击打开链接 【题意】 Alice和Bob玩游戏,一个数字,对于其在十进制下的每一位,玩家可以选择一个数值非0的位,将这个位置的数减去一个非0的数,使得这个位置的数在操作后非负。在某个玩家操作后,所有位置的数字都变为了0,则这个玩家获胜。 假定Alice和Bob都做出最优选择,且

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 20:40:47

    紫书 例题 7-13 快速幂计算 UVA1374 IDA*搜索

    【题意】 给出 n,问说至少计算几步得到 x^n。 【解题方法】 迭代深搜,枚举步数,然后深搜判断是否可行。需要优化,当当前数 now 按照最大方案执行后仍然小于 n,则说明不可行。紫书上说, 为了尽快接近目标应该先枚举较大的数,再枚举较小的数,我试了一下,先枚举小的数跑得比先枚举大的还要快100

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 20:12:30

    紫书 例题 7-11 宝箱 UVA 12325

    【题目链接】 点击打开链接 【题意】你有一个体积为N的箱子和两种数量无限的宝物。宝物1的体积为s1,价值为v1,宝物2的体积为s2,价值为v2.输入均为32位带符号整数。你的任务是计算最多能装多大价值的宝物。例如n=100,s1=v1=34,s2=5,v2=3,那么答案就为86,方法是

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 19:02:04

    紫书 例题7-8 Uva 10603 BFS

    【题意】 有三个杯子它们的容量分别是a,b,c, 并且初始状态下第一个和第二个是空的, 第三个杯子是满水的。可以把一个杯子的水倒入另一个杯子,当然,当被倒的杯子满了或者倒的杯子水完了,就不能继续倒了。 你的任务是写一个程序计算出用最少的倒水量,使得其中一个杯子里有d升水。如果不能倒出d升水的话,那

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:58:10

    紫书 例题7-7 UVA 1354

    【题意】给出了房间的宽度,天平长度为1,天平有左右两个空位,可以放重物或另一个天平,然后有n个重物放到天平上保持天平平衡的情况下问天平最宽延伸是多少。 【解题方法】 这道题十分的有意思,实在不知道怎么做,看了紫书的思路,仍然写不出代码,主要是不知道如何去枚举二叉树。查看了刘老师的标程,终于弄懂了、

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:49:58

    紫书 例题7-6 UVA 140

    【题意】给定一个图(V,E),其中V为顶点的集合,E为边的集合,属于VxV。给定V中元素的一种排序,那么顶点v的带宽定义如下:在当前给定的排序中,与v距离最远的且与v有边相连的顶点与v的距离。给定排序的带宽定义为各顶点带宽的最大值,这个题的题意要花点时间理解,具体可以看紫书 P 196,上面有图,可

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:44:54

    紫书 例题7-5 UVA 129

    【题意】输入正整数n,l,输出由前l个字符组成的,字典序第k小的没有两个相邻重复子串的串。 【解题方法】判断ABCABA是否包含重复子串的方法是这样的:运用回溯法,只要比较当前串后缀,因为回溯法的特性,我们只要考虑当前的情况即可,前面的不用管,这样递归可以保证从头到尾都是成立的,当然后缀要从一个比

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:41:52

    紫书 例题7-4 UVA 524

    【题意】把1-n,连续的放到一个环里,使相邻的数字和为素数,输出所有结果。 【解题方法】回溯法的简单应用。 【AC代码】 // //Created by just_sort 2016/1/5 //Copyright (c) 2016 just_sort.All Rights Reserved

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:39:45

    紫书 例题7-3 UVA 10976

    【题意】给你一个数k,求所有使得1/k = 1/x + 1/y成立的x≥y的整数对。 【解题方法】数论,枚举。枚举所有在区间(k+1,2k)上的y即可,当1/k - 1/y的结果分子为1即为一组解。 【AC代码】 // //Created by just_sort 2016/1/3 //Co

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:37:48

    紫书 例题7-2 UVA 11059 暴力枚举

    【题意】给出一个序列,问这个序列中最大连续累乘的子序列中,最大的值为多少,如果都为负数,则输出。 【解题方法】整个元素最多有18个,大小最大10.所以要开到long long。然后列举所有长度即可。 【AC代码】 // //Created by just_sort 2016/1/3 //

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 17:47:34

    紫书 例题7-10 编辑书稿 UVa11212 IDA*

    【题目链接】点击打开链接 【题意】 可以看紫书 208 页,比较难写就不介绍了。 【解题思路】本题利用迭代加深搜索,也是一道典型的状态空间搜索问题,状态就是1~n的排列,初始状态是输入,终止状态是1,2,……n。由于n≤9,排列最多有9!=362880个,但由于每个状态的后继状态比较多,因此仍有

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 17:07:05

    IDA* 求解埃及分数问题

    【题目链接】点击打开链接 【题意】中文题目 【解题方法】 迭代加深搜索,实质上是限定下界的深度优先搜索。即首先允许深度优先搜索K层,若没有发现可行解,再将K+1后 重复以上步骤搜索,直到搜索到可行解。 在迭代加深搜索的算法中,连续的深度优先搜索被引入,每一个深度约束逐次加1,直

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 15:39:02

    HDU 3507 斜率优化入学习

    【题目链接】 点击打开链接 【题意】大概题意就是要输出N个数字a[N],输出的时候可以连续的输出,每连续输出一串,它的费用是 “这串数字和的平方加上一个常数M”。 【写在前面】 思想参考BLOG : 点击打开链接 【解题方法】斜率优化, 做这个题之前还不知道什么叫斜率优化,或许是有了单调队

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 13:23:43

    HDU 2191 二进制优化 和 单调队列优化

    【题目链接】 点击打开链接 【题意】中文题目 【解法1】 暴力。拆成01背包即可。复杂度 O(n*m*m) int weight[110],value[110],cnt[110]; int dp[110]; int main() { int C; scanf("

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 10:47:28

    HDU 3401 Trade 单调队列优化DP

    【题目链接】 点击打开链接 【题意】 大概就是说一个人现在炒股,他有两种操作,一种是买股票(这个当然是花钱), 一个是卖股票(这里钦定为挣钱)。然后每个人在每天买和卖股票的数量是有限制的,并且还有一个限制是一个人拥有的股票数不能超过MaxP。还有一个人执行操作的间隔必须大于W。问这个人最后最

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 09:37:26

    UESTC - 594 我要长高 单调队列优化DP

    【题目链接】 点击打开链接 【题意】中文题目。 【解题方法】 容易想到一个非常朴素的DP。dp[i][j] 代表第i个儿子,身高为j的最低花费。 dp[i][j] = min(dp[i-1][k] + abs(j - k) * C + (x[i] - j) * (x[i] - j));    

    来自 just_sort
    00
  • avatar just_sort 2017-01-07 14:33:50

    CodeForces - 91B 单调队列 或 线段树

    【题意】给一个序列,从右边开始看,对于第i个数字a[i],在右边找到一个比它小(严格小)的,最靠右的位置,k,输出k-i-1,如果一个都找不到,输出-1。对于序列的每个元素都要输出。 【解题方法1】 线段树。节点保存最小值,每次把节点更新为INF,然后查找整个区间最右边比它小的数的位置。 【代码

    来自 just_sort
    00
  • avatar just_sort 2017-01-07 11:34:20

    HDU 3706 Second My Problem First 单调队列简单题

    【题目链接】点击打开链接 【题意】非常简单,题目很短,自己读一下就好。 【解题思路】 单调队列的应用,维护一个递增的长度为A的单调队列了可以了。但是这题用数组的话,会MLE,反正我是被卡MLE了。所以改用STL的deque实现,可以解决本题。 【AC代码】 // //Created

    来自 just_sort
    00
  • avatar just_sort 2017-01-06 21:11:21

    HDU 3530 Subsequence 单调栈应用

    【题目链接】点击打开链接 【题意】 在一个队列中求一个最长子序列使得该子序列满足最大值与最小值的差大于k小于m求该子序列的最大长度 【解题方法】 维护一个单调递增的栈和一个单调递减的栈,在满足条件时,维护答案最大值即可。 【AC代码】 // //Created by just_sort 2

    来自 just_sort
    00
  • avatar just_sort 2017-01-06 20:22:34

    POJ 2823 Sliding Window 单调队列优化 滑动窗口

    【题意】 n个数,现在有一个大小为w的划窗,窗口每个时刻向后移动一位,求出每个时刻窗口中数字的最大值和最小值。 【解题方法】 求最大值:建立一个单调递减队列,元素从左到右依次入队,入队之前必须从队列尾部开始删除那些比当前入队元素小或者相等的元素,直到遇到一个比当前入队元素大的元素,或者队列

    来自 just_sort
    00
  • avatar just_sort 2017-01-06 15:15:30

    LightOJ - 1265 Island of Survival 脑洞 概率DP 1月3日

    【题目链接】点击打开链接 【题意】 岛上有一个人,t只老虎和d只鹿,每天都会有两个生物随机碰面,有以下几种情况①老虎与人碰面,人被吃掉②老虎与鹿碰面,鹿被吃掉③老虎与老虎,两只老虎同归于尽④鹿与鹿碰面,什么都不会发生⑤鹿与人碰面,人可以选择杀死鹿或不杀鹿(取决于你),问最后人存货下来的最大概率.

    来自 just_sort
    00
  • avatar just_sort 2017-01-06 11:31:22

    Codeforces Round #336 (Div. 1) B - Zuma 1月3日

    【题目链接】点击打开链接 【题意】给出一个长度为n的序列c[i],每次操作可以删去一个回文子串,求将整个序列删除完需要的最少操作数,n<=500 【解题方法】区间DP.区间dp,记dp[i][j]为删完[i,j]这一段的最少操作次数,一种转移是枚举一个k,将这一段分为[i,k]和[k+1,

    来自 just_sort
    00
  • avatar just_sort 2017-01-06 10:49:29

    SPOJ_MINSUB:Largest_Submatrix(二分+单调栈)

    【题目链接】点击打开链接 【题意】 是说给定一个R*C的非负矩阵,试求出一个包含数字数>=K的子矩阵,使得这个子矩阵中最小的数字最大. 【解题思路】              主要是二分答案,即二分那个最小的数字,然后针对每次二分的值mid,可以将原矩阵根据是否满足A[i][j]>=

    来自 just_sort
    00
  • avatar just_sort 2017-01-05 13:41:28

    POJ2082 最大矩形面积 单调栈

    【题目链接】           点击打开链接 【题意】           给了一些h*w的矩形,大小可不等,求可组成的最大矩形面积是多少?单调栈经典题,做法和点击打开链接 完全相同。 【AC代码】 // //Created by just_sort 2016/1/5 //Cop

    来自 just_sort
    00
  • avatar just_sort 2017-01-05 13:18:47

    POJ 2559 Largest Rectangle in a Histogram 单调栈学习

    【题意】             给定从左到右多个矩形,已知这此矩形的宽度都为1,长度不完全相等。这些矩形相连排成一排,求在这些矩形包括的范围内能得到的面积最大的矩形,打印出该面积。所求矩形可以横跨多个矩形,但不能超出原有矩形所确定的范围。           【解题方法】        

    来自 just_sort
    00
  • avatar just_sort 2017-01-08 18:35:29

    紫书 例题7-1 UVA 725

    【题意】 给你一个数字n,用0~9,10个数字组成两个五位数,使得他们的商为n,按顺序输出所有结果。 【解题方法】暴力。直接枚举第二个数字,范围(1000,100000),然后判断即可。 【AC代码】 // //Created by just_sort 2016/1/3 //Copyrigh

    来自 just_sort
    00
  • avatar just_sort 2017-01-04 15:34:26

    1月2日 51 Node 1189 阶乘分数

    【题目链接】 点击打开链接 【题意】中文题面。 【解题方法】 Wannafly的题解,然后再次谢谢qwb巨对我的解答疑惑。对了上面的推导还可以参考一下下面的blog里面约数个数和质因子个数的博客:点击打开链接 【AC代码】 // //Created by just_sort 20

    来自 just_sort
    00
  • avatar just_sort 2017-01-04 13:55:16

    1月2日 Codeforces Round #276 (Div. 1) D. Kindergarten

    【题目链接】 点击打开链接 【题意】 给定一个包含n个元素的数组,我们可以把位置连续的数分为一组,每组至少包含一个元素。 每组对答案的贡献是这个组内最大的数和最小的数的差值。 对于单个元素组成的组,差值为0。输出答案的最大值,1 <= n <= 1e6, 第i个数大小ai(-

    来自 just_sort
    00
  • avatar just_sort 2017-01-03 21:52:44

    51Node Treecnt 1月1日

    【题目链接】点击打开链接 【题意】中文题目 【解题方法】 我们考虑每一条边对答案的贡献。假如这条边一边有a个节点,另一边有b个节点。那么如果我要选中这一条边,我就必须要在两边都选上至少一个节点,且选的节点总个数等于k。我们考虑反面,就是只在一边选k个点,显然方案数是C(a,k)+C(b,k)总

    来自 just_sort
    00
  • avatar just_sort 2017-01-03 19:25:32

    SPOJ Time Limit Exceeded

    【题目链接】点击打开链接 【题意】 【解题方法】             Wannafly的每日一题,通过这个题我学到了新的知识。就是维护如何维护高维前缀和。这个题首先不考虑c[i]的限制,我们可以想到一个dp,就是dp[i][j]表示长度为i的序列以j结尾的方案数。显然有dp[i][

    来自 just_sort
    00
  • avatar just_sort 2017-01-02 21:33:07

    算法入门经典2 第6章习题 题解

    【序】          这章的课后习题,完成了一共10道,后面真是有些做不动了。之后有空再来补一下剩下的几题,这些题真是写炸了。好多题想法不对,只能看题解慢慢啃了,自己弄懂到去写出来也花了很多时间。就把我完成的题目的解题方法和代码记录一下吧。 这里面6-7, 6-10, 6-13还没有AC,这些

    来自 just_sort
    00
  • avatar just_sort 2017-01-02 12:28:41

    2016 - 12 月 27 SPOJ Interesting Subset

    【题目链接】 点击打开链接 【题意】给定一个集合,该集合由1,2,3....2n组成,n是一个整数。问该集合中有趣子集的数目,答案mod1e9+7。x的子集合有趣定义为,该子集中至少有两个数,a和b,b是a的倍数且a是集合中最小的元素。 【解题方法】考虑一下枚举一个最小元素,那么比它大的元素的个

    来自 just_sort
    00
  • avatar just_sort 2017-01-02 11:53:31

    uvalive 6955 Finding Lines rand() 随机算法

    【题目链接】点击打开链接 【题意】给了两个数n,p。问在平面上是否存在一条直线经过ceil(n*p/100)个点。 【解题方法】随机算法。由于O(n*n)显然会超时,我们这里应用随机算法来找直线。为什么可以用随机算法呢?这里p<=20,所以选取两个点在一条直线上的概率为1/25。也就是选取

    来自 just_sort
    00
  • avatar just_sort 2017-01-01 19:13:09

    SPOJ - PLSQUARE

    【题目链接】 点击打开链接 【题意】给了一个n*n的字符矩阵,求最大的k使得存在一个k*k的子矩阵,满足这个k*k的矩阵里横和竖的所有字符串都是回文串。 【解题方法】Wannafly群赛题。详细解题方法看这里点击打开链接                       大致的方法就是分为两个dp,

    来自 just_sort
    00
  • avatar just_sort 2017-01-01 16:30:00

    SPOJ - Horace and his primes(素数+二分查找)

    【题目链接】 点击打开链接 【题意】               给你一个数列的第一个数,例如90,那么我每次将这个n分解成素数,90 = 2*3^2*5,那么数列的第二个数是2+3+5 = 10;               那么数列第三个数有 10 = 2*5 ,2+5 = 7,所以数列的

    来自 just_sort
    00
  • avatar just_sort 2017-01-01 14:05:35

    12-30 Wannafly每日一题 Pretty Song

    【题目链接】 点击打开链接 【解题方法】 求一个字符串的所有字串的权值和,每个字串的权值为元音字母的个数比上字串的长度 将字串转化为01串,那么区间[l,r]的字串的权值为(s[r]-s[l-1])/(r-l+1),枚举长度k,则所有字串的权值和为 Sigma(1/k *(s[k]-[s0

    来自 just_sort
    00
  • avatar just_sort 2016-12-31 14:29:40

    “玲珑杯”ACM比赛 Round #7 B -- Capture(并查集+优先队列)

    初始时有个首都1,有n个操作 +V表示有一个新的城市连接到了V号城市 -V表示V号城市断开了连接,同时V的子城市也会断开连接 每次输出在每次操作后到首都1距离最远的城市编号,多个距离相同输出编号最小的城市 输入数据保证正确,每次添加与删除的城市一定是与首都相连的 每次都只需要知道最远

    来自 just_sort
    00
  • avatar just_sort 2016-12-30 16:53:20

    线性规划与网络流24题之 试题库问题

    【题目链接】点击打开链接 【解题方法】这道题和圆桌问题没什么区别,都属于多重匹配。方法完全一样。 【问题分析】 二分图多重匹配问题,用最大流解决。 【建模方法】 建立二分图,每个类别为X集合中的顶点,每个题为Y集合中的顶点,增设附加源S和汇T。 1、从S向每个Xi连接一条容量为该类别所需数量的有

    来自 just_sort
    00
  • avatar just_sort 2016-12-30 15:58:56

    线性规划与网络流24题之 魔术球问题

    【题目地址】 点击打开链接 【问题分析】 枚举答案转化为判定性问题,然后最小路径覆盖,可以转化成二分图最大匹配,从而用最大流解决。 【建模方法】 枚举答案A,在图中建立节点1..A。如果对于i<j有i+j为一个完全平方数,连接一条有向边(i,j)。该图是有向无环图,求最小路径覆盖。如果

    来自 just_sort
    00
  • avatar just_sort 2016-12-30 15:20:56

    线性规划与网络流24题之 圆桌问题

    【题目地址】点击打开链接 【问题分析】 二分图多重匹配问题,可以用最大流解决。 【建模方法】 建立二分图,每个单位为X集合中的顶点,每个餐桌为Y集合中的顶点,增设附加源S和汇T。 1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。 2、从每个Yi顶点向T连接一条容量为该餐

    来自 just_sort
    00
  • avatar just_sort 2016-12-29 21:47:31

    Codeforces Round #386 (Div. 2)

    【A】给了一些水果,用这些水果来制作一种食物需要的比例是1:2:4,问制作最多的完整食物需要的水果数目是多少? 首先很容易确定的水果数目就是min(a, b/2, c/4),然后用这个数目乘以7就是我们要的答案了。 【B】通过对样例的观察,我们不难得到解决的方法,我们用两个指针,l,r对于n分奇

    来自 just_sort
    00
  • avatar just_sort 2016-12-29 11:51:58

    算法入门经典2 第6章例题

    【序】                            第6章一共有22个例题,这些例题大多十分经典,在教材和题解的帮助下,已经全部通过了书上的例题。现在就把我做题过程总结一下。 【正文】                          题目传送门:点击打开链接         

    来自 just_sort
    00
  • avatar just_sort 2016-12-28 14:15:02

    SWUST状态压缩入门 解题报告

    【序】         由于昨天大佬讲课,很多人没来,在做完这个训练,我希望用我自己的粗浅理解能够帮到大家,还有训练已经过去几天了,也希望大家抓紧时间去完成这个专题训练,不然这个专题就开得毫无意义了。然后下面的题解我会细致的讲解题目的解法,以及我是如何理解这道题,争取大家都可以很快的看懂。 【正

    来自 just_sort
    00
  • avatar just_sort 2016-12-26 16:24:27

    算法入门经典2 第5章解题报告

    【题目链接】点击打开链接 【写在前面】 这章的部分习题很难,我现在的能力并不能全部做出来这些题,暂时我只能做到这里了,接下来我把我做出来的题目分享一下解题方法,等自己能够做剩下的题了,再回来解决这些题。然后由于书上的例题和习题的题意都有中文描述,我就不写题意了,只写我的做法。 【例题篇】 【5

    来自 just_sort
    00
  • avatar just_sort 2016-12-26 12:31:29

    线性规划与网络流24题 飞行员配对方案问题

    【题目链接】点击打开链接 【解题方法1】 容易看出,这题就是裸的最大二分匹配,所以直接上最大匹配板子就可以过了。 【AC代码1】 // //Created by just_sort 2016/12/23 //Copyright (c) 2016 just_sort.All Rights Re

    来自 just_sort
    00
  • avatar just_sort 2016-12-26 10:42:56

    网络流24题题目列表

    【转载地址】点击打开链接 【判题地址】点击打开链接 转载自: 会根据我个人的能力,逐渐在这个专题中给出所列出的题目的解题报告。 判题系统我使用信息工程学院的。Click Here~ 问题编号 问题名称 问题模型 转化模型

    来自 just_sort
    00
  • avatar just_sort 2016-12-25 21:32:42

    Mutual Training for Wannafly Union #4

    【题目链接】 点击打开链接 【写在前面】现在还只会3题,还没去看讲题视频,剩下可以补的话会尽快补上来的。 【B】这道题看一下题上的图,就知道题意了,稍微写一下就发现他是一个等差数列求和的公式,我们可以把这些数放到数组里面,然后二分一下就可以了,直接开根可能会爆精度,但是这题没有,我直接开根也

    来自 just_sort
    00
  • avatar just_sort 2016-12-21 20:58:49

    算法入门经典2 第4章解题报告

    【题目链接】点击打开链接   密码是: 960626 【写在前面】 例题,我就不写了,书上都有非常多的方法思路,下面我写的是第4章的习题,UVA220还未AC,以后有空再来补上。 【4-1 象棋】非常简单的题,单纯的模拟,代码量有点大,写成函数可以让自己的思路清晰起来。还要注意一些TRICK。我

    来自 just_sort
    00
  • avatar just_sort 2016-12-20 21:48:15

    1.13 Codeforces 30D Kings Problem 贪心 计算几何

    【题意】 有n + 1个点,其中n个点都在数轴x轴上。 求最短的从第k个点开始的哈密尔顿路。 n ≤ 10 【解题方法】 题解描述来自xhr大牛的论文 先对x轴上的点按x坐标排序,设排序后为a 1 ...a n . 设x轴外的点为p 如果人正好在那个x轴外的点,可以证明最优解是 di

    来自 just_sort
    00
  • avatar just_sort 2016-12-20 17:08:52

    1.12 Codeforces 28D Do not fear, DravDe is kind DP 思维

    【题目地址】点击打开链接 【题意】 给定长度为n的四元组序列 (v i ,c i ,l i ,r i ) 要求选出一个子序列(也就是原序列去掉若干元素后得到的序列), 使得满足: • 子序列中所有的四元组c i + l i + r i 均相等 • 第一个元素的l i = 0, 最后一个元素的r

    来自 just_sort
    00
  • avatar just_sort 2016-12-20 15:24:30

    Codeforces Round #388 (Div. 2) A,B,C,D 题解

    【A】水题,分奇偶贪心即可。复杂度O(n) int main() { int n; cin>>n; if(n%2==0) { cout<<n/2<<endl; for(int i = 0; i &

    来自 just_sort
    00
  • avatar just_sort 2016-12-18 12:04:46

    算法入门经典2 第3章解题报告

    【写在前面】 就不写题意了,紫书上面有中文翻译,下面水题我直接给出代码了,一些需要推导的详细写一下! 【3-1】水题,顺序扫描一遍就行了。复杂度O(len) char s[82]; bool vis[82]; int main() { int T; scanf("%d

    来自 just_sort
    00
  • avatar just_sort 2016-12-17 13:56:31

    Codeforences 23E Tree

    【题意】给定一个n结点的树,删去若干边,要求最大化得到的所有连通块大小的乘积。n <= 700 【分析】蓝儿完全不会做这题,看着cxlove神的题解学习了。点击打开链接  dp[i][j] 代表以 i为根的子树节点i所在连通块节点个数为j的最大值!那么我们树DP的时候,就只需要考虑一下孩子节

    来自 just_sort
    00
  • avatar just_sort 2016-12-17 09:18:30

    Codeforences 23D Tetragon

    【题意】给定3个点,判定是否存在一个严格凸四边形,使得其中三条边的中点恰好是这3个点。不超过50000组数据。 坐标范围比较小。 【解题方法】 假设四边形四个点是a , b , c , d。中点为k , l , m分别为ab , bc , cd的中点。 那么作m点关于l点的对称点m‘,容易得到

    来自 just_sort
    00
  • avatar just_sort 2016-12-14 14:56:07

    Codeforences 17E Palisection

    【题意】给定一个长度为n的小写字母串。问你有多少对相交的回文子串(包含也算相交)。n ≤ 2 ∗ 10 6 【解题方法】可知求相交的比较难,但是求不相交的却很简单,先用manacher算法o(n)的求出每个点的回文串最长有多长。再求出st,en数组,分别代表以i为开头的回文串有几个,以i为结尾的回

    来自 just_sort
    00
  • avatar just_sort 2016-12-13 20:26:18

    Codeforences 17C Balance

    数组,开小了,暴力调了2小时才发现。。。。。 【AC代码】 // //Created by just_sort 2016/12/13 //Copyright (c) 2016 just_sort.All Rights Reserved // #include <ext/pb_ds/a

    来自 just_sort
    00
  • avatar just_sort 2016-12-13 13:41:01

    Codeforences 15 E triangles

    这题好难,大佬的博客写得太好了,连我这种弱鸡都可以看懂,具体讲解可以看这篇博客 点击打开链接

    来自 just_sort
    00