首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
zxp扶摇直上九万里
获赞
18
粉丝
8
关注
9
看过 TA
12
湖南省醴陵第一中学
2023
算法工程师
IP属地:上海
我不怕千万人阻挡,只怕自己投降
私信
关注
拉黑
举报
举报
确定要拉黑zxp扶摇直上九万里吗?
发布(75)
刷题
zxp扶摇直上九万里
2020-01-02 12:51
算法工程师
[ZJOI2014]力 题解
题目地址 洛谷P3338 Solution 第一道FFT的应用AC祭! 我们要求: ( 直接在除法的时候消掉了qwq) Step 0 卷积是什么? 首先我们要有明确的目标,我们要把上面的式子推成卷积的形式,我们就要来回顾一下卷积是什么。卷积的形式如下: Step 1 直接推式子 有了目标,我们就好来推式子了(推式子真好玩),下面给出推理的重要步骤,尽量没有繁琐的步骤,读者可以自己思考一下。 改变一下 的上下标表示形式,原式变成 如果 也累加进去,对答案不影响,所以式子变成 Step 2 转化 设 ,所以原式变成 令 ,则原式变成 这时我们发现,左边已经是一个卷积的形式,...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:49
算法工程师
Educational Codeforces Round 77 比赛总结
比赛情况 我太菜了 A题 加减乘除不会 B题 二元一次方程不会 C题 gcd不会 就会一个D题二分答案大水题,本来想比赛最后一分钟来一个绝杀,结果 Wrong Answer on test 4 比赛总结 问题1:有点读不懂题目。 解决方法:读题目后如果发现没有看懂,再多读几遍样例,看看样例的解释,大概就懂了。(如果再读不懂就得锻炼自己的阅读理解了) 问题2:花了点时间想了个假题。 解决方法:其实就是没有看懂题目,和问题1一样的方法去解决。 问题3:卡在一个题动不了。导致后面会做的题没去做。 解决方法:因为有些知识点确实不太擅长,比如我在C题想了20min假题,又想了30...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:48
算法工程师
矩阵 总结
前言 矩阵是一种较为基础的数学工具,OI里面好像不常考?,反正学完数学一本通里的矩阵,做一些矩阵的应用感觉就应该可以了。行列式也是很有趣的东西,我花时间钻研了一下。下面归纳总结一下我做过的一些矩阵的题型 如果定义这种不会请百度吧 -> 百度矩阵 矩阵乘法 矩阵里面最主要的一种。下面是矩阵乘法的一些题。 矩阵快速幂 P3390模板题 基础。 矩阵加速递推数列 P1939模板题 加速加法递推直接设状态转移矩阵就好了。 石头游戏 其实想清楚了石头要从一个格子转移到另一个格子,就可联想到用矩阵来表示格子与格子间的的转移。码量有点大。 Codeforces 1182E Product Or...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:47
算法工程师
算法竞赛进阶指南 学习笔记
目标 && 前言 近期的目标就是刷《算法竞赛——进阶指南》这本书 先花两三天左右把 0x00 基本算法 刷完,好的题目我录下来。 用一两天快速地把 0x10 基本数据结构 刷完,因为比较简单。好的题目录下来。 0x20 搜索 先放在这边,因为我觉得搜索比较毒瘤,过了初赛再刷搜索,顺便提高代码能力。 0x30 数学知识 数学我不太擅长,先留着 0x40 数据结构进阶 马上就要开学了,这个看看一周到一周半的时间能不能刷完,好的题目我会录下来。 0x50 动态规划 刷完上面这个就要赶紧刷下面这个,两周到三周,重难点,好的题录下。 0x60 图论 两到三周 刷完这里水平应...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:46
算法工程师
动态规划学习
动态规划学习 前言 以前我也算是接触过一点DP,陆陆续续学了一些背包问题,线性动规和区间动规。现在我再次发现了动规的重要性,决定在暑假里专门刷一些动规题。这篇blog主要记录我刷过的一些DP题。 引用 _皎月半撒花 大佬的一段话 动态规划自古以来是凌虐萌新的分水岭,但有些认为并没有这么重要——会打暴力,大不了记忆化。但是其实,动态规划学得好不好,可以彰显出一个的基本素养——能否富有逻辑地思考一些问题,以及更重要的——能否将数学、算筹学(决策学)、数据结构合并成一个整体并且将其合理运用。 推荐 (大佬的blog) <什么是动态规划> —— by知乎大佬 <入门DP总结&...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:45
算法工程师
牛客OI周赛13-提高组 比赛总结
比赛情况 1h才写出T1 100pts + T2 50pts(都是简单dp可还行)。然后就去颓废了。颓废完来康康T3的暴力,wow,T3咋这么难呢!?期望概率好像不太会了,退了吧qwq。 所以最后 100+50+0=150pts, rank 22。 比赛总结 说实话比赛前还有些紧张呢,但是我这次吸取了经验,牢记dalao之前对我讲的,“花2h肝T1,T2是值得的。”(CSP-S就是因为花2h+肝T3暴力,让我留下了终身的遗憾),于是安心写T1,T2,稳扎稳打拿下150pts 在这次比赛学到了一个简单的树状数组优化dp。 T1 0还是1 定义 f[i,0/1] 表示使用完前 i ...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:44
算法工程师
Codeforces Round #605 (Div. 3) 比赛总结
比赛情况 2h才刀了A,B,C,D。E题的套路做的少,不过ygt大佬给我讲完思路后赛后2min就AC了这题。 比赛总结 比赛时不用担心“时间短,要做多快”,这样会匆匆忙忙,反而会做得慢。比赛时应该要不紧不慢,理性思考,内心平静,题目反而会迎刃而解。 这次比赛又看错了题(B,D)。 解决办法:这次比赛看错题是因为不够细心,不够细心是因为急躁,怕做不完。所以沉稳冷静的分析,反而能更好地完成比赛。 那么就开始上题解吧! A cf常出的分类讨论题(OI好像不考?)。 如果三个人的位置互不相同,我们希望最左和最右的两个人尽量靠近,中间这个人走不走没有影响。 如果有两个人位置相同,问题就转化为...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:44
算法工程师
Codeforces Round #606 Div. 2 比赛总结
比赛情况 bq. A题 Wrong Answer on test 2 , E题sb题没切。bqbqbq. 比赛总结 bq. 那就直接上题解吧!^-^ A 数位dp,分类讨论,注意细节。 Talk is cheap.Show me the code. #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); ...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:43
算法工程师
[算进] 双端队列 题解
Problem ACwing 题目地址 Solution 好题,代码短,思维性强,细节多。 我们应该推导出以下两条性质: 让我们来手玩一下样例,样例排序后应该是这样子的:0 3 3 6 6 9,其中相同的数在排序后的序列是连续的一段,而双端队列中元素应该是序列中连续的一段。(并没有用) 双端队列添加元素,先是添加一个到中间,再是往两边插入数字,假设双端队列中一段元素分别是 ,且 是第一个加入的元素。记 表示这个元素在原序列中的下标,那么就有 。(这个性质就很重要了) 考虑一个双端队列,用函数 来形象的表示这个数列的特征(当然这个函数是离散的,为了形象,将他连续),函数的图像如下...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 12:42
算法工程师
[算进] 数据备份
Problem Luogu 题目地址 ACwing 题目地址 Sulotion 代码短,思维强,实现妙(就算猜出性质也不一定会实现),神仙题啊,科科(我太菜了而已)。 首先有一个显然的性质:选出来的这 对点一定相邻。 根据这个性质,我们做第一步问题转换:记两个点 和 之间的距离为 ,那么我们就得到一个长度为 的数组 ,我们要在 中选出 个数,并且这 个数两两不能相邻。 (做到这里就不会了是吧?)既然没有什么头绪,我们就从 的情况逐步推起,考虑像 [算进]序列 (就是上一题,虽然这两题看起来毫无联系的样子)一样用数学归纳法解决问题。 显然我们要选 ,并且记这个数为 ...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 13:06
已编辑
算法工程师
[算进] 数据备份
Problem Luogu 题目地址 ACwing 题目地址 Sulotion 代码短,思维强,实现妙(就算猜出性质也不一定会实现),神仙题啊,科科(我太菜了而已)。 首先有一个显然的性质:选出来的这 \(k\) 对点一定相邻。 根据这个性质,我们做第一步问题转换:记两个点 \(i\) 和 \(i+1\) 之间的距离为 \(D_i\),那么我们就得到一个长度为 \(n-1\) 的数组 \(D\),我们要在 \(D\) 中选出 \(k\) 个数,并且这 \(k\) 个数两两不能相邻。 (做到这里就不会了是吧?)既然没有什么头绪,我们就从 \(k=1\) 的情况逐步...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 13:06
已编辑
算法工程师
[算进] 双端队列 题解
Problem ACwing 题目地址 Solution 好题,代码短,思维性强,细节多。 我们应该推导出以下两条性质: 让我们来手玩一下样例,样例排序后应该是这样子的:0 3 3 6 6 9,其中相同的数在排序后的序列是连续的一段,而双端队列中元素应该是序列中连续的一段。(并没有用) 双端队列添加元素,先是添加一个到中间,再是往两边插入数字,假设双端队列中一段元素分别是 \(x_1,x_2...x_n\) ,且 \(x_m\) 是第一个加入的元素。记 \(ID(x_i)\) 表示这个元素在原序列中的下标,那么就有 \(ID(x_1)>ID(x_2)>...&g...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 13:08
已编辑
算法工程师
[算进] 蚯蚓 题解
Problem 洛谷P2827 题目地址 Solution 直接用优先队列模拟可以得到不少的分数,时间复杂度 \(O(m \log m),m<=7*10^6\) ,但是并不能通过此题,我们要考虑挖掘一些性质优化时间复杂度。 假设现在有两条蚯蚓,长度分别记为 \(x_1,x_2\),且满足 \(x_1>=x_2\)。 令 \(l_1\) 表示 \(x1\) 切掉后 \(\lfloor px_1 \rfloor\) 这部分(left左边),\(r_1\) 表示切掉后 \(x_1 - \lfloor px_1 \rfloor\) 这部分(right右边),\(l_2,r_2\)...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 13:08
已编辑
算法工程师
[算进] 赶牛入圈 题解
Problem ACwing 题目地址 Solution 低级套路题。 二分边长,二维离散化前缀和预处理,贪心双指针判定即可。 时间复杂度 \(O(n^2 \log n)\),因为离散化了,\(n<=500\) Code Talk is cheap.Show me the code. #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(...
0
点赞
评论
收藏
转发
zxp扶摇直上九万里
2020-01-02 13:08
已编辑
算法工程师
[算进] 防线 题解
题目地址 ACwing题目地址 Solution 套路题。不会做只是我没见过这个套路而已 突破口: 但是整条防线上也最多只有一个位置有奇数个防具 我们知道一个原理 :偶+偶=偶,奇+偶=奇。 又因为我们可以快速算出一个前缀和,比如说算出 \(x\) 之前有多少个防具,(用等差数列的一些公式快速\(O(1)\)算出,因为有 \(n\) 个等差数列所以算一次前缀和的的时间是 \(O(n)\))。记 \(x\) 的前缀和为 \(S(x)\) 我们又发现如果答案(奇数)在 \(p\) 这个位置,\(\forall x \in [0,p)\) \(S(x)\) 都是偶数,而 \(\fora...
0
点赞
评论
收藏
转发
1
2
3
4
5
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务