zxyoi_dreamer-CSDN博客

原创【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≥1ixfi。考虑 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∣nf(d)g(dn)，不难发现 Dirichlet 卷积的

2020-05-25 09:27:32 1221 2

原创【CF917E】Upside Down（哈希二分）（后缀数组）（AC自动机）

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

2020-05-20 21:45:43 873

原创【2015集训队互测】文学（区间DP）（计算几何）

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

2020-04-23 20:49:16 604 1

原创【洛谷P2839】middle（二分答案）（主席树）

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

2020-04-23 20:39:40 322

原创【集训队互测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 419

原创【清华集训2017】生成树计数（生成函数）（prufer序列）（牛顿恒等式）

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

2020-04-22 11:31:34 530

原创【LOJ6609】无意识的石子堆加强版（容斥）（DP）

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

2020-04-22 08:47:15 495

原创【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 506

原创【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 367

原创【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 568

原创【校内模拟】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 347

原创【校内模拟】Kingdom（DP）

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

2020-04-20 15:22:05 210

原创【校内模拟】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 408

原创【2019集训队互测】公园（广义串并联图）（动态DP）

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

2020-04-18 19:52:02 1317 1

原创【CodeForces1336】简要题解

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

2020-04-17 17:37:27 374

原创【校内模拟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 252

原创【校内模拟】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 186

原创【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 281

原创【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 280

原创【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 321

原创【THUPC2019】找树 / findtree（FWT）（矩阵树）

传送门题解：送分题。首先求生成树肯定是矩阵树。然后我们发现这里的卷积全部都是位运算。众所周知位运算卷积的DFT可以直接考虑每一位的操作，理解的话其实就是每位表示一个维度，然后各个维度上进行各自的DFT即可。该怎么搞怎么搞。代码：#include<bits/stdc++.h>#define ll long long#define re register#defi...

2020-04-15 15:56:26 574

原创【THUPC2019】不用找的树 / tree（树分块）（树形DP）

传送门是我没见过的树分块姿势，出题人写的题解跟****一样，只有会这道题的人才看得懂，反正我没看懂，我看了std那8K难以形容的代码才知道题解真就NM乱写。严格来说，只有分块的具体方法那里是乱写，但是那里乱写直接导致了后续的无法理解。出题人：反正预计也不会有人想去写，题解乱写就行了。那乱写说是垃圾也就不为过了。所以这里来一个我的视角的题解。更离谱的是树上距离的定义居然是路径上点数而不...

2020-04-15 14:37:05 602 1

原创【2019集训队互测】序列

传送门题解：小清新送分题。设序列长度为 2k2^k2k，按照那个预处理完了之后，所有序列一定是有一半完全一样，另一半递归满足这个性质。所以描述一个序列只需要 log⁡m\log mlogm 的复杂度。发现在xor卷积下，两个满足该性质的序列卷积结果依然满足，所以用这个方式维护下去即可。代码：#include<bits/stdc++.h>#define ll long...

2020-04-14 16:25:34 337

原创【2019集训队互测】最短路径（点分治）（NTT）（分治）

传送门题解：树的部分直接点分治+NTT合并算出所有距离有多少点对即可。有环的话，再上一个分治即可。代码：#include<bits/stdc++.h>#define ll long long#define re register#define cs constnamespace IO{inline char gc(){ static cs int Rlen...

2020-04-14 16:21:38 388 1

原创【2019集训队互测】整点计数（min_25筛）

传送门这里稍微口胡记录一下要点，详细的自己去看xyx的集训队论文。题解：容易发现我们实际上要算的就是以 xxx 为斜边的沟谷数的数量。即统计有多少对 (y,z)(y,z)(y,z) ，满足 y2+z2=x2y^2+z^2=x^2y2+z2=x2。我们用高斯整数的角度来看，其实就是求 x2x^2x2 是多少个高斯整数与其共轭复数的乘积。在这道题里面，我们相当于是要对 x2x^2x2 在...

2020-04-14 16:18:32 283

原创【2019集训队互测】学习轨迹（贪心）

传送门题解：首先没有限制的话排个序就完事了。如果有限制的话，显然我们需要干的事情就是做出修正。按照权值从小到大排序。考虑什么情况下非法，权值小的依赖权值大的。这个时候的修正非常明显，把这个区间拎出来，无依赖的升序，然后有依赖的降序排在后面。这样的区间可以通过一次差分前缀和找出来。容易注意到有的时候我们把若干个区间合并可以得到更优的答案。简单讨论可以发现，如果不是全部合并，必然是...

2020-04-14 15:54:56 511

原创【2015集训队互测】机器人/Robot（超哥线段树）

传送门超哥线段树板子题。好像这是我又一次直接在考场上莽出来板子，之前一次超哥线段树都没有写过。上一次莽出来板子还是后缀平衡树。题解：简单叙述一下超哥线段树是怎么做的，其实知道原理就是瞎写了。我们要解决的问题是在二维平面上插入一条直线（线段的情况过会讨论），同时询问某个 x=x0x=x_0x=x0 上最高（或最低）的直线。首先强制在线的话可以转成半平面交或者凸包搞。否则我们可以用...

2020-04-14 15:38:01 256

原创【校内模拟】覆盖（DFS序）（二维数点）

简要题意：给一棵树和若干条路径，请你求出选择两条不同的路径，它们存在覆盖关系的概率。题解：一条路径可以根据两边两个点的DFS序描述成二维平面上的一个点。一条路径覆盖另一条可以转化为该路径对应的二维平面点在某个矩形中。二维数点瞎写即可，特殊处理一下路径一模一样的情况，不过不清楚数据卡没卡这个。代码：#include<bits/stdc++.h>#define ll l...

2020-04-14 15:25:16 175

原创【校内模拟】数值修改（贪心）（DP）

简要题意：给一个十进制数，每次可以选择它的一个数码，然后它的值减去你选择的这个数码。重复这个操作，直到这个数变成0，问最少需要多少次操作。x≤1e18x\leq 1e18x≤1e18脑子卡住是什么感觉。就是发现了正解要用的性质，不知道为什么就是没有继续往下细想。啊艹为什么题解：首先容易注意到答案是单调不减的。要证明这一点可以归纳，考虑 iii 和 i+1i+1i+1 假设之前的...

2020-04-14 15:19:07 177

原创【THUPC2019】摆家具 / furniture（计数）（BSGS优化矩阵快速幂）

传送门题解：考虑一个序列 qqq 对询问 p,tp,tp,t 的贡献。容易想到我们需要求出进行 ttt 次操作后有 iii 个位置和原序列不同的方案数，列出来发现 ttt 转移到 t+1t+1t+1 的形式和 ttt 无关，可以矩阵乘法计算，由于询问有点多，可以考虑BSGS优化一下。然后需要计算的就是 dif[p][i]dif[p][i]dif[p][i] 表示和 ppp 有iii 个位...

2020-04-13 16:44:55 349

原创【USACO19FEB】Mowing Mischief P（决策单调性）（线段树辅助分治）

传送门题解：容易想到首先要求一个LIS。根据以其结尾的LIS长度，把点分为若干集合，设为 SlS_lSl，容易注意到一个集合中横坐标增加的同时纵坐标减小。容易得到一个显然的DP：dpi=min⁡j∈Sl−1xj<xi,yj<yidpj+(xi−xj)∗(yi−yj)dp_i=\min_{j\in S_{l-1}x_j<x_i,y_j<y_i}dp_j+(x_i-...

2020-04-13 16:37:27 671

原创【校内模拟】幻想（后缀平衡树）

简要题意：给你一个字符串 SSS，请你支持：末尾加字符末尾删字符给一个询问串 QQQ ，求 QQQ 在 S[l:r]S[l:r]S[l:r] 中出现了多少次。强制在线题解：如果第三个操作没有 l,rl,rl,r 的限制就是 BZOJ4768，后缀平衡树裸题。有的话也没什么区别，开个vector维护一下子树内的点有哪些就行了。复杂度好像是两个 log，但是跑得飞起。一个lo...

2020-04-09 17:24:37 270 2

原创【校内模拟】黑暗（第二类斯特林数）（多项式求逆）

简要题意：here题解：设 c(G)c(G)c(G) 表示图 GGG 的联通块数量，首先利用第二类斯特林数转成下降幂：nm=∑k=0mSm,knk‾n^m=\sum_{k=0}^mS_{m,k}n^{\underline k}nm=k=0∑mSm,knk考虑 c(G)k‾c(G)^{\underline k}c(G)k 的意义，就是有序选择 kkk 个连通块的方案数，这部分有点像...

2020-04-09 17:18:21 221

原创【校内模拟】深邃（贪心）（二分答案）

简要题意：一棵树，有 kkk 个关键点，请你把树划分为若干联通块，使得每个联通块包含至少一个关键点，最小化最大的联通块的大小。题解：首先容易注意到可以二分答案。然后考虑怎么判断，进行dfs，每个点尽量贪心往下划分。hvuhv_uhvu 表示 uuu 为根的子树，uuu 这个联通块还能多容呐的点数。ntunt_untu 表示 uuu 为根的子树，无法向下分到任何一个联通块的点数。...

2020-04-09 17:09:17 136

原创【校内模拟】亲（斯特林反演推式子）

link另一种做法：直接考虑答案的表达式：Ans=∑i=0n(ni)Qi∑j=1ijkAns=\sum_{i=0}^n{n\choose i}Q^i\sum_{j=1}^ij^kAns=i=0∑n(in)Qij=1∑ijk考虑对 jjj 转下降幂，利用第二类斯特林数。Ans=∑i=0n(ni)Qi∑j=1i∑t=0kSk,t(jt)t!=∑t=0kt!Sk,t∑i=0n(ni)Q...

2020-04-07 15:55:12 235

原创【校内模拟】考试（生成函数）（牛顿恒等式）

简要题意：你有 nnn 个连续随机变量 xix_ixi，xix_ixi 在 [0,ai][0,a_i][0,ai] 中均匀随机，求 E((∑i=1nxi)m)E((\sum\limits_{i=1}^n x_i)^m)E((i=1∑nxi)m)。题解：考虑求定积分，然后二项式展开，式子很长不写了，最后发现是个卷积。我们需要求的是如下生成函数的第 mmm 项 ∏i=1n(eaix...

2020-04-07 15:28:23 422

原创【校内模拟】亲（二项式展开）（多项式快速幂）（快速插值）（MTT）

简要题意：你有一个数，初始为000，有 nnn 个机会，每个机会有 Q/(1+Q)Q/(1+Q)Q/(1+Q) 的概率使你的数 +1，请计算所有小于等于你的数的自然数的 kkk 次幂之和的期望。题解：设 fn,if_{n,i}fn,i 表示用了前 nnn 个机会，你的数的 iii 次幂的期望。转移考虑二项式展开，乘的东西不变，直接多项式快速幂。根据期望的线性性，由于 kkk 次幂之和...

2020-04-07 15:20:48 352

原创【校内模拟】羊（杜教筛）

求 ∑k=1n∑i=1k∑j=1kgcd(i,j,k)\sum_{k=1}^n\sum_{i=1}^k\sum_{j=1}^kgcd(i,j,k)k=1∑ni=1∑kj=1∑kgcd(i,j,k)题解：设 f(n)=∑i=1n∑j=1ngcd(i,j,n)f(n)=\sum_{i=1}^n\sum_{j=1}^ngcd(i,j,n)f(n)=∑i=1n∑j=1ngcd(i,j,n)...

2020-04-07 15:15:13 208

原创【题目泛做】道路（矩阵快速幂）（二项式展开）

简要题意：一张有向图，求 u−>vu->vu−>v所有长度不超过 kkk 的路径的长度 TTT 次方之和。n≤50,T≤50,k≤1e9n\leq 50,T\leq 50,k\leq 1e9n≤50,T≤50,k≤1e9。题解：暴力的思路是矩阵 AlA_lAl 表示长度为 lll 的 u−>vu->vu−>v 路径有多少条，然后矩阵乘法。正解也非常...

2020-04-03 20:08:59 615

原创【题目泛做】拆分（网络流）

CF 212A 数据范围放大版。题解：首先容易发现每个点的 minmax 差不会超过 111，且差为 111 当且仅当度数不是 ttt 的倍数。换言之，只要保证每个点 iii 分给 jjj 的都在 ⌊deg/t⌋\lfloor deg/t\rfloor⌊deg/t⌋ 和 ⌈deg/t⌉\lceil deg/t\rceil⌈deg/t⌉ 即可。证明考虑归纳即可。那么第一个思路就很显然了，考...

2020-04-03 20:01:51 196

空空如也

空空如也