sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

全部文章 / 题解（共372篇）

【每日一题】5月15日储物点的距离来自专栏

解题思路前缀和，千万千万注意减法取模……我半个多小时。。区间问题，居然要全部转移那么最简单模拟的话，出题人变态一点，每个区间都是最左端和最右端。时间复杂度毫无疑问爆炸了这时候，昨天的直播课，雨巨小姐姐刚好又说到了区间问题的解决办法！！吹爆。每个步骤都去模拟太蠢了，想想能不能用前缀和代替一下。区间问...

2020-05-15

2 845

【每日一题】5月14日maze 来自专栏

解题思路思维转换，从地图起点找终点退出来，因为存在传送机，具体不能一遍普通的bfs跑出来，需要比较细心的处理细节。那么我们换个角度，如果我们把这个地图里的每个位置当作一个节点，去创建一个图会怎么样呢？初始化地图输入时，每一个可以转移的小数点，边权是1，这里注意一个细节，别建反图，没什么意义。q次输...

2020-05-14

1 779

牛客算法周周练6

B、华华对月月的忠诚辗转相减法（更相减损术），gcd与斐波那契数列的关系。先介绍下辗转相除法之外的辗转相减法。gcd(a,b)如果a>b那么会等于gcd(a-b,b)。如果b>a那么会等于gcd(a,b-a)，如果a，b相等此时就是gcd。还有一个结论就是 gcd(2a,2b) = 2...

2020-05-12

2 742

牛客算法周周练6

A、青蛙过河是不是乍一眼看起来像哈诺塔……恭喜你被骗了。汉诺塔可以随意移动，虽然也有一定前提。但是对这个题目来说最要命的约束条件就是到了对面就不能动了。所以就决定了，一定是重的青蛙先跳去对面。所以我们从几个极端来看。如果给出莲叶数是n，石头数目是m。如果m是0，那么最多可以允许 n + 1 个青蛙...

2020-05-12

0 720

【每日一题】5月13日加分二叉树来自专栏

解题思路区间dp又又又是区间dp；看来是个极其重要的动态规划模型吖！这里给出的数据规模小于等于30，很明显可以开下很多维的数组，运行的时间复杂度也很高。题目第二行给出的是每个节点的初始值。我们要找到一个前序序列，让题目给出的函数值最大。根据题目给出中序序列为 1 2 3 4 5 6 7 …… n那...

2020-05-12

1 728

【每日一题】5月12日模拟战役来自专栏

解题思路终于有一个简单模拟了。虽然这题介绍一大堆，总结起来就是几句话，给出地图n列，前4行是a的地盘，后四行是b的地盘，每个人地盘上面有星号代表大炮。大炮会 3 * 3的波及周围，会一直传递，b先手，a立刻反击b出手的大炮，问b能不能消灭a全部的大炮，如果能最后剩余最大大炮数是几。那么很显然，我们...

2020-05-11

1 840

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

C、张老师的旅行区间dp，动态规划众多模型中的一种，解决区间问题上有广泛的应用。基本思想就是一重循环枚举长度，还要一重循环枚举起点，终点就已经确定。关于决策点根据题目是否需要枚举或者优化成记录这里不展开。本题不需要枚举决策点，因为老师需要花费时间最短一定是从区间这一边一直走到另一边。那么我们根据...

2020-05-11

0 585

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

给出的仅为我的做题顺序，与题目难度不一定匹配 F、排列计算前缀和给定区间，可以控制区间元素加1，最后把区间元素的染色次数排序，从次数最大开始填最大的数。具体区间元素+1，又不用模拟去实现，直接在左端点处加1，右端点后面一个点减1即可。最后求前缀和就行。再把求好的前缀和数组排个序，大功告成 #in...

2020-05-10

2 991

牛客练习赛63

F、牛牛的树行棋博弈论sg函数与dfs。前导知识sg函数：SG函数：首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。对于任意状态 x ，定义...

2020-05-10

1 805

牛客练习赛63

D、牛牛的01限定串简单动态规划如果你学过这个或者见过这个模型的动态规划那么这题就是个很简单很简单的dp。）当然我不会，看了题解补提才马后炮的。题解表示，这种两种状态的字符串，特别是给定的长度，每位个数是多少个的，转换到一个n + 1,m + 1的棋盘去看。例如这题的第一个样例。转化成一个 7 行...

2020-05-10

0 533