• 等级
  • 142810 访问
  • 434 原创
  • 2 转发
  • 7795 排名
  • 39 评论
  • 91 获赞

[LibreOJ 3124]【CTS2019】氪金手游【容斥原理】【概率】【树形DP】

DescriptionSolution首先它的限制关系是一个树形图首先考虑如果它是一个外向树该怎么做。这是很简单的,我们相当于每个子树的根都是子树中最早出现的点,概率是容易计算的。设DP状态f[i][j]f[i][j]f[i][j]为做到以i为根的子树,子树中权值W的和为j且满足限制关系的概率。然后就可以直接利用子树背包DP来转移了。如果有些边是反向(儿子到父亲)的,我们可以通过...

2019-05-21 20:14:06

[LibreOJ 3120]【CTS2019】珍珠 【生成函数】【计数】

DescriptionSolution有一个直观的思路是考虑每种颜色个数的奇偶性,奇数个数的颜色不能超过n−2mn-2mn−2m因此若n−2m≥Dn-2m\geqDn−2m≥D则答案一定是DnD^nDn否则由于每种颜色其实没有区别,我们考虑一种颜色为奇数和为偶数的指数型生成函数奇数是ex−e−x2e^x-e^{-x}\over22ex−e−x​,偶数是ex+e−x2e^x+e^{...

2019-05-21 19:59:09

[LibreOJ 3119]【CTS2019】随机立方体【计数】【容斥】

DescriptionSolution记N=min(n,m,l)N=min(n,m,l)N=min(n,m,l)首先考虑容斥,记f(i)f(i)f(i)为至少有i个位置是极大的,显然极大的位置数上界是N。那么显然Ans=∑i=kN(−1)i−kf(i)(ik)Ans=\sum\limits_{i=k}^{N}(-1)^{i-k}f(i){i\choosek}Ans=i=k∑N​(−...

2019-05-21 17:22:52

【学习小记】Berlekamp-Massey算法

PrefaceBM算法是用来求一个数列的最短线性递推式的。形式化的,BM算法能够对于长度为n的有穷数列或者已知其满足线性递推的无穷数列aaa,找到最短的长度为m的有穷数列ccc,满足对于所有的i≥ni\geqni≥n,有ai=∑j=1mcjai−ja_i=\sum\limits_{j=1}^{m}c_ja_{i-j}ai​=j=1∑m​cj​ai−j​TextBM算法的流程十分简洁明了—...

2019-05-09 20:24:28

稀疏图的随机游走问题

Description给出一张n个点,m条边的平面图,从1号点开始随机游走,抵达n号点则结束,问期望步数?n<=5000Solution这题在wxh的IOI2019国家候选队论文中也提到了首先考虑平面图有什么好性质,它的边数不会很多!实际上(根据论文),大于等于3个点的平面图边数不会超过3n-6,也就是说边数和点数是同阶的。我们可以将概率写成数列的形式,实际上它是一个线性递推具...

2019-05-09 19:53:28

【数论模板】二次剩余Cipolla算法,离散对数BSGS 算法

CipollaLLksm(LLk,LLn){ LLs=1; for(;n;n>>=1,k=k*k%mo)if(n&1)s=s*k%mo; returns;}namespacenumber{ LLD; structZ { LLx,y; Z(LL_x=0,LL_y=0){x=_x,y=_y;} }; Zoperator...

2019-05-09 11:28:10

2019.5 北京集训小结

5.3Day0省选结束那天下午突然被通知晚上19:30的飞机去北京十一集训还没来得及回家收拾行李就匆忙赶往机场到了酒店已经0点后了累得半死5.4Day1果然是帝都的权贵学校,跟我们农村大山中学完全不是一个世界的东西...

2019-05-08 13:45:24

新博客开张啦!

新的博客链接:https://www.cnblogs.com/BAJimH/有些重要的博客会在两边都复制一份

2019-05-07 21:24:17

【GDSOI2019】总结

Day1进入考场的时候相当紧张,只好靠音乐来缓解。电脑非常的卡,保存、编译都卡半天,ctrl+W居然还被重定向到打开一个什么猎奇玩意做题效率–看T1思索一段时间,居然不会!考场内迟迟没有想起键盘声果然今年画风突变,往年的送分签到题没有了。花了大概1.5h把前三题看完,只有T3是会的T2暴力非常清晰,先去写了T2暴力。接下来肝T1,明知道这是个高维前缀和,但是对这东西不是很熟练...

2019-05-02 22:58:26

[JZOJ6152] Endless【并查集】【SA】【ST表】

DescriptionT组数据,T≤10000,∑n≤300000T\leq10000,\sumn\leq300000T≤10000,∑n≤300000Solution先考虑怎么把这些平方串弄出来这似乎是一个很经典的套路了(WC2019的时候好像讲了)枚举平方串的长度为2L,那么我们在L,2L,3L…的位置设置关键点,用SA或者二分+哈希求出相邻关键点的最长公共前缀和最长公共后缀...

2019-04-29 21:55:02

【WC2019】数树【计数】【DP】【多项式】

Description此题含有三个子问题问题1:给出n个点的两棵树,记m为同时在两棵树中的边的个数,求ymy^mym问题2:给出n个点的一棵树,另外一棵树任意生成,求所有方案总的ymy^mym的和问题3:两棵树均任意生成,求所有方案总的ymy^mym的和Solution留坑待填Code#include<bits/stdc++.h>#definefo(i,a,...

2019-04-20 21:48:44

【HNOI2019】部分题简要题解

题意懒得写了LOJDay1T1鱼个人做法比较猎奇,如果有哪位大佬会证明能分享一下的话感激不尽。题解:枚举鱼尾和鱼身的交点D,将所有其他点按照到D的距离排序,距离相同的分一组。感性的理解,对于每个点D,暴力枚举距离相等的点对(B,C)。这样总的数量不会很多。感觉仍然是O(n2)O(n^2)O(n2)级别的。那么我们对枚举的D,将所有的点对的中垂射线和点按照极角排序,扫一圈就能得到答...

2019-04-11 15:45:42

【NOI2019十二省联合省选】部分题简要题解

Day1T1异或粽子题意:给出一个长为n的序列,选择K个不完全重合的区间使得每个区间的异或值的总和最大。题解:先做一个前缀异或和,对于每一个右端点我们记录三元组(l,r,x)表示在左端点在[l,r][l,r][l,r]内,最大异或值为x,塞进堆里。每次取出堆顶,并将该三元组对应的区间分裂成两个,重新扔回堆里。计算区间最大异或值利用可持久化字典树。时间复杂度O(nlog⁡n+Klog⁡M...

2019-04-11 14:58:18

[LibreOJ #2341]【WC2018】即时战略【交互】【LCT】

Description有一棵n个点的结构未知的树,初始时只有1号点是已被访问的。你可以调用交互库的询问函数explore(x,y),其中x是已访问的点,y是任意点。它会返回x向y方向走第一步的点,如果该点未被访问,则将其标记为已访问。你需要实现一个函数,它通过接口得到n和T,需要在T次explore操作内将所有的点标记(也就是说走完这棵树)。要求最严格的两档数据:n<=30000...

2019-03-31 21:41:30

【学习小记】半平面交——排序增量法

Preface之前的半平面交的算法是基于分治和凸包合并的,分治两边,计算出半平面交,再合并凸包。而这种排序增量法好写简洁常数小,适合在比赛中使用。Text为了避免半平面交区域无界的情况,我们在无穷远处四个方向加上四个半平面的限制。可以看出,有限的半平面交是一个凸包方便起见,我们用点+向量的形式来表示一个半平面,向量的左手向就是半平面的方向。定义半平面的极角为向量的极角,我们将半平面按...

2019-03-31 15:18:59

[JZOJ6093]【GDOI2019模拟2019.3.30】星辰大海【计算几何】【半平面交】

Description给出平面上n个点,其中1号点是可以移动的,但是移动的范围不能改变任意三个点所成的角的状态([0,π),[π,π],(π,2π][0,\pi),[\pi,\pi],(\pi,2\pi][0,π),[π,π],(π,2π])。求可移动的范围。n≤500000n\leq500000n≤500000Solution画一个图可以感受出来,实际上1号点移动的范围就是不能越过其...

2019-03-31 14:54:17

[JZOJ6096] 森林【倍增】【贪心】

Description我们定义对一棵树做一次变换的含义为:当以1号节点为根时,交换两个互相不为祖先的点的子树;一棵树的权值为对它进行至多一次变换能得到的最大直径长度;初始时你只有一个节点1,你需要执行n-1个操作,第i次操作会给出一个整数x,表示新加入第i+1号点,并与第x号点连一条边。每次操作后输出当前的树的权值。强制在线n<=200000Solu...

2019-03-29 20:29:23

[JZOJ6088] [BZOJ5376] [loj #2463]【2018集训队互测Day 1】完美的旅行【线性递推】【多项式】【FWT】

DescriptionSolution我们考虑将问题一步步拆解第一步求出FS,iF_{S,i}FS,i​表示一次旅行按位与的值为S,走了i步的方案数。第二步答案是FS,iF_{S,i}FS,i​的二维重复卷积,记答案为SS,iS_{S,i}SS,i​,那么FS,i×ST,jF_{S,i}\timesS_{T,j}FS,i​×ST,j​能够贡献到SS&T,i+jS_{S\...

2019-03-28 22:00:49

[JZOJ6089]【CodeChef 2014 April Challenge】Final Battle of Chef【数据结构】【整体二分】

Descriptionn,q,V≤100000,wi≤109n,q,V\leq100000,w_i\leq10^9n,q,V≤100000,wi​≤109Solution又是一道大数据结构由于有一个下取整,这就导致了不同时间的修改值是不能简单的直接加在一起的。容易发现,1操作的影响只会影响到距离不超过log的点。这样我们很容易得到一个qlog⁡nlog⁡2Vq\logn\log...

2019-03-28 15:38:48

[JZOJ6090]【GDOI2019模拟2019.3.27】圆【数学】

Description有nnn场比赛,第i场比赛的前aia_iai​名晋级有q次询问,每次询问一个区间[l,r][l,r][l,r],和一个xxx,表示只参加[l,r][l,r][l,r]的比赛,每场的排名会独立的在[1..x][1..x][1..x]中随机。回答至少有一场晋级的概率。没有模数答案与标准答案相差10−610^{-6}10−6以内即为正确。Soluton很有意思的一题。...

2019-03-28 15:10:39

BAJim_H

比孤独更可悲的事情,就是根本不知道自己很孤独,或者分明很孤独,却把自己都骗得相信自己不孤独。
关注
  • 中国
奖章
  • 持之以恒
  • 1024勋章
  • 勤写标兵Lv1
  • 勤写标兵Lv2