• avatar JZYshuraK 2018-07-18 22:37:00

    [bzoj1606][Usaco2008 Dec]Hay For Sale 购买干草_动态规划_背包dp

    Hay For Sale 购买干草 bzoj-1606 Usaco-2008 Dec 题目大意:约翰遭受了重大的损失:蟑螂吃掉了他所有的干草,留下一群饥饿的牛.他乘着容量为C(1≤C≤50000)个单位的马车,去顿因家买一些干草.  顿因有H(1≤H≤5000)包干草,每一包都有它的体积Vi(l≤

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-17 21:16:00

    [bzoj1180][CROATIAN2009]OTOCI_LCT

    OTOCI bzoj-1180 CROATIAN-2009 题目大意:给你n个离散的点,m个操作。支持:两点加边(保证还是森林),修改单点权值,询问两点是否联通,查询联通两点之间路径权值。 注释:$1\le n \le 30,000$,$1\le m \le 300,000$。 想法:显然,又

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-18 23:12:00

    [bzoj2124]等差子序列_线段树_hash

    等差子序列 bzoj-2124 题目大意:给定一个1~n的排列,问是否存在3个及以上的位置上的数构成连续的等差子序列。 注释:$1\le n\le 10^4$。 想法:这题就相当于是否存在3个数i,j,k,a[i]表示i位置上的数,使得:i<j<k且a[k]-a[j]=a[j]-a

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-17 21:06:00

    [bzoj1610][Usaco2008 Feb]Line连线游戏_暴力枚举

    Line连线游戏 bzoj-1610 Usaco-2008 Feb 题目大意:Farmer John最近发明了一个游戏,来考验自命不凡的贝茜。游戏开始的时 候,FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板,其中第i个点 的横、纵坐标分别为X_i和Y_i (-

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-16 23:03:00

    [bzoj4659\2694]Lcm_数论_莫比乌斯反演

    Lcm bzoj-4659 bzoj-2694 题目大意:给出A,B,考虑所有满足l<=a<=A,l<=b<=B,且不存在n>1使得n^2同时整除a和b的有序数对(a,b),求其lcm(a,b)之和。答案模2^30。 注释:$1\le A,B\le 4\cdot 1

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-15 23:13:00

    [bzoj3282]Tree_LCT

    Tree bzoj-3282 题目大意:给你n个点m个操作。更改单点权值,加边,删边;查询路径异或和。 注释:$1\le n,m\le 10^5$ 想法:看到了加边删边,果断想到LCT维护。至于路径异或和,我们只需要维护每个点对应splay的子树异或和,然后查询的时候直接access+spla

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-14 07:34:00

    [bzoj2789][Poi2012]Letters_树状数组

    Letters bzoj-2789 Poi-2012 题目大意:给定两个字符串A和B,每次交换A中相邻两个数。问至少交换多少次,可以将A变成B。 注释:$2\le n\le 10^6$ 想法:我们发现,A中任意两个相同字符的相对位置是不会发生改变的,所以我们可以直接求逆序对即可。 最后,附上

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-12 20:54:00

    [bzoj1090][SCOI2003]字符串折叠_区间dp

    字符串折叠 bzoj-1090 SCOI-2003 题目大意:我说不明白...链接 注释:自己看 想法:动态规划 状态:dp[i][j]表示从第i个字符到第j个字符折叠后的最短长度。 转移:dp[l][r]=min(r-l+1,dp[l][k]+dp[k+1][r]) 当k+1~r可以有

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-12 20:46:00

    [bzoj1614][Usaco2007Jan]Telephone Lines 架设电话线_二分答案_最短路

    Telephone Lines bzoj-1614 Usaco-2007Jan 题目大意:给你一个n个点m条边的带边权无向图,求最短路。可以选取k条边免费。 注释:$1\le n\le 10^3$,$1\le m\le 10^5$ 想法:一眼分层图最短路啊! 我都想出来了就上网查一下题解吧

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-12 20:32:00

    [bzoj3389][Usaco2004Dec]Cleaning Shifts安排值班_最短路

    Cleaning Shifts bzoj-3389 Usaco-2004Dec 题目大意:每天有n个时间段,每个时间段都必须安排一个奶牛值班。有m个奶牛,每个奶牛只有一个空闲时间s[i]~e[i],求至少动用多少奶牛。 注释:$1\le n\le 10^6$,$1\le m\le 25,000$

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-12 20:12:00

    [bzoj3680]吊打XXX_模拟退火

    吊打XXX bzoj-3680 题目大意:在平面上给定n个点,每个点有一个权值。请在平面上找出一个点(不一定在这n个点内找)使得这个点到n个点的距离*权值最小,即求这n个点的重心。 注释:$1\le n\le 10^4$,$-10^5\le x_i,y_i\le 10^5$。 想法: 模拟退

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-15 23:22:00

    [bzoj5118]Fib数列2_费马小定理_矩阵乘法

    Fib数列2 bzoj-5118 题目大意:求Fib($2^n$)。 注释:$1\le n\le 10^{15}$。 想法:开始一看觉得一定是道神题,多好的题面啊?结果...妈的,模数是质数,费马小定理就tm完事了,将fib数列的通项公式列出来然后费马小定理... 最后,附上丑陋的代码...

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-12 20:22:00

    [bzoj4562][Haoi2016]食物链_记忆化搜索_动态规划

    食物链 bzoj-4562 Haoi-2016 题目大意:给你n个点,m条边的DAG,求所有的满足条件的链,使得每条链的起点是一个入度为0的点,中点是一条出度为0的点。 注释:$1\le n\le 10^5$,$1\le m\le 2*10^5$。 想法:考试T2,全场切 动态规划 状态:

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-11 09:00:00

    长枪短炮技巧の菜刀流[处理一些问题的小方法]

    杂技篇【长期更新】 1.在O(n)时间内处理出一个字符串的所有循环字符串的hash值:将字符串倍长,然后通过取模运算实现   for(int j=0;j<=(n<<1)-1;j++) f[j+1]=f[j]*base+s[j%n]-'a'+1; 2.一个图是不是二分图的充要条

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-10 20:53:00

    [bzoj2186][Sdoi2008]沙拉公主的困惑_数论

    沙拉公主的困惑 bzoj-2186 Sdoi-2008 题目大意:求N!中与M!互质的数的个数。 注释:$1\le N,M\le 10^7$。 想法:显然是求$\phi(M!)$。这东西其实只需要将数据极限范围内所有的逆元崩出来就行了... ... 最后,附上丑陋的代码... ...

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-10 20:47:00

    [bzoj3209]花神的数论题_数位dp

    花神的数论题 bzoj-3209 题目大意:sum(i)表示i的二进制表示中1的个数,求$\prod\limits_{i=1}^n sum(i)$ 注释:$1\le n\le 10^{15}$。 想法:喷一下题目...神tm数论题,明明是个dp。 显然,如果稍微打个表的话就可以发现,有很多数

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-10 20:34:00

    [bzoj3038/3211]上帝造题的七分钟2/花神游历各国_线段树

    上帝造题的七分钟2 bzoj-3038 题目大意:给定一个序列,支持:区间开方;查询区间和。 注释:$1\le n\le 10^5$,$1\le val[i] \le 10^{12}$。 想法:这题还挺挺有意思的。查询区间和我们可以用前缀和,但是用上去区间修改就不难想到线段树。那么我们思考如何

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-09 16:37:00

    [bzoj1002][FJOI2007]轮状病毒_递推_高精度

    轮状病毒 bzoj-1002 FJOI-2007 Description   轮状病毒有很多变种,所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的,2个原子之间的边表示这2个原子之间的信息通道。如下图所示   N轮状

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-09 16:29:00

    [bzoj4864][BeiJing2017Wc]神秘物质_非旋转Treap

    神秘物质 bzoj-4864 BeiJing-2017-Wc 题目大意:给定一个长度为n的序列,支持插入,将相邻两个元素合并并在该位置生成一个指定权值的元素;查询:区间内的任意一段子区间的最大值减最小值的最大值或最小值。 注释:$1\le n,m \le 10^5$,m为操作个数。 想法:

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-09 15:23:00

    [bzoj1552\bzoj2506][Cqoi2014]robotic sort 排序机械臂_非旋转Treap

    robotic sort 排序机械臂 bzoj-1552 bzoj-2506 Cqoi-2014 题目大意:给定一个序列,让你从1到n,每次将[1,p[i]]这段区间反转,p[i]表示整个物品权值第i小的。 注释:$1\le n\le 10^5$。 想法:非旋转Treap裸题,随题目要求。只需

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-09 10:20:00

    [bzoj2631]tree_LCT

    tree bzoj-2631 题目大意:给定一个n个点的树,每个点的初始权值为1,支持:删边加边(这两个操作同时进行,保证操作之后还是一棵树),路径加,路径乘,查询路径和。 注释:$1\le n,q\le 10^5$,$1\le c \le 10^4$。 想法:暴力给的很优雅:15‘没有加边删

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-08 10:26:00

    [bzoj4487][Jsoi2015]染色_容斥原理

    染色 bzoj-4487 Jsoi-2015 题目大意:给你一个n*m的方格图,在格子上染色。有c中颜色可以选择,也可以选择不染。求满足条件的方案数,使得:每一行每一列都至少有一个格子被染色,且所有的颜色必须都出现过。 注释:$1\le n,m,k\le 400$。 想法:显然直接求每个求,我

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-07 23:24:00

    [bzoj2529][Poi2011]Sticks_贪心

    Sticks bzoj-2529 Poi-2011 题目大意:给你n根木棒,每种木棒有长度和颜色,颜色共有k种,求满足条件的3根木棒使得这3根木棒颜色互不相同且可以围成三角形。 注释:$1\le n \le 10^6$,$1\le k\le 50$。 想法:我们这么想:假设当前木棍是满足题意的

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-07 22:48:00

    [bzoj2049][Sdoi2008]Cave 洞穴勘测_LCT

    Cave 洞穴勘测 bzoj-2049 Sdoi-2008 题目大意:维护一个数据结构,支持森林中加边,删边,求两点连通性。n个点,m个操作。 注释:$1\le n\le 10^4$,$1\le m\le 2\cdot 10^5$。 想法:刚学了一发LCT,写一道照学长抄一道板子题。话说什么是

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-07 21:28:00

    [bzoj1212][HNOI2004]L语言_AC自动机_动态规划

    L语言 bzoj-1212 HNOI-2004 题目大意:给你一个n个单词的集合,然后给你m条字符串。问每条字符串可以被理解的最长前缀。被理解当且仅当存在一种分割使得每一段都是集合里的元素。 注释:$1\le n,m\le 20$,长度不超过1M 想法:做了上一道,感觉这是个大水题... ..

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-07 19:49:00

    [bzoj1861][Zjoi2006]Book 书架_非旋转Treap

    Book 书架 bzoj-1861 Zjoi-2006 题目大意:给你一个序列,支持:将指定编号的元素抽出,放到序列顶(底);将指定编号元素左右篡位;查询指定编号元素位置;查询指定数量位置元素编号。 注释:$1\le n,m\le 8\cdot 10^4$ 想法:非旋转Treap裸题 需要注

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-07 19:08:00

    [bzoj4027][HEOI2015]兔子与樱花_贪心_树形dp

    兔子与樱花 bzoj-4027 HEOI-2015 题目大意:每个点有c[i]朵樱花,有一个称重m, son[i]+c[i]<=m.如果删除一个节点,这个节点的樱花或移动到它的祖先中深度最大的,且没有被删除的节点,求在满足所有点界限的情况下,最多能删除的节点数。 注释:$1\le n\le

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-04 19:39:00

    [bzoj1084][SCOI2005]最大子矩阵_动态规划_伪·轮廓线dp

    最大子矩阵 bzoj-1084 SCOI-2005 题目大意:给定一个n*m的矩阵,请你选出k个互不重叠的子矩阵使得它们的权值和最大。 注释:$1\le n \le 100$,$1\le m\le 2$,$1\le k\le 10$。 想法:不会。。。看了数据范围..卧槽?m<=2???

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-02 20:17:00

    [bzoj2466][中山市选2009]树_树形dp

    树  bzoj-2466 中山市选-2009 题目大意:给定一棵树,每一个点有一个按钮和一个灯泡。如果按下一个点的按钮那么和这个点直接相连的点包括这个点的灯泡的状态会改变。如果是点亮就会变成熄灭,如果是熄灭就会变成点亮。 注释:$1\le n\le n$ 想法:啥jb数据范围啊,不是树形dp吗

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-02 19:50:00

    [bzoj4127]Abs_树链剖分_线段树

    Abs bzoj-4127 题目大意:给定一棵数,支持链加和链上权值的绝对值的和。 注释:$1\le n,m \le 10^5$,$\delta \ge 0$,$|a_i|\le 10^8$。 想法:看完题,以为又是什么数据结构裸题。然后发现绝对值... ...卧槽?啥jb玩意儿?绝对值?这怎

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-02 19:12:00

    [bzoj3696]化合物_树形dp

    化合物 bzoj-3696 题目大意:给你一棵树,定义两个点i , j之间的A值是(dis[i]-dis[lca(i,j)])xor(dis[j]-dis[lca(i,j)])。对所有的k$\in$[1,n],A值等于k的点对数量。 注释:$1\le n\le 10^5$,$1\le maxdi

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-07 21:10:00

    [bzoj3530][Sdoi2014]数数_AC自动机_数位dp

    数数 bzoj-3530 Sdoi-2014 题目大意:给你一个整数集合,求所有不超过n的正整数,是的它的十进制表示下不能再一段等于集合中的任意数。 注释:$1\le n \le 1200$,$1\le |S|\le 100$,$1\le L\le 1500$,L是总长度之和。 想法:咳咳,显

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-04 19:04:00

    [bzoj1055][HAOI2008]玩具取名_区间dp

    玩具取名 bzoj-1055 HAOI-2008 题目大意:给你一个用W,I,N,G组成的字符串,给你一些这四个字符之间的变换规则,每一个变换规则都是由一个字符变成两个字符,问这个字符串是否可能是由一个单独的字符变成的。 注释:$1\le Len\le 200$,每种字符的变换规则<=16

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-01 13:22:00

    [bzoj2748][HAOI2012]音量调节_动态规划_背包dp

    音量调节 bzoj-2748 HAOI-2012 题目大意:有一个初值,给你n个$\delta$值,求最后不超过给定的限制的情况下的改变的最大值。每个$\delta$值可以+也可以-。 注释:$1\le n\le 50$,$1\le 限制\le 1000$。 想法:正负背包。在背包的之后更新用

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-01 12:50:00

    [bzoj1070][SCOI2007]修车_费用流

    修车 bzoj-1070 SCOI-2007 题目大意:有m个人要修n台车,每个工人修不同的车的时间不同,问将所有的车都修完,最少需要花费的时间。 注释:$2\le m\le 9$,$1\le n \le 60$ 想法:想起了那句话...(如果题面复杂,dp状态不可描述,一看数据范围发现才几百

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-07-01 12:40:00

    [bzoj1218][HNOI2003]激光炸弹_暴力

    激光炸弹 bzoj-1218 HNOI-2003 题目大意:在笛卡尔坐标系上有n个点,问一个平行于坐标轴的r*r的正方形可以最多覆盖多少个目标。 注释:$1\le n \le 10000$,$1\le answer\le 32767$。 想法:更一道水题。我们将所有的目标按坐标排序,之后暴力枚

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-06-13 10:11:00

    [bzoj2938][Poi2000]病毒_AC自动机

    病毒 bzoj-2938 Poi-2000 题目大意:给你n个01串,问是否存在一个无限长的01串使得这个01的任意子串都不等于给出的01串。 注释:All_length<=30,000 想法:裸题,介绍一下AC自动机。   什么是AC自动机?简单讲,就是Trie+KMP。KMP就是单

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-06-03 23:15:00

    [bzoj1001][BeiJing2006]狼抓兔子_网络流_最小割转对偶图

    狼抓兔子 bzoj-1001 BeiJing2006 Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的, 而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:  

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-30 20:35:00

    [bzoj3505][CQOI2014]数三角形_组合数学

    数三角形 bzoj-3505 CQOI-2014 题目大意:给你一个n*m的网格图,问你从中选取三个点,能构成三角形的个数。 注释:$1\le n,m\le 1000$。 想法:本来是想着等中考完了之后花上一周的时间把之前欠的blog都更掉,然后做了这道题发现网上的题解让我匪夷所思(他们写着任

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-29 09:52:00

    [bzoj2600][Ioi2011]ricehub_二分

    ricehub bzoj-2600 Ioi-2011 题目大意:在数轴上有r块稻田,稻田坐标为整数。计划建造一个米仓,使得它可以收取尽量多的稻米。米仓的坐标仍需为整数。每一块权值为val的稻田距离米仓的距离为dis,那么收取这个稻田上的大米的代价是val*dis。我们只有b元运费,问最多能收取多少

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-27 22:16:00

    [bzoj1316]树上的询问_点分治

    树上的询问 bzoj-1316 题目大意:一棵n个点的带权有根树,有p个询问,每次询问树中是否存在一条长度为Len的路径,如果是,输出Yes否输出No. 注释:$1\le n\le 10^4$,$1\le p\le 100$,长度$\le 10^6$。 想法:有根树tm是啥意思?根在jb哪呢?

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-27 22:05:00

    [bzoj3062][Usaco13Feb]Taxi_贪心

    Taxi bzoj-3062 Usaco13Feb 题目大意:有n个奶牛想坐出租车。第i头奶牛在起点a[i]等候,想坐出租车到b[i]。Bessie从0出车,车上只能坐一头奶牛。她必须完成所有奶牛的要求而且她必须从0到m。 注释:$1\le n\le 10^5$,$1\le m\le 10^9$

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-25 16:38:00

    [bzoj3061][Usaco13Feb]Partitioning the Farm_动态规划_状压dp

    Partitioning the Farm bzoj-3061 Usaco13Feb 题目大意:给定一个n*n的方格图,用k条贯穿方格图的直线将整个方格图分割,使得每一块的权值和的最大值最小。 注释:$1\le n \le 15$,$1\le k \le 2n-2$。 想法:想到dp不难,但是

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-25 16:18:00

    [bzoj1251]序列终结者_splay

    序列终结者 bzoj-1251 题目大意:给定一个长度为n的正整数序列,支持区间加,区间反转,查询区间最大值。所有元素开始都是0. 注释:$1\le n\le 5\cdot 10^4$,操作个数不多于$10^6$。 想法:splay模板题,splay在rotate时注意fa的从属,以及哨兵节点

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-25 16:12:00

    [bzoj3702/2212][Poi2011]二叉树/Tree Rotations_线段树

    二叉树 Tree Rotations bzoj-3702 bzoj-2212 Poi-2011 题目大意:现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点,满足这些权值为1到n的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换,使得最终所

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-25 14:59:00

    [bzoj3192][JLOI2013]删除物品_树状数组_栈

    删除物品 bzoj-3192 JLOI-2013 题目大意:给你n个物品,分成2堆。所有的物品有不同的优先级。我只可以将一堆中的堆顶移动到另一个堆的堆顶。而如果当前物品是全局所有物品中优先级最高的,我可以直接将其删除。询问最小移动多少次,删除不计入总次数。 注释:$1\le n\le 10^5$

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-25 14:46:00

    [bzoj3694]最短路_树链剖分_线段树

    最短路 bzoj-3694 题目大意:给你一个n个点m条边的无向图,源点为1,并且以点1为根给出最短路树。求对于2到n的每个点i,求最短路,要求不经过给出的最短路树上的1到i的路径上的最后一条边。 注释:$1\le n \le 4000$,$1\le m\le 10^5$。 想法:对于任意两个

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-24 20:53:00

    [bzoj3747][POI2015]Kinoman_线段树

    Kinoman bzoj-3747 POI-2015 题目大意:有m部电影,第i部电影的好看值为w[i]。现在放了n天电影,请你选择一段区间l~r使得l到r之间的好看值总和最大。特别地,如果同一种电影放了两遍及以上,那么这种电影的好看值将不会被获得。 注释:$1\le m \le n \le 1

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-24 20:40:00

    [bzoj1598][Usaco08Mar]牛跑步_A*_Dijkstra

    牛跑步 bzoj-1598 题目大意:给你n个点,m条边的有向图。求从1到n的严格的第k短路。 注释:$1\le n\le 1000$,$1\le m \le 10,000$,$1\le k \le 100$。 想法:   A*:俗称机器人走路算法。就是说从一个点走到另一个点的最短路径,显然

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-24 20:27:00

    [bzoj1592][Usaco09Feb]Making the Grade 路面修整_动态规划

    Making the Grade 路面修整 bzoj-1592 题目大意:给你n段路,每段路有一个高度h[i],将h[i]修改成h[i]$\pm\delta$的代价为$\delta$,求将这n段路修成非严格单调的最小代价。 注释:1$\le$n$\le$2000,$1\le A_i\le 10^

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-24 18:03:00

    [bzoj3339]Rmq Problem||[bzoj3585]mex_线段树

    Rmq Problem bzoj-3339||mex bzoj-3585 题目大意:给定一个长度为n的数列a,多次讯问区间l,r中最小的不属于集合{$A_l,A_{l+1}...A_r$}的非负整数。 注释:n,q$\le$200,000 ; 0$\le A_i \le$200,000 ; $A

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-13 16:53:00

    [bzoj1925][Sdoi2010]地精部落_递推_动态规划

    地精部落 bzoj-1925 Sdoi-2010 题目大意:给你一个数n和模数p,求1~n的排列中满足每一个数的旁边两个数,要么一个是边界,要么都比它大,要么都比它小(波浪排列个数) 注释:$1\le n\le 4200$ , $1\le p\le 10^9$。 想法:神题!这题标签给的是dp

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-13 16:39:00

    [bzoj1047][HAOI2007]理想的正方形_动态规划_单调队列

    理想的正方形 bzoj-1047 HAOI-2007 题目大意:有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 注释:$2\le a,b,n\le 10^3$,$n\le min(a,b)$。 想法:我的思路简直要死。通常的,我

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-11 18:32:00

    [bzoj3126][USACO2013]Photo_动态规划_单调队列

    Photo bzoj-3126 题目大意:给你一个n长度的数轴和m个区间,每个区间里有且仅有一个点,问最多能有多少个点。 注释:$1\le n \le 2\cdot 10^5$,$1\le m\le10^5$。 想法:开始和GXZlegend在那里贪心。贪了挺久发现几乎所有的贪心策略都会被卡,

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-11 11:29:00

    [bzoj2654]tree_二分_kruskal

    tree bzoj-2654     题目大意:给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。     注释:$1\le V\le 5\cdot 10^4$,$1\le E \le 10^5$,$1\le val_i\le 100$。

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-11 09:30:00

    [luogu1373]小a和uim之大逃离_动态规划

    小a和uim之大逃离     题目大意:有一个n*m的矩阵。每个格子上有一坨0~k不等量的权值。有两个人,每个人任选一个格子作为出发点,并只能向下或向右走。求最后两个人所得到的权值mod k相等的方案数。     注释:$1\le n,m\le 800$,$1\le k \le 15$。   

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-11 08:40:00

    [luogu1156]垃圾陷阱_动态规划_背包dp

    垃圾陷阱 luogu-1156     题目大意:Holsteins在距离地面D英尺的地方,FJ间隔时间ti会往下扔第i个垃圾。Holsteins对待每一个垃圾都会选择吃掉或者垫高。Holsteins有10个点儿的生命值,每个垃圾会给她提供f的生命值。每小时Holsteins会消耗一定的生命值。问

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-11 08:22:00

    [luogu2209][USACO13]燃油经济性Fuel Economy_贪心

    燃油经济性Fuel Economy 题目大意:FJ想要去旅行。他的车总容量为G,每行驶一个单位就消耗一个单位的油。FJ要行驶D个单位的距离。期间存在n个加油站,每个加油站有一个价格,表示在这个燃油站买一个单位的油的价格val;还有一个距离d,表示这个燃油站距离FJ起点的距离。FJ起始有B个单位的油

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-05-01 22:07:00

    [bzoj1007][HNOI2008]水平可见直线_单调栈

    水平可见直线 bzoj-1007 HNOI-2008     题目大意:给你n条直线,为你从上往下看能看见多少跳直线。     注释:能看见一条直线,当且仅当这条直线上存在一条长度>0的线段使得这条线段上方没有其他直线,$1\le n 5\cdot 10^4$。       想法:神题q

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-27 18:22:00

    [bzoj1010][HNOI2008]玩具装箱toy_斜率优化dp

    玩具装箱toy bzoj-1010 HNOI-2008     题目大意:P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-20 19:59:00

    [jdoj1258]野生动物园(change by panxf)_权值线段树_组合数

    人品计算     题目大意:n个数的a序列,m组询问。每次询问给出T,A,B,K。求在a序列的[A,B]的位置之内的K小值P,的$C_{T}^{P \% T} \% 10111$。     注释:每组询问保证区间只相交,不包含。$1\le n \le 10^5$,$1\le m \le 10^4

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-20 19:35:00

    [bzoj3037/2068]创世纪[Poi2004]SZP_树形dp_并查集_基环树

    创世纪 SZP bzoj-3037/2068 Poi-2004 题目大意:给你n个物品,每个物品可以且仅可以控制一个物品。问:选取一些物品,使得对于任意的一个被选取的物品来讲,都存在一个没有被选取的物品,而且选取的个数最大。 注释:$1\le n \le 10^6$。 想法:显然,和骑士类似的

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-19 08:48:00

    [bzoj1040][ZJOI2008]骑士_树形dp_基环树_并查集

    骑士 bzoj-1040 ZJOI-2008     题目大意:n个骑士,每个骑士有权值val和一个讨厌的骑士。如果一个骑士讨厌另一个骑士那么他们将不会一起出战。问出战的骑士最大atk是多少。     注释:$1\le n,atk\le 10^6$。       想法:树形dp的一道好题qwq

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-17 19:08:00

    不小心磕々绊々の全球流[手白错误合集]

    [数据结构] 左偏树 1.左偏树merge函数当左儿子的dis小于右儿子的dis时应该swap(lson[x] , rson[x]),写成swap(dis[lson[x]] , dis[rson[x]])。 set 1.set中的begin()和end()是不一样的,begin()有值而en

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-16 20:52:00

    [bzoj1455]罗马游戏_左偏树_并查集

    罗马游戏 bzoj-1455     题目大意:给你n个人,2种操作,m次操作:1.将i号士兵所在的集合的最小值删除 2.合并i和j两个士兵所在的团体     注释:$1\le n\le 10^6$,$1\le m \le 10^5$。       想法:又是GXZlegend讲课,可并堆中的

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-14 22:07:00

    [poj2417]Discrete Logging_BSGS

    Discrete Logging poj-2417     题目大意:求$a^x\equiv b(mod\qquad c)$     注释:O(分块可过)       想法:介绍一种算法BSGS(Baby-Step Giant-Step),网上大佬说拔山盖世qwq         算法是这样

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-14 07:24:00

    [bzoj2599][IOI2011]Race_树上点分治

    Race bzoj-2599     题目大意:询问一颗树上最短的、长度为k的链,边有边权,n个节点。     注释:$1\le n \le 2\cdot 10^5$,$1\le k \le 10^6$。       想法:树上点分治的另一种表现方式。首先,由于题目中要求的是最小值,我们发现这

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-11 20:42:00

    [bzoj3697]采药人的路径_点分治

    采药人的路径 bzoj-3697     题目大意:给你一个n个节点的树,每条边分为阴性和阳性,求满足条件的链的个数,使得这条链上阴性的边的条数等于阳性的边的条数,且这条链上存在一个节点,这个节点到一个端点的链也是阴阳相等,到另一个顶点也是阴阳相等。    注释:$1\le n \le 10^5$

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-09 20:41:00

    [poj3735] Training little cats_矩乘快速幂

    Training little cats poj-3735     题目大意:给你n个数,k个操作,将所有操作重复m次。     注释:三种操作,将第i个盒子+1,交换两个盒子中的个数,将一个盒子清空。$1\le m \le 10^9$ , $1\le n , k \le 100$。     

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-09 08:30:00

    [poj3070]Fibonacci_矩乘_快速幂

    Fibonacci poj-3070     题目大意:求Fibonacci第n项。     注释:模数为10000,$1\le n \le 10^9$。       想法:矩阵题,用例题6的想法,我们构造矩阵           $\begin{pmatrix} 0 & 1 \\

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-08 20:51:00

    矩阵学习摘记,欢迎指正

    矩阵乘法学习摘记 ​ ——JZYshuraK 18.4.8 http://www.matrix67.com/blog/archives/276 例题1 ​ 为什么一定要将本来只有两维的点设为一个\(1\cdot 3​\)矩阵,原因在于,我们在处理所有操作时,必须使得每一个操作矩阵都是正方形(

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-18 10:11:00

    [bzoj4003][JLOI2015]城池攻占_左偏树

    城池攻占 bzoj-4003 JLOI-2015     题目大意:一颗n个节点的有根数,m个有初始战斗力的骑士都站在节点上。每一个节点有一个standard,如果这个骑士的战斗力超过了这个门槛,他就会根据城池的奖励增加自己的战斗力。具体地:每一个城池有一个flag和一个val,表示成功到达这个城

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-10 20:40:00

    [bzoj1468][poj1741]Tree_点分治

    Tree bzoj-1468 poj-1741     题目大意:给你一颗n个点的树,求树上所有路径边权和不大于m的路径条数。     注释:$1\le n\le 4\cdot 10^4$,$1\le m \le 10^9$。       想法:GXZlegend给高一讲点分治,去听了之后的第

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-08 10:42:00

    [poj1363]Rails_模拟_栈

    Rails poj-1363     题目大意:判断一个序列是否是1~n的合法出栈序列。     注释:$1\le n\le 10^4$。       想法:开始想到一种想法。         对于一段序列来讲,显然从首元素开始的连续小于尾元素的序列必定为合法出栈序列,所剩下的数所组成的序列

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-06 20:39:00

    JLOI2018 记

    2018JL省选记     又是一年省选。今年的我,依然好菜啊...   [Day 0]       呼...好紧张,明天就省选了。下周就有学长退役了吧,机房又该恢复冷清了吧。只剩下为数不多的几个i7接送着来来往往的OIers。明天看我一顿暴力然后写中考卷。   [Day 1]      

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-04-03 19:29:00

    [poj3321]Apple Tree_dfs序_树状数组

    Apple Tree poj-3321     题目大意:给你一个根固定的树,每一个点的点权是0或1,查询子树点权和。     注释:$1\le n \le 10^5$。       想法:刚刚学习dfs序,刷到水题偶哈哈。         什么是dfs序?就是在遍历树的时候记录的每个点的出

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-30 21:01:00

    [poj3974]Palindrome_Manacher

    Palindrome poj-3974     题目大意:求字符串的最长回文子串。     注释:$1\le strlen(s) \le 10^6$.       想法:介绍一种字符串算法——Manacher。求以每一个字符和字符间隔为回文中心的回文半径长度。什么是Manacher?    

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-29 10:11:00

    [poj1062]昂贵的聘礼_最短路_离散化

    昂贵的聘礼 poj-1062     题目大意:原文链接?不是英文题,自己看     注释:$1\le N \le 100$。       想法:开始的想法有些过于简单,因为落下了一个条件:就是等级限制是一条路径上的任意两点而不是相邻两点。所以我们考虑枚举当前可接受等级的区间。显然最多只有10

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-28 21:23:00

    [poj1068]Parencodings_模拟

    Parencodings     题目大意:给你一个P序列,表示从左到右的右括号左边有多少左括号,求M序列。     注释:M序列定义为每一个右括号左边最近的没有被之前的右括号匹配的括号之间,有多少已经匹配的括号队对。$1\le number for P\le 20$。       想法:暴力

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-28 08:49:00

    [poj1012]Joseph_Joseph

    Joseph     题目大意:给你2*k个人,前k个是好人,后k个是坏人,编号从1到2*k。每次从上一个死掉的人的下一个开始查m个人并将第m个人杀死。问最后剩下的全是好人的m是多少。     注释:$1\le k \le 14$。       想法:开始觉得自己想的有些简单,然后发现其实就是

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-28 08:10:00

    [poj3984]迷宫问题_bfs

    迷宫问题     题目大意:给你一个5*5的矩阵,求左上角到左下角的最短路径。     注释:0或1的矩阵,1表示不能走,0表示能走,保证有唯一最短路径。       想法:bfs爆搜练习题。通过其实点,定义方向数组,然后进行bfs遍历即可。     最后,附上丑陋的代码... ...

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-26 08:17:00

    [poj3468]A Simple Problem with Integers_线段树

    A Simple Problem with Integers     题目大意:给出n个数,区间加、查询区间和。     注释:1<=n,q<=100,000.(q为操作次数)。       想法:嗯...学了这么长时间线段树,发现我tm竟然不会lazy标记??!好吧,看来线段树又

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-26 10:42:00

    [luogu1168]中位数_优先队列

    中位数     题目大意:输出读入的前2*k+1个数的中位数。一共有n个数,按照读入顺序。     注释:$1\le n \le 10^9$。       想法:这是优先队列的一个应用qwq。我们弄两个堆。小根堆和大根堆,保证:大根堆中的任意一个数都小于小根堆,而且大根堆中的元素个数始终比小根

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-23 08:30:00

    [poj2185]Milking Grid_KMP

    Milking Grid poj-2185     题目大意:给出一个字符矩阵,求最小覆盖矩阵(可以残余).     注释:$1\le R\le 10^5$,$1\le C \le 75$       想法:和bzoj1355不同的是,bz那题求的是最小覆盖子串。这题其实异曲同工。Discus

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-22 21:03:00

    [bzoj1355][Baltic2009]Radio Transmission_KMP

    Radio Transmissio bzoj-1355 Description     给你一个字符串,它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少. Input     第一行给出字符串的长度,1 < L ≤ 1,000,0

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-22 19:54:00

    [poj2752]Seek the Name, Seek the Fame_KMP

    Seek the Name, Seek the Fame poj-2752     题目大意:给出一个字符串p,求所有既是p的前缀又是p的后缀的所有字符串长度,由小到大输出。     注释:$1\le strlen(p)\le 4\cdot 10^5$。       想法:显然,这样的所有的字

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-22 19:15:00

    [poj3461]Oulipo_KMP

    Oulipo poj-3461     题目大意:给你两个字符串s和p,问s中有多少个等于p的子串。     注释:$1\le strlen(p)\le 10^4\qquad1\le strlen(s)\le 10^6$       想法:刚刚学习KMP,先来一道裸题。什么是KMP?    

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-22 07:57:00

    [poj2002]Squares_hash

    Squares poj-2002     题目大意:在笛卡尔坐标系中给出n个点,求这些点可以构成多少个正方形。     注释:$1\le n\le 10^3$,$-2\cdot 10^3\le x , y\le 2\cdot 10^3$.       想法:最基本的办法是n个点中枚举三个点,然

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-21 08:49:00

    [poj3349]Snowflake Snow Snowflakes_hash

    Snowflake Snow Snowflakes poj-3349     题目大意:给出n片雪花,每片雪花有6个角,每个角有一个权值。如果两片雪花中能够各选出一个点,使得从该点顺时针或者逆时针转,得到的权值序列完全相符,那么我们就说这两片雪花是完全相同的。     注释:$1\le n\le

    来自 JZYshuraK
    00
  • avatar 晨微雨梦宿雨飞 2019-09-12 20:10:11

    最小的K个数

    最直观的想法是使用冒泡排序,因为每一趟冒泡排序后,最小的一定在最上面,因此最外层只需要K次循环 import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumber

  • avatar JZYshuraK 2018-03-20 19:59:00

    [bzoj1601]灌水_kruskal

    灌水 bzoj-1601     题目大意:给你n块地,将两块地之间连通有代价$P_{i,j}$,单独在一块地打井需要代价$C_i$,问将所有的井都有水的代价是多少。     注释:1<=n<=300.       想法:这种题做过一遍就好了,我们新建立一个0号节点。如果两块地之间

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-20 19:05:00

    [poj3687]Labeling Balls_拓扑排序

    Labeling Balls poj-3687     题目大意:给出一些球之间的大小关系,求在满足这样的关系下,编号小的尽量比编号大的球的方案。     注释:1<=N(球的个数)<=200,1<=M(题目给出的关系数)<=40000.       想法:和poj10

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-20 20:25:00

    [bzoj1707]tanning分配防晒霜_贪心+排序

    tanning分配防晒霜 bzoj-1707     题目大意:给出每个点所能接受的区间,给出m个可以使单个点固定在一个值的方法,每种方法能使用有限次。     注释:1<=N<=2500       想法:这题是瞎jb写然后A了,看了大佬的证明才知道自己写的贪心是正确的。对于每一

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-20 18:37:00

    [poj1094]Sorting It All Out_拓扑排序

    Sorting It All Out poj-1094     题目大意:给出一些字符串之间的大小关系,问能否得到一个唯一的字符串序列,满足权值随下标递增。     注释:最多26个字母,均为大写。       想法:显然,很容易想到用toposort处理,对于每一个刚刚读入的大小关系,我们对

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-20 10:42:00

    [poj2585]Window Pains_拓扑排序

    Window Pains poj-2585     题目大意:给出一个4*4的方格表,由9种数字组成。其中,每一种数字只会出现在特定的位置,后出现的数字会覆盖之前在当前方格表内出现的。询问当前给出的方格表是否合法。     注释:输入格式需要注意。       想法:toposort裸题,我们

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-19 21:03:00

    [poj2367]Genealogical tree_拓扑排序

    Genealogical tree poj-2367     题目大意:给你一个n个点关系网,求任意一个满足这个关系网的序列,使得前者是后者的上级。     注释:1<=n<=100.       想法:刚刚学习toposort,什么是toposort?         就是每一

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-19 20:06:00

    [poj2406]Power Strings_hash

    Power Strings poj-2406     题目大意:询问一个字符串最多几个相同且连续的字符串构成(Eg:abababab由4个构成,abcd由1个构成)。     注释:字符串长度为n,$1\le n\le 10^6$.       想法:hash裸题,通过Hash求出单个字符串的

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-19 19:22:00

    [poj3904]Sky Code_状态压缩_容斥原理

    Sky Code poj-3904     题目大意:给你n个数,问能选出多少满足题意的组数。     注释:如果一个组数满足题意当且仅当这个组中有且只有4个数,且这4个数的最大公约数是1,$1\le n\le 10^4$。       想法:我们显然可以知道4个数是可以不用两两互质的,所以正

    来自 JZYshuraK
    00
  • avatar JZYshuraK 2018-03-19 10:41:00

    [luogu2831][noip d2t3]愤怒的小鸟_状压dp

    愤怒的小鸟 noip-d2t3 luogu-2831     题目大意:给你n个点,问最少需要多少条经过原点的抛物线将其覆盖。     注释:1<=点数<=18,1<=数据组数<=30。且规定抛物线是开口向下的。       想法:其实一开始的想法是很偏的,就是设dp[

    来自 JZYshuraK
    00