• 2016 CCPC Changchun Onsite

    2016 CCPC Changchun Onsite

    hdu5912.Fraction计算连分数的答案,直接模拟即可[crayon-59951178c143b418454968/]hdu5914.Triangle问长度1到n的线段,至少要去掉多少,使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列,手算完打表[crayon-59951178c144c840634847/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd,求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现,第k大的全排列的权值为n-2+k构造方式...

  • 2016 ACM/ICPC Asia Regional Qingdao Online

    2016 ACM/ICPC Asia Regional Qingdao Online

    大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的,其质因数个数不会超过30个dfs出所有数字,二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...

  • 2016 Multi-University Training Contest 5

    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次发...

  • 【cf698X】Codeforces Round #363 (Div. 1)

    【cf698X】Codeforces Round #363 (Div. 1)

    A.Vacations题意:给出每天contest和gym的开关状态,不能连续俩天参加相同活动,问n天最少休息多少天用F(i,0-2)表示前i天,第i天的状态为(rest,contest,sport),最多能有多少天不休息简单dp一下[crayon-59951178c3939100985122/]B.FixaTree给出n个结点的父亲,问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树,剩下的每个环要选出一个当根,然后再把所有的环连成树答案是环数-(是否存在自环)[crayon-5995...

  • Codeforces Round #360 (Div. 1)

    Codeforces Round #360 (Div. 1)

    A.NP-HardProblem二分图染色[crayon-59951178c49dc064641543/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-59951178c49e8030590115/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-59951178c49ed360662856/] ...

  • 2014pku计算概论入学测试

    2014pku计算概论入学测试

    poj1961Periodkmp求出fail数组后,前i个的重复子串就是i-fail(i)[crayon-59951178c4fd1355105834/]poj1276 CashMachine用f(i,j)表示前i种面值,达到j的面值和,所需要的第i种钞票的最少数量[crayon-59951178c4fdb918726945/]poj1702 Eva'sBalance先把n转为3进制,若p位为2,就在左盘放3^p,进位若p位为1,就在右盘放3^p[crayon-59951178c4fe3096041541/]poj1273 DrainageDitches大名鼎鼎的草地排水,网络流模板[crayon-5...

  • 2013pku计算概论入学测试

    2013pku计算概论入学测试

    OpenJ_Bailian3254.约瑟夫问题2模拟,用vector比较方便[crayon-59951178c652c127411741/]poj2393.Yogurtfactory求出将酸奶保存到某一天的最小代价贪心[crayon-59951178c6538157880596/]poj1321.棋盘问题回溯裸题[crayon-59951178c653c625346148/]poj2576.TugofWarf(i,j,k)表示前i个选j个能不能凑成k,第一维滚动[crayon-59951178c6541155182920/]poj1974.RebuildingRoads用f(i,j)表示子树i,剩j个结点需要至少删多少条边[c...

    22016年6月28日1,582模拟,贪心,深度搜索,树形动规
  • Codeforces Round #359 (Div. 1)

    Codeforces Round #359 (Div. 1)

    A.Robbers'watch可以先算出n-1,m-1所需的位数如果位数和超过7,根据抽屉原理,则一定会存在相同的数字特判一下输出0后,位数小等于7的情况暴力即可枚举i<n,j<m,七进制拆分一下看有没有相同数字[crayon-599511790096c715021938/]B.KayandSnowflake题意是询问一棵树某些子树的重心树的重心定义为,删去这个结点后,剩下的连通块大小不超过1/2*(总结点数)用yi表示x结点的儿子预处理size[x]和mx[x]表示树的大小,yi树的最...

    32016年6月24日1,246树形动规
  • 【NOI联考by ysy】庆典

    【NOI联考by ysy】庆典

    【题目描述】战狂在昌和帝国的首都法法城召开了庆典,向一万名最杰出的士兵分发了用魔法猪做的猪肉饺子,士兵们吃了猪肉饺子后,战斗力大幅提高。为了保护战狂的安全以及维护现场秩序,大预言家抽调了n名普通士兵组成了m个小队完成一些不同的任务。由于一些特殊的原因,所有小队的人数都互不相同。你需要求出有多少种可能的组队方案。注意士兵是相同的,而小队是不同的。【输入数据】第一行两个个整数n,m。【输出数据】一行一个数...

    02016年6月17日975递推与动规
  • 【tyvj1520】树的直径

    【tyvj1520】树的直径

    描述Description树的直径,即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1,即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是,从树的任意一个结点a出发,走到距离最远的结点b,再从结点b出发,能够走的最远距离,就是树的直径。树中相邻两个结点的距离为1。你的任务是:给定一棵树,求这棵树中距离最远的两个结点的距离。输入格式InputFormat输入共n行第一行是一个正整数n,表示这棵树的结点...

    22016年6月15日2,170树形动规,广度搜索
  • 【小奇模拟赛】[bzoj3576]小奇的博弈2

    【小奇模拟赛】[bzoj3576]小奇的博弈2

    【题目背景】小奇和提比开脑洞又发明了新的游戏。【问题描述】给定一个数字F,游戏系统产生T组游戏。每组游戏包括n堆糖果,小奇和提比轮流操作。每次操作时,一方将某一堆数量不小于F的糖果分成M堆(M>=2且每次可以不同),要满足M堆中任意两堆糖果的差值不超过1,且不存在空堆。若一方不能操作,它就输了。假设提比和小奇都非常机智,小奇先手,请你预测一下游戏的结果。【输入格式】第一行有2个整数T,F接下来T行,每...

    02016年5月21日1,369博弈论,记忆化搜索
  • 【cf666X】 Codeforces Round #349 (Div. 1)

    【cf666X】 Codeforces Round #349 (Div. 1)

    A.ReberlandLinguistics此题最重要的是理解题意!!!英语渣伤不起给定一个字符串,先去掉一个长度至少为5的前缀,要求把剩下的字符串划分成长度为2或3的串,这些串相邻之间不能完全相同,问可能有哪些长度为2或3的串看错题意就写了个哈希+搜索一直wa,后来领悟了就没另起炉灶,改成了牵强的记搜大概和dp差不多意思,f[i][0/1]表示前i个字符,最后一个串长度为2/3是否可行,转移显然。。。[crayon-599511790237d200185769/]B.W...

    02016年5月1日1,274广度搜索,记忆化搜索
  • Manthan, Codefest 16

    Manthan, Codefest 16

    A.EbonyandIvory给定a,b,c求一组整数解x,y使得x*a+y*b=c题解数据范围很小暴力枚举x[crayon-59951179027e1045702419/]B.ATrivialProblem求n!有多少个0题解暴力求n!被多少个2和5整除[crayon-59951179027e9541857159/]C.SpySyndrome2给定长为(n<=10000)的主串,给(m<=100000)个长不超过1000的子串,总长不超过1000000求一个主串由子串的反串拼出的解法题解求每个子串的哈希值,主串每位枚举串长<=1000,求...

    132016年3月6日1,132STL,树形动规