东溪看水

题解

/ 注册

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

【牛客编程巅峰赛S1第3场】位数求和

题目所有的长度为 n 的数中，各个位上的数字之和为 m 的这些数的和是多少呢。给定 n 和 m，求这些数的和。解题思路使用暴力法：长度为的数的范围是。遍历该范围的数值，求出每个数的各个位上的数字之和是否与相等，若相等，将这个数累计加入最终结果。 C++代码 class So...

牛客编程巅峰赛S1

2020-07-17

0 569

【牛客编程巅峰赛S1第3场】找卧底

题目在包含 n+1 个数的序列 a 中找出重复的数。序列 a 中包含从 1 到 n 的整数，且只有一个数有重复值。要求时间复杂度为 O(n)，额外空间复杂度为 O(1)。解题思路解法一先排序，再找重复值排序可以直接使用 sort() 函数，其时间复杂度为，接着遍历数组，如果相邻两个数相等...

位运算牛客编程巅峰赛S1

2020-07-17

7 708

可持久化动态图上树状数组维护01背包

题目有一个长度为序列（序列下标从 1 开始），每次可以从任意位置花费的代价来把删除。注意，删除后后面的数会依次向前补上（下标 -1 ) 。求把整个序列删完的最小代价。解题思路当是正数时，在下标 1 的位置删除代价最小，即。当是负数时，在其当前所在下标的位置删除代...

2020-07-15

0 763

数列下标

题目给出一个数列，求出一个数列。其中表示数列中右边第一个比大的数的下标（从 1 开始计数），没有找到这一个下标就为 0。解题思路在从右向左遍历数组 A 时维护一个栈。这个栈存储数列 A 的下标。如果栈非空，且栈顶的元素（下标）所代表的值小于等于当前的值，这表示栈顶下标 ...

栈

2020-07-15

3 933

「水」悠悠碧波

题目给定字符串 s，求一个最长的字符串 t，t 满足以下条件：它是 s 的前缀；它是 s 的后缀；除前缀和后缀外，它还在 s 中出现过至少一次。解题思路暴力求解：先判断前缀和后缀，再判断中间是否存在该字符串。 C++代码 #include<iostream> using names...

字符串

2020-07-08

0 818

绝地求生(pubg)

题目求最少要拾取多少个子弹到背包中，使得背包里的子弹个数恰好是 x 的倍数且是 y 的倍数。解题思路求 x 和 y 的最小公倍数。先求 x 和 y 的最大公因数 k = __gcd(x,y)，则最小公倍数为 x * y / k。 C++代码 #include<iostream> #...

gcd 数学

2020-07-08

0 791

Circle

题目要把这个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。解题思路不考虑互质，一共有 n 对相邻的数。由更相减损术知，数对 (x-1, x) 的最大公因数与 (1, x-1) 的最大公因数相同，即为 1，互质。所以，可以将 n 个数字按从小到大的顺序排列并连...

数学 gcd

2020-07-08

0 707

「木」迷雾森林

题目帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走。现在给出森林的地图，保证可以到达出口，请问有多少种不同的方案。答案对2333取模。0 - 空地1 - 树（无法通过）保证出发点和终点都是空地。解题思路使用动态规划思想。地图左下角的坐标为 (m-1,0)，右上角的坐...

动态规划

2020-07-07

0 655

过河卒

题目 A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不能通过对方马的控制点。棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)（n<21，m<21），C 点 (x...

动态规划

2020-07-07

0 578

数字三角形

题目打印数字三角形，从 1 开始输出，第 i 行输出 i 个数，每个数字按 4 个位置输出。解题思路注意最后一行不要打印换行符。 C++代码 #include<cstdio> using namespace std; int main(){ int n; scan...

2020-07-07

1 894