• 【codeforces】数据结构杂题

    【codeforces】数据结构杂题

    一些数据结构简单题:570C.Replacement427B.PrisonTransfer519B.AandBandCompilationErrors650A.Watchmen466C.NumberofWaysCHSEQ22.ChefandFavouriteSequence460C.Present459D.PashmakandParmida’sproblem528A.GlassCarving704A.Thor339D.XeniaandBitOperations527527D.CliqueProblem718D.AndrewandChemistry570C.Replacement给定一个长为n的字符串(包含小写字母和'.'),有m次操作...

    02016年10月23日1,372数据结构
  • 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把一个文本...

  • 《数据结构与算法》作业 —— KMP

    《数据结构与算法》作业 —— KMP

    英文好难,我好菜QAQ你们这里洋文好的人多得很哪求神犇指点

    12016年10月8日1,396KMP
  • 【cf715X】Codeforces Round #372 (Div. 1)

    【cf715X】Codeforces Round #372 (Div. 1)

    A.PlusandSquareRoot推公式可得,可构造每次按完的数为i*(i+1)[crayon-58d3669470bc1904828387/]B.CompleteTheGraph给一张无向图,要求赋值一些边的边权,使得最终S到T的最短路为L用f(i,j)表示从S到点i,经过j条无边权的边的最短路选择一个最小的j,使得f(T,j)+j<=L更改这条路径上的边权,使得最短路为L,将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法,写起来会短一些...

    02016年9月19日969dijkstra,构造
  • 2016 ACM/ICPC Asia Regional Dalian Online

    2016 ACM/ICPC Asia Regional Dalian Online

    1002DifferentGCDSubarrayQuery问长为n的序列,m个询问,问区间[L,R]所有子段的不同gcd值个数考虑固定左端点,随着右端点的移动,gcd至多衰减log次(每次至少折半)从n开始添加询问的左端点,用树状数组维护每个gcd右端点的最小值[crayon-58d3669471361121499601/]1007FriendsandEnemiesn个人,每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...

  • 【TYVJ】P1001-1099题解(44/99)by hzwer

    【TYVJ】P1001-1099题解(44/99)by hzwer

    只写简要题解,详见tyvj官方题解我会尽量给出简单直白的代码【tyvj1001】第K极值排序,计算出m并判断其是不是质数只需要循环到√m即可[crayon-58d3669472383044274194/]【tyvj1002】NOIP2005谁拿了最多奖学金模拟[crayon-58d3669472393743146512/]【tyvj1003】越野跑如果是平地,来回要花2F时间,否则花U+D的时间[crayon-58d366947239c104575826/]【tyvj1004】滑雪记忆化搜索,从每个点向更低点记忆化深搜[crayon-58d36694...

    62016年8月25日8,409入门
  • 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次发...

  • 再见,OI

    再见,OI

    信息学全国赛(NOI2015),疏散日,杭州学军中学,暴雨。我校买的下午的车票,省队几个一起通宵麻将的同学天没亮就坐车去了,只留我在空荡荡的宿舍楼里,开始码退役纪念帖。然而灵感娇生惯养,回忆也时断时续,这坑一直留到现在。怎么写都像记流水账,也无奈,我笔都不会握了还想写文呢,纯粹自己感动自己。想象中的回忆录大抵是这样,有点文艺范。能自豪地拿给人看,给没竞赛的朋友看,也留给未来的自己。别人看完说:真他妈热...

    1232016年7月26日18,061竞赛历程
  • BestCoder Round #84

    BestCoder Round #84

    1001Aaronson对n做二进制拆分,注意m对30取min[crayon-58d3669495bdc642432122/]1002Bellovin直接输出F,显然是字典序最小的方案[crayon-58d3669495bee205202237/]1003Colmerauer用单调栈预处理下每个点向左/右第一个小等于它的元素,向上/下第一个大等于它的元素(一开始我用set预处理结果TLE)。然后计算每个元素对答案的贡献,若设四个方向第一个使得其不能成为鞍点的数与其的距离分别为L,R,U,D则其对答案的贡献为L...

    22016年7月24日950算法
  • 【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-58d3669497111041735807/]B.FixaTree给出n个结点的父亲,问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树,剩下的每个环要选出一个当根,然后再把所有的环连成树答案是环数-(是否存在自环)[crayon-58d3...

  • AHSOFNU NOIP模拟赛整理(update)by hzwer

    AHSOFNU NOIP模拟赛整理(update)by hzwer

    把几个包整合了一下,并做了一些修改------------------------以下是原文-------------------------------既然我退役了就发点福利给大家2014-2015年我校各类模拟赛。。。包括我和lwh学长从各处搬运的。。。以及部分原创题。。。大部分为noip难度希望能对大家起到一点帮助0.0打包下载地址:http://pan.baidu.com/s/1eSpxMpG提取密码:vtdr文件夹里没有题解的话。。。我的博客里也许有。。。还有在vjudge上组的题http://acm.hust....

    372016年7月16日3,717算法
  • 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日1,466深度搜索,链表,点分治
  • FJ2016集训 day5

    FJ2016集训 day5

    打了个酱油,身败名裂0。01冷战1.1题目大意给定一副N个点的图。动态的往图中加边,并且询问某两个点最早什么时候联通。1.2题解考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并,这棵树的深度是O(logn)的。我们将一个点连向其父亲的边权设为这条边加入的时间,那么每次询问时,暴力查询树上从u到v所经过边权的最大值即可。时间复杂度为O(nlogn),常数较小。假如写了常数较大的可以得到80分。[crayon-58d36694987ac8...

    42016年7月7日1,278并查集