2 Liang-梁

尚未进行身份认证

暂无相关描述

等级
博文 43
排名 11w+

珍珠项链(洛谷-P2768)(Dp矩阵加速)

文章目录题目思路代码题目Luogu题目大意:kkk种珍珠,每种珍珠都要用上,问能做出长度[1,2,…,N]的首饰的方案数,答案模123456789112345678911234567891T<=10,1<=N<=1000000000,0<=K<=30T<=10,1<=N&lt...

2019-04-05 18:21:23

保卫王国(NOIP-2018)(倍增Dp预处理,动态查询)

文章目录题目思路代码题目Luogu-传送门题目大意:给你一棵树进行染色,iii号节点染色费用为pip_ipi​,要求相邻两个节点必须有一个要染色,现在给出mmm个询问,分别要求两个节点必须(染|不染)色,对于每个询问求出最小染色代价数据范围:1≤n,m≤100000,1≤pi≤1000001\len,m\le100000,1≤p_i≤1000001≤n,m≤100000,1≤...

2019-04-03 14:06:04

[USACO18DEC]The Cow Gathering(洛谷-5157)(树-思维题)

文章目录题目描述思路代码题外话题目描述Luogu-传送门思路首先我们可以发现这是棵树然后我们可以通过分析题目发现:如果此时走的人牛不是叶节点,最终会剩下至少两个单独的节点,不符合题意所以我们每次删除只能删除叶节点(a,b)(a,b)(a,b)表示aaa必须比bbb之前删那么假设我们现在有棵树表示牛之间的关系(根节点任意):然后我们现在有几组(a,b)(a,...

2019-03-11 13:21:01

Uva-11077(Find the Permutations-排列统计)(斯特林数+Dp)

文章目录题目题目大意:数据范围思路代码题目vjudge传送门Uva传送门题目大意:给出1~n的排列,可以通过一系列的交换成{1,2,3,…,n}给定n,k求统计有多少个排列至少需要交换k次才能变成{1,2,3,…,n}数据范围1≤n≤21,0≤k<n1\len\le21,0\lek<n1≤n≤21,0≤k<n思路我们首先记PPP...

2019-03-07 13:26:04

Kaleidoscope(HDU-6360)(Polya定理)

文章目录题目描述题目描述传送门-Vjudge传送门-HDU题目大意:给你一个菱形6面体(共60面),然后给你nnn种颜色给它每一个面上色,要求第iii种颜色必须至少涂c[i]c[i]c[i]次,问你方案数,方案数对ppp取模,多组数据数据范围:1≤T≤1000,1≤n≤60,1≤p1\leT\le1000,1\len\le60,1\lep1≤T≤1000,1≤...

2019-03-06 13:20:47

通俗易懂快速排序过程讲解,转自《坐在马桶上看算法:快速排序》

2018-10-30 09:32:33

股票交易(BZOJ-1855)(Dp转移优化+单调队列优化Dp)

文章目录前言题目思路代码题外话前言Dp优化最难理解了…题目传送门BZOJVjudge思路ap买入价bp卖出价as买入最大股bs卖出最大股首先,我们要写出一般形式的Dp。我们定义:f[i][j]:第i天此时手上股票数为j,前i天最大获利f[i][j]:第i天此时手上股票数为j,前i天最大获利f[i][j]:第i天此时手上股票数为j,前i天最大获利①我们先初始化边界,:...

2018-10-29 23:53:13

Subsequence(Hdu3530)(单调队列运用)

文章目录题目思路代码题目HduVjudge题目大意:给你一个长度为n的序列,让你求它的一个区间[L,R]使得区间内最大值和最小值差值在[m,k]范围内,求区间长度最大值。范围:1<=n<=100000,0<=m,a[i],k<=1000001<=n<=100000,0<=m,a[i],...

2018-10-29 15:45:51

Password(CodeForces-126B)(KMP算法变形,字符串Dp,Hash)

文章目录前言题目思路代码前言这里的Dp定义很容易和KMP的Fail数组搞混…题目传送门:CodeForcesVjudge题目大意:你现在有一个长度为n的字符串S,现在让你求它的一个最长子串T使其既为S前缀,又为S后缀,并且在S中非前缀非后缀中出现过一次数据范围:1≤n≤1061\len\le10^61≤n≤106思路思路很简单,定义:Dp[i]为i为末尾的子串的后...

2018-10-25 15:08:31

欧拉回路/路径浅谈(七桥问题,两种算法)

文章目录前言引子欧拉回路/路径定义欧拉路径欧拉回路无向图(连通)欧拉回路-有向欧拉路径-有向有向图(连通)欧拉回路-无向欧拉路径-无向算法Fluery算法Hierholzer算法前言欧拉回路/路径在编程中经常涉及,而找欧拉回路/路径是出题者经常要考的东西…引子欧拉回路、路径问题来源于18世纪著名古典数学问题之一,问题如下:在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接...

2018-10-24 17:32:23

Robot Arms(AtCoder-4432)(二进制构造,数学归纳证明,贪心策略)

文章目录前言题目思路构造长度奇偶性判断无解把1去掉加一个1证明贪心走法代码题外话前言一道极为好的题,这思路我打包票比赛时写不出来…题目传送门:VjudgeAtcoder题目大意:现在你有n个点,然后让你构造一个长度为m的序列,序列中d[i]d[i]d[i]是每一次移动的距离,输出这个序列,你对每个点对(xi,yix_i,y_ixi​,yi​)每一次从原点出发执行m此操作,对于每一个...

2018-10-20 22:08:41

Nature Reserve(Codeforces Round #514 (Div. 2)-1060E)(三分答案,数学)

文章目录前言题目前言这种题没做过,但考试时想得差不多了…题目CF传送门题目大意现在有n个点,坐标分别为(xi,yi)(x_i,y_i)(xi​,yi​),现在求一个最小半径的圆,使得包含所有点且和xxx轴相切(只有一个交点),若不存在,输出-1答案精确到10−610^{-6}10−6inputinputinput101outputoutputoutput0.5inpu...

2018-10-06 11:25:43

Sergey and Subway(CodeForces-1060E#513)(DFS计数,数学)

文章目录前言题目思路代码前言本题思路极为简单和巧妙!题目CF传送门题目大意:给你一个有n个节点的树,如果有原树有两点距离为2则加一条边,求修改后所有点对的距离和.数据范围:2<=n<=2000002<=n<=2000002<=n<=200000样例:input1input1input1412131...

2018-10-06 09:43:35

Maximum Subrectangle(CodeForces-1060C#513)(预处理优化暴力)

文章目录前言前言打的时候开始写了O(n2logn)O(n^2log_n)O(n2logn​)的二分,调了半天…还是没过,然后发现直接预处理暴力就过了…

2018-10-05 16:23:29

琪露诺(洛谷P1725)(简单滑窗优化Dp)

文章目录题目题目大意:数据范围思路代码题目非常废话传送门题目大意:给你一个长度为n+1的格子,编号为[0,n],你在0,现在你要从0跳过n,每次你能跳到下一个格子的区间为[i+L,i+R],每个格子有一个价值A[i],求跳过n后使沿途格子价值和最大的最大值.数据范围对于60%的数据:N<=10,000N<=10,000N<=10,000对于10...

2018-10-04 13:24:25

Bash and a Tough Math Puzzle(CodeForces-11D)(线段树)

文章目录题目传送门题目题目大意思路代码常规版懒人加速版题目传送门CFVjudge题目Bashlikesplayingwitharrays.Hehasanarraya1a_1a1​, a2a_2a2​, …anofnintegers.Helikestoguessthegreatestcommondivisor(gcd)ofdifferent...

2018-10-03 18:39:54

陈太阳与取模(数学思维题)

文章目录题目大意题解代码题目大意陈太阳打了一个响指,这世上的数字便都减少了一半。对于所有在[L,R][L,R][L,R]中的正整数,陈太阳将他们都变成了除以A的余数。现在陈太阳想知道有多少个正整数X,满足对于任意正整数i∈[L,R]i∈[L,R]i∈[L,R],都有imodX≡(imodA)modXimodX≡(imodA)modXimodX≡(imodA)modX给定A,L,R,请你...

2018-10-02 19:31:25

划分物品

文章目录题目大意题解代码题目大意你有n个物品,第i个物品的重量是wiw_iwi​。你需要把这些物品划分成若干组,满足每一组的重量和都是质数。两个方案是不同的当且仅当存在两个物品i和j,在第一个方案里他们处在同一组,第二个方案里他们不处在同一组。输入格式第一行输入两个整数n。接下来一行n个整数wiw_iwi​。输出格式输出一行一个整数表示方案数,答案可能很大,...

2018-10-02 18:40:02

Team them up!-团队分组(UVa1627)(黑白染色+Dp 0-1背包)

前言题目思路细节提示代码题外话前言写了我好久……实现也比较丑陋……连续9行清空…输出也比较恶心题目传送门:VjudgeUVa(有点慢)题目大意:有n(n<=100)个人,把他们分成非空的两组,使得每个人都被分到一组,且在同一组中的人互相认识,要求两组成员人数尽量接近,多解时输出任意一组方案,无解时输出NoSolution...

2018-08-21 16:59:15

Tour(旅行)(UVa1347,ACM/ICPC SEERC 2005)(Dp优化去重)

前言题目思路状态转移方程统计答案有关初值代码题外话前言这道题的思路十分巧啊~题目传送门:VjudgeUVa(有点慢)题目大意:在平面上给你n(n<=1000)个点的坐标(按照x递增给出,各x坐标不同,且均为整数),现在你要设计一条路线,从最左边出发,走到最右边的点后再返回,要求除了最左点和最右点之外每个点恰好经过一次,...

2018-08-19 20:12:36
奖章
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得