递推与动规 - Page 2

2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-6904d7da8b8c2693820411/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-6904d7da8b8cf449808035/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
02016年11月6日6,340递推与动规,模拟,KMP,贪心,构造,主席树,深度搜索,二分法

2016 Multi – University Training Contest 5
本场抱住卓神大腿最后过了7题。。。感觉把PKU的牌子砸了。。。我做了100110051011随便口胡几句。。。1010看起来像后缀数组。。。但是交wa了几发不知道什么情况1001ATMMechine这题似乎0元钱也要取1次1元的来确认一下，不然没法解释样例\(f(i,j)\)表示有i元以内的钱，j次warning的机会然后枚举询问点k，有t种可能warning，那么转移给\(f(t-1,j-1)\)有i-k+1种可能取钱，转移给\(f(i-t,t)\)边界j为1的情况，有k元钱需要询问k+1次...
12016年8月3日5,739递推与动规,回文自动机,概率与期望
「CF698X」Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-6904d7da8cd78449531725/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-6904...
02016年7月20日5,139递推与动规,状压动规,拓扑排序,概率与期望
2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-6904d7da8d47a686369610/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-6904d7da8d489775467113/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-6904d7da8d492703553175/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-6...
42016年6月30日5,464递推与动规,KMP,最大流,后缀数组
「NOI联考by ysy」庆典
「题目描述」战狂在昌和帝国的首都法法城召开了庆典，向一万名最杰出的士兵分发了用魔法猪做的猪肉饺子，士兵们吃了猪肉饺子后，战斗力大幅提高。为了保护战狂的安全以及维护现场秩序，大预言家抽调了n名普通士兵组成了m个小队完成一些不同的任务。由于一些特殊的原因，所有小队的人数都互不相同。你需要求出有多少种可能的组队方案。注意士兵是相同的，而小队是不同的。「输入数据」第一行两个个整数n，m。「输出数据」一行一个数...
02016年6月17日3,750递推与动规
「CF611X」Good Bye 2015
智商基本已经放弃我了，身败名裂后的题解。因为太弱加上是个高三狗，所以就只有ABCD了QAQA.NewYearandDays求2016年有多少个星期n求2016年有多少个月有n号可以算好答案输出[crayon-6904d7da8e821306567810/]B.NewYearandOldProperty求L-R中有多少十进制数转为二进制只有1个0枚举0在哪一位，然后再枚举1的个数[crayon-6904d7da8e82d704674980/]C.NewYearandDomino求一个子矩形有多少种放置1*2的方式二维前缀和...
102016年1月2日4,310递推与动规,模拟,二分法,哈希表
「省选模拟赛」小奇挖矿 3
原题：「泉七培训-刘定峰」物流「题目背景」小奇在喵星系使用了无限非概率驱动的采矿机，以至于在所有星球上都采出了一些矿石，现在它准备建一些矿石仓库并把矿石运到各个仓库里。「问题描述」喵星系有n个星球，标号为1到n，星球以及星球间的航线形成一棵树。所有星球间的双向航线的长度都为1。小奇要在若干个星球建矿石仓库，设立每个仓库的费用为K。对于未设立矿石仓库的星球，设其到一个仓库的距离为i，则将矿石运回的费用为D...
02015年12月17日6,395递推与动规,深度搜索,广度搜索
「省选模拟赛」[hdu5171] 小奇的集合
注：原题没有考虑最大值为负数的情况「题目背景」小奇总是在数学课上思考奇怪的问题。「问题描述」有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大值。（数据保证这个值为非负数）「输入格式」第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。「输出格式」输出一个整数，表示和的最大值。答案对10000007取模。「样例输入」2236...
02015年11月22日4,533递推与动规,矩阵乘法
「NOIP模拟赛」[hdu5492] 小奇的矩阵
「题目背景」小奇总是在数学课上思考奇怪的问题。「问题描述」给定一个n*m的矩阵，矩阵中的每个元素aij为正整数。接下来规定1.合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1)，Aavg为Ai的平均数，路径的V值为(n+m-1)*∑(Ai-Aavg)^2(1<=i<=n+m-1)求V值最小的合法路径，输出V值即可，有多组测试数据。「输入格式」第一行包含一个正整数T，...
62015年10月5日5,717递推与动规,深度搜索
「NOIP模拟赛」小奇挖矿 2
原题：streaming_3noip模拟赛4和7「题目背景」小奇飞船的钻头开启了无限耐久+精准采集模式！这次它要将原矿运到泛光之源的矿石交易市场，以便为飞船升级无限非概率引擎。「问题描述」现在有m+1个星球，从左到右标号为0到m，小奇最初在0号星球。有n处矿体，第i处矿体有ai单位原矿，在第bi个星球上。由于飞船使用的是老式的跳跃引擎，每次它只能从第x号星球移动到第x+4号星球或x+7号星球。每到一个星球，小奇会采走该星球上所有的原矿...
22015年10月5日5,221递推与动规
「CF268D」Wall Bars
Manaoisworkingforaconstructioncompany.Recently,anordercametobuildwallbarsinachildren'spark.Manaowascommissionedtodevelopaplanofconstruction,whichwillenablethecompanytosavethemostmoney.Afterreviewingtheformalspecificationsforthewallbars,Manaodiscoveredanumberofcontroversialrequirementsanddecidedtotreatthemtothecompany'sadvantage.Hisresultingdesigncanbedescribedasfollows:Let'sintroducesomeuni...
22015年7月6日4,745递推与动规
「CF316D3」PE Lesson
SmartBeaverdecidedtobenotonlysmart,butalsoahealthybeaver!AndsohebegantoattendphysicaleducationclassesatschoolX.Inthisschool,physicaleducationhasaverycreativeteacher.Oneofhisfavoritewarm-upexercisesisthrowingballs.Studentslineup.Eachonegetsasingleballinthebeginning.Theballsarenumberedfrom1ton(bythedemandoftheinventorycommission).Figure1.Theinitialpositionforn = 5.Afterreceivingtheball...
02015年7月5日3,491递推与动规