• 「CF1229X」Codeforces Round #588

    「CF1229X」Codeforces Round #588

    A.MarcinandTrainingCamp若A觉得自己没有B强,B向A连边度数为0的点,是觉得自己比其它人都强的,把它们依此拓扑排序删除[crayon-65f910c10ee7b076357666/]B.KamilandMakingaStream从一个点向上走,区间gcd单调下降,且最多变化log次可以用树上倍增维护区间gcd,枚举每个点往上二分跳,暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd,以及它们贡献答案的次数,这个vector大小是logdfs暴力往儿子转移倍增:...

  • 程序设计实习实验班2017作业(算法 作业19, 20, 21)

    程序设计实习实验班2017作业(算法 作业19, 20, 21)

    一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-65f910c10fe2c764968796/]nnimn阶nim和,在二进制下,每一位求和后对(n+1)取模[crayon-65f910c10fe35115825981/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组,询问的时候直接向上倍增[crayon-65f910c10fe39754618070/]「poj1523」SPF求割点,并且求删去割点后的连通分量个数[cr...

  • 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,516深度搜索,链表,点分治
  • 「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟

    「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟

    「题目背景」微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》「问题描述」小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美,名花异石甚多,小奇在地图上标记了n处景观(标号从1到n),有些景观通过溪流连接,这样的溪流有m段。小奇想知道,有多少种泛舟的路径,经过的景观数大于等于K呢?(小奇不喜欢一次泛舟重复经过一个景观)「输入格式」第一行包括3个整数,n,m,K。接下来m行,每行2个整...

    72016年6月26日6,296点分治,树状数组
  • 树上问题入门

    树上问题入门

    结点、叶结点、分支结点、儿子结点有根树,无根树子孙、祖先、兄弟结点结点的度,结点的层次,树的度,树的深度森林,仙人掌,沙漠树的存储树的遍历结点的父亲,树的深度,树上距离,树的子树大小,树的最大子树,子树的最长链(以子树的根为一个端点,叶为另一个端点),子树最大权,次长链公共祖先,最近公共祖先链的长度树的直径树的重心[crayon-65f910c111887729851813/] ...

    02016年6月14日2,582
  • 二叉搜索树 / set入门

    二叉搜索树 / set入门

    仅列出纲要二叉树— 结点,叶结点,分支结点,结点的度左右孩子— 树的深度,大小二叉树类型—  满二叉树—  完全二叉树—  平衡二叉树二叉搜索树—性质1.前驱后继2.如何查找?—构建1.对已经排序的数快速构建二叉搜索树2.如何顺序插入?效率讨论STL-set顾名思义的操作—什么是Iterator?如何遍历set?用法示例—[crayon-65f910c111b74388241204/] 替罪羊树阅读http://pan.baidu.com/share/link?shareid=318543&a...

    02016年6月12日4,499STL,
  • 「小奇模拟赛2」[BZOJ3784] 小奇的树

    「小奇模拟赛2」[BZOJ3784] 小奇的树

    「题目背景」小奇在研究树时,遇到了一个难题。「问题描述」给定一棵n个节点的树,求前m条最长路径的长度。「输入格式」第1行2个整数n,m。接下来n-1行,每行3个整数u,v,l,表示u,v之间有一条长度为l的边。「输出格式」m行如题,从大到小输出。「样例输入」42121132143「样例输出」54「数据范围」序号nm数据类型1103暴力223323333暴力32000300000暴力42000300000暴力5500001随机生成6779817798随机生成7779827798随机生成877983...

    22016年5月22日7,502STL,ST表,点分治
  • 「省选模拟赛」小奇的花园

    「省选模拟赛」小奇的花园

    原题:「泉七培训-刘定峰」花园「题目背景」小奇在家中的花园漫步时,总是会思考一些奇怪的问题。「问题描述」小奇的花园有n个温室,标号为1到n,温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花,随着季节的变换,温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。「输入格式」第一行为两个整数n,q,表示温室的数目和操作的数目。第二行有n个整数T1...

    62015年12月19日9,312STL,树套树,treap,线段树,树链剖分
  • 「BZOJ1180」[CROATIAN2009] OTOCI

    「BZOJ1180」[CROATIAN2009] OTOCI

    Description给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作:1、bridgeAB:询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”,并且在结点A和结点B之间连一条无向边。2、penguinsAX:将结点A对应的权值wA修改为X。3、excursionAB:如果结点A和结点B不连通,则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作,要求在线处理所有...

    62015年7月1日5,793link cut tree
  • 「CF293X」Croc Champ 2013 – Round 2

    「CF293X」Croc Champ 2013 - Round 2

    A.WeirdGame两个人都应该采取贪心策略根据规则,先取0而对方不取0则败,所以有1则取1,当然尽量取对方也是1的那些取0的时候同理,尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-65f910c126e53469001718/]B.DistinctPaths容易发现,n+m-1>K时是无解的,那么有解的棋盘就很小了,状压使用的颜色+dfs然而这样的状态还是太多,我们发现dfs到一个格子的时候,所有未在棋盘上出现的颜色并无差别,所...

  • POJ训练记录2

    POJ训练记录2

    3613.CowRelays求经过n条边的最短路,floyd+倍增QAQ[crayon-65f910c1276de950946982/]2728.DesertKing最优比率生成树分数规划[crayon-65f910c1276e8574201980/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-65f910c1276...

1 / 9 1 2 3 ...9 下一页 »