- 博客(203)
- 收藏
- 关注
RSS订阅
原创 LeetCode76 最小覆盖子串
给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入：S = “ADOBECODEBANC”, T = “ABC”输出：“BANC”提示：如果 S 中不存这样的子串，则返回空字符串 “”。如果 S 中存在这样的子串，我们保证它是唯一的答案。题解：滑动窗口就完事时间复杂度O（n*字符集大小）字符本来该是0-127然鹅，实测里面只有字母…于是开了58。。。用时 23 ms，内存消耗 38
2020-10-22 19:57:27
194
原创 LeetCode15 三数之和
题目描述给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]代码class Solution { public List<List<Integer>> three
2020-09-24 15:20:12
198
原创 整理一些别人的博客
Java中格式化输出数字：https://blog.csdn.net/qq_29778641/article/details/82226397
2019-10-12 15:36:11
299
原创 【Java学习笔记】字符串连接符“+”
public class Test3 { public static void main(String[] args) { String str = "12" + 3; System.out.println(str); }}public class Test3 { public static void main(String[] arg...
2019-10-12 14:57:37
323
原创 博客重新启动通知&博客搬家通知
RT不会告诉搬家地址的XD今后学习类和技术类文章发在这里，计划总结类发在新博客（别想着吃瓜了，感情问题是没有感情问题的( i_i )
2019-09-27 16:13:25
333
原创 7月8日总结
这几天太颓废了，写点东西约束一下自己。明天要拼上命赶Deadline了。关于“不做空心人”这句话，写来警醒自己，但似乎没有起到作用呢。知识或是说信息，的确是多到难以想象，走马观花地逛知乎刷网页，像磕了药一样爽。毫无意识地就在获取信息的快感中沉沦了，应该做的要紧事，规划的提升自我的事，与家人相处的时间都在无休止的屏幕毒品上浪费了。 还有无用社交，这点也是要提防的。课件准备好，预演排练。读书，知...
2019-07-08 23:45:09
232
原创 周总结
7.31-8.5 Daily Routine： 英语：练字15’ ；报纸两页 ；单词60个；听力30’ 语文：练字；翻译；Alltogether： 语文：百家5课；传记文言文4课；背《阿房宫赋》； 数学：《题型全归纳》P71-85，P232-P250 （在导数一章上卡了好久好久，没有完成一天10页的目标） 英语：(˚ ˃̣̣̥᷄⌓˂̣̣̥᷅ )（除了routine以外并没有做什么…...
2018-08-20 00:14:30
350
原创 北大暑期课堂散心指南&游记
日程&amp;amp;吐槽： Day0 晚上 开营仪式： 一点关于北大计科的介绍 （这些教授们应该副业开个单口相声） Day1 上午 讲座 下午 上机考试： 三个小时十道题，非常简单，大概在NOIP D1T1~T2的难度。 （我自己来说很久没动过键盘了所以打字相当慢仅仅A了八道） （直接在openjudge上开的比赛） （应该没有很重视这一块的成绩因为有大量没有OI基础的学生） ...
2018-07-30 03:22:17
1281
原创 ReHello to The Cruel World
Nice and beautify 37-day summer vacation .Do as much as I can. Go and catch it, the chance won’t come itself !No fun evening ike today’s anymore. Stay Hungry Stay Foolish. Whatsmore ,keep calm ...
2018-07-23 01:10:09
361
原创 线性规划与网络流24题 题解及部分代码以及小结
1.飞行员配对方案问题 最大匹配 2 太空飞行计划问题 之前写的详细题解 最大权闭合子图->最小割#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespac...
2018-02-11 20:44:32
638
原创 bzoj1061 [Noi2008]志愿者招募（网络流解决线性规划问题）
bzoj1061 [Noi2008]志愿者招募原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1061题意： 一个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。布布希望用尽量少的费用招募足够的志愿者，求最优的招募方案的费用。...
2018-02-10 17:04:37
880
原创 bzoj2521 [Shoi2010]最小生成树（网络流最小割）
bzoj2521 [Shoi2010]最小生成树原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=2521题意： 某一个图可能有多种不同的最小生成树。例如，下面图 3中所示的都是图 2中的无向图的最小生成树： Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一...
2018-02-10 16:54:00
573
原创 bzoj1834 [ZJOI2010]network 网络扩容（费用流）
bzoj1834 [ZJOI2010]network 网络扩容原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1834题意： 给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。 求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。数据...
2018-02-10 16:37:36
336
原创 bzoj2229 [Zjoi2011]最小割（分治+最小割树）
bzoj2229 [Zjoi2011]最小割原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=2229题意： T组数据。 每组数据给定一个n个节点的无向图，有若干个询问，每个询问给出x，询问图中有多少对点它们的最小割的容量不超过x，注意（p,q），(q，p）算相同的点对。数据范围 T<=10,n<=150,m&l...
2018-02-10 16:27:44
403
原创 2.9_总结
—————————————- 牢骚 ————————————————- 今天的测验依旧爆炸垫底。难过归难过，究其原因是时间分配有问题。 大概是被雅礼的题虐惯了，看到第一题就想跳，今天全程没有看第一题我都不知道自己怎么想的，结果第一题实际上非常简单，成了全场唯一没有做的人。 花费了三个小时，想去得第二题的40分，最后一个小时匆匆写了一三题的暴力，结果第二题打的40分的表cena收不上去，mmp...
2018-02-09 20:30:40
452
1
原创 LOJ2325「清华集训 2017」小Y和恐怖的奴隶主（期望概率+矩阵快速幂）
LOJ2325「清华集训 2017」小Y和恐怖的奴隶主原题地址：https://loj.ac/problem/2325题意："A fight? Count me in!" 要打架了，算我一个。"Everyone, get in here!" 所有人，都过来！小Y是一个喜欢玩游戏的OIer。一天，她正在玩一款游戏，要打一个Boss。虽然这个Boss有1010010100 ...
2018-02-08 22:17:29
852
原创 CodeForces 696D Legen...（AC自动机+矩阵快速幂）
CodeForces 696D Legen…原题地址：http://codeforces.com/problemset/problem/696/D题意： Barney爱上了Nora 想发给她一段长为ll的话（一个由小写字母组成的串）让她开心一下。 Nora有n个喜欢的话（例如 I’m falling for you 这种情话。当然，给出的都是由小写字母组成的串），每个串ii有一个开心值aia_i
2018-02-06 17:03:14
413
原创 bzoj1444 [Jsoi2009]有趣的游戏（期望概率+AC自动机+高斯消元）
bzoj1444 [Jsoi2009]有趣的游戏原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3881题意： 数据范围 n , l, m≤ 10，0题解： Sengxian大佬的题解一个好想又好写的思路是直接算T=∞时，不能出现某个序列的概率， 就是补全AC自动机那个无向图的邻接矩阵，把可以转移到该串尾节点及包
2018-02-06 14:57:36
509
原创 bzoj4231 回忆树（AC自动机+fail树+KMP(+树状数组)）
bzoj4231 回忆树原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3881题意： 回忆树是树。 具体来说，是n个点n-1条边的无向连通图，点标号为1~n，每条边上有一个字符（出于简化目的，我们认为只有小写字母）。 对一棵回忆树来说，回忆当然是少不了的。 一次回忆是这样的：你想起过往，触及心底…唔,不对，我们要说题目。
2018-02-06 08:41:47
955
原创 bzoj3881 [Coci2015]Divljak（AC自动机+fail树+dfs序+树状数组+树链剖分）
bzoj3881 [Coci2015]Divljak原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3881题意： Alice有n个字符串S1,S2...Sn" role="presentation" style="position: relative;">S1,S2...SnS1,S2...SnS_1,S_2...S_n，Bob
2018-02-05 17:14:34
962
原创 bzoj2938 [Poi2000]病毒（AC自动机+DFS找环）
bzoj2938 [Poi2000]病毒原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=2938题意： 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
2018-02-05 16:54:39
302
原创 CodeForces 528D Fuzzy Search（FFT）
CodeForces 528D Fuzzy Search原题地址：http://codeforces.com/problemset/problem/528/D题意： 给给定两个字符串 S，T（字符集大小为4：A ,G ,C ,T），给定阀值 k， 定义T串在S串某位置匹配，当且仅当T串任意位置的这个字符所对应的母串的位置的左右k个字符之内至少有一个与这个字符相同的。 求T串在S串中的匹配次数。
2018-02-05 16:48:18
531
原创 bzoj4503 两个串（FFT好题）
bzoj4503 两个串 原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=4503题意： 兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次， 分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。数据范围 S 长度不超过 10^5， T 长度不会超过 S。 S 中只包含小写字母
2018-02-04 22:28:51
325
原创 bzoj3451 Tyvj1953 Normal（期望概率+点分治+FFT）
bzoj3451 Tyvj1953 Normal原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3451题意： 某天WJMZBMR学习了一个神奇的算法：树的点分治！ 这个算法的核心是这样的： 消耗时间=0 Solve(树 a) 消耗时间 += a 的 大小 如果 a 中 只有 1 个点 退出 否则在a中选一
2018-02-04 17:38:01
443
原创 ZOJ3874 Permutation Graph（DP+分治NTT）
ZOJ3874 Permutation Graph原题地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5482题意： 多组数据。 对于一个排列{a1，a2，… an}，如果他把每一对（ai，aj）满足 iaj（即逆序对）连接起来，会得到一张图。 例如，如果排列是{2,3,1,4}，则1和2连接，1和3连接。
2018-02-04 13:52:05
584
原创 bzoj3456 城市规划（分治NTT）
bzoj3456 城市规划原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3456题意： 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是
2018-02-04 09:09:00
752
原创 bzoj3992 [SDOI2015]序列统计（NTT快速幂）
bzoj3992 [SDOI2015]序列统计原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3992 题意： 小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。 小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，
2018-02-03 07:40:34
338
原创 HDU5307 He is Flying（FFT）
HDU5307 He is Flying原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=5307题意： 给定n个非负整数a1...an" role="presentation" style="position: relative;">a1...ana1...ana_1...a_n,对所有0≤S≤∑ai
2018-02-01 21:38:20
399
原创 bzoj3160 万径人踪灭（manacher+FFT）
bzoj3160 万径人踪灭原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3622题意： 给定一个长度为N且只有a,b的字符串，问有多少种方案从中选取一个子序列，使得： 1.位置和字符都关于某条对称轴对称。 2.不能是连续的一段。 数据范围 n题解： 首先求不连续的，就先求所有的，再用manacher求连续
2018-02-01 20:51:12
370
原创 bzoj3622 已经没有什么好害怕的了（容斥原理+DP+二项式反演）
bzoj3622 已经没有什么好害怕的了原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3622题意： 数据范围 1≤ n ≤ 2000,0 ≤ k ≤ n题解： 首先k+n" role="presentation" style="position: relative;">k+nk+nk+n不是偶数就无解了，让k=(
2018-01-31 14:58:23
513
原创 二项式反演证明
式一、 an=∑i=0n(ni)bi⇒bn=∑i=0n(−1)n−i(ni)aian=∑i=0n(ni)bi⇒bn=∑i=0n(−1)n−i(ni)aia_n=\sum\limits_{i=0}^n{n\choose i}b_i \Rightarrow b_n=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}a_i证明：  ...
2018-01-31 11:48:41
890
1
原创 bzoj4671 异或图（容斥原理 + 第二类斯特林数 + 高斯消元）
bzoj4671 异或图原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=4671题意： 定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中。 现在给定 s 个结点数相同的图 G1…s, ...
2018-01-31 09:01:22
560
原创 CDOJ1544 [“玲珑杯” 线上赛Round #17 B] 当咸鱼也要按照基本法（容斥原理 凑系数）
CDOJ1544 [“玲珑杯” 线上赛Round #17 B] 当咸鱼也要按照基本法原题地址： http://acm.uestc.edu.cn/#/problem/show/1544 http://www.ifrog.cc/acm/problem/1138题意： zhu有N条咸鱼（标号从1到N），每条咸鱼都有一个咸鱼值Ki，初始时所有Ki都是0. zhu有M个咸数，对于每个咸数x，
2018-01-30 22:36:53
827
原创 bzoj4455&UOJ185 [Zjoi2016]小星星（树形DP+容斥原理）
bzoj4455&UOJ185 [Zjoi2016]小星星原题地址： http://www.lydsy.com/JudgeOnline/problem.php?id=4455 http://uoj.ac/problem/185题意： 给你一个n 个点m 条边的无向图， 再给你一棵n 个点的树， 问有多少种点编号的映射方式， 使得n 个点恰好匹配，且树上的边均存在于原图中。数据范围
2018-01-30 14:07:47
836
原创 bzoj4727 [POI2017]Turysta（竞赛图构造哈密顿回路）
bzoj4727 [POI2017]Turysta原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=4727题意： 给出一个n个点的有向图，任意两个点之间有且仅一条有向边。对于每个点v，求出从v出发的一条经过点数最多， 且没有重复经过同一个点两次以上的简单路径。输入第一行包含一个正整数n(2<=n<=2000)，表示点数。接下来n-1行，其
2018-01-23 23:41:47
1546
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人