- 博客(37)
- 收藏
- 关注
RSS订阅原创 C语言里面数组，指针，结构体的一些见解
C语言里面数组，指针，结构体的一些见解1. 数组1.1 数组概念在c语言里面有数组这个概念， 就像传统的int a[5], char c[10] 其中a和c都为数组(a为int类型的数组, c为char类型的数组)， 数组和普通变量的区别就在于，他是一段连续的区域，在虚拟地址上是连续的，我们可以通过下标其中任意一个元素，第i个元素的地址为a0 + (i-1)*sizeof(T)(其中a0为数组收地址，T为数组的类型)。2. 指针2.1 指针概念c语言里面有指针这个概念，这也是c语言本身很重要的一
2020-08-05 09:59:48
497
原创 EIGENVECTORS FROM EIGENVALUES的一些看法
EIGENVECTORS FROM EIGENVALUES论文的一些小看法从特征值到特征向量,一种新的求解特征向量的方法. 由三位物理大佬 PETER B. DENTON, STEPHEN J. PARKE, XINING ZHANG共同发现, 由我们家喻户晓的大佬陶哲轩真神证明的.论文链接:https://arxiv.org/abs/1908.03795?context=math.RA...
2019-11-16 00:44:41
362
原创 数学建模感想篇
数学建模篇大三狗，一共参加了2次国赛，2次美赛。一次国赛省一，一次国赛国一。两次美赛都是h(qaq太菜了)。首先谈谈数学建模这个比赛吧。现在的数学建模竞赛有很多，由于笔者所在的学校只组织参加国赛和美赛，对于其他的数学建模竞赛不了解。国赛是每年9月份，大概开学的后两周那会，笔者所在的学校每年暑假都会有培训(感觉热成狗，而且作用还不是很大，遭罪啊)。美赛一般在寒假快接近春节的时候(这日子也是挺tm...
2019-04-19 12:12:38
6932
12
原创 环上最大连续和
环上最大连续和给定N,K以及一个环：A[1],A[2],A[3],…A[N]，其中A[1]的左边是A[N]。求该环上最大的连续子段和，要求选出的子段长度不超过K。输入描述：第一行两个整数N和K。接下来一行，N个整数表示A[i]。输出描述:输出题目要求的最大连续和。链接:https://www.nowcoder.com/questionTerminal/8db855bdae...
2019-04-12 18:28:41
335
原创 递推
递推玩了几天的组合排列之后，今天来玩玩递推吧。所谓递推，其实就是建立关系表达式，也就是建立两个式子之间的关系。上道题:https://nanti.jisuanke.com/t/36677解析这道题，首先直接正解，发现贼麻烦，根本做不出来(我tm就没见过可以正解求出来的)。那么我们要尝试找关系了。要求期望，首先我们得知道分母是什么，分母是就是1−n1-n1−n的可能存在的序列。分子就是这些序...
2019-03-20 14:51:52
892
原创 Mind control
组合一道组合数学题，做得很蛋疼，仿佛回到了高中数竞的生活(qaq), 链接http://acm.fzu.edu.cn/problem.php?pid=2303解析题目的意思很简单，把m个cake分给n个person, 每个person最多能拿一个cake, 然后这些person是有继承关系的，即这个人拿到蛋糕后，你能得到的信任是这个人以及它所有的子结点的值，求你能得到的值的期望。显然，当m...
2019-03-18 09:29:51
333
原创 Chosen by god
组合一道组合数学题，链接http://acm.fzu.edu.cn/problem.php?pid=2301解析题目的意思对方有两只怪物，一只血量为mmm, 另一只血量为无穷。游戏共nnn个回合，每个回合会随机地选择对方的一只怪物进行攻击，问在nnn回合内打死那只血量为mmm的概率为多大。 因为是nnn回合，每次攻击都有两种可能性，所以总的方案数为2n2^n2n，因为怪物的血量为mmm，所...
2019-03-18 08:58:22
332
原创 数论-GCD
数论-GCD数论只会gcd的弱渣今天做了道和gcd有关的题，分享一下:https://nanti.jisuanke.com/t/36675解析根据n≤5000000n \leq 5000000n≤5000000, 显然两两求gcdgcdgcd是不现实的，那么该怎么办呢？对于gcd(a,b)=cgcd(a,b)=cgcd(a,b)=c, 我们知道c是a,b的约数。那么要求最大的约数，我们可以...
2019-03-17 11:53:06
271
原创 割点与桥
割点与桥在前面已经学习了Tarjan算法的基础上，今天我们来学习下与之相关的两个很重要的东西-割点与桥.我们本次主要讨论的是无向图中的割点与桥。在无向图中割点的定义为:在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。桥的定义为:在一个无向图中，如果有一个边集合，删除这条边之后，图的连通分量增多，就称这个...
2019-03-14 18:19:36
322
原创 Tarjan算法
Tarjan算法Tarjan算法是一个很著名的算法，其主要的目的是用来求有向图的强连通分量，什么是强连通分量呢？ 简单点说就是存在一个点v1v_1v1能到点v2v_2v2，且v2v_2v2也能到v1v_1v1，那么v1,v2v_1, v_2v1,v2就构成一个强连通分量; 具体的定义参见百度。Tarjan算法步骤Tarjan算法采用的深度优先遍历的方式(DFS)，需要两个数组df...
2019-03-14 16:37:39
1203
4
原创 费马小定理
费马小定理费马是个很出名的大佬，比较熟悉就是费马大定理。今天我们来谈谈费马的小定理。这是数论里面一个非常重要的定理，在高中的数学联赛或者是信息学竞赛，以及大学的ACM竞赛都是很重要的一个定理。那么今天就来科普一下吧。定理讲诉费马小定理是这样的，对于整数aaa，和质数ppp，如果aaa与ppp互质，那么有ap−1≡1(modp)a^{p-1} \equiv1(mod p)ap−1≡1(modp...
2019-03-08 13:51:24
980
原创 线段树
线段树，是一种可以在O(logn)O(logn)O(logn)复杂度内维护区间操作的数据结构，它可以用于维护区间和，区间更新以及单点更新等等，使用起来也是非常灵活的。关于线段树的信息可以自己百度一下。我们先来看题。传送门:https://nanti.jisuanke.com/t/A2007这道题要我们维护的是区间和，但这个区间和是带权的。它同时也要支持单点的更新。为了实现这一操作，我们首先...
2019-03-08 12:22:15
91
原创 AVL-tree
AVL树昨天谈了堆，那么今天来谈下AVL树，它也是一种二叉树，而且是平衡的二叉树，对于点的插入和删除以及查找的复杂度都是O(logn)O(logn)O(logn)，可以说非常高效有用。简介:https://baike.baidu.com/item/AVL树/10986648AVL的简单介绍可以参考百度，也可以自己找本数据结构的书来看，一般里面都会提到这个数据结构。这个数据的出现是为了弥补不...
2019-03-07 12:01:08
123
原创 堆
堆这几天准备把三种比较重要的数据结构整理下，分别是堆，AVL树，红黑树。今天谈谈堆吧。简介:https://baike.baidu.com/item/堆/20606834?fr=aladdin简单的介绍百度百科上就有，他是一种二叉树形式的数据结构，主要是用来维护数据中的最小和最大值，且插入和删除操作的复杂度都为O(logn)O(logn)O(logn). 二叉树相信大家都知道吧(不知道的...
2019-03-06 14:37:54
107
原创 字母交换
字母交换传送门:https://www.nowcoder.com/practice/8da0ea4b4853464795f5c32634a1b06f?tpId=90&tqId=30817&tPage=3&rp=3&ru=/ta/2018test&qru=/ta/2018test/question-ranking这个是字节跳动的笔试题，感觉难度挺大的，用...
2019-03-05 19:13:00
522
原创 dp
dp又是动态规划，这是字节跳动校招的一道附加题-传送门:https://www.nowcoder.com/practice/58b04ed2865f4ff4921290f1bd4ee486?tpId=90&tqId=30811&tPage=2&rp=2&ru=/ta/2018test&qru=/ta/2018test/question-ranking解...
2019-03-04 11:50:29
128
原创 二分法
二分法二分法一种很常用的方法，之前的博文也介绍过二分法，今天来谈一谈二分的一种巧用。上题—传送门:https://www.nowcoder.com/practice/dcc301bc11a7420b88afdbd272299809?tpId=90&tqId=30813&tPage=2&rp=2&ru=/ta/2018test&qru=/ta/2018te...
2019-03-03 20:55:02
380
原创 DP
DP-解码传送门:https://www.nowcoder.com/practice/4acd516d09ea4f47bd72527bfd40ce2a?tpId=90&tqId=30922&tPage=8&rp=8&ru=/ta/2018test&qru=/ta/2018test/question-ranking看到这道题通过分析可以知道是要通过动态规...
2019-03-03 16:46:23
112
原创 LCS
LCS-最长公共子序列有时候我们会遇到要求两个字符串的公共最长序列，这就是LCS问题，它通常是用动态规划来求解.解析假设现在有两个字符串A, B，字符串A的长度为nnn, 字符串B的长度为mmm, 既然是dpdpdp, 那么就设dp[i][j]dp[i][j]dp[i][j]表示字符串从0的到iii位置和字符串从0到j位置的最长公共子序列, 那么就可以讨论A[i]==B[j],dp[i][...
2019-03-03 14:54:12
547
原创 背包问题
背包问题背包问题是一个很经典的问题，百度上可以找到很多有关这方面的描述，它是一类最优化问题，刷题遇到时一般都是用动态规划来解。其经典的状态转移方程为:dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j...
2019-03-02 15:06:23
146
原创 计算几何-求球冠体积
球冠的体积今天来谈谈计算几何，怎么就球冠的体积，对于一个高为hhh的球冠，如图所示:那么显然要求这个球冠的体积就需要积分，考虑截面法，这个球冠的每个横截面都是一个圆，这个圆的半径假设为rrr, 那么可以知道积分式为:V=π∫0h(r2−(r−x)2)dx=π[r⋅x2−13⋅x3]0h=π⋅h2(r−13⋅h)V=\pi\int_{0}^{h}(r^2-(r-x)^2)dx=\pi[r\c...
2019-03-02 11:45:25
3658
原创 并查集
数据结构-并查集今天要说的这个数据结构是并查集，一种很好用的东西，刷题也会经常用的。并查集一个比较主要的应用是求最小生成树(克鲁斯卡尔算法)。(并查集是什么，这个在这里就不多说了)还是那句话，话不多说，直接上题:传送门: https://ac.nowcoder.com/acm/contest/373/C解析这道题其实很简单，首先要想的他说强盗会从一个地方移动到另一个地方，很明显，就是告诉你...
2019-03-02 09:08:15
104
原创 概率dp(抽牌)
概率dp这是dp的一类题。主要是概率和动态规划结合题目，话不多说，直接上题;传送门:https://www.nowcoder.com/practice/8b8c4fc44b614862b2a4f53771577995?tpId=90&tqId=30855&tPage=4&rp=4&ru=/ta/2018test&qru=/ta/2018test/que...
2019-03-01 19:25:15
261
原创 dp
动态规划(dp)题目：https://www.nowcoder.com/practice/56d818ae68134c12b26e81f41ecafb9e?tpId=90&tqId=30841&tPage=4&rp=4&ru=/ta/2018test&qru=/ta/2018test/question-ranking一道京东的面试题，说下思路吧，其实很...
2019-03-01 16:44:25
314
原创 二分图
二分图简介二分图是一种很有用的数据结构，主要是用在处理一些二元关系上，还有网络流也会涉及这个东西。二分图是什么东西呢？二分图的具体定义可以参考百度百科:https://baike.baidu.com/item/二分图/9089095?fr=aladdin那么知道什么是二分图后就是该怎么判断一个图是否为二分图的条件了，判断一个图是否为二分图的充要条件为: 图至少有两个结点，且所有的回路长度均...
2019-02-27 15:16:43
109
原创 Mannacher 算法
Mannacher 算法马拉车算法(中文翻译，有点搞笑)主要是用来求解字符串的最大回文字串。回文串是一个很常出现的东西，求解字符串的回文串也是很经典的题目，马拉车算法是一个可以在O(n)O(n)O(n)复杂度内求解字符串的最大回文串的算法。基本介绍在求解前我们要先对该字符串做一些预处理，其过程为: 在字符串的最前面加上"@#", 当然这两个符号都不能出现字符串当中，之后在字符串每个字符后面加...
2019-02-26 19:37:31
454
原创 RMQ
RMQ一个高效的用于查询区间最大/最小值的方法，其需要O(nlogn)O(nlogn)O(nlogn)的时间复杂度进行预处理，之后对于每次的区间查询的复杂度为O(1)。预处理采用DP的思想(也可以说分治法). 设dp[i][j]dp[i][j]dp[i][j]表示从iii开始的连续2j2^j2j个数的最大值，显然初始值dp[i][0]=a[i]dp[i][0]=a[i]dp[i][0]=a[...
2019-02-26 15:16:28
798
原创 天上的星星-DP
DP+分割题目-天上的星星在一个星光璀璨的夜晚，蒜头巨一颗一颗的数天上的星星。蒜头君给天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象限。天上有nnn颗星星，他能知道每一颗星星的坐标和亮度。现在，蒜头君问自己qqq次，每次他问自己每个矩形区域的星星的亮度和是多少(包含边界的星星)输入格式第一行输入一个整数n(1≤n≤50000)n(1 \leq n \leq 50000)n(1...
2019-02-26 14:49:59
150
原创 数论
莫比乌斯反演+线性逆元题目-势能之和在学习了最小公倍数之后，花椰妹出了一道题打算考考蒜头君。她给出了nnn个整数aia_iai，并令它们的积为SSS，即S=a1⋅a2⋅a3⋯anS=a_1 \cdot a_2 \cdot a_3 \cdots a_nS=a1⋅a2⋅a3⋯an。这nnn个正整数组成多重集合，一共有2n−12^n-12n−1个真子集。对于一个包含mmm个数的子集ak...
2019-02-19 16:19:12
182
原创 数论-莫比乌斯反演
(数论-莫比乌斯反演)小学生一发一篇比较数学的博客，最近在学习莫比乌斯反演，这是数论上比较重要的一个定理，平时刷数论的题目也比较容易遇到，所以还是书此文来加深一下印象。莫比乌斯反演的引入考虑如下求和函数:F(n)=∑d∣nf(d)F(n)=\displaystyle\sum_{d|n}f(d)F(n)=d∣n∑f(d)我们有如下结论:f(n)=∑d∣nμ(d)F(nd)f(n)=\...
2019-02-18 16:59:13
215
原创 数论+容斥
(数论+容斥)小学生一发数论只会gcd的弱渣今天遇到一道加容斥的题目，感觉颇深，故特书此文来纪念一下。Rinne Loves Sequence题目描述:Rinne给你一个序列aaa，该序列初始为空，要求你支持如下操作：插入一个数，如果已经存在则忽略该操作删除一个数，如果不存在则忽略该操作询问∑i=1n∑j=i+1n[gcd(ai,aj)=1]\sum_{i=1}^{n}\sum_...
2019-02-18 10:00:10
252
原创 二分法+扫描线
(二分+扫描线)小学生一发一道典型的二分加扫描线的题目。人以群分题目描述:某班有nnn个同学，每个同学有一个外向程度aia_iai。由于要进行某个活动，需要把他们分成若干个小组，每个小组的人数至少为mmm人。不同外向程度的人在一个小组会产生不开心值，定义一个小组的不开心值为组内成员外向程度最大值和最小值的差。一个班级的不开心值为所有小组不开心值的最大值。那么问题来了，如何分组使得班级...
2019-02-17 19:16:36
343
原创 环状最大连续和
(最大连续和)小学生一发一道环状的最大连续和。蒜厂年会题目描述:在蒜厂年会上有一个抽奖，在一个环形的桌子上，有nnn个纸团，每个纸团上写一个数字，表示你可以得到多少蒜币。但是这个游戏比较坑，里面竟然有负数，表示你要支付多少蒜币。因为这些数字都是可见的，所以大家都是不会出现的陪的情况。游戏规则：每人只能抓一次，只能抓取一段连续的纸团，所有纸团是那个的数字和就是你可以获得的蒜币。蒜头君作...
2019-02-14 19:30:43
350
1
原创 后缀字符串
(字典树应用)小学生一发一道比较裸的字典树，巩固一下这个数据结构。后缀字符串题目描述:一天蒜头君得到nnn个字符串sis_isi, 每个字符串的长度都不超过10。蒜头君在想，在这nnn个字符串中，以sis_isi为后缀的字符串有多少个呢?输入:第一行输入一个整数nnn。(n<=105)接下来nnn行，每行输入一个字符串sis_isi。输出:输出nnn个整数，第ii...
2019-02-14 10:47:18
853
原创 忽明忽暗之打表篇
(数论打表篇)小学生一发一打打表的题目，反正现在一看到这种题目，打表大法好，我tm什么都不想就想打表(哈哈蛤)。忽明忽暗题目描述:走廊里有nnn盏灯，编号依次为1,2,3,....,n,1, 2, 3, .... , n,1,2,3,....,n,由学校电路控制中心管理。初始时，所有灯都是关闭的。某黑客入侵了学校电路的控制中心，黑客相让灯忽明忽暗，进行了nnn轮操作。第iii轮操作，会让...
2019-02-13 20:24:47
351
原创 概率期望-(炮台实验)
(概率期望)小学生一发一道和概率以及期望有关的题目，硬是磨了一下午才写出来，呜呜呜。炮台实验题目描述:蒜头君在玩一个战争模拟游戏，他有高度为1, 2, 3, …, n 的炮台各一个,他需要把这n个炮台从左往右排成一行，并且炮口都朝向右边。在这个游戏中，所有炮台发射的炮弹会摧毁前方所有高度比自己低的炮台。每当蒜头君把n个炮台排成一行后，可能会有一些炮台被摧毁。举个例子：当前有5个炮台，从...
2019-02-13 17:47:30
451
原创 小学生一发的刷题之路
(编程题-关灯)关灯游戏很早就想写博客了，一直没落实。接着今天这个机会开始人生的第一篇博客，不喜勿喷哈！！！关灯游戏题目描述:在Alice生日的那天，Bob送给了她n个灯泡。他们决定用这些灯泡玩一个游戏：他们把这些灯泡从左往右排成一行，在初始时，有些灯泡是点亮的，有些灯泡是熄灭的。接下来，他们轮流进行操作，Alice首先操作。在每一次操作中，轮到操作的人需要选择一个点亮的灯泡，然后把它以...
2019-02-11 20:58:14
948
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人