sunrise__sunrise

题解

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

/ 注册

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

【每日一题】5月11日Moovie Mooving 来自专栏

中文题意第一行给定n部电影，和观影时间l。后面n行分别给出第一个参数，这一部电影的播放时长a[i]，第二个参数播放次数m，后面m个参数是开始播放的时间点。问，是否一种观影方式让这个人一直处在看电影的状态，并且不能同时看一部电影2遍，就是刚刚出来又回去看这部电影。解题思路看到给出电影数最大20，...

2020-05-09

1 757

【每日一题】5月9日过河来自专栏

解题思路离散化+动态规划从简单方面入手，单纯考虑动态规划来说很容易找到状态转移方程。dp[i]代表来到位置i的最少石子数。那么：如果这个地方有石子 dp[i]=min(dp[i],dp[i - j]+1) j 在[s , t]中。如果这个地方没有石子 dp[i]= min(dp[...

2020-05-09

0 784

牛客练习赛

A、牛牛的三角形方法一，枚举第一二三个点，判断任意两边之和都要大于第三边，时间复杂度 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; inlin...

2020-05-09

1 672

牛客算法周周练5 来自专栏

A、多彩的树看到颜色最大只有10种，考虑枚举全部的颜色搭配，二进制枚举即可我们选取二进制位是1的表示该颜色本轮被选取。例如1011->第一种第二种第四种颜色被选取，第三种没被选中。这样一重循环枚举颜色组合，再去遍历这种颜色组合下的全部节点，通过DFS跑出每个符合颜色要求的连通块节点数。我们...

2020-05-08

6 816

5月8号软技第十五次周练

如果跳转失败点击这里解题思路对于每个人只能吃到的鸽子肉只能来自于一只鸽子但是一只鸽子可以给分割被很多人吃。那么我们假设mid可以满足当前分配，自然而然地就知道想要这个答案更大一点的，那么如果这个mid不够给人分配，那么答案一定比mid更小，这样就满足了二分的性质。这里还要特判0因为mid做了...

2020-05-07

4 597

【每日一题】5月8日codeJan与旅行来自专栏

解题思路给定n个城市坐标，每个城市可以多次到达，但是只有离开再回来才算次数+1，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。首先通过强大的观察法我们得到最终一定是在两个城市之间反复横跳，或者一次向一个方向走到m个城市，这两种方案。具体如何得到的：假设走到当前节点跳到后面节点后...

2020-05-07

1 985

【每日一题】5月7日「火」皇家烈焰来自专栏

「火」皇家烈焰字符串的长度为n对于30%的数据，n≤20对于60%的的数据，n≤1,000对于100%的数据，n≤1,000,000 直接枚举全部情况，对问好与特殊位置进行选择，计数，30分做法。三维线性dp，100分做法。通过三维数组dp[N][2][2]，0代表没有，1代表有烈焰，dp[...

2020-05-07

0 654

牛客算法周周练5 来自专栏

简单瞎搞题可以发现这题只存在两种状态0或者1，这种单一状态状态压缩动态规划的可以通过STL中的bitset去优化内存。比较容易发现当前状态一定可以通过前面一个状态转移过来，阶段的话可以选择在中的某个数据算平方。累加进当前状态具体实现就是，先处理第一次输入的数据，保证不全是0（其实按照0初始化为1...

2020-05-06

3 1062

牛客算法周周练5

D、小雨坐地铁分层建图，求单源最短路，不带负权边。如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二...

2020-05-06

2 640

牛客算法周周练5

C、序列最小化因为是一个全排列数组，最终一定全部换成1，那么这个过程中替换1以外的数字都是多花功夫，记录全部换成1最少的步骤。方法一：比较朴素的方法记录到1出现的位置，枚举最开始更新1的区间，再计算起始区间左边+右边需要的次数，更新答案取最小值即可。这种方法有一个好处，就是如果你采取这个方法，...

2020-05-06

0 782