2 zxyoi_dreamer

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 3k+

【LOJ6713】「EC Final 2019」狄利克雷 k 次根 加强版(狄利克雷生成函数)

传送门题解:我记得 SCOI2019 考完之后我就口胡过这个东西,当时D1T3 超矩形。。。考虑 Dirichlet 生成函数:F(x)=∑i≥1fiixF(x)=\sum_{i\geq 1}\frac{f_i}{i^x}F(x)=∑i≥1​ixfi​​。考虑 Dirichlet 卷积:(f∗g)(n)=∑d∣nf(d)g(nd)(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})(f∗g)(n)=∑d∣n​f(d)g(dn​),不难发现 Dirichlet 卷积的

2020-05-25 09:27:32

【CF917E】Upside Down(哈希二分)(后缀数组)(AC自动机)

传送门诈尸,主要是最近一直在刷水题感觉没有什么值得写的。口胡好题,不建议写。题解:一句话说,将出现的情况分为在 u-LCA链上 和横跨LCA 分别统计。在链上的可以直接建立正反AC自动机,然后树上DFS的同时AC自动机中DFS序+差分算一下出现次数即可。考虑横跨LCA的情况,找出 u->LCA 的后缀能匹配的最长前缀和 LCA->v 的前缀能匹配的最长后缀。那么所有能匹配的前缀和后缀都是最长匹配前缀和后缀的border,分为log个等差数列,算一下凑成原串的方案数即可。然后讲一下

2020-05-20 21:45:43

【2015集训队互测】文学(区间DP)(计算几何)

传送门题解:一个非常巧妙的DP,可以不能保证在枚举最优解的子集的情况下,一定构造出最优解,但是可以保证在所有情况中一定会算到最优解。首先对于能够一个半平面覆盖完的特殊处理一下。否则,解里面至少有两个半平面,首先枚举这两个半平面,剩下的是一个凸的无穷区域里面的点,以这两个半平面交点为中心,对未覆盖的点进行极角排序,枚举剩下的半平面,每个半平面会覆盖一些点,在极角序上形成了若干区间,记录 w...

2020-04-23 20:49:16

【洛谷P2839】middle(二分答案)(主席树)

传送门题解:复习一下常见的trick。求中位数转化为二分答案,大于等于的部分设置成 111 小的部分设置成 −1-1−1然后求和,看结果是否大于等于 000 来判断是否可行。这道题直接按照权值排序,以原序列标号为下标建立主席树,叶节点权值为在当前树中它应该为的权值,对于询问,中间的询问和,两边的询问最大前后缀即可。代码:#include<bits/stdc++.h>#...

2020-04-23 20:39:40

【集训队互测2012】JZPKIL(伯努利数)(Pollard-Rho)(积性函数)

传送门有了拉格朗日插值求自然数幂和,就算要好写也有差分法可以用,OI里面伯努利数还有什么用。当数据范围不大,但是需要多次求出具体系数的时候,伯努利数就有用了。在 O(n2)O(n^2)O(n2) 预处理组合数和 1−n1-n1−n 的逆元之后,利用伯努利数可以 O(n)O(n)O(n) 求出 nnn 次方幂和的多项式系数,这是拉格朗日插值和差分法不好做到的(当然也有可能是我菜)。算了,不...

2020-04-23 16:13:23

【清华集训2017】生成树计数(生成函数)(prufer序列)(牛顿恒等式)

传送门题解:凭借直觉 按照套路,考虑每个原来的连通块当成点,枚举prufer序列,假设第 iii 个连通块在 prufer 序列中出现了 cic_ici​ 次,不难发现对应的合法的 prufer 序列有 (n−2)!/∏ici!(n-2)!/\prod_i c_i!(n−2)!/∏i​ci​!,对应全树还需要乘上 ∏iaici+1\prod_i a_i^{c_i+1}∏i​aici​+1​。...

2020-04-22 11:31:34

【LOJ6609】无意识的石子堆 加强版(容斥)(DP)

传送门题解:冷静一下我们知道加强版常数上是不允许任何类型的牛顿迭代出现的,目前知道以下两种思路上不同的做法。首先不难发现每行都必须有两个石子,所以讨论的重点肯定在列上面。做法 1:行当做一个点集,列当做一个点集,每个位置放的石子视为一条行向列连出的边。不难发现这玩意是个二分图,设左边有 nnn 个二度点,右边有 kkk 个二度点和 2(n−k)2(n-k)2(n−k) 个一度点,需要...

2020-04-22 08:47:15

【LOJ3285】「USACO 2020 US Open Platinum」Circus(乱搞)(并查集)

传送门题解:大体思路大家区别不大,具体做法千奇百怪。。。点击此处膜拜大佬:here。我们考虑计算等价类的大小,即一个状态可以转移到多少个合法的状态。首先容易注意到一条链上啥都交换不了,也就是说我们需要跨过一堆度数为 222 的点。假设链两端的子树大小为 A,BA,BA,B ,当前考虑为 KKK,不难发现左右能进行交换当且仅当 K<A+B−2K<A+B-2K<A+B−...

2020-04-21 15:51:37

【LOJ3284】「USACO 2020 US Open Platinum」Exercise(容斥)

传送门题解:由于最后求的是所有lcm的乘积,直接分质数考虑即可。假设求出 ppp 的最大次数恰好为 eee 的置换有 g(p,e)g(p,e)g(p,e) 个,显然对答案的贡献为 (pe)g(p,e)(p^e)^{g(p,e)}(pe)g(p,e) ,并不显然。我们考虑计算出 ppp 的次数至少为 eee 的数量,记为 f(p,e)f(p,e)f(p,e),然后计算 ∑e=1f(p,e)...

2020-04-21 15:33:36

【LOJ3248】「USACO 2020.1 Platinum」Falling Portals(凸包)(倍增)

传送门题解:把每个点的 S−TS-TS−T 的图像画出来 fi(x)=−ix+Aif_i(x)=-ix+A_ifi​(x)=−ix+Ai​。很明显要问的就是允许走交点的情况下 iii 到达第 QiQ_iQi​ 的位置的最小横坐标是多少。考虑 A[Qi]A[Q_i]A[Qi​] 和 A[i]A[i]A[i] 的大小关系,它们决定在 x=0x=0x=0 的时候那条线在上面,于是我们的策略也就决...

2020-04-21 15:21:37

【校内模拟】music(多重分块)(非常规大小分块)

简要题意不放了,强制在线主席树SB题一道,卡空间需要用分块做到 O(n)O(n)O(n) 空间。题解:由于发下来的题解几乎就是在口胡,我跑去UOJ群问了一下这道题的 O(n)O(n)O(n) 空间做法,幸运地得到了myh的教育,下面的做法就来自于myh神仙。先考虑对时间进行分块,块大小为 SSS,考虑把每块中会进行修改的位置拿出来,然后把原序列中所有 n/Sn/Sn/S 的倍数的位置拿出来...

2020-04-20 20:34:26

【校内模拟】Kingdom(DP)

由于太过SB,懒得写简要题意了。。。题解:不难发现我们可以直接考虑 iii 能不能直接走到 jjj 然后 O(n2)O(n^2)O(n2) DP即可。最开始把题目看错成距离直线距离不超过 ddd 了,我Splay维护动态凸包都写完了艹。。线段的话也是非常简单,考虑一个不在圆 iii 内部的点,它显然会限制 iii 向后连出去的点的极角范围。于是维护这个范围即可,然而我的维护方式过于SB...

2020-04-20 15:22:05

【校内模拟】Fygon 2.0(状压DP)

原题传送门目前计蒜客上面AC数量还是0,我也懒得交,估计CF Gym里面也该有这道,懒得找了。题解:今天的签到题。把for循环换个思路考虑: for var in range ( l , r ):冷静一想不难发现等价于: for var in range ( 1 , n ): if(l <= var && var <= r)于是实际上要求的就是...

2020-04-20 15:14:11

【2019集训队互测】公园(广义串并联图)(动态DP)

传送门题解:只提一下记个要用的性质,证明去集训队论文里面看。满足题意限制的图称为广义串并联图。任何一个广义串并联图,去掉重边之后边数不超过点数的两倍。任何一个广义串并联图可以由如下的方式构造:初始只有一个点,每次可以选择 1)加一个点,并和图中原有点连一条边,2)选择两个直接相连的点,新加一个点与这两个点相连,并且可以选择是否删去原来连接这两个点的边。当然广义串并联图也是平面图,...

2020-04-18 19:52:02

【CodeForces1336】简要题解

比赛传送门A. Linova and Kingdom容易注意到我们在一个位置放下一个工业城市的贡献是 dep−sizdep-sizdep−siz,depdepdep 表示它到根还有多少个点没有放,sizsizsiz 表示它子树内有多少个点放了。显然我们每次只会选择剩下的子树的叶子,贪心即可。代码:#include<bits/stdc++.h>#define ll long ...

2020-04-17 17:37:27

【校内模拟20200417】

由于全是SB题,简述如下:T1:请你求出有多少个长度为 nnn 字符集为 kkk 的串,本质不同子串个数为 mmm。n≤10n\leq 10n≤10题解:本质不同子串个数只和最小表示有关,爆搜然后算即可。代码:#include<bits/stdc++.h>#define ll long long#define re register#define cs const...

2020-04-17 12:09:42

【校内模拟】play in array(块状链表)

简要题意:一个序列,请你支持将 ara_rar​ 挪到 al−1a_{l-1}al−1​ 和 ala_lal​ 之间,重新标号。询问在当前序列的第 lll 到第 rrr 个位置,kkk 出现了多少次。块链裸题,写就完事,好写的一B。顺便,std::list::size() 这个函数差点又把我坑惨了。至于到底问题在哪里:here代码:#include<bits/stdc...

2020-04-16 15:29:03

【CodeForces468】C. Hack it!(构造)

传送门题解:由于我校模拟考的时候 l,r,al,r,al,r,a 的限制为 1e16,所以这里讲一种把 l,rl,rl,r 往小了放的方法。首先问题转化为找到两个前缀使得答案 %a\%a%a 相等,根据抽屉原理问题一定有解。容易注意到 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y) 当且仅当 x+yx+yx+y 没有进位。容易想到把其中...

2020-04-16 15:18:20

【UR#8】决战圆锥曲线(线段树)

传送门题解:首先考虑暴力扫一遍出答案。然后注意到可能成为答案的 i,ji,ji,j 必然满足 i<j,yi>yji < j ,y_i>y_ji<j,yi​>yj​由于 yyy 是随机生成,期望的后缀最大值只有 O(log⁡n)O(\log n)O(logn) 个。于是我们直接用线段树找到后缀最大值即可,维护可以直接维护区间最大值,然后从右儿子开始df...

2020-04-16 15:03:31

【THUPC2019】令人难以忘记的题目名称 / game(数论)

传送门题解:倒着思考,什么样的序列必胜?首先是全0序列,然后是全等序列,然后是差分后是全等序列的。。。以此类推,必胜的序列必然满足它的某一阶差分在 %p 下是全0,且最少的差分次数就是答案。以下将差分定义为 Ai′=Ai−Ai+1A'_i=A_i-A_{i+1}Ai′​=Ai​−Ai+1​,这里省略了下标的取模,默认 AAA 是一个循环序列。首先我们知道一个差分后是数列可以写成 Ai′=...

2020-04-15 18:51:52

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 1024超级勋章
    1024超级勋章
    授予原创文章总数达到1024篇的博主,感谢你对CSDN社区的贡献,CSDN与你一起成长。
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。