小嗷犬

分类

题解(39)

/ 注册

全部文章（共40篇）

题解 | #小红的战争棋盘#

考察知识点：模拟大模拟题，需要考虑的情况比较多，下面的代码提供了一种写法。时间复杂度：O(kq)O(kq)O(kq) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsign...

C++ 模拟

2023-08-02

3 690

题解 | #牛牛与回文串#

考察知识点：构造由题易知，构造的回文串个数与字符串中出现次数为奇数的字符个数有关，所有成对出现的字符都不用单独构造。若所有字符都成对出现，则也至少需要构造 1 个回文串。因此回文串的个数应为 max(n, 1)，其中 n 为出现次数为奇数的字符个数。将单独出现的字符作为回文串的中心，其余字符成...

C++ 构造

2023-08-02

3 410

题解 | #再编号#

考察知识点：前缀和定义 sum(a)=∑i=1naisum(a)=\sum\limits_{i=1}^{n} a_isum(a)=i=1∑nai，考虑计算 sum(a′)sum(a')sum(a′)。 sum(a′)=∑i=1nai′=∑i=1n(sum(a)−ai)=∑i=1nsum(a)−...

C++ 前缀和

2023-08-02

3 361

题解 | #大佬的生日大礼包#

考察知识点：二分不难看出每种礼包的构成：「1 个 U 盘 + 1 个鼠标」 + 1 个「U 盘 / 鼠标 / 键盘」设 U 盘、鼠标、键盘数量为 a0,b0,ca_0, b_0, ca0,b0,c，分配完每个礼包本身含有的 1 个 U 盘和 1 个鼠标后的 U 盘、鼠标数量为 a,ba, b...

C++ 二分查找

2023-08-02

5 397

题解 | #iko和她的糖#

考察知识点：递归递归求解：当补给次数超过 3 次或当前糖果数量小于 0 时，返回。当当前位置超过 n 时，更新答案并返回。时间复杂度：O(2n)O(2^n)O(2n) + 剪枝 #include <bits/stdc++.h> using namespace std; ty...

C++ 递归

2023-08-02

2 408

题解 | #数圈圈#

考察知识点：前缀和使用 x[i]x[i]x[i] 记录数字 iii 的圈数，s[i]s[i]s[i] 记录 ∑j=1ix[j]\sum\limits_{j=1}^{i} x[j]j=1∑ix[j]，即前缀和。则数字 aaa 到 bbb 的总圈数为 s[b]−s[a−1]s[b] - s[a-1...

C++ 前缀和

2023-08-02

2 398

题解 | #牛牛的朋友#

考察知识点：贪心考虑两头牛时的情况，有以下 4 种移动方式：两头牛同时向左移动：距离不变两头牛同时向右移动：距离不变左边的牛向左移动，右边的牛向右移动：距离增大左边的牛向右移动，右边的牛向左移动：距离可能减小其中前两种情况对答案没有影响，第三种情况可以直接忽略，第四种情况需要考虑。 ...

C++ 贪心

2023-08-02

5 456

题解 | #牛牛的排序#

考察知识点：贪心由题易知，最坏情况下也只需要 3 次排序即可，因此考虑 0 ~ 3 次排序的情况：当数组本身有序时，不需要排序，输出 0；当最大值或最小值已经就位时，只需要排序 1 次，输出 1；当最大值与最小值都不在头尾时，需要排序 2 次，输出 2；当最大值位于头部，最小值位于尾部时...

C++ 贪心

2023-08-02

2 384

题解 | #递归函数的次数#

考察知识点：递归、滚动数组递归函数调用次数满足递推式 an=an−1+an−2+an−3+1a_n = a_{n-1} + a_{n-2} + a_{n-3} + 1an=an−1+an−2+an−3+1，其中 a1=a2=a3=1a_1 = a_2 = a_3 = 1a1=a2=a3...

C++ 递归滚动数组

2023-07-31

3 432

题解 | #多项式输出#

分别对 n+1 项进行判断，需要考虑的情况较多，有：系数为 0 时，不需要输出该项；系数为正且该项不是第一个输出项时，需要输出 +；系数为负时，需要输出 -；系数绝对值为 1 且不为常数项时，不需要输出系数；常数项不需要输出 x 和指数。非常数项指数为 1 时，不需要输出指数。 #i...

C++

2023-07-31

2 365