算法 - Page 111 - hzwer.com

「BZOJ1221」[HNOI2001] 软件开发
Description某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA,B种消毒方式的费用为每块毛巾fB，而买...
02014年3月16日4,218费用流

「BZOJ1263」[SCOI2006] 整数划分
Description从文件中读入一个正整数n（10≤n≤31000）。要求将n写成若干个正整数之和，并且使这些正整数的乘积最大。例如，n=13，则当n表示为4+3+3+3（或2+2+3+3+3）时，乘积=108为最大。Input只有一个正整数：n（10≤n≤31000）Output第1行输出一个整数，为最大乘积的位数。第2行输出最大乘积的前100位，如果不足100位，则按实际位数输出最大乘积。（提示：在给定的范围内，最大乘积的位数不超过5000位）。SampleInput13Sam...
32014年3月16日4,746高精度
「NOIP模拟赛」小奇挖矿
原题目名：经营与开发2015.9.13日hzwer重制了题面「题目背景」小奇要开采一些矿物，它驾驶着一台带有钻头（初始能力值w）的飞船，按既定路线依次飞过喵星系的n个星球。「问题描述」星球分为2类：资源型和维修型。 1.资源型：含矿物质量a[i]，若选择开采，则得到a[i]*p的金钱，之后钻头损耗k%，即p=p*(1-0.01k)2.维修型：维护费用b[i]，若选择维修，则支付b[i]*p的金钱，之后钻头修复c%，即p=p*(1+0.01c) （p为钻头...
02014年3月15日3,534递推与动规
「NOIP模拟赛」不等数列
不等数列(num.cpp/c/pas)「题目描述」将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。「输入格式」第一行2个整数n,k。「输出格式」一个整数表示答案。「样例输入」52「样例输出」66「数据范围」对于30%的数据：n<=10对于100%的数据：k<n<=1000题解f[i][j]表示前i个j个小于号的方案[crayon-6847b...
02014年3月15日3,426递推与动规
「NOIP模拟赛」高级打字机
高级打字机(type.cpp/c/pas)「题目描述」早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。请为这种高级打字机设计一个程序，支持如下3种操作：1.Tx：在文章末尾打下一个小写字母x。(type操作)2.Ux：撤销最后的x次修改操作。（Undo操作）（注意Query操作并不算修改操作）3.Qx：询问当前文章中第x个字母并输出。（Query操作）文章一开始可以视为空串。「输入格式」第1行：一...
92014年3月15日4,611模拟
「POJ1678」I Love this Game！
DescriptionAtraditionalgameisplayedbetweentwoplayersonapoolofnnumbers(notnecessarilydistinguishingones).Thefirstplayerwillchoosefromthepoolanumberx1lyingin[a,b](0<a<b),whichmeansa<=x1<=b.Nextthesecondplayershouldchooseanumbery1suchthaty1-x1liesin[a,b](Attention!Thisimpliesy1>x1sincea>0).Thenthefirstplayershouldchooseanumberx2suchthatx2-y1liesin[a,b]...Thegameendswhenoneof...
02014年3月15日3,025记忆化搜索
「BZOJ2064」分裂
Description背景：和久必分，分久必和。。。题目描述：中国历史上上分分和和次数非常多。。通读中国历史的WJMZBMR表示毫无压力。同时经常搞OI的他把这个变成了一个数学模型。假设中国的国土总和是不变的。每个国家都可以用他的国土面积代替，又两种可能，一种是两个国家合并为1个，那么新国家的面积为两者之和。一种是一个国家分裂为2个，那么2个新国家的面积之和为原国家的面积。WJMZBMR现在知道了很遥远的过去中...
12014年3月15日6,203状压动规
「cojs1487」麻球繁衍
「题目描述」万有引力定律：“使物体相互靠近的力的大小与物体的质量成正比——而物体的质量又由同一种力决定。这是一个有趣并且有益的例子，说明了科学是如何用A证明B，再用B证明A的。”——安布罗斯·比尔斯（美国讽刺作家——译者注）。你有一坨K个毛球（<星际迷航>中的种族——译者注）。这种毛球只会存活一天。在死亡之前，一个毛球有P_i的概率生出i个毛球(i=0,1,...,n-1)。m天后所有毛球都死亡的概率是多少？（包...
02014年3月14日14,649概率与期望
「BZOJ1305」[CQOI2009] dance跳舞
Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？Input第一行包含两个整数n和k。以下n行每行包含n个字符，其...
02014年3月13日7,566二分法,最大流
「BZOJ1013」[JSOI2008] 球形空间产生器sphere
Description有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。Input第一行是一个整数，n。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。Output有且只有一行，依次给出球心的n维坐标（n个实数），两个实数...
72014年3月13日8,316高斯消元
「BZOJ1088」[SCOI2005] 扫雷Mine
Description相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少...
02014年3月13日5,024模拟
「BZOJ1299」[LLH邀请赛] 巧克力棒
DescriptionTBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？Input输入数据共20行。第2i-1行一个正整数Ni，表示第i轮巧克力棒的数目。第2i行Ni个正整数Li,j，表示第i轮巧克力棒的长度。Output输出数据共10行。每行输出“YES”或“NO”，表示TBL是否...
02014年3月13日5,898博弈论