首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
Deep_Dark_FAntasy♂
获赞
627
粉丝
7
关注
15
看过 TA
47
男
清华大学
2027
算法工程师
IP属地:北京
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑Deep_Dark_FAntasy♂吗?
发布(240)
刷题
Deep_Dark_FAntasy♂
2020-09-23 20:28
已编辑
清华大学 能源动力类
拉格朗日插值法的介绍与应用
update 9.23 lagrange重心插值改进&&模板定理:给定n+1个不同数的取值,可以唯一确定一个次数不超过n的多项式。如何求出这个多项式可以使用拉格朗日插值法。拉格朗日插值法:假设我们得到了n+1个点,定义:xj的"开关"为:为什么称它为开关呢?因为构造使得pj(xj)=1,而带入任意xi(i不等于j)都pj=0,这样接着构造出这个n次多项式跟据开关的性质,我们知道Ln(xi)=yi下面介绍拉格朗日插值法的应用。求自然数的幂的前缀和当k=1的时候,我们知道柿子为(n+1)*n/2,可以推广,求和柿子一定是一个k+1次。跟据拉格朗日插值法,设答案柿...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-21 15:31
清华大学 能源动力类
B: Graph Theory Class
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6889伪图论题,板子找的好就能A。大概要求出这个东西:lcm(2,3)+min(lcm(2,4),lcm(3,4))+min(lcm(2,4),lcm(3,4))+min(lcm(2,5),lcm(3,5),lcm(4,5))...我们可以通过唯一分解定理的思路来取min,从i=3开始,若是一个质数,那么lcm取min后肯定是2*i,若不是一个质数,那么肯定为这个数自己,因此,我们的目标就是求i=3开始到n+1(注意)的数的和加上i=3开始的质数的和。鉴于n=1e11,直接套板子。值得注意的是n为1...
2020 CCPC网络赛
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-21 14:38
已编辑
清华大学 能源动力类
博弈Lunch
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6892思路:最初的思路是这样:把长度作素因子分解,这样分解次数之和(可拆分次数)就可以视作为一堆石子,什么时候取完就是全为1的情况也就是最后状态,但是这样直接转化为尼姆游戏会与题目中所说的有所区别,分解一次,假设除m(从一堆中拿走任意多个素因子(素因子乘积为m)后)在题目中会形成m个堆,那么我们思考,既然被分解后会形成m个堆,这想法还对吗?我们可以这样思考,如果从中拿走任意非2质数,那么肯定会形成奇数个石子数量相同的堆,那么其实最后尼姆异或的结果仍是1个堆的值,新多出来的m-1个堆异或后为0。如果从...
2020 CCPC网络赛
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-17 18:09
清华大学 能源动力类
Buy and Resell hdu-6438
题意:给出n,和a[i]代表第i天东西的行价,问收益最大是多少,在此前提下交易次数最少是多少?思路:维护一个小根堆,每次将堆顶与a[i]比较,如果a[i]<min,直接把a[i]放入,如果a[i]>min,那么可以a[i]-min就暂且作为我当前的收益,当然这不一定是最优的方案,考虑后面如果有a[j]>a[i],那我这个物品肯定在a[j]卖是最划算的。如果我在a[i]卖了后,再pusha[i]进小根堆,如果到了a[j]再卖的话这个过程中,你会发现ans先加了一个a[i]-min,又加了一个a[j]-a[i],那么其实对ans的贡献只有a[j]-min,就相当于min在a[j]...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-08 21:44
清华大学 能源动力类
翻硬币问题hiho1172
先看官方题解:这个游戏叫做Turning Turtles,它的本质就是Nim游戏。那么它到底是如何转化为Nim游戏的呢?让我们一步一步来分析。 首先,我们先将局面分解一下,每一次我们只考虑一枚硬币。不妨设所有硬币全部背面朝上的局面为局面0假设现在N枚硬币,只有第1枚是正面朝上的。该局面只能转化为全部硬币背面朝上的局面。我们假定该局面为 局面1,则局面1可以转化为局面0。假设只有第2枚是正面朝上的。该局面可以转化为:只有硬币1正面朝上;全部硬币背面朝上。我们假定该局面为 局面2,局面2可以转化为局面1和局面0。同理我们可以推定,第i枚硬币正面朝上的局面为局面i,局面i可以转化为局面0..i-1。...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-08 19:51
清华大学 能源动力类
Nim游戏拓展 阶梯博弈
题意:有一颗n个节点的树,1号点为根节点,其他点上分别放有若干个石子,两个人轮流操作,每次可以将某个节点上的若干个石子移动到这个节点的父亲上面,无法操作者负,问先手是否必胜。 以0(root)为的深度为1,我们首先发现,0作为root,它上面的石子不管有多少对结果都无法造成影响,故可以视为0,再考察深度为奇数的节点,如果这上面有石子,那么不管alice从这里拿多少石子移到父亲节点上,bob都可以模仿alice的操作,这样的话,这些石子又将放到深度为奇数的节点上,直到root,因此直到所有奇数深度都到root,alice无法操作了,就必败了。因此我们可以把奇数节点都视作0,即消失了,因为对答案没...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-04 21:16
清华大学 能源动力类
模线性方程组
模线性方程组题目链接:http://poj.org/problem?id=2947有m条记录,n个零件,那么就是m个方程,n个未知数,然后所花的天数和在工厂呆的天数对7同余,也就是求解一个模线性方程组。代码: #include<bits/stdc++.h> #define MAXN 310 #define N 310 #define MOD 7 using namespace std; int a[N][N];//增广矩阵 int x[N];//解集 bool freeX[N];//标记是否为自由变元 int GCD(int a,int b){ return !b?a...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-04 19:24
清华大学 能源动力类
EXTENDED LIGHTS OUT
题目链接:http://poj.org/problem?id=1222就是亮灯问题56的灯,列30个方程,异或方程组一套板子,完事*代码:** #include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h&g...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-09-04 17:08
清华大学 能源动力类
CCPC2016 B.异或方程组高斯消元板子题 Zhu and 772002
题目连接:https://vjudge.net/contest/392610#problem/B解题思路:对于每个质因子,显然只有偶数和奇数的两种情况需要考虑,考虑构建异或方程组。高斯消元法一个板子下来,求出自由未知元的个数,然后就是对自由元赋值,0或者1,总共有2^k种,别忘了去掉全是0的情况,因此答案是2^k -1 代码: #include<bits/stdc++.h> using namespace std; #define MOD 1000000007 #define MAXN 2010 #define N 2010 #define INF 0x3f3f3f3f typed...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-30 21:05
清华大学 能源动力类
2020hdu多校第二场1001 Total Eclipse
题目链接:https://vjudge.net/contest/391866#problem/A题目描述:开始的想法是都减去最小的值,这样一个连通块就被分为了若干连通块,如此重复。但这样不好实现。可以反过来去想。既然删点困难可以考虑其逆过程,加点。把所有点从大到小排序,然后放入集合中,然后遍历所有这个点相连的边(x,y),如果y在集合中,而且x,y还没有并查集合并,就合并它们,ans+=b[y]-b[x]最后再把所有根的值都加到ans代码: const int maxn = 1e5+7; vector<int> to[maxn]; bool vis[maxn]; int fa[...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-29 17:40
清华大学 能源动力类
H-Harmony Pairs
题目大意:给出n,问从0到n有多少数对(A,B),满足A<B,但是A的数位之和大于B的数位之和?解题思路:数位dp。之前使用数位dp,都是求解一个范围[L,R]内满足某个条件的数有多少。这次是求满足条件的对数。学到的第一个是用空间换时间,就是把lima,limb之类的都写进dp里,形成一个5维dpdp[pos][sum][lima][limb][limit]分别代表:1.当前搜索到的位置2.前面已经搜索出来的各位之差3.第一个数最高位此时是否有限制4.第二个数最高位此时是否有限制5.第二个数在前面是否已经大于了第一个数普通的数位dp是在dfs的时候构造一个满足条件的数,而这里的数位dp在...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-10 22:08
已编辑
清华大学 能源动力类
A-Permutation
题目链接:https://ac.nowcoder.com/acm/contest/5675/A思路:对于 i 位置若 a[i-1]* 2%p没有使用过就使用,否则就使用 a[i-1]* 3%p,若两个都已被使用,说明必定有冲突。代码: #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; bool vis[maxn]; int a[maxn]; int main() { int t, p; scanf("%d",&t); while(t--) ...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-10 21:00
清华大学 能源动力类
E-Game
题目链接:https://ac.nowcoder.com/acm/contest/5675/E题意:从右向左将木块推动,直到不能再推木块,求所有列的max的最小值。思路:比较直观的是二分答案M,然后从高度M,从右往左推,模拟。等价于求前缀平均值的最大。实际上从左往右先把所有能推到左边的都尽量平分到到这一部分去,即前缀和sum平分。考虑到第i列可能比第i-1列小,这时候由于取平均值不会更新答案,而当i列比第i-1列大可能更新答案。 代码: #include<bits/stdc++.h> using namespace std; typedef long long ll; cons...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-09 11:48
已编辑
清华大学 能源动力类
E-Groundhog Looking Dowdy(欧拉降幂,质因子)
题目链接:https://ac.nowcoder.com/acm/contest/5674/E思路:对于x,y的公共质因子p来说,如果在x的唯一分解中的幂次为m,在y的唯一分解中的幂次为n那么当mi >= nj的时候, 即j <= mi/n的时候,gcd的p的幂次为nj当mi < nj的时候,即j>= mi/n的时候,gcd的p的幂次为mi枚举i便可以确定mi/n对于大于mi/n的j来说,p的幂次的总和就是:mi(d-mi/n)对于小于等于m*i/n的j来说,p的幂次的总和就是:n(c+c+1+c+2+...+m*i/n)鉴于p的幂次最后会很大,可能会爆ll,可以使用欧...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-08 00:13
已编辑
清华大学 能源动力类
Fear Factoring(分块)
Problem C — limit 1 secondFear FactoringThe Slivians are afraid of factoring; it’s just, well, difficult.Really, they don’t even care about the factors themselves, just how much they sum to.We can define F(n) as the sum of all of the factors of n; so F(6) = 12 and F(12) = 28. Your taskis, given two ...
0
点赞
评论
收藏
转发
1
8
9
10
11
12
16
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务