首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
Deep_Dark_FAntasy♂
获赞
627
粉丝
7
关注
15
看过 TA
43
清华大学
2027
算法工程师
IP属地:北京
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑Deep_Dark_FAntasy♂吗?
发布(240)
刷题
Deep_Dark_FAntasy♂
2020-09-27 19:07
清华大学 环境科学与工程类
健康监测计划
链接:https://acm.ecnu.edu.cn/contest/317/problem/B/思路:按k我们来考虑k=0,那么肯定一个都不放,k=1,那么显然只能放一个,k=2呢?所有叶子结点都放,先去想k=4,那就是把叶子结点都去了,然后新的树中的叶子结点。k=3呢?就是k=4中,新选的点中随便取一个。这样一直把外圈缩进k/2次,所有的叶子结点就都是答案,那么如何判断k/2次呢,记录个深度,如果深度<=k/2并且它是叶子结点就算是要去的点。用queue把叶子结点放进来,并且每个叶子结点更新它对连的点,时间复杂度O(n) 代码: #include<bits/stdc++.h&g...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-27 17:24
已编辑
清华大学 环境科学与工程类
233 Matrix
链接:http://acm.hdu.edu.cn/showproblem.php?pid=5015思路:我们可以考虑将每个列向量组看成由前一个列向量组通过线性变换得到的。矩阵快速幂的核心思想就是构造关系矩阵,即考虑当前列向量组如何由之前向量组左乘一个矩阵得到。那么考察某一列与之前一列的关系,我们发现,首先233到2333的关系是23310+3,即a0i=a0i-110+3,能够显然发现我们通过10和a01,a02,a03,a04...a0n是构造不出来这个关系的,那么我们就把这个n*n矩阵给拓展一下,多一个维度,最后加个3。然后列向量最后加个1,然后为了使得这一变换的初始能够变换过来,应该对第...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-26 18:53
清华大学 环境科学与工程类
集合操作
思路:很容易知道所有的情况共有2^n个,然后我们思考不可能存在的情况有多少种。我们知道每次都可以从前m+1个种取一个。当我们左边减少0个,那么右边m+1到n中任意数字减少都不行,因此答案有2^(n-m-1)-1种(真子集都是不存在的情况,-1是因为自己一个不去)当我们左边m+1个中减少1个,那么答案为C(m+1, 1)(2^(n-m-2)-1)若从左边m+1个中减少2个,那么答案为C(m+2, 2)(2^(n-m-3)-1)。。。以此类推直到最后情况即n-m-i-1==0即可代码: #include<bits/stdc++.h> using namespace std; typed...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-26 12:07
清华大学 环境科学与工程类
Mu函数
思路:看到K这么大,我们知道这种题一般要先从找规律的角度尝试一下。f(x)=x+Mu(x),那么跟据Mu(x),我们知道如果x的Mu(x)为0,不管经过多少次迭代,其结果都是0如果Mu(x)不为0呢,通过对Mu(x)打表我们可以大胆猜测,在k很大的时候,要么x通过迭代到了Mu(x)=0的点,会产生-1,1的死循环。代码: #include<bits/stdc++.h> using namespace std; #define int long long const int MAXN = 1e7+10; int prime[MAXN], prime_tot; bool prime_...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-26 10:58
清华大学 环境科学与工程类
数树
思路:可以从度的角度来考虑来考虑相连如果是两个D>1的结点相连,我们知道这一定是两颗树合并了,那么树++,如果其中一个D=1,那就是一个点和并到了一颗树上,树的个数不变,如果两个D=0的点相连,树的个数++接下来考虑断开如果是两个D>1的结点断开,我们知道肯定是1棵树变成了2颗树。如果其中一个D=1,那么就是把一个叶子结点分出去了,树的个数不变。如果两个点的度都为1,那么分成的两个东西都是单个结点,树的数目--代码: #include<bits/stdc++.h> using namespace std; const int maxn = 1e8+7; int n; i...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-25 12:54
清华大学 环境科学与工程类
牛牛的mex
链接:https://ac.nowcoder.com/acm/contest/7079/A思路:让求在这个区间的最小未出现的最小自然数,那么可以反向思维来求不在这个区间出现的最小自然数。那么维护一个前缀和后缀最小值即可。代码: #include<bits/stdc++.h> using namespace std; const int maxn = 1e5+7; int a[maxn]; int sm[maxn], bm[maxn]; int main() { int n, q; cin >> n >> q; sm[0] = n; b...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 20:49
清华大学 环境科学与工程类
#165. 拉格朗日插值
题目链接:https://loj.ac/problem/165拉格朗日插值重心优化 #include<bits/stdc++.h> using namespace std; #define int long long const int mod = 998244353; const int maxn = 3010; int num, x[maxn], y[maxn], w[maxn]; int q_pow(int a, int b){ int ans = 1; while(b > 0){ if(b & 1){ ...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:45
清华大学 环境科学与工程类
两个数互质
如何判断两个数互质: 来源:https://blog.csdn.net/HelloZEX/article/details/82667263 bool isrp(int a, int b) { if(a==1||b==1) // 两个正整数中,只有其中一个数值为1,两个正整数为互质数 return true; while(1) { // 求出两个正整数的最大公约数 int t = a%b; if(t == 0) { break; } else ...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:45
已编辑
清华大学 环境科学与工程类
lower_bound和upper_bound
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 ———————————————— 版权声明:本文为CSDN博主「brandong」的原创文章,遵循 CC 4.0 BY-...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:44
清华大学 环境科学与工程类
DFS实现种子填充
种子填充(连通块)紫皮书p162 要实现bfs算法需要标记数组 需要使用回溯法 #include <cstdio> #include <cstring> const int maxn = 100 + 5; char pic[maxn][maxn]; int m, n, idx[maxn][maxn];//idx是记录连通分量编号(避免一个格子访问多次) void dfs(int r,int c,int id) { if(r < 0 || r >= m || c < 0 || c >= n) return;//边界判断回溯 ...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:44
已编辑
清华大学 环境科学与工程类
【寒假坚持学习鸭】2.1日(暴力dfs)
题目地址:3rd_Practice_A:Illusive Chase 题目大意:先给你一幅图,0表示可以走,1表示障碍物。在第1s的时候,向R(右)走12步,第2s的时候,向D(下)方向走12步,第3s的时候向右走一步。问有多少个起始点满足要求。 tag:对每个点来遍DFS note:二维数组中的xy容易搞混,,, up和down的加减容易搞混 前几次提交中忽略了i=1~a的过程中碰到障碍的情况 通过此题更加理解DFS、回溯法、边界 此题的核心语句:if(dfs(cx,cy,step+1)) return 1 AC代码: #include <iostream> #inclu...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:44
清华大学 环境科学与工程类
【寒假坚持学习鸭】2.2日(dfs求连通块)
题目地址 题意:给你一个有m条权值为1的无向边的完全图,问你得到的最小生成树的权值为多少 tag:最小生成树,贪心思想 题解:能用权值为0的边就用。 那么对那m条边的端点,将能用0边到达的点都缩在一起 形成一个个连通块 在对缩完的点进行用1边连接,所以答案为缩完后的点数减一 dfs求连通块 u[x] :与vis[x]一样的作用 set g[maxn] 每个点都记录自己与哪些点距离为1 set vis 每个点通过g[maxn]结合着vis便可知自己还与哪些点距离为0 vector ret 对dfs中的的点暂时记录与其距离为0的点 #include<bits/stdc++.h>...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:43
已编辑
清华大学 环境科学与工程类
最小生成树(MST)的Kruskal算法
内容来源 紫皮书p356 kruskal算法的思想在于合并 Kruskal算法的第一步是给所有边按照从小到大的顺序排列。这一步可以直接使用sort。接下来从小到大依次考察每条边(u,v)。 u,v如果在同一个连通分量中,那么加入(u,v)后会成环 伪代码: 把所有边排序,记第i小的边为e[i]; 初始化MST为空 初始化连通分量,让每个点自成一个独立的连通分量 for(int i = 0; i < m; i++) if(e[i].u和e[i].v不在同一个连通分量) { 把边e[i]加入MST 合并e[i].u和e[i].v所在的连通分量 } 最关键...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:43
清华大学 环境科学与工程类
最短路问题(Dijkstra算法、Bellman-Ford算法)
1.Dijkstra算法 Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路,即从单个源点出发,到所有节点的最短路。该算法同时适用于有向图和无向图。 伪代码如下: 清除所有点的标号 设d[0]=0, 其他d[i]=INF 循环n次 { 在所有未标号结点中,选出d值最小的结点x 给结点x标记 对于从x出发的所有边(x,y),更新d[y] = min{ d[y], d[x]+w(x,y)} } 模拟Dijkstra算法:https://www.bilibili.com/video/av36886088 完整算法 memset(v, 0, si...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-23 17:43
已编辑
清华大学 环境科学与工程类
【寒假坚持学习鸭】2.3日(差分约束)
题目地址:https://vjudge.net/contest/354354#problem/F 参考博客:https://blog.csdn.net/qq_28954601/article/details/60969313 主要参考博客: 差分约束算法总结:https://www.cnblogs.com/wjhstudy/p/9757046.html 题意:假设当前有这样一个序列S=a1,a2,a3…an ,现在给出一些不等式,使得 ai+ai+1+ai+2+…+ai+n<ki 或 ai+ai+1+ai+2+…+ai+n>ki ,问这样的一个序列是否存在。 tag:差...
0
点赞
评论
收藏
转发
1
3
4
5
6
7
16
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务