3 Mys_C_K

尚未进行身份认证

人生有许多道:曾经踏足的是道,即将踏往的也是道,那什么才是道呢?唯有脚下走的才是道。一切精神或者物质都归于虚无,然后从混沌中衍生出三万道。在悲喜间涉足一条无数前人经历过,且将有无数后人奔赴的道,无论是否已经或者将要到达彼岸,然后便不再回头或是左顾右盼,即使有些道繁盛至极,夜灯如昼,无数人一浪又一浪的涌去,造就了世人皆知的辉煌;即使有些道草木凋敝,荒草丛生,只等勇敢的开拓者斩开荆棘,创造一片天地;这些都无所关,无所在意,彼岸何如、来日何方甚至过往旧事都化作一缕云烟,飘渺碧霄,我自撷高山之月色,独随足落处往行。

等级
TA的排名 9k+

脑部进食 - 高斯消元

题目大意:有一张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

游戏 - 博弈论 - 结论

题目大意:你有两个序列{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

标记的连接图 - dp

题目大意:对所有n个点的无向连通图求1到2的最短路并求和,n≤400n\le400n≤400。题解:首先转化为1到所有点都距离和,最后除以n-1。然后一个直接dp是直接分层,这样是四次的。一个做法是你倒着去分层,这样每次往前新增一层,后面所有点的距离+1。另一个做发是假定当前没加进去的距离都是当前层数+1,然后每次添加一些点,没有被添加的点距离+1。还有一个做法是直接维护……#inclu...

2019-06-11 15:31:09

THUPC2019 & CTS2019 & APIO2019 游记

THUPC去之前勤学苦练了……端茶倒水。练习赛零贡献拿了本算导。正式赛_rqy和zyb疯狂带飞,鄙人只写了个J和L,然后那个L还被疯狂卡常,最后还是请zyb帮忙写了个松式基排。最后发现是rk2,感觉自己这个交了四五发的L是罪魁祸首,心态崩了,我对不起你们(哭)。CTSDay1很愉快的玩了很长时间的提答。那个T1做到最后差一步钦定偏序使其变成一个树,T2差的还远,T3最后交错点了摔。最后...

2019-05-21 18:33:09

SDOI2019 R2D1T3 世界地图 - 最小生成树 - kruskal重构树 - 虚树

这题在场上只有我一个人过感觉非常蒙蔽这题不是送分吗(逃)听Claris说原本这个题打算是桥计数然后要类似虚仙人掌(瑟瑟发抖)总之考虑每次都是合并一个前缀和后缀,考虑类似于LCT维护MST的做法,每次加入一条边,形成环了的话就把环上最大边删掉。然后注意你每次只会加形如(m,i)−(1,i)(m,i)-(1,i)(m,i)−(1,i)(方便起见列在前)的边,因此以前缀为例,只有那些是第一列点某两点...

2019-05-09 10:46:35

SDOI2019 Round2 游记

R1和R2之间又去了广州,然后最后得知myh两天rk1第一天AK成gd队长真心膜拜(正向奶成功(逃))R2前几天在家里通过看数竞(雾)想出了不少OI题(大雾)Day0抽签被分到了小房间,发现里面有当时省前十的一半多(貌似),感觉非常蒙蔽。晚上头疼,用宾馆的浴缸跑了个澡,好爽。Day1早上拿到题看T1,读成区间修改,还想那个单点修改意义何在,然后想了很久都不会(伏笔摔)看T2,想了会...

2019-05-08 21:20:11

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

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

「NOI2016」优秀的拆分 - SAM

一类处理字符串相交的好东西。题目就是要对每个位置求一整个位置为结尾/开头的能写成SS的串的数量。除了一些麻烦的算法以外(比如在SAM上启发式合并之类的),一个简单的做法是枚举S的长度,不妨设为d,然后将原串每d个字符切开,发现SS这个串至少碰到两个缝隙,因此计算相邻两段的lcp/lcs就可以知道SS的结尾在某一段中合法的区间,然后用差分维护答案即可。#include<bits/stdc...

2019-05-02 20:41:42

电梯 - dp - 单调队列

题目大意:总之就是有个dp[n]=min⁡i=0n−1max⁡{dp,p[i]}+max⁡j=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−1​max{dp,p[i]}+maxj=i+1n​t[j]的dp,要做到线性求dp[n]\...

2019-05-02 20:33:08

道路 - 矩阵乘法 - 倍增

题目大意:给定一张图GGG,求∑i=1kiTGi,T,∣G∣≤100,k≤109\sum_{i=1}^ki^TG^i,T,|G|\le100,k\le10^9∑i=1k​iTGi,T,∣G∣≤100,k≤109题解:一些显然的做法是把那个幂次拆成斯特林数然后就是要求从路径上再选出若干条不同的边的方案数,这个就可以直接拿来倍增做到O(n^5lgk)了。考虑直接对这个倍增:ST(k)=∑i=1...

2019-05-02 20:21:41

函树(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

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

重复子串(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

密集子图(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

取石子 - 线段树

题目大意:有两个人,一开始分别有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

子矩形 - 随机 - 二分

题目大意:给一个每个位置有点权的网格,求点权和除以周长最大的子矩阵。n≤500n\le500n≤500题解:考虑可以二分后做一个类似最大子矩阵的东西。然后发现枚举上下边界可以放到前面枚举,然后再二分,这样把上下边界的枚举随机打乱然后每次判一下是否有可能比当前答案优即可,这样复杂度就是O(n3)O(n^3)O(n3)了。#include<bits/stdc++.h>#defi...

2019-04-16 16:15:01

发电机感觉!!! - 组合数学 - 概率

题目大意:给你一段圆弧,对应弧度不小于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

法 - 分类讨论

题目大意:给一张无向图求两两点间的最短路。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

选数 - 容斥 - 分块 - 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=1n​f(i)ϕ(i),f(i)f(i)f(i)表示选k个不同的数...

2019-04-16 15:46:42

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。