- 博客(574)
- 收藏
- 关注
RSS订阅原创 脑部进食 - 高斯消元
题目大意：有一张n个点的有向图，每条边有个字符，一开始在1，每次随机一条出边走过去，这样经过的边上的字符会形成一个字符串。给你两个串s和t，问形成的字符串第一次包含s为子串或者包含t为子序列时，期望走了几次或者判断答案趋于无穷。n≤20,∣s∣≤10,∣t∣≤50n\le20,|s|\le10,|t|\le50n≤20,∣s∣≤10,∣t∣≤50题解：显然可以高消。注意到这个转移的图是个∣t∣+...
2019-06-11 16:04:17
498
原创 游戏 - 博弈论 - 结论
题目大意：你有两个序列{an}{bm}\{a_n\}\{b_m\}{an}{bm}，以及两个指针c,dc,dc,d，初始c=d=1c=d=1c=d=1。有两个人，每次每个人可以选择修改c和d中的恰好一个，或者结束游戏，结果是ac+bda_c+b_dac+bd。同一对(c,d)不能被访问100次。第一个人希望结果尽量小，第二个人希望结果尽量大，问最后结果是多少。题解：首先等价于每一对(c,...
2019-06-11 15:53:39
479
2
原创 标记的连接图 - dp
题目大意：对所有n个点的无向连通图求1到2的最短路并求和，n≤400n\le400n≤400。题解：首先转化为1到所有点都距离和，最后除以n-1。然后一个直接dp是直接分层，这样是四次的。一个做法是你倒着去分层，这样每次往前新增一层，后面所有点的距离+1。另一个做发是假定当前没加进去的距离都是当前层数+1，然后每次添加一些点，没有被添加的点距离+1。还有一个做法是直接维护……#inclu...
2019-06-11 15:31:09
369
原创 THUPC2019 & CTS2019 & APIO2019 游记
THUPC去之前勤学苦练了……端茶倒水。练习赛零贡献拿了本算导。正式赛_rqy和zyb疯狂带飞，鄙人只写了个J和L，然后那个L还被疯狂卡常，最后还是请zyb帮忙写了个松式基排。最后发现是rk2，感觉自己这个交了四五发的L是罪魁祸首，心态崩了，我对不起你们（哭）。CTSDay1很愉快的玩了很长时间的提答。那个T1做到最后差一步钦定偏序使其变成一个树，T2差的还远，T3最后交错点了摔。最后...
2019-05-21 18:33:09
877
原创 SDOI2019 R2D1T3 世界地图 - 最小生成树 - kruskal重构树 - 虚树
这题在场上只有我一个人过感觉非常蒙蔽这题不是送分吗（逃）听Claris说原本这个题打算是桥计数然后要类似虚仙人掌（瑟瑟发抖）总之考虑每次都是合并一个前缀和后缀，考虑类似于LCT维护MST的做法，每次加入一条边，形成环了的话就把环上最大边删掉。然后注意你每次只会加形如(m,i)−(1,i)(m,i)-(1,i)(m,i)−(1,i)（方便起见列在前）的边，因此以前缀为例，只有那些是第一列点某两点...
2019-05-09 10:46:35
712
原创 SDOI2019 Round2 游记
R1和R2之间又去了广州，然后最后得知myh两天rk1第一天AK成gd队长真心膜拜（正向奶成功（逃））R2前几天在家里通过看数竞（雾）想出了不少OI题（大雾）Day0抽签被分到了小房间，发现里面有当时省前十的一半多（貌似），感觉非常蒙蔽。晚上头疼，用宾馆的浴缸跑了个澡，好爽。Day1早上拿到题看T1，读成区间修改，还想那个单点修改意义何在，然后想了很久都不会（伏笔摔）看T2，想了会...
2019-05-08 21:20:11
988
1
原创 codechef Annual Parade - 费用流 - 二分
题目大意：总之就是要做最小路径覆盖，路径只要不是长度大于1的环就要额外支付C的代价。多次给出C求答案。n≤250,m≤30000,q≤104n\le250,m\le30000,q\le10^4n≤250,m≤30000,q≤104题解：考虑固定c怎么做。考虑无向图最小路径覆盖的过程，每次要么是合并两条路径，可以少支付一个C，要么形成一个环，也可以少支付一个C。因此就是最小路径覆盖每次增广收益是c...
2019-05-02 20:54:34
461
原创 LOJ 6494 LJJ 的字符串 - 后缀数组
题目大意：给一个串S，对S的所有前缀T求：对所有满足1≤i<j≤i+len−1<j+len−1≤∣T∣1\le i<j\le i+len-1<j+len-1\le|T|1≤i<j≤i+len−1<j+len−1≤∣T∣并且T[i…i+len−1]=T[j…j+len−1]T[i\dots i+len-1]=T[j\dots j+...
2019-05-02 20:48:40
464
原创 「NOI2016」优秀的拆分 - SAM
一类处理字符串相交的好东西。题目就是要对每个位置求一整个位置为结尾/开头的能写成SS的串的数量。除了一些麻烦的算法以外（比如在SAM上启发式合并之类的），一个简单的做法是枚举S的长度，不妨设为d，然后将原串每d个字符切开，发现SS这个串至少碰到两个缝隙，因此计算相邻两段的lcp/lcs就可以知道SS的结尾在某一段中合法的区间，然后用差分维护答案即可。#include<bits/stdc...
2019-05-02 20:41:42
427
原创 电梯 - dp - 单调队列
题目大意：总之就是有个dp[n]=mini=0n−1max{dp,p[i]}+maxj=i+1nt[j]\text{dp}[n]=\min_{i=0}^{n-1} \max \{\text{dp},\text p[i]\}+\max_{j=i+1}^{n}\text t[j]dp[n]=mini=0n−1max{dp,p[i]}+maxj=i+1nt[j]的dp，要做到线性求dp[n]\...
2019-05-02 20:33:08
297
原创 道路 - 矩阵乘法 - 倍增
题目大意：给定一张图GGG，求∑i=1kiTGi,T,∣G∣≤100,k≤109\sum_{i=1}^ki^TG^i,T,|G|\le100,k\le10^9∑i=1kiTGi,T,∣G∣≤100,k≤109题解：一些显然的做法是把那个幂次拆成斯特林数然后就是要求从路径上再选出若干条不同的边的方案数，这个就可以直接拿来倍增做到O(n^5lgk)了。考虑直接对这个倍增：ST(k)=∑i=1...
2019-05-02 20:21:41
535
原创 函树(hs) - 莫比乌斯反演 - 虚树
题目大意：给一颗树，求∑x,yφ(x×y)dist(x,y)\sum_{x,y}\varphi(x\times y)\text{dist}(x,y)∑x,yφ(x×y)dist(x,y)。n≤105n\le10^5n≤105题解：∑x,yφ(x×y)dist(x,y)=∑x,yφ(x)φ(y)gcd(x,y)φ(gcd(x,y))dist(x,y)=∑d=1ndφ(d)∑d∣x,d∣yφ...
2019-05-02 19:37:56
367
原创 Apple - 高斯消元 - 概率与期望
题目大意：有两个变量x,y初始为0，每次x=(x+1)%n或者y=(y+1)%m。问第一次变成x=X,y=Y时的期望步数。题解：显然直接列方程高消，可以将(n-1,m-1)看作0求(n-1-X,m-1-Y)的答案。注意到可以只设最后一行或者最后一行一列求解。不过后者好实现一点，所以场上写了这个。#include<bits/stdc++.h>#define rep(i,a,b) f...
2019-05-02 19:21:56
308
3
原创 重复子串(string) - SAM - 启发式合并 - 线段树
题目大意：给一个字符串多次询问一个子串s的权值。一个字符串的权值定义为最长的出现了至少两次的子串的长度。n,m≤105n,m\le10^5n,m≤105。题解：考虑把串反过来，建SAM。显然询问要先二分一波。那就是求对应下标在某个区间内的点是否存在两个点其LCA的val大于等于二分的值。考虑哪些点对有可能成为答案，显然如果有三个前缀下标a,b,c满足a<b<c（设ps(a)表示前...
2019-04-16 16:33:39
384
原创 密集子图(graph) - dp
题目大意：给一张有向完全图，每条边有一个出现概率p。问有多大的概率使得每个点离1号点的最短路不超过k。n≤12n\le12n≤12。题解：考虑设dp[i,s,t]表示最短路不超过i的点集是s，最短路恰好是i的点集是t，转移枚举下一层，发现可以预处理转移的代价这部分是O(4nn)O(4^nn)O(4nn)的。然后这题略卡空间，需要处理(s,t)−>s′(s,t)->s&...
2019-04-16 16:23:34
1682
原创 取石子 - 线段树
题目大意：有两个人，一开始分别有x和y个石子。两个人轮流操作n轮，第i轮从对面那里拿来a_i个石子，若不足则全拿。m次修改x或y或a_i然后问最后第一个人手上有几个石子。n,m≤5×105n,m\le5\times10^5n,m≤5×105题解：显然就是每次x加或者减一个数字对s取min对0取max。考虑分治，设solve(L,R,x)表示做完L,R的操作，x会变成多少。首先考虑(mid,...
2019-04-16 16:20:22
256
原创 子矩形 - 随机 - 二分
题目大意：给一个每个位置有点权的网格，求点权和除以周长最大的子矩阵。n≤500n\le500n≤500题解：考虑可以二分后做一个类似最大子矩阵的东西。然后发现枚举上下边界可以放到前面枚举，然后再二分，这样把上下边界的枚举随机打乱然后每次判一下是否有可能比当前答案优即可，这样复杂度就是O(n3)O(n^3)O(n3)了。#include<bits/stdc++.h>#defi...
2019-04-16 16:15:01
211
原创 发电机感觉！！！ - 组合数学 - 概率
题目大意：给你一段圆弧，对应弧度不小于32π\frac32\pi23π，然后在这个弧上随机选择n−1n-1n−1个点，求着n−1n-1n−1个点和弧的两端点形成的凸包包含圆心的概率。n≤107n\le10^7n≤107题解：考虑推式子……一种推法是把弧切均分成k段，然后求一个答案然后另k足够大取极限（其实就是求导），场上这么玩的。另一种方法就是仍然考虑计算不合法的，枚举哪一段大于π\piπ...
2019-04-16 16:10:53
758
1
原创 法 - 分类讨论
题目大意：给一张无向图求两两点间的最短路。m≤n+300,n≤105m\le n+300,n\le10^5m≤n+300,n≤105题解：考虑首先将度数为1的点删掉，每次删掉一个点就会影响这个点挂到的那个点出发的最短路次数。然后问题转为在一张所有点度数大于1的图上求两两点最短路，并且每条最短路都要乘以两端的次数。首先注意到∑d=2m⇒∑(d−2)=2(m−n)⇒∑[d>2]...
2019-04-16 16:01:49
304
原创 选数 - 容斥 - 分块 - FWT
题目大意：有n个数字，要求选出k个不同的数字使得异或和是s，对所有选择方案求gcd并求和。n≤106,ai,s≤m≤50000n\le10^6,a_i,s\le m\le50000n≤106,ai,s≤m≤50000题解：首先关于gcd可以容斥成∑i=1nf(i)ϕ(i)\sum_{i=1}^n f(i)\phi(i)∑i=1nf(i)ϕ(i)，f(i)f(i)f(i)表示选k个不同的数...
2019-04-16 15:46:42
273
原创 操作 - 分治NTT
题目大意：有n个操作和一个数字初始为0，每个操作形如有p的概率加a，1-p的概率乘b。现在随机打乱这个操作序列，问操作完数值的期望是多少。题解：每次就是让x变成kx+b。手玩一下发现答案就是：1n!∑i=1nbi∑j=0n−1j!(n−j−1)![xj]∏t=1n(x+kt)x+ki\frac1{n!}\sum_{i=1}^nb_i\sum_{j=0}^{n-1}j!(n-j-1)![x^...
2019-04-16 15:40:17
630
原创 SDOI2019 Round1 十二省联考游记
Day-1火车从北京来到济南（早上五点半就起了真惨）还有北京的地铁买票真麻烦，居然没有网络买票，还要先下载一个什么通行然后买票再取票……Day0不到七点就起来了，然后就是不知道怎么回事就过了一天……？（完全无有回忆）下午去报到的时候意外得知我校下一届居然有两名学妹参加省选？（大雾）Day1进场之后拿到题。看T1第一反应是两个log并且不知道k是干嘛的。看T2第一反应体面好长还是个...
2019-04-09 13:42:59
885
1
原创 反射弧(arcs) - 分块 - 哈希表
题目大意：n个点排成一行，每个点有一个颜色C。问有多少a<b<a′<b′a<b<a'<b'a<b<a′<b′，使得Ca=Ca′,Cb=Cb′,Ca!=CbC_a=C_{a'},C_b=C_{b'},C_a!=C_bCa=Ca...
2019-04-09 11:33:24
324
原创 异或和(xorsum)
题目大意：定义F({an})F(\{a_n\})F({an})为{an}\{a_n\}{an}的所有子序列的异或和的和。给定n,L,Rn,L,Rn,L,R，要求ai∈[L,R]a_i\in[L,R]ai∈[L,R]，求F({an})F(\{a_n\})F({an})有多少种可能的值。100000组数据，n≤100,L,R≤1018n\le100,L,R\le10^{18}n≤100,L,...
2019-04-09 11:28:55
4550
原创 路径(path) - 随机 - 树dp
题目大意：给一颗树，每个点有点权w。你可以选择一个不超过T的非负整数C，然后给所有点的点权+C，然后所有点的点权对P取模。这之后你要选择若干点不相交的链，假设链上的点权和S，选了k条，那么收益是Sk+1\frac{S}{k+1}k+1S。求最大收益。n≤5000,P≤105n\le5000,P\le10^5n≤5000,P≤105题解：考虑确定C之后可以二分然后dp。发现有用的C是O(n...
2019-04-09 11:15:23
248
原创 见面会EX - dp - 斜率优化 - 单调队列
题目大意：参考这篇blog，但是数据范围是1e7。题解：这题居然有线性做法是真的秀……就是这个题不能直接线性的原因是斜率优化没办法支持删除信息，因此需要用分治/线段树等来去掉删除。然后有一个黑科技：考虑将序列划分为若干段，使得不存在一个转移区间同时和至少三个段有交。划分方法是，由于转移区间端点是不降的，因此就是从左端点开始能向右就向右，可以发现这样划分是正确的。这样有什么好处呢？会发现...
2019-04-09 11:06:44
258
原创 Elephant - 平衡树 - 矩阵乘法
题目大意：设FM(k)F_M(k)FM(k)表示一张M个点的无向完全图从1走k步回到自己的方案数。给定序列{an}\{a_n\}{an}，支持：区间加，区间翻转，区间求FM(ai)F_M(a_i)FM(ai)的gcd\gcdgcd。其中M是固定的（输入的常数）。题解：通过观察发现gcd(FM(k1),FM(k2))=FM(gcd(k1−1,k2−1)+1)\gcd \left(F_...
2019-04-03 07:35:25
256
原创 Duck - 线段树优化建图 - 强连通分量
题目大意：给定n个区间[li,ri]，求一个排列p，元素x若满足至少有一个[lx,rx]中的元素y严格在x前面，就会获得vx的收益。问最大收益。n<=2e5.题解：考虑x向[lx,rx]连边，那么对于不同的强连通分量，总是能做到排在前面的强连通分量内的点全部获得收益；没有出边的强连通分量总是至少存在一个点没有办法获得收益，钦定是那个最小的点即可。线段树优化建图一下。#include<...
2019-04-03 07:29:30
183
原创 见面会 - dp - 斜率优化 - 李超线段树
题目大意：给你n个区间，你要划分成若干段，使得每段交非空，以及每段收益是C(长度，2)。求最大收益。题解：显然dp，斜率游化，然后发现每个点贡献的是一段区间，询问的横坐标就是下标，因此直接区间李超线段树即可。#include<bits/stdc++.h>#define rep(i,a,b) for(int i=a;i<=b;i++)#define Rep(i,v) rep...
2019-04-01 19:37:14
395
原创 家访 - 最短路 - 启发式合并 - 可并堆
题目大意：给一张图，但是有条边不能通过，但是只有到达那条边的端点之后才能知道这条边不能通过。求最坏情况下的最短路。题解：显然先求一个最短路树（到T的），那么只可能删树上的边（否则没有意义）。因此设ans[s]表示答案，不难发现ans[x]=max(min(ans[y]+w(x,y)),g[x])ans[x]=max(min(ans[y]+w(x,y)),g[x])ans[x]=max(min...
2019-04-01 19:33:44
251
原创 为时已晚，有机体 - 贪心 - 基环树
题目大意：给你内向基环树森林，一开始每个点都有个人，每秒所有人会沿着出边走一步，你可以在任意秒取走某个点的人（只能取一次），使得人数最多。现在你要修改尽量少的出边，使得最后你能取出最多的人，以及假设刚刚的答案是k，对每个t∈[0,k]t\in[0,k]t∈[0,k]求修改t条边后，你最多能拿到多少人。题解：第一问显然是联通快数或者减1。考虑第二问，假设现在在算ttt的答案。首先未必最后形成...
2019-04-01 19:22:48
4143
原创 farm - 容斥
题目大意：令F(a,b)F(a,b)F(a,b)表示是否存在一个点(x,y)(x,y)(x,y)使得其和(a,0),(0,b)(a,0),(0,b)(a,0),(0,b)围成的三角形面积是s。求∑a=1mF(a,n)+∑b=1nF(0,b)\sum_{a=1}^mF(a,n)+\sum_{b=1}^nF(0,b)∑a=1mF(a,n)+∑b=1nF(0,b)。1000组数据，n=n1n2n3n...
2019-03-19 16:16:47
402
原创 bipartite - LCT
题目大意：加边删边判定图是否是二分图。n<=1e5.题解：还是维护最大删除时间生成树，当加入一条边形成奇环的时候，将换上删除时间最小的边断开，并截止这个时间之前都不会是二分图。#include<bits/stdc++.h>#define rep(i,a,b) for(int i=a;i<=b;i++)#define mp make_pair#define fir ...
2019-03-19 16:07:14
220
原创 password - 乱搞
题目大意：有个数列{an}\{a_n\}{an}，告诉你{bn}，bk=∑i=1nai and ak\{b_n\}，b_k=\sum_{i=1}^na_i\text{ and }a_k{bn}，bk=∑i=1nai and ak，以及{cn}，ck=∑i=1nai or ak\{c_n\}，c_k=\sum_{i=1}^na_...
2019-03-19 16:04:11
189
原创 最近点 - 可持久化点分树 - 主席树
题目大意：给一棵树，点有黑白，每次形如翻转一个点颜色，询问到某个点的最近黑色点距离，以及返回之前某个版本。题解：显然将点分树可持久化一下，然后用一个可持久化堆（虽然写了个可持久化线段树）维护一下即可。点分树可持久化可以暴力拿个主席树维护点分树的点到堆的编号的映射，也可以将原树三度化之后直接可持久化，后者这部分复杂度一个log（但是并不很快）。#include<bits/stdc++.h&...
2019-03-19 15:59:52
495
原创 enos - 动态dp
题目大意：给一棵树，每个点有三种颜色，初始全为0,。若干次操作每次操作形如将x到y路径上的点颜色全部改为c，或者询问某个点所在的同色连通块大小。n,q≤105n,q\le10^5n,q≤105题解：显然可以动态dp……#include<bits/stdc++.h>#define rep(i,a,b) for(int i=a;i<=b;i++)using namespace...
2019-03-19 15:53:45
315
原创 Election Campaign - dp - 线段树合并
题目大意：有一颗树和m条链，每条链有个价值，你要选出若干两两点不相交的链使得选出来的链的价值之和最大。题解：显然dp，然后发现要维护的东西可以用一个线段树合并维护。#include<bits/stdc++.h>#define rep(i,a,b) for(int i=a;i<=b;i++)#define Rep(i,v) rep(i,0,(int)v.size()-1)...
2019-03-19 15:49:22
216
原创 密室逃脱 - dp
题目大意：有n个房间，i和i+1之间有扇门，能被打开当且仅当第i个房间有ai个人按下按钮或者第i+1个房间有bi个人按下按钮。门打开后人可以双向通过。按按钮的人不能移动，一旦放开按钮门就会关死。现在要求你在每个房间放一些人，使得放的总人数最多，并且不存在一种方案使得第1个房间有至少m个人。n<=1000,m,ai,bi<=10000；题解：神仙dp。考虑这个操作是可逆的。考虑最后...
2019-03-19 15:46:44
1091
原创 灯 - 分块
题目大意：有一列灯，每个灯有颜色。每次操作形如将某种颜色的灯全部点亮或者熄灭，问亮着的灯的段数。一开始全灭。n,q≤105n,q\le10^5n,q≤105。题解：显然先把相邻颜色相同的球扔掉，然后用点数减边数统计段数（连通块数），点数显然，考虑边数。转为一个对颜色建点的图，两点连边边权表示这两种颜色有多少灯是相邻的，那么边数是O(n)的。然后每次就是加入或者删除一个点求生成子图边权之和。显然...
2019-03-19 15:32:45
211
原创 时机成熟之时 - 概率与期望 - 组合计数
我终于知道min-max的期望形式为啥是对的了题目大意：有n个球，每次等概率的选一个球涂黑。假设T次后所有球都被涂黑了，求∑i=1Tik\sum_{i=1}^T i^k∑i=1Tik的期望。n,k≤100n,k\le100n,k≤100题解：这题有很多种推法，自己yy了这么一个：answer=∑i≥1P(i)∑k=1ijk=∑j≥1jk∑i≥jP(i)=∑j≥1jk(1−∑i=1j−1P(...
2019-03-19 15:23:34
457
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人