2 C20200324_wyl

尚未进行身份认证

我要认证

超蒟蒻

等级
TA的排名 40w+

[HDU4336]Card Collector(概率DP and 概率容斥)(过程详解)

这是我这两类题目的第一次尝试我会对过程进行详解剖析题意:意思就是你吃干脆面集卡片,多组数据,每组数据,给定n种卡片,以及开到每一种卡片的概率。求开到所有卡片的期望次数。方法一:概率dp最后是(fs+1)首先n<=20,又是集到或没集到,看得出来状态压缩Dp的雏形:我习惯顺推,情况的表示可能与常见表示方式不一(但希望大家,包括我自己,习惯倒推,因为顺推概...

2019-08-24 20:43:25

2019/8/15题解+总结

今日总结:爆零了,主要原因在于时间分配不匀,和太过贪心,以及基础知识反应不及时。第一题我没想出正解,但是-1下来打完有20分,后悔没有骗分。第二题初做有灵感,线段树映射x轴加速也想过,可惜一直想正解,最后时机没把握住。第三题的奇怪数据方式和数学公式把我唬住了,没有细看,以为是道数论题,结果前缀后就可以。总的来说,发挥失常也有,知识不牢也有,需要抓紧时间提升能力。【[USAC...

2019-08-16 07:37:06

STO GZM Orz %%%% ender魔王考试题解(前两道)(贪心和DP)STO WK orz

STO Ender orz 太强了 STO WK orz 太神了首先,为什么是前两道呢?因为最后一道是导数推论+泰勒展开,对于我一个初中生来说只能稍作理解,严格推论还是写不出第一题 W题目描述给定正整数n,将其表示为n=a_1+a_2+...a_m,其中a_i的绝对值为2的非负整数幂(即a_i=1,-1,2,-2,4,-4or so)求最小的m输入格式...

2019-07-26 13:55:21

Tunnel Warfare (鬼子进村)(ZKW线段树)

题目链接(洛谷)题目链接(HDU)题目链接(vjudge)由于题意简单,所以不解释为何用线段树,我用的是重口味线段树。三方探查过后,大概可以把题意归纳为:最开始所有点为1。然后有一种操作,将此点置0(单点修改),这个应该都会。第二种操作,将上一个被修改的点修复(单点修改),有时候会连续修好几个,所以你需要一个栈。第三种操作,求与一个点相连的最长(区间查询),我求的是...

2019-06-26 13:32:45

测试人品Miller_rabin算法(二次探测定理 + 费马小定理)

今天我来为大家介绍一个算法:Miller_Rabin算法是一个rp测试算法,顺便测试素数。错误几率为4−s4^{-s}4−s,s为循环次数开始之前,介绍两个要用到的数论公式:1.费马小定理:若p为质数,那么np−1≡1(Mod p)若p为质数,那么n^{p-1}\equiv1(Mod\ p)若p为质数,那么np−1≡1(Mod p)2.二次探测定理:若p为质数,...

2019-04-23 13:55:59

小凯的疑惑(Noip 提高组 2017 d1 1)+[USACO4.1]麦香牛块Beef McNuggets

大家好,我很久都没来水题解了,昨天我们社团的考试中考了小凯的疑惑这道经典的数论题,但由于大家早已做过Noip2017所以直接拿出公式,一秒过题,但却不能证明,令我痛心,今天我就来写一篇题解,以浇胸中块垒,顺便也解一道Dp+数论。小凯的疑惑+麦香牛块简化题目:小凯的题意大约为有a,b大于0,gcd(a,b)=1(互质),求最大n,nan+bm,n和m0。乍一看以为很难,感...

2019-04-13 16:13:37

前期总结+开学展望(WYL)

知识总结:之前我们学了很多知识,包括有这几大类。基础知识:顺序,选择,循环,(多维)数组,字符串,排序,结构体。算法:贪心,递归,递推,搜索,二分,dp(优化),树形dp。数据结构:栈,队列,map,动态数组,set,双线队列,线段树,树状数组。图论:最短路,最小生成树,拓扑排序,最近公共祖先。总的来说,我们已从初学编程的菜鸟变成了学了一会编程的菜鸟老手,较...

2019-02-27 13:28:52

lca小结

LCA(最近公共祖先)先有一棵树,选两个点向上爬相遇的第一个点就是这两个点的lca,如2是1和7的lca,1是6和5的lca。理解了吧。一棵树理解倒是很简单,现在来讲实现方法(四种)。根据一道模板题来讲吧见百练(1986:Distance Queries)一般的lca题都是求边权和,因为他们懒得给根为了让你随便选一个当根。一.暴力搜索两个先到同一深度,再一起向上爬,时间...

2019-01-31 20:54:45

添加括号题解(兼平行四边形优化dp小记)

本人做了这道题后发现这道题不仅涉及到括号匹配递归,又涉及刚学的平行四边形优化dp,于是来写题解。小记平行四边形优化是个玄学,主要看题感和运气,你觉得是就是,可以用这种优化的题主要有以下特征:dp[i][j]=max/min(dp[i][j],dp[k][j-1]+w[k+1][i]);(k为1~n)或dp[i][j]=max/min(dp[i][j],dp[i][k]+dp[k...

2019-01-03 14:05:26

四连测(二)

我来水第二篇题解,let's go;测量温度(temperature)题目描述见洛谷([POI2011]TEM-Temperature)题目理解考场思维:题目描述什么乱七八糟的,第一题肯定不难,按常用的区间思维(s[i-1].r>=s[i].l),没想到老师连面子都不给,直接出难题。下来之后发现:我把题意改成了有可能平衡。于是题目应该是(s[i-1].l&lt...

2018-12-30 00:28:25

四连测总结(WYL)

本次考试为校内退役(你还没退呢!)四连测,顾名思义,考不好就会退役(回家养猪),我心里慌得一批(稳如老狗),所以勤奋学习期末考试,于是考的不错看看前面的大佬(⊙o⊙)。考试总结        我考完第一次考试的时候就已经悟了,我是一个(天才,貌如潘安,诗如李白)没有压力就浪的飞起的人,第一次随便读读题,不思考就开始打代码,运气搞定一道单调队列水题(但我手写了deque,浪费时间,下次不做这...

2018-12-26 13:59:32

退役四连测题解(一)

猴子题目描述           有Q只猴子要从第一棵树到第n棵树去,第i只猴子一次跳跃的最远距离为Ki。如果它在第x棵树,那它最远可以跳到第x+Ki棵树。如果第j棵树的高度比第i棵树高或相等,那么它从第i棵树直接跳到第j棵树,它的劳累值会增加1。所有猴子一开始在第一棵树,请问每只猴子要跳到第n棵树花费的劳累值最小。输入第一行一个整数n,表示有n棵树。(2<=n<=10...

2018-12-24 14:04:36

【NOIP2015普及组】推销员

 在下蒟蒻,欢迎各位大佬与我交流,此处为我洛谷空间题目描述:题目出处【问题描述】   阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有N 家住户,第i家住户到入口的距离为 Si 米。由于同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相等。阿明会从入口进入,依次向螺丝街的X家住户推...

2018-12-03 14:18:25
勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。