首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
Deep_Dark_FAntasy♂
获赞
627
粉丝
7
关注
15
看过 TA
46
男
清华大学
2027
算法工程师
IP属地:北京
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑Deep_Dark_FAntasy♂吗?
发布(240)
刷题
Deep_Dark_FAntasy♂
2020-08-07 23:42
清华大学 能源动力类
计算方法:如何计算回文的阶梯型增长
今天做题时遇到了一个问题:对于一个序列S1,S2,S3,S4,S5,...,Sn如何计算以下的这些东西:i=1 S1+S2+...+Sni=2 S1+2S2+...+2Sn-1+Sni=3 S1+2S2+3S3+...+3Sn-1+Sn...i=n-2 S1+2S2+3S3+...+3Sn-1+Sni=n-1 S1+2S2+...+2Sn-1+Sni=n S1+S2+...+Sn很容易看出它们的规律,就是系数是回文的,并且阶梯增长的。我就暂且先把它叫做回文的阶梯增长那么如何来计算呢?我们可以这样来思考:对于每个i来说,所有系数本来都是i,然后每次从左到右第i位的系数都会固定下来,因此之后的回合...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-03 11:59
清华大学 能源动力类
A-Social Distancing(dp打表)
题目链接:https://ac.nowcoder.com/acm/contest/5672/A题目描述:求在一个半径r的圆内整点上放置n个人,使得两两距离和最大。(n<=8 r<=30)解题思路:考虑dp打表,状态dp[i][j][k]为放置i个点,横坐标和为j,纵坐标和为k的每个点和圆心的的距离的平方和的最大值。为什么这样dp?把题目中的公式先写出来:由于减法不好维护,我们尝试转化为加法:我们可以单独来看前面的xi^2+xj^2+yi^2+yj^2,它们可以写为(xi^2+yi^2)+(xj^2+yj^2)这个累加也就是在求所有的两两组合,每个出现n-1次,比如a、b、c,它们的...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-02 22:00
清华大学 能源动力类
(贪心:模拟退火算法)洛谷P1337 [JSOI2004]平衡点 / 吊打XXX
链接:https://www.luogu.com.cn/problem/P1337模拟退火算法学习参考:https://www.cnblogs.com/flashhu/p/8884132.htmlhttps://99nl.blog.luogu.org/guan-yu-mu-ni-tui-huo-di-xue-xi-bi-ji思路:模拟退火适用的问题通常是一些求最优解的问题比如把问题抽象地看成一个长得毫无规律的函数,而最优解就是函数的最低点。 模拟退火过程简要概述:我们给一个初始解x,并让它不断变动。要模拟变动的大小随温度的降低而降低,我们每次的delta x应该在一个大小与T成正比的范围内随...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-02 13:02
清华大学 能源动力类
小数取整进1
Blow up the Enemy题意:爸爸和儿子玩游戏,每个人只能从n个武器中选择一种战斗,每种武器还有两个属性,一个是伤害A,另一个是两次使用的时间间隔D,爸爸的武器随机选择,儿子想赢得比赛,替他选一种武器,求最大的获胜率。思路这题很简单,在时间相同的情况下打出的伤害最先到达100就是最好的武器,爸爸能赢就只能选择最好的武器中一把,能赢的概率再乘上50%,主要值得注意的是怎么算伤害达到100所花费的时间:((100+a-1)/a-1)*t这里需要学的小技巧是小数取整的时候如何进1加上a-1是为了如果还有剩余不到a的生命值,最后小数取整需要进1,如果刚好打完了生命值,加a-1也不会对答案有影...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-02 00:19
已编辑
清华大学 能源动力类
B-Mask Allocation
链接:https://ac.nowcoder.com/acm/contest/5672/B题意:n * m个口罩,装最少的箱,使得在个数平均的情况下,既能分箱分给n个医院,也能分给m个医院。思路:我们当然要从n,m中最小的那个考虑,所以考虑装口罩最多的盒子,显然不能超过n,不然人数在m的时候这盒子分不出去了。不妨设(n<m)继续考虑字典序最大,医院数量为n的时候需要给每个医院安排m个口罩,贪心的思考,我们可以先给前n个医院各n个口罩,然后还剩nm-nn个,剩余的这些既要能组成(m-n)个n,也要能组成n个(m-n),那么问题就变为了有nm-nn个口罩,如何分使得既能分箱给m-n个‘医院’...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-08-01 23:56
已编辑
清华大学 能源动力类
H-Dividing
链接:https://ac.nowcoder.com/acm/contest/5672/H题意:正整数二元组Legend Tuple(n,k)是这样定义的 (1,k)总是Legend Tuple 若(n,k)是Legend Tuple,那么(n+k,k)也是 若(n,k)是Legend Tuple, 那么(nk, k)也是统计有多少个Legend Tuple(n,k)满足1<=n<=N, 1<=k<=K, 其中N,K是不超过1e12的整数思路:看也看不出来什么,这种题就是写写找找规律。能看出只有ak和ak+1满足题意(a是任意整...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-30 12:30
清华大学 能源动力类
完全平方数的尾巴
题目链接:https://ac.nowcoder.com/acm/contest/6488/B题目大意:给一个数判断是否个完全平方数对1000取模得到的。解题思路:若x是由(kk)%1000得到的即x=(k%1000 * k%1000) % 1000只要取遍0-999的全部数就可知道可以所有取到的x值了。*代码:** class Solution { public: /** * * @param x int整型 * @return bool布尔型 */ bool solve(int x) { for(int i = 0...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-30 00:40
清华大学 能源动力类
D-Drop Voicing
题目链接:https://ac.nowcoder.com/acm/contest/5670/D题目大意:Miyako想通过Drop-2和Invert两种操作把一个给定的排列变成1,2,...,n,连续做任何次数的Drop-2是一个multi-drop,求需要多少次multi-drop Drop-2操作可以把p-1位放到首位Invert操作可以把第一位放到最后 解题思路:每次操作还是通过环来想。两种操作就是整体在转圈圈和前n-1项在转圈圈我们思考一下操作的意义,Invert操作不必多说,Drop-2操作让前n-1项转圈相当于在调整pn和其他的相对位置关系。我们只需要相对位置是1,2,...,n就...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-29 22:52
清华大学 能源动力类
E-Bogo Sort
题目链接:https://ac.nowcoder.com/acm/contest/5670/E题目大意:求可以通过这个函数排好序的排列个数。这个的shuffle实现的功能就是让a[i] = b[p[i]],把原来p[i]位置的a放到i位置。我们画个图来看看。我们可以把这个环想象为一个在转圈圈的传送带,1,2,3...,n通过这个环的转动来生成的排列都可以再通过环的转动来转回1,2,3...n,也就是说我们要去求这些置换的循环节。每次转的时候是所有环一起转,因此转lcm次才能转回最开始的样子。这题在代码实现上:1.需要考虑怎么去考虑这个环。2.因为很多个数的lcm最后可能很大,因此还需考虑如何求...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-29 16:52
清华大学 能源动力类
ACPC 2014 G. Special Christmas Tree
题目描述:在保证所有叶子节点都挂礼物(礼物总数为L)且二叉树的高度不超过H的情况下,二叉树最多能有几个结点?解题思路:这道题从叶子结点的个数来入手,因为最后我们的二叉树显然是H的高度,我们不妨一层一层的来看,如果当前层的叶子结点小于等于礼物数量的话,就加上这一层,如果当前层的叶子结点数目大于礼物数量的话,这一层只能由L个,后面的(H-i)层也只能由L个。代码: #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll T, H, L, cnt = 0; ...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-29 16:41
清华大学 能源动力类
ACPC 2014 A.Game of Peace
题目描述:从(x,0)开始,每次的操作就是都把多的那个复制一下加给少的那个,做了N次操作后,会产生bug,即多的那个会+y,后面不会再出现bug,问M次后,两个数的gcd是多少。解题思路:这种叠加的题目首先考虑一下斐波那契数列。这道题写写样例就知道确实是关于斐波那契数列的。加了y以后,关于y的系数也是斐波那契数列。但是n和m的范围都特别大,会爆longlong。于是你想用个大数模板,结果居然超了内存。最终,你不得不向打表势力低头,于是你发现i>=n的所有gcd都相同。代码: #include<bits/stdc++.h> using namespace std; typede...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-29 11:27
清华大学 能源动力类
I-Hard Math Problem
题目链接:https://ac.nowcoder.com/acm/contest/5670/I题目大意:大本营(H)必须与一个gold miner(G)和一个elixir collector(E)相邻,f(n,m)表示在nm的方格中能最多放多少个H。问n->∞, m-> ∞时,f(n,m)/nm 的值是多少。解题思路:一开始尝试了打表找规律,wa了一发。后来从无穷入手考虑了几何意义。反正我们要求无限大的一个平面的这个值,考虑时候能找到一种单位块来填充整个平面。这样我们只需让单位块的值越大越好,也就是考虑这样一个式子:H/(H+G+E),从贡献的角度来考虑,一个G对上下左右都有贡献,...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-29 11:12
清华大学 能源动力类
F-DPS
题目连接:https://ac.nowcoder.com/acm/contest/5670/F题目大意:i号玩家对敌人的伤害是di,跟据公式来模拟图表。解题思路:水题,模拟。代码: #include<bits/stdc++.h> using namespace std; int d[110]; map<int, int> memo; int main() { int n, maxd = 0; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf(...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-29 10:24
清华大学 能源动力类
K K-Bag
题目链接:https://ac.nowcoder.com/acm/contest/5671/K题目大意:一个由一些1-n的排列组成的数列称为k-bag。比如1,2,3,2,1,3,3,2,1就是一个k-bag。部分k-bag是k-bag的一个子串,现在给一个长度为n的数列,判断是否是一个部分k-bag。解题思路:参考sunsetcolors的解法:https://blog.nowcoder.net/n/1cf39334dfea43339767441bc1e836b6跟据题意能想到,满足条件的序列,我们不管头和尾,中间一定要是几个k排列摆放的过程。但是我们并不清楚,头和尾在什么位置结束。因此我们...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
Deep_Dark_FAntasy♂
2020-07-27 23:42
清华大学 能源动力类
B-Binary Vector
题目链接:https://ac.nowcoder.com/acm/contest/5671/B题目大意:随机生成n个n维{0,1}组成的向量,它们线性无关的概率记为f(n)求解f(1)⊕f(2)⊕....⊕f(N)解题思路:由于这N个向量线性无关,则这N个N维向量组的秩为N,考虑每次将随机生成的向量加入之前向量组中,那么最后N个向量线性无关当且仅当每次加入的向量都不属于之前的空间。那么每次可以将随机生成的向量加入之前的向量组中的概率是(2^N-2^i)/2^N, 分子可以这样理解:2^N是所有的情况,2^i是所有在之前的向量组(空间)的情况。从而推出f(N)的公式。但N是2e7啊,会超时。虽然...
2020牛客暑期多校训练...
0
点赞
评论
收藏
转发
1
9
10
11
12
13
16
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务