Browsed by
Category: ACM Algorithm

ACM&算法

CF 543A Writing Code 完全背包问题

CF 543A Writing Code 完全背包问题

time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly ai bugs in every line of code that he writes. Let’s call a sequence of non-negative integers v1, v2, …, vn a plan, if v1 + v2 + … + vn = m. The programmers follow the plan like that: in the beginning the first programmer writes the first v1 lines of the given…

Read More Read More

动态规划建模方法

动态规划建模方法

  转载 http://www.cnblogs.com/sdjl/articles/1274312.html 通过金矿模型介绍动态规划 对于动态规划,每一个刚接触的人都须要一段时间来理解,特别是第一次接触的时候总是想不通为什么这样的方法可行,这篇文章就是为了帮助大家理解动态规划,并通过解说主要的01背包问题来引导读者怎样去思考动态规划。本文力求通俗易懂,无异性,不让读者感到迷惑,引导读者去思考,所以假设你在阅读中发现有不通顺的地方,让你产生错误理解的地方,让你难得读懂的地方,请跟贴指出,谢谢! —-第一节—-初识动态规划——– 经典的01背包问题是这种: 有一个包和n个物品,包的容量为m,每一个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,可以得到的最大价值是多少?[对于每一个物品不可以取多次,最多仅仅能取一次,之所以叫做01背包,0表示不取,1表示取] 为了用一种生动又更形象的方式来解说此题,我把此题用还有一种方式来描写叙述,例如以下: 有一个国家,全部的国民都很老实憨厚,某天他们在自己的国家发现了十座金矿,而且这十座金矿在地图上排成一条直线,国王知道这个消息后很高兴,他希望可以把这些金子都挖出来造福国民,首先他把这些金矿依照在地图上的位置从西至东进行编号,依次为0、1、2、3、4、5、6、7、8、9,然后他命令他的手下去对每一座金矿进行勘測,以便知道挖取每一座金矿须要多少人力以及每座金矿可以挖出多少金子,然后动员国民都来挖金子。 题目补充1:挖每一座金矿须要的人数是固定的,多一个人少一个人都不行。国王知道每一个金矿各须要多少人手,金矿i须要的人数为peopleNeeded。 题目补充2:每一座金矿所挖出来的金子数是固定的,当第i座金矿有peopleNeeded人去挖的话,就一定能恰好挖出gold个金子。否则一个金子都挖不出来。 题目补充3:开採一座金矿的人完毕开採工作后,他们不会再次去开採其他金矿,因此一个人最多仅仅能使用一次。 题目补充4:国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人,因此这些人可能不够把全部的金子都挖出来,可是国王希望挖到的金子越多越好。 题目补充5:这个国家的每个人都非常老实(包含国王),不会私吞不论什么金子,也不会弄虚作假,不会说谎话。 题目补充6:有非常多人拿到这个题后的第一反应就是对每个金矿求出平均每个人能挖出多少金子,然后从高到低进行选择,这里要强调这样的方法是错的,假设你也是这样想的,请考虑背包模型,当有一个背包的容量为10,共同拥有3个物品,体积各自是3、3、5,价值各自是6、6、9,那么你的方法取到的是前两个物品,总价值是12,但明显最大值是后两个物品组成的15。 题目补充7:我们仅仅须要知道最多能够挖出多少金子就可以,而不用关心哪些金矿挖哪些金矿不挖。 那么,国王到底怎样知道在仅仅有10000个人的情况下最多能挖出多少金子呢?国王是怎样思考这个问题的呢? 国王首先来到了第9个金矿的所在地(注意,第9个就是最后一个,由于是从0開始编号的,最西边的那个金矿是第0个),他的臣子告诉他,假设要挖取第9个金矿的话就须要1500个人,而且第9个金矿能够挖出8888个金子。听到这里国王哈哈大笑起来,由于原先他以为要知道十个金矿在仅有10000个人的情况下最多能挖出多少金子是一件非常难思考的问题,可是,就在刚才听完他的臣子所说的那句话时,国王已经知道总共最多能挖出多少金子了,国王是怎样在不了解其他金矿的情况下知道最多能挖出多少金子的呢?他的臣子们也不知道这个谜,因此他的臣子们就问他了:“最聪明的国王陛下,我们都没有告诉您其他金矿的情况,您是怎样知道终于答案的呢?” 得意的国王笑了笑,然后把他最得意的“左、右手”叫到跟前,说到:“我并不须要考虑终于要挖哪些金矿才干得到最多的金子,我仅仅须要考虑我面前的这座金矿就能够了,对于我面前的这座金矿不外乎仅有两种选择,要么挖,要么不挖,对吧?” “当然,当然”大臣们回答倒。 国王继续说道:“假设我挖取第9座金矿的话那么我如今就能获得8888个金子,而我将用去1500个人,那么我还剩下8500个人。我亲爱的左部下,假设你告诉我当我把全部剩下的8500个人和全部剩下的其他金矿都交给你去开採你最多能给我挖出多少金子的话,那么我不就知道了在第9个金矿一定开採的情况下所能得到的最大金币数吗?” 国王的左部下听后回答道:“国王陛下,您的意思是假设我能用8500个人在其他金矿最多开採出x个金币的话,那您一共就行获得 x + 8888个金子,对吗?” “是啊,是啊……假设第9座金矿一定开採的话……”大臣们点头说到。 国王笑着继续对着他的右部下说到:“亲爱的右部下,或许我并不打算开採这第9座金矿,那么我依旧拥有10000个人,假设我把这10000个人和剩下的金矿都给你的话,你最多能给我挖出多少个金子呢?” 国王的右部下聪明地说道:“尊敬的国王陛下,我明确您的意思了,假设我回答最多能购开採出y个金币的话,那您就能够在y和x+8888之间选择一个较大者,而这个较大者就是终于我们能获得的最大金币数,您看我这样理解对吗?” 国王笑得更灿烂了,问他的左部下:“那么亲爱的左部下,我给你8500个人和其余金矿的话你能告诉我最多能挖出多少金子吗?” “请您放心,这个问题难不倒我”。左部下向国王打包票说到。 国王高兴地继续问他的右部下:“那右部下你呢,假设我给你10000个人和其余金矿的话你能告诉我最多能挖出多少金子吗?” “当然能了!交给我吧!”右部下同左部下一样自信地回答道。 “那就拜托给你们两位了,如今我要回到我那舒适的王宫里去享受了,我期待着你们的答复。”国王说完就開始动身回去等消息了,他是多么地相信他的两个大臣可以给他一个准确的答复,由于国王事实上知道他的两位大臣要比他聪明得多。 故事发展到这里,你是否在想国王的这两个大臣又是怎样找到让国王惬意的答案的呢?他们为什么可以如此自信呢?其实他们的确比国王要聪明一些,由于他们从国王的身上学到了一点,就是这一点让他们充满了自信。 国王走后,国王的左、右部下来到了第8座金矿,早已在那里等待他们的金矿勘測兵向两位大臣报道:“聪明的两位大臣,您们好,第8座金矿须要1000个人才干开採,能够获得7000个金子”。 由于国王仅给他的左部下8500个人,所以国王的左部下叫来了两个人,对着当中一个人问到:“假设我给你7500个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?” 然后国王的左部下继续问还有一个人:“假设我给你8500个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?” 国王的左部下在心里想着:“假设他们俩都能回答我的问题的话,那国王交给我的问题不就攻克了吗?哈哈哈!” 由于国王给了他的右部下10000个人,所以国王的右部下相同也叫来了两个人,对着当中一个人问:“假设我给你9000个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?” 然后国王的右部下继续问他叫来的还有一个人:“假设我给你10000个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?” 此时,国王的右部下同左部下一样,他们都在为自己如此聪明而感到满足。 当然,这四个被叫来的人相同自信地回答没有问题,由于他们相同地从这两个大臣身上学到了相同的一点,而两位自觉得自己一样非常聪明的大臣得意地笑着回到了他们的府邸,等着别人回答他们提出来的问题,如今你知道了这两个大臣是怎样解决国王交待给他们的问题了吗? 那么你觉得被大臣叫去的那四个人又是怎么完毕大臣交给他们的问题的呢?答案当然是他们找到了另外八个人! 没用多少功夫,这个问题已经在全国传开了,很多其它人的人找到了更很多其它的人来解决问题,而有些人却不须要去另外找两个人帮他,哪些人不须要别人的帮助就能够回答他们的问题呢? 非常明显,当被问到给你z个人和仅有第0座金矿时最多能挖出多少金子时,就不须要别人的帮助,由于你知道,假设z大于等于挖取第0座金矿所须要的人数的话,那么挖出来的最多金子数就是第0座金矿可以挖出来的金子数,假设这z个人不够开採第0座金矿,那么能挖出来的最多金子数就是0,由于这唯一的金矿不够人力去开採。让我们为这些不须要别人的帮助就行准确地得出答案的人们鼓掌吧,这就是传说中的底层劳动人民! 故事说到这里先暂停一下,我们如今又一次来分析一下这个故事,让我们对动态规划有个理性认识。 子问题: 国王须要依据两个大臣的答案以及第9座金矿的信息才干推断出最多可以开採出多少金子。为了解决自己面临的问题,他须要给别人制造另外两个问题,这两个问题就是子问题。 思考动态规划的第一点—-最优子结构: 国王相信,仅仅要他的两个大臣可以回答出正确的答案(对于考虑可以开採出的金子数,最多的也就是最优的同一时候也就是正确的),再加上他的聪明的推断就一定能得到终于的正确答案。我们把这样的子问题最优时母问题通过优化选择后一定最优的情况叫做“最优子结构”。 思考动态规划的第二点—-子问题重叠: 实际上国王也好,大臣也好,全部人面对的都是相同的问题,即给你一定数量的人,给你一定数量的金矿,让你求出可以开採出来的最多金子数。我们把这样的母问题与子问题本质上是同一个问题的情况称为“子问题重叠”。然而问题中出现的不同点往往就是被子问题之间传递的參数,比方这里的人数和金矿数。 思考动态规划的第三点—-边界: 想想假设不存在前面我们提到的那些底层劳动者的话这个问题能解决吗?永远都不可能!我们把这样的子问题在一定时候就不再须要提出子子问题的情况叫做边界,没有边界就会出现死循环。 思考动态规划的第四点—-子问题独立: 要知道,当国王的两个大臣在思考他们自己的问题时他们是不会关心对方是如何计算如何开採金矿的,由于他们知道,国王仅仅会选择两个人中的一个作为最后方案,还有一个人的方案并不会得到实施,因此一个人的决定对还有一个人的决定是没有影响的。我们把这样的一个母问题在对子问题选择时,当前被选择的子问题两两互不影响的情况叫做“子问题独立”。 这就是动态规划,具有“最优子结构”、“子问题重叠”、“边界”和“子问题独立”,当你发现你正在思考的问题具备这四个性质的话,那么恭喜你,你基本上已经找到了动态规划的方法。 有了上面的这几点,我们就行写出动态规划的转移方程式,如今我们来写出相应这个问题的方程式,假设用gold[mineNum]表示第mineNum个金矿可以挖出的金子数,用peopleNeeded[mineNum]表示挖第mineNum个金矿须要的人数,用函数f(people,mineNum)表示当有people个人和编号为0、1、2、3、……、mineNum的金矿时可以得到的最大金子数的话,f(people,mineNum)等于什么呢?或者说f(people,mineNum)的转移方程是如何的呢? 答案是: 当mineNum = 0且people >= peopleNeeded[mineNum]时 f(people,mineNum) = gold[mineNum] 当mineNum = 0且people < peopleNeeded[mineNum]时 f(people,mineNum) = 0 当mineNum != 0时 f(people,mineNum)…

Read More Read More

[转载]有向图强连通分量的Tarjan算法

[转载]有向图强连通分量的Tarjan算法

转自:https://www.byvoid.com/blog/scc-tarjan [有向图强连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。 直接根据定义,用双向遍历取交集的方法求强连通分量,时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法,两者的时间复杂度都是O(N+M)。本文介绍的是Tarjan算法。 [Tarjan算法] Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。 定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出, Low(u)=Min { DFN(u), Low(v),(u,v)为树枝边,u为v的父节点 DFN(v),(u,v)为指向栈中节点的后向边(非横叉边) } 当DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。 算法伪代码如下 tarjan(u) { DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) else if (v in S) // 如果节点v还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 repeat v = S.pop // 将v退栈,为该强连通分量中一个顶点 print v until (u== v) } 接下来是对算法流程的演示。 从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。…

Read More Read More

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

题目链接 http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=337 代码神马的还没有写完 ,先把思路放上来 等到代码写好之后再贴代码 A Taxi Fare 水题,注意精度问题 求出来的两个费用都要四舍五入 如果只对最后一次进行四舍五入的话会WA B Unrequited Love 这个题是想法+STL搞 首先 根据名流问题的思想 我们可以通过O(N)的算法排除掉不可能是答案的人 最后剩下一个人判断一下他是不是喜欢宴会上的所有人即可。 具体思想如下:如果A喜欢B,那么B就不可能是Unrequited Love King or Queen (以下简称ans)反之,如果A不喜欢B 那么A就不可能是 ans 因此每次判断都会使问题的规模缩小1 这样就可以把问题规模在O(N)时间内缩小到 1,这样就只用判断一下这个人是不是ans即可,具体实现的时候 用 set存所有的喜欢关系 每个关系用一个二元组 pair<int,int>来表示,每一个名字映射到一个map<string,int>上 ,在具体实现时可以对上面的名流问题的解法进行优化,我们只需要一重循环从1—>N初值ans=1 然后去判断 如果ans不喜欢 i 或者 i喜欢ans 那么我们就更新ans 为 i 这里我们只判断了两种情况 实际上,ans 和 i之间的关系有四种 : ans喜欢i ans不喜欢i i喜欢ans i不喜欢ans 我们需要说明一下 循环中 既不满足 2 也不满足 3的i值一定不会是ans  ,很明显可以看出,这时,i和ans的关系一定是 1 4的任意一种,而这两个关系的任何一个 都说明了 i不可能是ans 所以我们这时候不去更新ans是正确的。因此这个算法的具体实现也没有问题了。 然后最后得到的ans我们还要判断一下他是不是喜欢所有人 。 —ps 这个题和性别无关哦~~~  heterosexuals 男男之间也可以互相喜欢哒 。有些人没看到这个地方以为是只有异性之间才可以互相喜欢 那么就会把问题搞错搞复杂 C Count the Trees 还是用hash的思想来稿 具体实现可以用map 这个题让我们判断有多少相同的子树,每个子树的样式可以用一个标号唯一确定 一棵树总共有n棵子树,同时 每个子树的结构可以用它的左右子树来唯一表示 ,这样的话 就建立了对应关系 我们用…

Read More Read More

[转]Fibonacci 数列的基本性质

[转]Fibonacci 数列的基本性质

fibonacci数列的性质: 1.gcd(fib(n),fib(m))=fib(gcd(n,m)) 证明:可以通过反证法先证fibonacci数列的任意相邻两项一定互素,然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m)),递归可 求gcd(fib(n),fib(m))=gcd(fib(k),fib(l)),最后k=l,不然继续递归。K是通过展转相减法求出,易证k=gcd(n,m),所以gcd(fib(n),fib(m)) =fib(gcd(n,m))。   2.如果fib(k)能被x整除,则fib(k*i)都可以被x整除。 3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1 4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n) 5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1 6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1) 7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1 8.f(n+m)=f(n+1)·f(m)+f(n)*f(m-1) 9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1) 10.f(2n-1)=[f(n)]^2-[f(n-2)]^2 11.3f(n)=f(n+2)+f(n-2) 12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

Calculate Prime S Time Limit: 2000MS Memory Limit: 262144KB 64bit IO Format: %lld & %llu Description Define S[n] as the number of subsets of {1, 2, …, n} that contain no consecutive integers. For each S[n], if for all i (1 ≤ i < n) gcd(S[i], S[n]) is 1, we call that S[n] as a Prime S. Additionally, S[1] is also a Prime S. For the Kth minimum Prime S, we’d like to find the minimum S[n]which is multiple of X and not less than the Kth minimum Prime S. Please tell us the corresponding (S[n] ÷ X) mod M. Input There are multiple test cases. The first line of input…

Read More Read More

快速幂算法 NEU 1391

快速幂算法 NEU 1391

本文是从以前的博客搬运而来 导致阅读效果不好请谅解 Orz 1391: Big Big Power 时间限制: 1 Sec  内存限制: 256 MB 提交: 123  解决: 14 题目描述 Calculate the power num a^(b^c) mod 1e9+7 输入 Multiple test cases,each case has three integers a,b and c . a,b,c is less than 1e9;   输出 Output the answer in each line   样例输入 2 3 2 样例输出 512 这道题的解法是快速幂 和费马小定理 正在研究 这是题解AC代码 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 const LL mod = 1000000007; 7…

Read More Read More

[MARK]各种字符串hash算法

[MARK]各种字符串hash算法

// RS Hash Function unsigned int RSHash(char* str) { unsigned int b = 378551 ; unsigned int a = 63689 ; unsigned int hash = 0 ; while (*str) { hash = hash * a + (*str ++ ); a *= b; } return (hash & 0x7FFFFFFF ); } // JS Hash Function unsigned int JSHash(char* str) { unsigned int hash = 1315423911 ; while (*str) { hash ^= ((hash << 5 ) + (*str ++ ) + (hash >>…

Read More Read More

hash 算法基础

hash 算法基础

首先来看一下什么是hash hash 实际上就是一个映射函数 ,使得把某一个不满足条件的量(可能难于存储 可能没法表示)映射到一个满足条件的量上 举个简单的例子理解一下 : 某学校要对2014级新生进行入学成绩统计 要用数组来存储学生的信息 而大家的学号都是 2014**** 这样的形式且每人的学号唯一确定  那么如果开一个数组大小为  20150000肯定是足够我们使用了 ,不过 在这个大数组里 ,最多只用了 10000个值,所以我们考虑用一个后四位作为存储的数组下标而不是整个学号 这其实就是一个hash的思想  我们相当于建立了一个hash函数 f(x)=x%10000 这样的话我们节省了空间 同样也使效率变得高 最简单的hash思想 桶排序 参见 HDU 的 1425题 (排序复杂度可以简化到 n) 冲突 我们通过上面学生的例子 能够发现,一个理想的hash函数应该是个一一映射的函数 即仅存在唯一一组y,x使得f(x)=y 但是 ,实际使用的时候 ,hash函数的这个性质很难保证甚至根本不能保证 举个例子 :把1000000个数映射到100个hash表上 (hash表就是指存hash映射关系的那个数组) 那么 一定会有多个不同值映射到了一个地址上 ,这样的现象叫做 冲突(collision)   那么如何解决冲突就成为了很重要的问题 我们在这里介绍几个方式 主要介绍第一个方式 线性探测再散列 线性探测再散列 这个方法的思想就是 如果遇到了冲突,那么就去查找它的下一个地址处是否已经有值,一直走下去 (走到头的话就回到数组首端) 直到遇到没有值的地方或者是又再次回到了f(k)处 结束循环 成功找到的话把值放进去 ,否则hash散列失败 举个例子如下 我们对这六个数字进行散列操作 有 23%7=2 46%7=4 19%7=5 55%7=6 38%7=3 233%7=2 我们会发现 在地址2处产生了冲突,因此我们使用线性探测再散列 按照由左到右的顺序来执行hash 在处理233之前的结果为下图 这时 由于f(233)=2但是 2处已经有值 所以 执行下面操作 :逐次循环后移直到找到hash表内值为空的地方再放入233 结果就是 : 这就是线性探测再散列法处理冲突 代码如下 int hash[MOD]; //存储映射关系 int num[MOD]; //检查hash表该位置是否为空…

Read More Read More