• 等级
  • 5396 访问
  • 44 原创
  • 0 转发
  • 117983 排名
  • 26 评论
  • 78 获赞

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

NOIp2018游记

不敢先发出去…瑟瑟发抖…所以等联赛结束了再发好惹…Day0hzxjhs承办NOIp太棒啦!!!然鹅并不是西溪紫金港校区的话不知道比西溪好到哪里去不要被西溪领导看到QAQ晚上直接飞到华里酒店环境好评!!!颓+睡觉+rp+rp++rp++++rp...

2018-11-11 21:42:09

UOJ#351.新年的叶子

瞎bbnoip全真模拟赛又挂了。。出题人居然又贺了三道原题。。T3.走向巅峰新年的叶子//原题链接被出题人魔改之后的题面…T1暴力T2爆蛋,,于是只好来做T3思路树的多条直径一定会相交所以我们用最暴力的做法(去考提高的应该都会吧先随便选一个点找到离这个点最远的一些点作为直径的左端点们在随便选一个左端点找到与她最远的一些点也就是右端点们然后再树上乱搞即可)算出这段区间...

2018-11-05 19:52:07

莫比乌斯反演

莫比乌斯反演就是背两个公式证明略F(n)=∑d∣nf(d)F(n)=\sum_{d|n}f(d)F(n)=d∣n∑​f(d)f(n)=∑d∣nμ(d)F(nd)f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})f(n)=d∣n∑​μ(d)F(dn​)F(n)=∑n∣df(d)F(n)=\sum_{n|d}f(d)F(n)=n∣d∑​f(d)f(n)=∑n∣dμ(dn...

2018-10-22 18:00:13

种族并查集

蒟蒻太菜了…大佬又要嘲讽我了用处对于普通的并查集,我们只维护了每个元素之间的同类关系,但是如果给的关系不一定是同类,可能是像团伙里一样对立的关系,像食物链一样的A→B,B→C,C→AA\toB,B\toC,C\toAA→B,B→C,C→A的关系,这时候就要用到种族并查集。实现种族并查集,就是把同一个集合中的每个元素赋予多个不同的属性,在不同属性的对应元素间建立关系,关系与关系之间能够...

2018-10-18 18:20:59

牛客网NOIP赛前集训营-提高组(第五场)Solution

众人:这次题目好难T^TJiry:这次题目简单就没做ppt了众人:初赛切线段期望为什么是1/3?Jiry:你积分积一下就好,这不是高考范围的吗众人:吉老师您出复赛吗?Jiry:你认为我会出我就不会出,你认为我不会出我就会出(疯狂暗示)A-同余方程B-旅游题意就是给你一张边权为2i2^i2i的无向图,问走完每条边最后回到起点的最小距离是多少其实我们的目标是把这个普通的无向图变成...

2018-10-15 22:22:49

牛客网NOIP赛前集训营-普及组(第四场)Solution

无聊去水了场普及组结果ak了(逃A-新个税按照题目要求直接模拟即可需要注意的是小于等于5000元的情况,否则只有50分#include<cstdio>#include<stdlib.h>usingnamespacestd;intal,sa,de;voidstop(){printf("%d\n",al-de);

2018-10-07 17:20:48

preNoip中时间复杂度的计算

特征方程法解一阶线性代数递推式数列{ana_nan​}满足a1=b,an+1=can+da_1=b,a_{n+1}=ca_n+da1​=b,an+1​=can​+d,求该数列的通项公式针对递推关系式作出一个特征方程x=cx+dx=cx+dx=cx+d定理:设上述递推关系式的特征方程根为x0x_0x0​当x0=a1x_0=a_1x0​=a1​时,an=a1a_n=a_1an​=a1​...

2018-10-03 16:22:30

NowcoderWannafly挑战赛25游记(A~D)

A-因子p≤10000p\leq10000p≤10000说明ppp分解质因数后各个质因子的个数不会很多只需要考虑n!n!n!中ppp的每一个质因子的个数最后ans=min(⌊allnum⌋)ans=min(\lfloor\frac{all}{num}\rfloor)ans=min(⌊numall​⌋)(allallall表示ppp的某个质因子在n!n!n!中的个数,numnumnum表...

2018-09-29 20:49:02

牛客网NOIP赛前集训营-提高组(第三场)A-管道维修

A-管道维修题目描述在维修下水管道的过程中,发现一块n×m的易堵区域。为了方便表示,将易堵区域第iii行第jjj列的格子命名为格子(i,j)(1≤i≤n,1≤j≤m)(i,j)(1≤i≤n,1≤j≤m)(i,j)(1≤i≤n,1≤j≤m)。每次维修下水道时,其中有些格子是堵塞状态,有些则是未堵塞状态。维修需要分步进行:所有与n×mn×mn×m长方形四周边界相邻的格子或者与未被堵塞的格子相邻(四...

2018-09-23 14:01:04

牛客练习赛27(A,C,E题解)

A纸牌最优解为a−b2=n2,b−a=n2,a−b=0a-\frac{b}{2}=\frac{n}{2},b-a=\frac{n}{2},a-b=0a−2b​=2n​,b−a=2n​,a−b=0(niseven)a−b+12=n−12,b−a=n+12,a−n−12=0a-\frac{b+1}{2}=\frac{n-1}{2},b-a=\frac{n+1}{2},a-\frac{n-1}...

2018-09-22 22:07:57

CodeForces 264B.Good Sequences(DP)

B.GoodSequences(2s,256M)SquirrelLissisinterestedinsequences.Shealsohaspreferencesofintegers.Shethinksnnnintegersa1, a2, ..., ana1, a2, ..., ana_1, a_2, ..., a_naregood.Nowsh...

2018-08-28 12:48:46

点积和叉积(基本的东西,先挖个坑)

点积(数量积,内积)点积就是高中人教版必修四中提到的数量积用符号表示a⋅ba⋅ba\cdotb表示计算方法a⋅b=cosθ|a|×|b|a⋅b=cosθ|a|×|b|a\cdotb=cos\theta|a|\times|b|还有一种计算方法:a(x1,y1),b(x2,y2),a⋅b=x1×x2+y1×y2a(x1,y1),b(x2,y2),a⋅b=x1×x2+y1...

2018-08-20 13:29:52

CodeForces343D.Water Tree(树链剖分)

D.WaterTreetimelimitpertest4secondsmemorylimitpertest256megabytesMadscientistMikehasconstructedarootedtree,whichconsistsofnvertices.Eachvertexisareservoirwhichcan...

2018-08-16 12:51:23

CodeForces 196C.Paint Tree(分治+极角排序)

C.PaintTreetimelimitpertest2secondsmemorylimitpertest256megabytesYouaregivenatreewithnnnvertexesandnnnpointsonaplane,nothreepointslieononestraightline.Yourtas...

2018-08-11 07:21:09

Fxkkks

been jinxed
关注
  • student
  • 中国 浙江省 杭州市