数学 - Page 10 - hzwer.com

「CF493D」Vasya and Chess
Vasyadecidedtolearntoplaychess.Classicchessdoesn'tseeminterestingtohim,soheplayshisownsortofchess.Thequeenisthepiecethatcapturesallsquaresonitsvertical,horizontalanddiagonallines.Ifthecellislocatedonthesamevertical,horizontalordiagonallinewithqueen,andthecellcontainsapieceoftheenemycolor,thequeenisabletomovetothissquare.Afterthattheenemy'spieceisremovedfromtheboard.Thequeencannotmovetoacellc...
02014年12月4日3,741博弈论

「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,897递推与动规,容斥原理
「考后欢乐赛」最小公倍数
题目描述给定两个正整数，求他们的最小公倍数。样例输入2812样例输出84数据范围对于40%数据：1<=a,b<=10^9对于60%的数据：1<=a,b<=10^12对于100%数据：1<=a,b<=10^100 提示：为了略微降低题目难度，增加以下条件：输入数据保证a>=b输入数据保证a、b没有前导0输入数据保证除了在两个正整数a、b之间的空格和行末换行符以外，不存在其他非数字字符最后友情提醒：高精除高精写二分做法风味更佳对...
02014年11月12日4,845高精度,最大公约数与最小公倍数
「NOIP模拟赛」calc
题目说明给三个正整数n，m和p，求(n^1+...n^m)modp。输入格式一行，三个整数n，m和p。输出格式输出答案。样例SampleInput225SampleOutput1数据范围n,p<=10^8m<=10^17相关信息文件名:calc.pas/c/cpp输入文件:calc.in输出文件:calc.out时限:1s空间限制:64MB题解暴力直接快速幂正解应该是矩阵乘法然后我作死试图用数论。。。逆元没学好根据等比数列求和公式得到（省略）/（n-1）modp发现n-1和p可能不互质，然后（省略）/（...
02014年11月6日3,809快速幂,乘法逆元
「NOIP模拟赛」最大公约数
「问题描述」话说CD比较欠扁，他表示在课室的日子没有教主在旁边打他的日子太寂寞了，所以这一晚，他终于来到了电脑室被打。由于CD是大家的宠物，于是大家都来打CD了。电脑室里有n个人，第i个人希望打CDai下。但是太多人打CD，他又会不爽，于是他规定只能有K个人打到他，并且为了公平起见，最终K个人打他的次数都必须是相同的，CD规定这个次数就是这K个人希望打他的次数的最大公约数。为什么是最大公约数呢？因为他...
02014年11月2日3,768调和级数
「NOIP模拟赛」日历游戏
「问题描述」moreD和moreD的宠物CD正在玩一个日历游戏，开始时，他们从1900年1月1日到2012年12月22日（你懂的……）选一个日期开始，依次按照如下规则之一向后跳日期：1.跳到日历上的下一天。2.跳到日历上的下个月的同一天（如果不存在，则不能这么做）。要是谁正好到达2012年12月22日那么他就赢了，如果到达这天之后的日期那他就输了——原因你也懂的。每次都是moreD先走的。现在，给你一个日期，请问moreD一定能赢吗？「输...
02014年11月2日5,100博弈论,记忆化搜索
「BZOJ2440」[中山市选2011] 完全平方数
Description小X自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日，小W想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第K个数送给了小X。小X很开心地收下了。然而现在小W却记不起送给小X的是哪个数了。你能帮他一下吗？Input包...
02014年10月25日6,636莫比乌斯反演
「vijos1889」天真的因数分解
描述小岛:什么叫做因数分解呢?doc:就是将给定的正整数n,分解为若干个素数连乘的形式.小岛:那比如说n=12呢?doc:那么就是12=2X2X3呀.小岛:呜呜,好难,居然素数会重复出现,如果分解后每一个素数都只出现一次,我就会.wish:这样来说,小岛可以正确分解的数字不多呀.doc:是呀是呀.wish:现在问题来了,对于给定的k,第k个小岛无法正确分解的数字是多少?格式输入格式输入只有一行,只有一个整数k.输出格式输出只有一行,只有一个整数,表示小岛无...
02014年10月25日4,753莫比乌斯反演
「NOIP模拟赛」jams倒酒
Jams是一家酒吧的老板，他的酒吧提供2种体积的啤酒，aml和bml，分别使用容积为aml和bml的酒杯来装载。酒吧的生意并不好。Jams发现酒鬼们都很穷，不像他那么土豪。有时，他们会因为负担不起aml或者bml酒的消费，而不得不离去。因此，Jams决定出手第三种体积的啤酒(较小体积的啤酒)。Jams只有两种杯子，容积分别为aml和bml，而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。倒酒步骤为:规定a&...
02014年10月23日3,582扩展欧几里得算法
NOIP2005篝火晚会
描述佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。佳佳可向同学们下达命令，每一个命令的形式如下：(b...
32014年10月21日5,157置换
「BZOJ1119」[POI2009] SLO
Description对于一个1-N的排列(ai)，每次你可以交换两个数ax与ay(x<>y)，代价为W(ax)+W(ay)若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。Input第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。2<=n<=1000000100<=wi<=65001<=ai,bi<=nai各不相等，bi各不相等(ai)<>(bi)样例中依次交换数字(2,5)(3,4)(1,5)Output一个数，最小代价。...
02014年10月12日3,632置换
「BZOJ1770」[Usaco2009 Nov] lights 燈
Description貝希和她的閨密們在她們的牛棚中玩遊戲。但是天不從人願，突然，牛棚的電源跳閘了，所有的燈都被關閉了。貝希是一個很膽小的女生，在伸手不見拇指的無盡的黑暗中，她感到驚恐，痛苦與絕望。她希望您能夠幫幫她，把所有的燈都給重新開起來！她才能繼續快樂地跟她的閨密們繼續玩遊戲！牛棚中一共有N（1<=N<=35）盞燈，編號為1到N。這些燈被置於一個非常複雜的網絡之中。有M（1<=M<=595）條很神奇的無向...
32014年10月1日6,168深度搜索,高斯消元