• 「CF1242X」Codeforces Round #599 (Div. 1)

    「CF1242X」Codeforces Round #599 (Div. 1)

    A.TilePainting对n做因式分解,如果n有超过一个质因数t,则答案是1,否则答案是t。因为两个质因数求gcd以后是1,则ax+by可以把所有格子染上。[crayon-6754da6956942512714844/]B.0-1MST求补图的联通块个数,BZOJ1098原题。维护一个1-n的链表,表示有哪些点还没确定所在连通块。从1-n枚举点x,用bfs把与x同一连通块的点找出来,每次bfs只需要考虑还在链表里的点,这样每一条边要不然在原图中,要不然不在原图中使得某个点...

  • 2018-2019 NOIP课件 by hzwer

    2018-2019 NOIP课件 by hzwer

    分享一下这两年做的课件链接:https://pan.baidu.com/s/1DUUkwBrAE5tH1lFvNSkocQ提取码:2vfp

  • 【LOJ】小奇 NOIP 练习题

    【LOJ】小奇 NOIP 练习题

    可以在https://loj.ac/problems/tag/207AC这些题目小奇采药小奇取石子小奇的旅行计划小奇探险小奇采药对于30%的数据,\(O(2^n)\)枚举取or不取对于60%的数据,\(O(nm)\)做01背包,即\(f(i,j)\)表示前i株草药,耗费j的时间能达到的最大代价。对于100%的数据,注意到m,t,v纯随机那么不会选太多的草药,而耗时较少的草药有很大概率存在于最优解中针对这些性质优化搜索当然也可以合理使用随机化和卡时,复杂度O(玄学)小奇取石子在n...

  • 「百度之星2017」程序设计大赛 初赛(B)

    「百度之星2017」程序设计大赛 初赛(B)

    好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-6754da69579cd657844865/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\),和小等于m的对于元素个数很多的集合,每个集合bfs一次,预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少,建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力,结果还过了[crayon-6754da69579d7577916031/]1005.度度熊的交易计划预...

  • 2017ACM萧山训练第3场(World Final 2013)

    2017ACM萧山训练第3场(World Final 2013)

    A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a),判图中是否有环,有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-6754da69583d7789174454/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-6754da69583e2403929630/]D.Factors爆搜前16个素数[crayon-6754da69583ee582352638/]F.LowPower二分答案贪心检验[crayon-6754da69583f5459719728/]H:М...

  • 程序设计实习实验班2017作业(算法 作业1, 5)

    程序设计实习实验班2017作业(算法 作业1, 5)

    「Bailian4115」鸣人和佐助bfs的时候多一维记录查克拉[crayon-6754da6958fee132553776/]「poj1190」生日蛋糕/泰国佛塔从下往上一层一层搜索,每一层枚举半径和高度(注意范围)根据每一层半径和高度严格递减,进行一些剪枝:1、剩下的若干层都放最小的圆柱,体积也不够2、剩下的若干层都放最小的圆柱,得出的表面积比当前最优解劣3、剩下的体积所需的最小表面积加上当前表面积比当前最优解劣[crayon-6754da6958ff9176622926/]「B...

  • 2015程序设计实习实验班免修考试(校内)

    2015程序设计实习实验班免修考试(校内)

    「poj1037」decorativefence用f(i,j)表示长度为i,开头为j,开头为上升的序列用g(i,j)表示长度为i,开头为j,开头为下降的序列考虑在序列的第二位放一个数字,改变上升/下降预处理完之后,一位位枚举贪心[crayon-6754da6959dd9697400633/]「poj1011」Sticks经典的搜索剪枝1.长度取值范围是木棍的最长长度到长度总和之间。2.长度总和一定可以整除原来的长度。3.从大到小排序搜索。4.某次组合时,如果不能加入某根木棍,同种长度的木...

  • 2016 ACM – ICPC Shenyang Onsite

    2016 ACM - ICPC Shenyang Onsite

    一些队友写的还没太搞清楚,就先贴几题hdu5948.ThickestBurger模拟[crayon-6754da695a6d6389577205/]hdu5949.Relativeatomicmass模拟[crayon-6754da695a6de021911328/]hdu5950.Recursivesequence\(f_1=a,f_2=b,f_i=f_{i-2}*2+f_{i-1}+i^4\),求\(f_n\)推出式子后矩阵乘法[crayon-6754da695a6e2736758506/]hdu5952.CountingCliques求一个无向图大小为S的团的数量由于图的度数很小,选一个点,在其所有相邻点中取S-1个复杂度...

  • 「CF718X」Codeforces Round #373 (Div. 1)

    「CF718X」Codeforces Round #373 (Div. 1)

    A.EfimandStrangeGrade给一个长为n的小数,有t次操作,每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字,从其开始考虑四舍五入如果四舍五入到小数点,将小数点去掉最后再处理一下整数位的进位问题[crayon-6754da695ac5d985375106/]C.SashaandArray给定一个长度为n的数列an,有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...

  • 2016 CCPC Changchun Onsite

    2016 CCPC Changchun Onsite

    hdu5912.Fraction计算连分数的答案,直接模拟即可[crayon-6754da695b24d668129098/]hdu5914.Triangle问长度1到n的线段,至少要去掉多少,使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列,手算完打表[crayon-6754da695b257028345193/]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把一个文本...

  • FJ2016集训 day7

    FJ2016集训 day7

    题目来自coolinging(orz)Problem1挑选子序列(sequence.cpp/c/pas)题目来源:原创考察要点:搜索与剪枝、dancinglinks、二分、排序涉及要点:动态规划、随机化算法、贪心解题报告:题目可以理解为在串t中选取m个字母,每个字母覆盖串s1和串s2的部分位置,使串s1和串s2被完全覆盖,求满足如上条件时距离的最小值。对于数据点1,n<=10,T<=10,可以直接枚举选取哪m个字母,简单计算即可。由此可知,对于本题来说,判定比求解...

    42016年7月9日5,873深度搜索,链表,点分治
1 / 17 1 2 3 ...17 下一页 »