• 等级
  • 14956 访问
  • 58 原创
  • 0 转发
  • 76596 排名
  • 33 评论
  • 200 获赞

(wqs二分)CF739E Gosha is hunting

传送门这篇林克卡特树+简单的wqs二分/凸优化是来骗访问量的Solution这其实是个wqswqswqs二分套wqswqswqs二分O(nab)\mathcal{O(nab)}O(nab)的dpdpdp很好写我们要做的是用凸优化,把时间复杂度降到O(nlog⁡alog⁡b)\mathcal{O(n\loga\logb)}O(nlogalogb)显然这是一个凸函数,为什么呢?因为你...

2019-05-15 19:19:21

[学习笔记]dp凸优化/wqs二分&[八省联考2018]林克卡特树lct

废话很早就想学wqs二分,结果拖了好久。因为以前是看了几遍都没有懂。。(太菜了后来因为计划里凸优化的题(比如CF321ECielandGondolas,CF739EGoshaishunting…)太多了。。又不会高深的数据结构,所以只能硬着头皮学网上blog这么多,还是wqs神仙本人的论文最好懂。。网上应该会有,这边就不放资源了然后灵光一现就突然懂了先上题这道算是经典题了叭...

2019-05-14 19:10:24

上海华师大"游族杯"acm现场赛一日游

这篇算是[余姚之魂——雀魂的后续]叭(https://blog.csdn.net/jokingcoder/article/details/89502201)day3于是我们就坐大巴去了上海(一路颠簸)不知道为什么雀魂这么耗电。。所以后半程就开始看杂志。。他们居然还能玩起狼人杀。。到了华师大第一眼居然看不出这是在大学里面(我果然是孤陋寡闻后来是xjd学长和另外一个不知道叫什么的小哥哥...

2019-04-27 21:40:52

余姚之魂——雀魂(ZJOI2019Day2游记)

(这是个什么沙雕标题)day1为什么只有我的游记是从day1开始的。。。因为窝前一天还在补文化课。。。寝室铃响,6:08起床去食堂吃早饭,6:39上车,7:42准时到达余姚中学报告厅的空调吹得蒟蒻瑟瑟发抖上午的神仙zyz讲课(雾树上分治+杂题选讲难度比提高略微高一点点???虽然没有完全掉线,恐怕也是半离线了没错后来就去打雀魂了...

2019-04-25 14:45:22

[HNOI2016]树-缩点+倍增lca+主席树(码农)

传送门博主心态以崩,打到一半再打啥都不知道所以先挖坑,等心态恢复好了继续打专业挖坑不填100年#include<cstdio>usingnamespacestd;structTemplateTree{ inttot=0,lst[N],size[N],dfn[N],dep[N]; structEdge{ intto,nxt; }e[...

2019-04-22 20:55:27

CF731D.80-th Level Archeology(暴力)

为什么这么水一道题没人写呢qwq传承cy的水博客精神(雾传送门RuA!题意给你一堆字符串(其实是数组?)对每个字符(数)+x+x+x(超过ccc就从头开始)Solution要满足整体字典序非递减,那不就是前一个的字典序一定要小于等于当前的字典序咩?发现两个字符串的相对顺序不会变所以只要找到相邻两个第一个不同的位置(或者说某一个先没有了)这样我们就可以使前一个字母小于后一个字母所需要...

2019-04-21 19:38:05

c++模拟质点在万有引力下的运动轨迹

2019-04-19 16:21:46

JZOJ5813Count-质因数分解+dp

#include<cstdio>#include<algorithm>#include<cstring>#defineMOD998244353usingnamespacestd;typedeflonglongLL;LLdp[10000][220],all;intcc[110];inlineLLqui_pow(...

2019-04-18 21:22:34

ZJOI2014力-FFT快速傅里叶变换

Luogu-ZJOI2014力说在前面鸣谢hsy\mathcal{h{\color{red}sy}}hsy

2019-04-17 21:13:09

[ZJOI2012]波浪——dp+__float128卡精度

ZJOI2012波浪题意在1→N1\toN1→N的全排列PPP中L=∣P1–P2∣+∣P2–P3∣+…+∣PN−1–PN∣L=|P_1–P_2|+|P_2–P_3|+…+|P_{N-1}–P_N|L=∣P1​–P2​∣+∣P2​–P3​∣+…+∣PN−1​–PN​∣问L≥ML\geqML≥M的概率有多大,保留k位小数,k≤30k\leq30k≤30Solution(这个solut...

2019-04-12 19:19:52

[学习笔记]dsu on tree

dsuontreeBBdsuontree树上并查集?其实这东西跟并查集一点关系都没有吧(可能是我太年轻树上启发式合并和莫队一样有着看上去貌似特别高深的名字,其实就是XJB暴力正题实质上dsuontree运用了一个轻重链剖分的思想。适用于不带修改的树上询问操作离线操作比莫队优越有些树上题目我们每次暴力时间复杂度是O(n2)\mathcal{O(n^2...

2019-04-08 16:08:43

CF260E Dividing Kingdom(暴力+线段树)

原题E.DividingKingdomAcountrycalledFlatlandisaninfinitetwo-dimensionalplane.Flatlandhasnnncities,eachofthemisapointontheplane.FlatlandisruledbykingCircleIV.CircleIVhas...

2019-04-03 21:02:04

镇海三日游——ZJOI2019游记

写在前面突然想起来是时候(乱)写一篇游记了我只是一只辣么弱的蒟蒻,jls你居然还忍心骗我说不是你出题。。。Day0在学校听完一个讲座后直接去了镇海,没去镇中。。。因为蒟蒻太菜了tg都打不到515然后就去宾馆嗨皮了♂宾馆就在镇中走出100m左右,炒鸡近然后。。也没有到多晚,颓了会儿BigBangTheoryDay1~3(自闭了)大早上的,lyxlyxlyx神仙讲了《具体数学》...

2019-03-29 18:28:43

[学习笔记]拉格朗日插值法

pre很早以前就知道这玩意儿,但是一直没有学。。。然后突然看到了这东西,就顺便学了一下然后发现十分简单用途(众所周知,n阶多项式能用n+1对不同的(x,y)来表示)能将n阶多项式的点值表达式转换成系数表达式,主要就是用了构造法实现这个叫Joseph-LouisLagrange的神仙把这个多项式分成了n个部分的和使第iii个部分fi(xi)=yi,fi(xj)=0(j≠i)f_i...

2019-03-28 18:40:52

POJ1764.Dice Contest(矩阵快速幂)

原题地址蛮好的一道题目,但是一开始根本想不到这是矩阵快速幂一开始最简单的想法就是dp,因为如果两个相差比较远的块中间是不可能走回头路的,只有可能是上下移动,所以就能使用dp来维护相邻两列之间的转移我们用f[i][j][k]f[i][j][k]f[i][j][k]表示在第iii列,第jjj行,骰子状态为kkk的最小代价这里的状态存储方式需要使用得当一个有242424种状态转移方程为f[i]...

2019-03-18 20:34:05

[一道感觉做过的题]翻牌游戏

(巨弱写题解不易,转载或沿袭请标明出处)题面题目描述现在有nn种图案以及2n2n张卡牌,每张卡牌上有一种图案,每种图案对应两张卡牌一开始卡牌都是面朝下放在桌子上的,玩家每次可以翻开其中两张卡牌:如果这两张卡牌的图案相同,则这两张牌都会被移除否则这两张牌必须留在原处,并保持图案向下摆放现在某位玩家的策略是这样的:如果知道某些卡牌的图案相同,则优先翻开这些卡牌否则随机翻开两张...

2019-03-10 17:59:58

[IOI2008]Island(基环树的直径+优化)

原题地址其实是一道很坑的模板题题意很简单——给定几个基环树的森林,求每棵基环树的直径长度之和基环树的直径有两种情况不经过环的,每一棵子树的直径中最长的经过环的,环上的一部分加上对应的两颗子树的深度如图:对于第一种情况的话,计算出每棵树的直径求一个max就好了第二种情况可能相对麻烦一点。。。其实可以把以环上的点为根的所有子树的深度求出来,然后再在环上跑用单调队列维护的dp就好...

2019-03-07 19:32:09

CH4302-Interval GCD(线段树+树状数组+GCD)

原题地址题意维护两个操作区间加区间GCDSoluiton这里有一个很巧妙的方法——更相减损术就是数论里的加减法对GCD封闭也就是gcd(a1,a2,...,an)=gcd(a1,a2−a1,a3−a2,...,an−an−1)gcd(a_1,a_2,...,a_n)=gcd(a_1,a_2-a_1,a_3-a_2,...,a_n-a_{n-1})gcd(a1​,a...

2019-03-06 19:27:19

[APIO2010]巡逻(树的直径+再次直径)

题面楼主回归了(这段时间去颓文化课了题目的意思是让你在一棵树上加K条边,再从1出发经过所有节点和所有边(点和边均可重复)回到1的最短路径鉴于K==1||K==2,分类讨论就好了K=1不加边的时候ans=edges_sum*2加一条边能将ans减少这条边两点之间原来的距离-1显然找直径是最合适的。。所以ans=edges_sum*2-diamete...

2019-03-02 16:05:05

球体积公式推导(积分)

球的体积刚刚学了定积分的一点皮毛…来玩一玩废话不多说,Let’sstart设球的半径为RRR我们把球(我们通过半球来考虑)切成好多好多(nnn片)薄片,就是一个一个的圆,设圆的半径分别为rrr面积S(r)=πr2S(r)=\pir^2S(r)=πr2到圆心距离为xxx的圆的半径f(x)=R2−x2f(x)=\sqrt{R^2-x^2}f(x)=R2−x2​可以得到V=2∫0...

2018-11-19 19:13:17

Fxkkks

been jinxed
关注
  • student
  • 中国 浙江省 杭州市
奖章
  • 持之以恒
  • 勤写标兵Lv1