hzwer.com - Page 20

「POJ2154」Color
DescriptionBeadsofNcolorsareconnectedtogetherintoacircularnecklaceofNbeads(N<=1000000000).Yourjobistocalculatehowmanydifferentkindsofthenecklacecanbeproduced.YoushouldknowthatthenecklacemightnotuseupalltheNcolors,andtherepetitionsthatareproducedbyrotationaroundthecenterofthecircularnecklaceareallneglected.YouonlyneedtooutputtheanswermoduleagivennumberP.InputThefirstlineoftheinputisa...
02015年4月24日4,402置换,筛法,快速幂,欧拉函数

「POJ2409」Let it Bead
Description"LetitBead"companyislocatedupstairsat700CanneryRowinMonterey,CA.Asyoucandeducefromthecompanyname,theirbusinessisbeads.TheirPRdepartmentfoundoutthatcustomersareinterestedinbuyingcoloredbracelets.However,over90percentofthetargetaudienceinsiststhatthebraceletsbeunique.(Justimaginewhathappenediftwowomenshowedupatthesamepartywearingidenticalbracelets!)It'sagoodthingthatbracele...
02015年4月24日3,754置换,快速幂
「BZOJ2154」Crash的数字表格
Description今天的数学课上，Crash小朋友学习了最小公倍数(LeastCommonMultiple)。对于两个正整数a和b，LCM(a,b)表示能同时被a和b整除的最小正整数。例如，LCM(6,8)=24。回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张N*M的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i,j)。一个4*5的表格如下：1234522641036312154412420看着这个表格，Crash想到了很多可以思...
22015年4月24日6,520莫比乌斯反演
「BZOJ3624」[Apio2008] 免费道路
DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树，得出必须添加的0的边反过来，将0的边加至K条，再放1的边[crayon-67bbd15dc4361745757114/] ...
02015年4月24日5,478贪心,并查集
「BZOJ2811」[Apio2012] Guard
DescriptionInputOutputSampleInput534121341440451SampleOutput35HINT在这个样例中，有两种可能的安排方式：1，3，5 或者 2，3，5。即 3 和 5后面必然躲着一个忍者。考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一种安排方案使得它后面没有躲忍者，因此不应该输出 1。同理，不应该输出 2。题解首先先将0的区间去除，可以用线段树TT如果去除0剩下的坐标编号等于忍者数，则所有剩下的坐标...
122015年4月24日7,796贪心,线段树,二分法
「BZOJ3676」[Apio2014] 回文串
Description考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。Input输入只有一行，为一个只包含小写字母(a-z)的非空字符串s。Output输出一个整数，为逝查回文子串的最大出现值。SampleInput「样例输入l」abacaba「样例输入2]wwwSampleOutput「样例输出l」7「样例输出2]4HINT一个串是回文的，当且仅当它从左到右读和从右到...
182015年4月23日11,266后缀自动机,manacher
「BZOJ4002」[JLOI2015] 有意义的字符串
Description B君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入b;d;n，求((b+sqrt(D)/2)^N的整数部分，请输出结果Mod7528443412579576937之后的结果吧。Input一行三个整数b;d;nOutput 一行一个数表示模7528443412579576937之后的结果。SampleInput159SampleOutput76HINT 0<b^2<d<(b+1)2<10^18。题解http://blog.csdn.net/popoqqq/article/details/45148309为什么我不知道...
12015年4月23日4,895矩阵乘法
「BZOJ3990」[SDOI2015] 排序
Description 小A有一个1-2^N的排列A[1..2^N],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1<=i<=N),第i中操作为将序列从左到右划分为2^{N-i+1}段,每段恰好包括2^{i-1}个数,然后整体交换其中两段.小A想知道可以将数组A从小到大排序的不同的操作序列有多少个,小A认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同). 下面...
32015年4月23日6,151深度搜索
「BZOJ3210」花神的浇花集会
Description在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。具体浇水活动详情请见BZOJ3153但这不是重点花神出了好多题，每道题都有两个参考系数：代码难度和算法难度花神为了准备浇花集会的题，必须找一道尽量适合所有人的题现在花神知道每个人的代码能力x和算法能力y，一道题（代码难度X算法难度Y）对这个人的不适合度为 Max(abs(X–x),abs(Y–y))也就是说无论太难还是太简单都会导致题目不适合做（...
02015年4月23日3,478其它
「BZOJ3207」花神的嘲讽计划Ⅰ
Description背景花神是神，一大癖好就是嘲讽大J，举例如下： “哎你傻不傻的！「hqz：大笨J」” “这道题又被J屎过了！！” “J这程序怎么跑这么快！J要逆袭了！” ……描述这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录： 1.“J你在讲什么！” “我在讲XXX！” “哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！” “……” 2. “J你XXX讲...
22015年4月22日6,683可持久化线段树,哈希表
「BZOJ4008」[HNOI2015] 亚瑟王
Description小K不慎被LL邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前OIer，小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连Spaly都敲不对了，因此，希望你能帮帮小K，让他感受一下当欧洲人是怎样的体验。本题中我...
12015年4月22日7,541递推与动规,概率与期望
「BZOJ3996」[TJOI2015] 线性代数
Description给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出DInput第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。Output输出最大的DSampleInput3121310123237SampleOutput2HINT 1<=N<=500题解倒腾下式子发现是...
02015年4月22日6,134最小割