算法 - Page 103 - hzwer.com

「CF415D」Mashmokh and ACM
Mashmokh'sboss,Bimokh,didn'tlikeMashmokh.Sohefiredhim.MashmokhdecidedtogotouniversityandparticipateinACMinsteadoffindinganewjob.HewantstobecomeamemberofBamokh'steam.Inordertojoinhewasgivensomeprogrammingtasksandoneweektosolvethem.Mashmokhisnotaveryexperiencedprogrammer.Actuallyheisnotaprogrammeratall.Sohewasn'tabletosolvethem.That'swhyheaskedyoutohelphimwiththesetasks.Oneofthesetas...
02014年4月7日3,672递推与动规,筛法

「CF415C」Mashmokh and Numbers
It'sholiday.Mashmokhandhisboss,Bimokh,areplayingagameinventedbyMashmokh.InthisgameMashmokhwritessequenceof n distinctintegersontheboard.ThenBimokhmakesseveral(possiblyzero)moves.Onthefirstmoveheremovesthefirstandthesecondintegerfromfromtheboard,onthesecondmoveheremovesthefirstandthesecondintegeroftheremainingsequencefromtheboard,andsoon.Bimokhstopswhentheboardcontainslessthantwonumbers...
02014年4月7日3,951构造,筛法
「CF415B」Mashmokh and Tokens
BimokhisMashmokh'sboss.Forthefollowing n dayshedecidedtopaytohisworkersinanewway.Atthebeginningofeachdayhewillgiveeachworkeracertainamountoftokens.Thenattheendofeachdayeachworkercangivesomeofhistokensbacktogetacertainamountofmoney.Theworkercansavetherestoftokensbuthecan'tuseitinanyotherdaytogetmoremoney.Ifaworkergivesback w tokensthenhe'llget dollars.Mashmokhlikesthetokenshoweverhel...
02014年4月7日2,751其它
「CF415A」Mashmokh and Lights
Mashmokhworksinafactory.Attheendofeachdayhemustturnoffallofthelights.Thelightsonthefactoryareindexedfrom 1 to n.Thereare n buttonsinMashmokh'sroomindexedfrom 1 to n aswell.IfMashmokhpushesbuttonwithindex i,theneachlightwithindexnotlessthani thatisstillturnedonturnsoff.Mashmokhisnotveryclever.Soinsteadofpushingthefirstbuttonhepushessomeofthebuttonsrandomlyeachnight.Hepushed m ...
02014年4月7日2,261模拟
「BZOJ1036」[ZJOI2008] 树的统计Count
Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身Input输入的第一行为一个整数n，表示节点的个数。接下来n–1行，每行2个整数a和b，表示节点a和节点b之...
272014年4月6日40,483线段树,树链剖分,link cut tree
「BZOJ1602」[Usaco2008 Oct] 牧场行走
DescriptionN头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。这n块土地被n-1条边连接。奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的...
02014年4月6日4,787最近公共祖先
「BZOJ1611」[Usaco2008 Feb] Meteor Shower流星雨
Description去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息：一场流星雨即将袭击整个霸中，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，芙蓉哥哥开始担心自己的安全问题。以霸中至In型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将霸中放入一个直角坐标系中，芙蓉哥...
02014年4月6日3,283广度搜索
「ch30」摆花
背景及描述艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。输入格式输入有1+m行，第一行有两个用空格隔开的正整数n、m，m表示花的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种花和第j种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位...
02014年4月5日5,015递推与动规,矩阵乘法
「BZOJ1669」[Usaco2006 Oct] Hungry Cows饥饿的奶牛
DescriptionFarmerJohn养了N(1<=N<=5,000)头奶牛，每头牛都有一个不超过32位二进制数的正整数编号。FJ希望奶牛们在进食前，能按编号从小到大的顺序排好队，但奶牛们从不听他的话。为了让奶牛们养成这个习惯，每次开饭时，FJ从奶牛中顺序地挑出一些，这些奶牛的编号必须按挑出的顺序递增。然后FJ让被挑出的奶牛们吃饭——其他奶牛就只能饿肚子了。现在，你得到了这一次开饭前队伍中从前到后所有奶牛的编号。奶牛们...
02014年4月5日3,886递推与动规,二分法
「NOIP模拟赛」翻转排序
题目描述Alex得到了存放着一个1-n排列的容器。这个容器支持的唯一操作，是翻转排列的某一段。思考很久之后，他决定用以下方式让这个排列有序：1找到每一个极大的下降子序列（子序列要求连续）2对于每个长度大于1的极大下降子序列，对它进行翻转3如果排列依然不是有序的，转1我们举一个例子：初始排列是(53142)一开始极大的下降子序列是(531)(42)把这些序列翻转后得到13524接下来的极大下降子序列是(1)(3)(52)(4)翻转后是13254接下...
02014年4月5日3,072其它
「NOIP模拟赛」DNA序列
题目描述来自JSSI（JinkelaStateScientificInstitute）的科学家们尝试制造一个长度为N并且只包含A的DNA序列，不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改，来得到一个全部是A的序列。篡改的方式有两种：1更改某一位上部件的状态（A变成B，B变成A）2更改某个前缀内所有部件的状态两种操作的代价都为1。你的任务自然是求最小代价。输入第一行为N，序列长度。第二...
02014年4月5日3,572递推与动规
「NOIP模拟赛」求和式
题目描述作为本场考试的第一题，你的任务十分简单：给定长度为n的序列A[i]，求所有A[i]xorA[j](i<j)的值之和输入第一行一个整数N接下来N行，第i行为A[i]输出所需的值样例输入3735样例输出12样例解释7xor3+3xor5+7xor5=4+6+2=12数据范围对于40%的数据，N<=5000对于100%的数据，N<=1000000题解转为二进制一位一位处理统计第i位所有数字0或1的个数，记为a[i]和b[i]则对于答案的贡献为a[i]*b[i]*1<<(i-1)[crayo...
02014年4月5日2,784其它