递推与动规 - Page 7

「BZOJ2298」[HAOI2011] problem a
Description一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)Input第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、biOutput一个整数，表示最少有几个人说谎SampleInput3200222SampleOutput1题解100%的数据满足：1≤n≤100000 0≤ai、bi≤n求最多说真话的人数，答案即为n-ans设dp[i]表示在前i名中最多有多少人说真话dp...
32014年12月1日5,340递推与动规

「BZOJ1049」[HAOI2006] 数字序列
Description现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。Input第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。Output第一行一个整数表示最少需要改变多少个数。第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。SampleInput45235SampleOutput14HINT「数据范围」90%的...
12014年12月1日5,302递推与动规
「BZOJ1042」[HAOI2008] 硬币购物
Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。Input第一行c1,c2,c3,c4,tot下面tot行d1,d2,d3,d4,sOutput每次的方法数SampleInput1251023231101000222900SampleOutput427HINT数据规模di,s<=100000tot<=1000题解我想起了cf的某道题。。。dp预处理+容斥原理byvoid：设F[i]为不考虑每种硬币的数量限制的...
32014年11月30日8,606递推与动规,容斥原理
NOI2009诗人小G
DescriptionInputOutput对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出"Toohardtoarrange"(不包含引号)。每个输出后面加"--------------------"SampleInput4493brysj,hhrhl.yqqlm,gsycl.492brysj,hhrhl.yqqlm,gsycl.110056poet110046poetSampleOutput108--------------------32--------------------Toohardtoarrange--------------------1000000000000000000---...
02014年11月29日5,830递推与动规,贪心,决策单调性
「BZOJ3437」小P的牧场
Description 背景小P是个特么喜欢玩MC的孩纸。。。描述小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需...
22014年11月29日6,230递推与动规,斜率优化
「BZOJ3427」POI2013 Bytecomputer
DescriptionAsequenceofN integersI1,I2…Infromtheset{-1,0,1}isgiven.Thebytecomputerisadevicethatallowsthefollowingoperationonthesequence:incrementingI(i+1)byI(i)forany1<=I<=N.Thereisnolimitontherangeofintegersthebytecomputercanstore,i.e.,eachI(i)can(inprinciple)havearbitrarilysmallorlargevalue.Programthebytecomputersothatittransformstheinputsequenceintoanon-decreasingsequence(i...
02014年11月22日2,634递推与动规
「BZOJ1089」[SCOI2003] 严格n元树
Description如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：给出n,d，编程数出深度为d的n元树数目。Input仅包含两个整数n,d(0 < n < = 32, 0 <= d <=16)Output仅包含一个数，即深度为d的n元树的数目。SampleInput「样例输入1」22「样例输入2」...
02014年11月14日4,936递推与动规,高精度
「NOIP模拟赛」篮球比赛1
Czhou为了提高机房里各种神牛的身体素质，决定在每次训练后举行篮球比赛。为了保持比赛公平，Czhou要将神牛们分成两队。首先神牛们赛前都要排成固定的队伍；然后Czhou将队伍分成一半（前一半和后一半队伍人数可以不等），再分别从两个队伍中选出一些人进行篮球比赛。为了保持公平性，Czhou要求第一个队伍参加比赛的神牛能力的XOR值等于第二个队伍参加比赛的神牛能力的and值。为了增加比赛趣味，每次比赛的参加神牛们不能...
02014年11月5日3,324递推与动规
「NOIP模拟赛」序列问题
「题目描述」小H是个善于思考的学生，她正在思考一个有关序列的问题。她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。这两个集合要满足以下的条件：1.两个集合中的元素都为整数，且都在[1,n]里，即Si，Ti∈[1,n]。2.对于集合S中任意一个元素x，集合T中任意一个元素y，满足x<y。3.对于大小分别为p,q的集合S与T，满足 a[s1]xora[s2]xora[s3]...xora[sp]=a[t1]anda[t2]anda[t3]...anda[tq]....
02014年11月4日5,671递推与动规,深度搜索
「NOIP模拟赛」改造二叉树
「题目描述」小Y在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch，则key[p]<key[rch]；注意，本...
12014年11月4日2,668递推与动规
「NOIP模拟赛」机房人民大团结
最近，机房出了一个不团结分子：Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”，使同学们神志不清，殴打他人，砸烂计算机，破坏机房团结。幸运地，一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起，共同对抗Dr.Weissman及“教授糖豆”。同学们十分具有社会责任感：他们害怕“教授糖豆”流向社会，导致动乱。于是，刚才提到的和谐家身先士卒，为了实验，品尝“教授糖豆”。每个“教授糖豆”的性质都有所不同。同志...
02014年11月2日2,924递推与动规
「NOIP模拟赛」迎接仪式
「问题描述」LHX教主要来X市指导OI学习工作了。为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。为了简单描述这个不和谐的队列，我们用“j”替代“教”，“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。为了让教主...
02014年11月2日2,691递推与动规