当前位置: 首页 > news >正文

蓝桥杯c++算法秒杀【6】之动态规划【下】(数字三角形、砝码称重(背包问题)、括号序列、异或三角:::非常典型的必刷例题!!!)

别忘了请点个赞+收藏+关注支持一下博主喵!!!!  !  !  !  !

关注博主,更多蓝桥杯nice题目静待更新:)

动态规划

三、括号序列

【问题描述】

        给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加 完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。

        两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。

        例如,对于括号序列 (((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()() 、()(()) 、(())()、(()()) 和 ((()))。

【输入格式】

        输入一行包含一个字符串s,表示给定的括号序列,序列中只有左括号和右括号。

【输出格式】

        输出一个整数表示答案,答案可能很大,请输出答案除以1000000007(即109+7) 的余数。

【样例输入】

        ((()

【样例输出】

        5

【评测用例规模与规定】

        对于40%的评测用例,|s|⩽200。

        对于所有评测用例,1⩽|s|⩽5000。

解析:

        在开始解题之前,我们先分析两个问题。

        问题1. 什么情况下必须要添加左括号,什么情况下必须添加右括号?

        问题2. 我们添加的左括号会和我们添加的右括号匹配吗?

        对于问题1,我们可从以下两方面作进一步思考:

        (1)当一个右括号之前已经没有可以与其相匹配的左括号时,我们必须要添加左括号。例如() )从左往右看,第二个右括号之前已经没有左括号可以与其匹配(第一个左括号和第一个右括号匹配),这时候我们就必须添加左括号。

        (2)当一个左括号之后已经没有可以与其相匹配的右括号时,我们必须要添加右括号。例 如(( )从右往左看,第二个左括号之后已经没有右括号可以与其匹配(第一个右括号和第 一个左括号匹配),这时候我们就必须添加右括号。

        对于问题2,答案是“不会”。

        我们可以使用反证法来证明:

        (1)假设操作完成后的括号序列为 XXX ( XXX ) XXX(、) 为我们添加的互相匹配 的左括号和右括号,X 表示原序列的括号,或是我们添加的与原序列括号相匹配的 括号。

        (2)那么该序列 XXX(XXX)XXX 若是一个合法序列,则将 (、) 去掉后的序列 XXX XXX XXX也会是个合法序列(对于一个合法的括号序列,去掉任意一对匹配的左右括号,它也依旧合法)。

        (3)所以如果我们添加的左右括号相互匹配,它们将起不到什么作用,只会徒然增长序 列的长度。而题目要求我们的序列长度尽可能短,所以我们添加的左括号不会和我 们添加的右括号匹配( 即我们添加的左括号只会受原序列中的括号影响,添加的右括号只会受原序列中的括号影响)。

         因此,我们可以将左括号的添加方案右括号的添加方案分开计算,然后再将其合并为 答案(因为左括号和右括号的添加是互不影响的、独立的,所以 答案 = 左括号的添加方案数 × 右括号的添加方案数)。

        下面分别给出3种解题方式,分别是暴力做法、能拿 40% 分数的做法、满分做法。大家仔细体验这3种解题方式的特点,其中 “ 能拿 40% 分数的做法 ” 给出的解题方式,虽然拿不了满分, 但在实际竞赛中,也可以视情况使用。

方式1:暴力做法

        本题作为2021年蓝桥杯省赛压轴题之一,相信绝大部分人在做的时候都会一头雾水,甚 至在已知上面信息的情况下,也还是会找不到切入点。

         不过没有关系,蓝桥杯毕竟是个根据通过的数据量来给分的比赛,所以我们并不需要在 第一步就思考出它的满分做法。

        那第一步该做什么呢?暴力!

        有一个做题技巧:在面对一道完全没有头绪的题目时,请不要傻等着浪费时间,可以先尝试用暴力的方法解题,然后再在暴力的基础上思考如何优化复杂度。这样不仅能帮助梳理 题目的约束,同时也可以发现题目的隐含性质。

        前面我们分析出添加的左右括号是互不影响的,所以接下来让我们先来尝试下如何用暴 力求解的左括号的添加方案数

        首先确定一种暴力方法,比如在每个右括号前添加若干个左括号从而产生若干个新的括号序列,再从中计算最短的合法括号序列的个数。

        假设原序列中有 cnt 个右括号,以这 cnt 个右括号为分界线,一共可以划分出 cnt+1 个区域:区域 1 )区域 2 ) 区域 3 )... ) 区域 cnt+1。显然我们只能在第1∼cnt个区域添加左 括号,因为若是在第cnt+1区域添加左括号,将不会有右括号可以与它匹配。

         那每个区域要添加多少个左括号呢?加多少个左括号都可以。因此我们可以枚举每个区域要添加的括号数。

        不过既然要枚举,就得设置一个枚举上限。很显然,我们添加的左括号数不可能大于原序列中的右括号数,所以可以设置每个区域的上限为原序列中的右括号数cnt。

        设置完上限后,我们就可以从第一个区域开始依次枚举要添加的左括号数。

         当第 cnt 个区域枚举结束后,将会得到一个全新的括号序列。根据枚举的不同,我们也将得到多个全新的、不同的括号序列。我们再从这些新的括号序列中计算长度最短的、合法 的序列个数,即可得到答案。

        可问题又来了,如何判断一个括号序列是否合法呢?

        这个简单。我们添加左括号的目的是为了让原序列中的每个右括号之前都有对应的左括号与其相匹配,所以只要新的括号序列中的每个右括号之前有对应的左括号可以与其相匹配 即为合法序列。

        上述整个过程可以使用DFS来实现。

参考代码如下【时间复杂度为 O(len×cnt^{cnt})】

#include <bits/stdc++.h>
using namespace std;int n, cnt, ans, min_len = 0x3f3f3f3f;
string s;bool check(string s) {int left = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') left++;else left--;if (left < 0) return false;}return true;
}void dfs(int p, string new_s) {if (p == n) { // 枚举结束if (check(new_s)) { // 判断这个新的括号序列是否合法if (new_s.size() == min_len) ans++; // 如果长度和最小长度相同,则答案个数+1else if (new_s.size() < min_len) {min_len = new_s.size();ans = 1; // 如果长度比最小长度还短,则作为新的最小长度}}return;}if (s[p] == '(')dfs(p + 1, new_s + '(');else {for (int i = 0; i <= cnt; i++) { // 如果是右括号, 则在该右括号前枚举要添加的左括号个数istring add = "";for (int j = 1; j <= i; j++) add += '(';dfs(p + 1, new_s + add + ')');}}
}signed main() {cin >> s;n = s.size();for (int i = 0; i < s.size(); i++)if (s[i] == ')') cnt++;dfs(0, "");cout << ans << '\n';return 0;
}

        以上的暴力做法对于第1∼cnt个区域都从0∼cnt枚举了要添加的左括号个数,这无 疑产生了大量不合法的括号序列,那要如何减少不合法的括号数呢?可以从每个区域的枚举上限入手。

        我们令每个区域的枚举上限都为cnt的理由是“添加的左括号数不可能大于原序列中的右括号数”。这里添加的左括号数指的是所有区域的总添加数,而不是单一区域的添加数。

        因此,我们可以设置一个动态的枚举上限total来简单优化一下枚举的次数(详见下方代码)。 

参考代码如下

void dfs(int p, string new_s, int total) { // total表示还可以添加的左括号数。在开始DFS之前,total = cntif (p == n) { // 枚举结束if (check(new_s)) { // 判断这个新的括号序列是否合法if (new_s.size() == min_len)ans++; // 如果长度和最小长度相同,则答案个数+1else if (new_s.size() < min_len) {min_len = new_s.size();ans = 1; // 如果长度比最小长度还短,则作为新的最小长度}}return;}if (s[p] == '(')dfs(p + 1, new_s + '(', total);else {for (int i = 0; i <= total; i++) { // 如果是右括号, 则在该右括号前枚举要添加的左括号个数istring add = "";for (int j = 1; j <= i; j++)add += '(';dfs(p + 1, new_s + add + ')', total - i); // 当前区域添加了i个左括号,那后面的区域可以添加的左括号总数为total-i}}
}

        与优化前相比,虽然上述方法能一定程度上减少一些不合法的括号序列,但产生的不合法括号序列依旧很多,这并不能起到很有效的作用。

         那还能进行哪些优化呢?我们重新思考这句话:添加的左括号数不可能大于原序列中的右括号数。既然如此,那到底要添加多少左括号呢?

        回顾一下,我们添加左括号的目的是让原序列中的每个右括号的前面都有对应的左括号 与其相匹配。也就是说,只有在原序列中的某个右括号之前没有可以与其相匹配的左括号时, 我们才有必要添加左括号。

         例如,对于括号序列 ) ( ( ) ) ) ,它的第1个右括号前没有可以与其相匹配的左括号,所 以我们至少要添加1个左括号;第2∼3个右括号前都有左括号可以与其相匹配,所以至少 要添加的左括号个数为0;第4个右括号前没有可以与其相匹配的左括号,所以我们至少要添加1个左括号。

        有了这个条件,我们就可以制定贪心策略:只有当必须要添加左括号时才添加左括号,这样就可以保证我们添加的括号总数最小(记添加的最小总数为need),相关代码参考完整代 码的第26∼31行。

        这样我们就可以将枚举上限设置为need(need⩽cnt),从而减少不合法括号序列的 产生。不过很显然这优化力度还远远不够,甚至在最坏的情况下(need=cnt)起不到任何作用。

        那还有什么办法可以优化呢?能不能一次性避免所有不合法括号序列的产生呢?

        答案自然是“能”。只要保证产生的括号序列都是合法的即可避免不合法括号序列的产生。

        那如何保证产生的括号序列都是合法的呢?只要保证每个右括号之前都有可以与之匹配的左括号即可。

        于是我们就可以在DFS过程中记录未匹配的左括号个数,当某个右括号之前未匹配的 左括号个数为0时,我们就必须添加左括号(从1开始枚举添加的左括号个数)。这样就能保证产生的括号序列都是合法的,也就不需要用 check() 函数来判断序列的合法性。完整代码如下。

参考代码如下

#include <bits/stdc++.h>
using namespace std;int n, cnt, ans, min_len = 0x3f3f3f3f;
string s;void dfs(int p, string new_s, int total, int left) {if (p == n) { // 枚举结束if (new_s.size() == min_len)ans++; // 如果长度和最小长度相同,则答案个数+1else if (new_s.size() < min_len) {min_len = new_s.size();ans = 1; // 如果长度比最小长度还短,则作为新的最小长度}return;}if (s[p] == '(')dfs(p + 1, new_s + '(', total, left + 1); // 未匹配的左括号个数+1else {int st = 0; // 枚举起点if (left == 0) st = 1; // 该右括号之前未匹配的左括号个数为0,那么为了保证序列合法,它之前至少要添加一个左括号for (int i = st; i <= total; i++) { // 如果是右括号,则在该右括号前枚举要添加的左括号个数i,从st开始枚举string add = "";for (int j = 1; j <= i; j++)add += '(';dfs(p + 1, new_s + add + ')', total - i, left + i - 1); // 需要从未匹配的左括号中拿出一个和当前右括号匹配,所以要-1}}
}signed main() {cin >> s;n = s.size();for (int i = 0; i < s.size(); i++)if (s[i] == ')')cnt++;int need = 0, left = 0; // need表示最少需要添加的左括号数,left表示未匹配的左括号个数for (int i = 0; i < s.size(); i++) {if (s[i] == '(')left++; // 未匹配的左括号个数+1elseleft--; // 拿走一个左括号与该右括号匹配,左括号个数-1if (left < 0)need++, left = 0; // 该右括号之前没有左括号可以与其匹配,此时就必须添加左括号}dfs(0, "", need, 0);cout << ans << '\n';return 0;
}

        以上就是暴力求解左括号添加方案数的过程,右括号添加方案数的求解类似,就不过多阐述。

         暴力的优化到此结束。

         可见,采用暴力解法虽然可以避免所有不合法括号序列的产生,但产生出的合法括号序列的数量也相当多,因此我们无法通过“暴力”来解决本题。

方式2:能拿40%分数的做法
        1. 求原括号序列中第 i (1 ⩽ i ⩽cnt ) 个右括号之前的左括号数

        我们虽然求解了need(最少需要添加的左括号数),但这个 need 是对于整个括号序列的。而对于原括号序列的某个右括号,我们并不知道它之前必须要添加多少个左括号。

        于是我们可以定义原括号序列中第i个右括号之前的左括号数为num[i],那么第 i 个右括号之前需要添加的左括号数就等于i−num[i]。

         num[i] 的求解如下。

参考代码如下:

int left = 0, cnt = 0;
for (int i = 1; i <= n; i++) {if (s[i] == ')') {num[++cnt] = left;}if (s[i] == '(') {left++; // left 表示原序列区间[1, i]的左括号个数}
}
        2. 计算方案数 

        通过前面的步骤,我们将问题转换成了 “ 往cnt个区域中添加need个左括号的合法方案数 ” 的求解。

        假设现在有i个区域(右括号),一共往这个i个区域中添加了j个左括号,要想得出其中的合法方案数,该怎么计算呢?

        我们可以先定义 dp[i][j]  来表示往前 i 个区域中共添加了 j 个左括号后的所有合法方案数,而往前i个区域中添加了j个左括号相当于往前i−1个区域中添加了k(0 ⩽ k ⩽j )个 左括号,并往第i个区域中添加了 j−k 个左括号。由此,我们可以就可推出dp[i][j]的状态 转移式。

提示如下:

        不过要想求解dp[i][j] ,只有状态转移式还不够,我们还需确定其初状态(即确定i=1 时dp[1][j] 对应的值)。

         i =1 时的特殊情况我们可以分为以下两部分讨论。

         (1)j ∈(1∼need)。显然,前 1 个区域(右括号)添加了1,2,3, ..., need 个左括号的 方案数都为1(need 表示最少需要添加的左括号个数),所以dp[1][1∼need]=1。

        (2)j =0。这部分又可细分为两种情况。

                 • 第1个区域包含原序列的左括号,那么dp[1][0] = 1,即前 1 个区域(右括号) 添加了0个左括号的方案数为1。

                 • 第1个区域不包含原序列的左括号,那么j=0是不合法的,该情况不能作为一 个方案(对于一个合法序列的任意前缀,左括号的个数一定要大于等于右括号), 所以dp[1][0] = 0 。 

由于我们要的是合法序列,所以当右括号的个数为i时,它前面的左括号的个数必然大 于等于i,即添加的左括号数j +原序列的左括号数num[i]⩾i。

        接下来,我们就可以完成dp[i][j] 的求解。

参考代码如下

for (int i = 1; i <= need; i++) dp[1][i] = 1;if (num[1] > 0) dp[1][0] = 1;for (int i = 2; i <= cnt; i++) {// 1. j + num[i] >= i// 2. 最少添加的数量为needfor (int j = i - num[i]; j <= need; j++) {for (int k = 0; k <= j; k++) {dp[i][j] += dp[i-1][k];dp[i][j] %= mod;}}
}

答案可用dp[cnt][need]表示,即前cnt个区域添加了need个左括号的所有合法方案数。

        至此,添加左括号的方案数就计算完成了。

         对于右括号的添加方案,我们可以将原括号序列反转,并令(为)、)为(,然后按照求左 括号的方案数的方法再求一遍即可。 

参考代码如下【时间复杂度为O(N^{3})】

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 5e3 + 10, mod = 1e9 + 7;
string s;
int dp[N][N], num[N];int calc(int need, bool flag) {memset(dp, 0, sizeof(dp));memset(num, 0, sizeof(num));// flag=1表示统计添加左括号的方案数; flag=0表示统计添加右括号的方案数(翻转)if (!flag) {reverse(s.begin(), s.end());for (int i = 0; i < s.size(); i++) {if (s[i] == ')') s[i] = '(';else s[i] = ')';}}int left = 0, cnt = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == ')') num[++cnt] = left; // cnt为右括号的编号if (s[i] == '(') left++; // left表示原序列区间[1, i]的左括号的个数}// 区域1有左括号时dp[1][0] = 1, 否则dp[1][0] = 0if (num[1] > 0) dp[1][0] = 1;for (int i = 1; i <= cnt; i++) dp[1][i] = 1;for (int i = 2; i <= cnt; i++) {// 1. j + num[i] >= i// 2. 最少添加的数量为needfor (int j = max(0LL, i - num[i]); j <= need; j++) {for (int k = 0; k <= j; k++) {dp[i][j] += dp[i-1][k];dp[i][j] %= mod;}}}return dp[cnt][need];
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> s;int need = 0, tmp = 0; // need表示最少需要添加的左括号数,tmp表示序列前缀和for (int i = 0; i < s.size(); i++) {if (s[i] == '(') tmp++;else tmp--;if (tmp < 0) need++, tmp++; // tmp < 0表示右括号数大于左括号数,此时需要添加左括号使得左括号数>=右括号数}int need2 = tmp;cout << calc(need, 1) * calc(need2, 0) % mod << '\n';return 0;
}
方式3:满分做法

         要想拿满分需要在 “ 方式2:能拿40%分数做法 ” 的步骤上作进一步优化。

         在上述步骤中,我们得到dp[i][j]=dp[i−1][0]+dp[i−1][1]+...+dp[i−1][j]。

        如果接触过“完全背包”,那就应该联想到用完全背包的前缀和来优化:

已知:::::

        

移项得:::

再令 j = j − 1,得::: 

        这样就可以去掉一层循环,复杂度为O(N^{2})。 不过需要注意,这是前缀和优化,也就是要使dp[i][j]=dp[i−1][j]+dp[i][j−1],须满 足所有的dp[i][j] = 

        而我们在求解dp[i][j] 时,有以下两种情况。

        所以dp[i][j] = dp[i−1][j] +dp[i][j − 1] 的转移并不完全合法。

         那怎么办呢?

        我们可以用类似的方法来优化。 定义pre[] 数组。 

        这样时间复杂度就优化到了O(N^{2})。 

参考代码6-3-7 【时间复杂度为 O(N^{2})】

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 5e3 + 10, mod = 1e9 + 7;
string s;
int dp[N][N], num[N], pre[N], nex[N];// 计算方案数
int calc(int need, bool flag) {if (!need) return 1; // 不需要添加括号也是一种方案memset(dp, 0, sizeof(dp));memset(num, 0, sizeof(num));memset(pre, 0, sizeof(pre));memset(nex, 0, sizeof(nex));// flag = 1 表示统计添加左括号的方案数; flag = 0 表示统计添加右括号的方案数(翻转)if (!flag) {reverse(s.begin(), s.end());for (int i = 0; i < s.size(); i++) {if (s[i] == ')') s[i] = '(';else s[i] = ')';}}int left = 0, cnt = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == ')') num[++cnt] = left; // cnt为右括号的编号if (s[i] == '(') left++; // left表示原序列区间[1, i]的左括号的个数}// 区域1有左括号时dp[1][0] = 1, 否则dp[1][0] = 0if (num[1] > 0) dp[1][0] = 1, pre[0] = 1;for (int i = 1; i <= cnt; i++) dp[1][i] = 1, pre[i] = pre[i - 1] + 1;for (int i = 2; i <= cnt; i++) {for (int j = 0; j <= need; j++) nex[j] = 0;for (int j = max(0LL, i - num[i]); j <= need; j++) {dp[i][j] = pre[j];if (j - 1 < 0) nex[j] = dp[i][j];else nex[j] = (nex[j - 1] + dp[i][j]) % mod;}for (int j = 0; j <= need; j++) pre[j] = nex[j]; // 先用nex[]存储dp[i-1]的信息,再将nex[]的值赋给pre[],这样下次循环pre[]存的值就是dp[i-1]的值}return dp[cnt][need];
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> s;int need = 0, pre = 0; // need表示最少需要添加的左括号数,pre表示序列前缀和for (int i = 0; i < s.size(); i++) {if (s[i] == '(') pre++;else pre--;if (pre < 0) need++, pre++; // pre < 0表示右括号数大于左括号数,此时需要添加左括号使得左括号数>=右括号数}int need2 = pre;cout << calc(need, 1) * calc(need2, 0) % mod << '\n';return 0;
}

 四、异或三角

【问题描述】

        给定T个数n1,n2,...,nT,对每个ni请求出有多少组a,b,c满足:

        (1)1⩽a,b,c⩽ni;

        (2)a⊕b⊕c=0,其中⊕表示二进制按位异或;

        (3)长度为a,b,c的三条边能组成一个三角形。

【输入格式】

        输入的第一行包含一个整数T。

        接下来T行每行一个整数,分别表示n1,n2,...,nT。

【输出格式】

        输出T行,每行包含一个整数,表示对应的答案。

【样例输入】

        

【样例输出】

        

【评测用例规模与规定】

        对于10%的评测用例,T=1,1⩽ni⩽200;

        对于20%的评测用例,T=1,1⩽ni⩽2000;

        对于50%的评测用例,T=1,1⩽ni⩽220;

        对于60%的评测用例,1⩽T⩽100000,1⩽ni⩽220;

        对于所有评测用例,1⩽T⩽100000,1⩽ni⩽230。

解析:

        题目对于我们要求解的a,b,c 设定了两个十分重要的限制条件。

         • 限制条件1: a ⊕ b ⊕ c=0。

        • 限制条件2: 长度为a,b,c 的三条边能组成一个三角形。

这两个条件不难解读。

         根据异或运算的归零律(相同数的异或值为0)可得

         • (a⊕b)=c。

         • (b⊕c) =a。

         • (a⊕c)=b。

         根据三角形的不等式定理(两边之和大于第三边)可得

        • a+b>c。

        • a+c>b。

        • b+c>a。

         解读完两个限制条件后,我们进入解题环节。

(这里我们不再赘述,直接给100%满分做法)

        对于50%、60%分数做法的测试数据,因为a的最大范围为220=1048576,所以我们 可以通过枚举来确定a。但在满分做法的测试数据中,n的最大范围为230次方,显然,枚举是不可能的了。

        那怎么办呢?

        回顾一下我们先前对于各个得分点的处理步骤。

         (1)10%分数:暴力枚举3个数并统计答案。

         (2)20%分数:无法枚举3个数,转换成枚举两个数,通过两个数的异或计算得到第三 个数并统计答案。

        (3)50%分数、60%分数:无法枚举两个数,转换成枚举一个数、数位dp一个数,通过两个数的异或计算得到第三个数并统计答案。

         既然此前我们在无法枚举一个数时,使用数位dp来代替处理,那么现在无法枚举a时, 是不是也能用数位dp来代替处理呢?

        下面来尝试一下。

        还是以a为最大值,先对其进行处理。对于a,由于它是第一个要确定的数,因此我们仅须对它增设一个限制条件:a < n (将其上界定为n即可)

        接下来考虑b(此时a已确定)

参考代码如下【时间复杂度为O(Tlog^{2})(常数较大,请务必进行卡常数优化)】

#pragma GCC target("avx2,fma")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;// 快速读取整数
template<typename T>
void read(T &res) {bool flag = false;char ch;while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48);flag && (res = -res);
}// 快速输出整数
template<typename T>
void Out(T x) {if (x < 0) putchar('-'), x = -x;if (x > 9) Out(x / 10);putchar(x % 10 + '0');
}int n, dp[32][2][2][2][2], num[32];// 深度优先搜索
inline int dfs(int len, bool limit1, bool limit2, bool ok1, bool ok2) {if (!len) return ok2 ? 1 : 0;if (~dp[len][limit1][limit2][ok1][ok2]) return dp[len][limit1][limit2][ok1][ok2];int up1 = limit1 ? num[len] : 1, res = 0;for (int i = 0; i <= up1; i++) {int up2 = limit2 ? i : 1;for (int j = 0; j <= up2; j++) {if (!ok1 && !i && j) continue;res += dfs(len - 1, limit1 && i == up1, limit2 && j == up2, ok1 || (j == i && j == 1), ok2 || (j == 1 && j != i));}}return dp[len][limit1][limit2][ok1][ok2] = res;
}// 解决问题
inline int solve(int n) {memset(dp, -1, sizeof(dp));int len = 0;while (n) {num[++len] = n & 1;n >>= 1;}return dfs(len, 1, 1, 0, 0);
}signed main() {int T = 1;read(T);while (T--) {read(n);Out(solve(n) * 3), putchar('\n');}return 0;
}

别忘了请点个赞+收藏+关注支持一下博主喵!!!!  !  !  !

关注博主,更多蓝桥杯nice题目静待更新:)

 

相关文章:

蓝桥杯c++算法秒杀【6】之动态规划【下】(数字三角形、砝码称重(背包问题)、括号序列、异或三角:::非常典型的必刷例题!!!)

别忘了请点个赞收藏关注支持一下博主喵&#xff01;&#xff01;&#xff01;! ! ! ! &#xff01; 关注博主&#xff0c;更多蓝桥杯nice题目静待更新:) 动态规划 三、括号序列 【问题描述】 给定一个括号序列&#xff0c;要求尽可能少地添加若干括号使得括号序列变得合…...

MR30分布式 IO 模块在冷却水泵系统中的卓越应用

在当今各类工业生产以及大型设施运行的场景中&#xff0c;冷却水泵系统起着至关重要的作用&#xff0c;它犹如保障整个运转体系顺畅运行的 “血液循环系统”&#xff0c;维持着设备适宜的温度环境&#xff0c;确保其稳定、高效地工作。而随着科技的不断发展&#xff0c;明达技术…...

微前端基础知识入门篇(二)

概述 在上一篇介绍了一些微前端的基础知识,详见微前端基础知识入门篇(一)。本文主要介绍qiankun微前端框架的实战入门内容。 qiankun微前端实践 通过Vite脚手架分别创建三个程序,主应用A为:vite+vue3+ts,两个微应用分别为B:vite+vue3+ts;C:vite+React+ts。因为qiankun的…...

直接抄作业!Air780E模组LuatOS开发:位运算(bit)示例

在嵌入式开发中&#xff0c;位运算是一种高效且常用的操作技巧。本文将介绍如何使用Air780E模组和LuatOS进行位运算&#xff0c;并通过示例代码帮助读者快速上手。 一、位运算概述 位运算是一种在计算机系统中对二进制数位进行操作的运算。由于计算机内部数据的存储和处理都是…...

从零开始理解JVM:对象的生命周期之对象销毁(垃圾回收)

一、JVM参数 在学垃圾回收器之前&#xff0c;我们先要知道&#xff0c;jvm参数是怎么回事。因为配置各种回收器&#xff0c;必须对应各种参数设置。 标准参数&#xff08;-&#xff09; 所有的JVM实现都必须实现这些参数的功能&#xff0c;而且向后兼容 -help-version 非标准参…...

计算机网络的发展

目录 起源与早期发展 ARPANET与TCP/IP协议的诞生 互联网的诞生与普及 高速互联网与无线网络的兴起 移动互联网与云计算的崛起 物联网、区块链与自动驾驶技术的兴起 起源与早期发展 计算机网络的雏形最早可以追溯到20世纪60年代&#xff0c;主要是为了共享大型计算资源。当…...

python3 自动更新的缓存类

这个类会在后台自动更新缓存数据&#xff0c;你只需要调用方法来获取数据即可。 自动更新缓存类 以下是 AutoUpdatingCache 类的实现&#xff1a; import threading import timeclass AutoUpdatingCache:def __init__(self, update_function, expiry_time60):""&qu…...

PICO 获取设备号 SN码

Unity版本 2020.3.42f1c1PICO SDK版本PICO Unity Integration SDK-3.0.5-20241105Pico设备pico 4ultra 注意 此api暂时只测试企业版本 pico 4ultra 代码 using Unity.XR.PICO.TOBSupport;private void Awake() {bool result PXR_Enterprise.InitEnterpriseService();Debug.L…...

spf算法、三类LSA、区间防环路机制/规则、虚连接

1.构建spf树&#xff1a; 路由器将自己作为最短路经树的树根根据Router-LSA和Network-LSA中的拓扑信息,依次将Cost值最小的路由器添加到SPF树中。路由器以Router ID或者DR标识。广播网络中DR和其所连接路由器的Cost值为0。SPF树中只有单向的最短路径,保证了OSPF区域内路由计管不…...

计算机基础(下)

内存管理 内存管理主要做了什么&#xff1f; 操作系统的内存管理非常重要&#xff0c;主要负责下面这些事情&#xff1a; 内存的分配与回收&#xff1a;对进程所需的内存进行分配和释放&#xff0c;malloc 函数&#xff1a;申请内存&#xff0c;free 函数&#xff1a;释放内存…...

OpenCV从入门到精通实战(七)——探索图像处理:自定义滤波与OpenCV卷积核

本文主要介绍如何使用Python和OpenCV库通过卷积操作来应用不同的图像滤波效果。主要分为几个步骤&#xff1a;图像的读取与处理、自定义卷积函数的实现、不同卷积核的应用&#xff0c;以及结果的展示。 卷积 在图像处理中&#xff0c;卷积是一种重要的操作&#xff0c;它通过…...

Java基础——(一)Java概述

Java特性 简单性&#xff1a;Java与C很相似&#xff0c;但剔除了C中许多比较复杂并且很少使用的功能&#xff0c;比如头文件、指针运算、结构、联合、操作符重载、虚基类等&#xff0c;从而使Java更易于上手、学习。面向对象&#xff1a;Java是一门面向对象语言&#xff0c;具…...

关于IDE的相关知识之三【插件安装、配置及推荐的意义】

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///C爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于ide插件安装、配置及推荐意义的相关内容…...

C++设计模式之组合模式的基本结构

组合模式的UML类图表示如下&#xff1a; ------------------ ------------------ | Component | <----- | Leaf | ------------------ ------------------ | operation() | | operation() | ------------------ --…...

Apache OFBiz xmlrpc XXE漏洞(CVE-2018-8033)

目录 1、漏洞描述 2、EXP下载地址 3、EXP利用 1、漏洞描述 Apache OFBiz是一套企业资源计划&#xff08;ERP&#xff09;系统。它提供了广泛的功能&#xff0c;包括销售、采购、库存、财务、CRM等。 Apache OFBiz还具有灵活的架构和可扩展性&#xff0c;允许用户根据业务需求…...

梯度——多元函数偏导数——梯度算子的理论基础

梯度是一个数学概念&#xff0c;在多维空间中表示函数在某一点处变化最快的方向和变化率。 对于一个多元函数 f ( x 1 , x 2 , ⋯ , x n ) f(x_1, x_2, \cdots, x_n) f(x1​,x2​,⋯,xn​)&#xff0c;其梯度是一个向量&#xff0c;记作 ∇ f \nabla f ∇f或者 grad f f f&…...

【GPT】力量训练的底层原理?

详细解读力量训练的每一个底层原理 力量训练之所以有效&#xff0c;是因为它利用了肌肉、神经系统和生物化学反应的基本机制。以下逐一详细解析&#xff0c;并解释相关概念。 1. 应力-恢复-适应理论 概念解析 应力&#xff08;Stress&#xff09;&#xff1a;指训练带来的负…...

Django 路由层

1. 路由基础概念 URLconf (URL 配置)&#xff1a;Django 的路由系统是基于 urls.py 文件定义的。路径匹配&#xff1a;通过模式匹配 URL&#xff0c;并将请求传递给对应的视图处理函数。命名路由&#xff1a;每个路由可以定义一个名称&#xff0c;用于反向解析。 2. 基本路由配…...

Unity项目性能优化列表

1、对象池 2、检查内存是否泄露。内存持续上升(闭包、委托造成泄露) 3、检查DrawCall数量&#xff0c;尽量减少SetPassCall 4、尽量多的利用四种合批 动态合批(Dynamic Batching)静态合批(Static Batching)GPUInstancingSRP Batcher 动态合批消耗内存把多个网格组合在一起合并…...

docker启动kafka、zookeeper、kafdrop

1、启动zookeeper docker run -d --name zookeeper -p 2181:2181 -t wurstmeister/zookeeper2、启动kafka docker run -d --name kafka --publish 9092:9092 --link zookeeper:zookeeper -e KAFKA_BROKER_ID1 -e HOST_IP127.0.0.1 -e KAFKA_ZOOKEEPER_CONNECTzookeeper:2181…...

Pytest使用Jpype调用jar包报错:Windows fatal exception: access violation

问题描述 ​   之前我们有讲过如何使用Jpype调用jar包&#xff0c;在成功调用jar包后&#xff0c;接着在Pytest框架下编写自动测试用例。但是在Pytest下使用Jpype加载jar包&#xff0c;并调用其中的方法会以下提示信息&#xff1a; ​   虽然提示信息显示有Windows显示致命…...

【AI赋能 Python编程】第十一章 Python技能提升指南:借助AI加速学习

AI赋能 Python编程-系列文章目录 第十一章 Python技能提升指南&#xff1a;借助AI加速学习 文章目录 AI赋能 Python编程-系列文章目录第十一章 Python技能提升指南&#xff1a;借助AI加速学习 前言明确学习目标基础入门指导进阶学习指导学习过程互动综合学习提示模板 前言 在…...

️ 爬虫开发中常见的性能优化策略有哪些?

在爬虫开发中&#xff0c;性能优化是确保爬虫稳定、高效运行的关键。以下是一些常见的性能优化策略&#xff0c;结合了搜索结果中的信息&#xff1a; 异步编程&#xff1a; 使用 asyncio 和 aiohttp 实现高并发&#xff0c;提高爬取效率。异步请求允许在等待一个请求完成的同时…...

Ubuntu安装不同版本的opencv,并任意切换使用

参考&#xff1a; opencv笔记&#xff1a;ubuntu安装opencv以及多版本共存 | 高深远的博客 https://zhuanlan.zhihu.com/p/604658181 安装不同版本opencv及共存、切换并验证。_pkg-config opencv --modversion-CSDN博客 Ubuntu下多版本OpenCV共存和切换_ubuntu20如同时安装o…...

《操作系统 - 清华大学》5 -4:虚拟技术

文章目录 0. 虚拟存储的定义1. 目标2.局部性原理3. 虚拟存储的思路与规则4. 虚拟存储的基本特征5. 虚拟页式存储管理5.1 页表表项5.2 示例 0. 虚拟存储的定义 1. 目标 虚拟内存管理技术&#xff0c;简称虚存技术。那为什么要虚存技术&#xff1f;在于前面覆盖和交换技术&#…...

网安瞭望台第5期 :7zip出现严重漏洞、识别网络钓鱼诈骗的方法分享

国内外要闻 7 - Zip存在高危漏洞&#xff0c;请立刻更新 2024 年 11 月 24 日&#xff0c;do son 报道了 7 - Zip 中存在的一个高严重性漏洞 CVE - 2024 - 11477。7 - Zip 是一款广受欢迎的文件压缩软件&#xff0c;而这个漏洞可能会让攻击者在存在漏洞的系统中执行恶意代码。…...

【JS】面试八股文

类型 JavaScript 有哪些数据类型,它们的区别? 答:JavaScript 共有八种数据类型, 分别是 Undefined、 Null、 Boolean、Number、String、Object、Symbol、BigInt。 其中 Symbol是ES6中新增的,BigInt 是 ES2020 中新增的。 Symbol 代表创建后独一无二且不可变的数据类型,…...

1、正则表达式

grep匹配 grep用来过滤文本内容&#xff0c;以匹配要查询的结果。 grep root /etc/passwd&#xff1a;匹配包含root的行 -m 数字&#xff1a;匹配几次后停止 -v&#xff1a;取反-i&#xff1a;忽略字符的大小写&#xff0c;默认的&#xff0c;可以不加-n&#xff1a…...

带有悬浮窗功能的Android应用

android api29 gradle 8.9 要求 布局文件 (floating_window_layout.xml): 增加、删除、关闭按钮默认隐藏。使用“开始”按钮来控制这些按钮的显示和隐藏。 服务类 (FloatingWindowService.kt): 实现“开始”按钮的功能&#xff0c;点击时切换增加、删除、关闭按钮的可见性。处…...

uniapp开发微信小程序笔记8-uniapp使用vant框架

前言&#xff1a;其实用uni-app开发微信小程序的首选不应该是vant&#xff0c;因为vant没有专门给uni-app设置专栏&#xff0c;可以看到目前Vant 官方提供了 Vue 2 版本、Vue 3 版本和微信小程序版本&#xff0c;并由社区团队维护 React 版本和支付宝小程序版本。 但是我之前维…...

C++软件设计模式之组合模式与其他模式的协作举例

组合模式&#xff08;Composite Pattern&#xff09;、装饰器模式&#xff08;Decorator Pattern&#xff09;、享元模式&#xff08;Flyweight Pattern&#xff09;、迭代器模式&#xff08;Iterator Pattern&#xff09;和访问者模式&#xff08;Visitor Pattern&#xff09;…...

ArcGIS pro中的回归分析浅析(加更)关于广义线性回归工具的补充内容

在回归分析浅析中篇的文章中&#xff0c; 有人问了一个问题&#xff1a; 案例里的calls数据貌似离散&#xff0c;更符合泊松模型&#xff0c;为啥不采用泊松而采用高斯呢&#xff1f; 确实&#xff0c;在中篇中写道&#xff1a; 在这个例子中我们为了更好地解释变量&#x…...

mybatis-plus 实现分页查询步骤

MyBatis-Plus 是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。它提供了代码生成器、条件构造器、分页插件等多种功能&#xff0c;其中分页查询是一个常用的功能。 以下是如何在 MyBatis-Plus 中实现分页查询…...

Vue开发中常见优化手段总结

Tree Shaking or Trunk 动态引入&#xff08;Dynamic Imports&#xff09; 动态引入是指在代码执行过程中&#xff0c;根据需要动态加载模块&#xff0c;而不是在应用启动时一次性加载所有模块。这可以通过JavaScript的import()函数实现&#xff0c;它返回一个Promise对象&…...

IDEA无法创建java8、11项目创建出的pom.xml为空

主要是由于Spring3.X版本不支持JDK8&#xff0c;JDK11&#xff0c;最低支持JDK17 解决的话要不就换成JDK17以上的版本&#xff0c;但是不太现实 另外可以参考以下方式解决 修改spring初始化服务器地址为阿里云的 https://start.aliyun.com/...

TCP/IP网络编程-C++(上)

TCP/IP网络编程-C &#xff08;上&#xff09; 一、基于TCP的服务端/客户端1、server端代码2、client端代码3、socket() 函数3.1、函数原型3.2、参数解析3.2.1、协议族&#xff08;domain参数&#xff09;3.2.2、套接字类型&#xff08;type参数&#xff09;3.2.3、最终使用的协…...

在线绘制Nature Communication同款双色、四色火山图,突出感兴趣的基因

导读&#xff1a;火山图通常使用三种颜色分别表示显著上调&#xff0c;显著下调和不显著。通过为特定的数据点添加另一种颜色&#xff0c;可以创建双色或四色火山图&#xff0c;从而更直观地突出感兴趣的数据点。 《Nature Communication》文章“Molecular and functional land…...

ctfshow pwn wp

文章目录 Test_your_ncpwn-0pwn1pwn2pwn3pwn4 前置基础pwn5pwn6pwn7pwn8pwn9pwn10pwn11pwn12pwn13&#xff1a;gcc编译执行C语言代码pwn14&#xff1a;gcc编译执行C语言代码pwn15&#xff1a;nasm编译asm&#xff0c;ld链接为可执行文件pwn16&#xff1a;gcc编译汇编文件.s为可…...

【数据结构实战篇】用C语言实现你的私有队列

&#x1f3dd;️专栏&#xff1a;【数据结构实战篇】 &#x1f305;主页&#xff1a;f狐o狸x 在前面的文章中我们用C语言实现了栈的数据结构&#xff0c;本期内容我们将实现队列的数据结构 一、队列的概念 队列&#xff1a;只允许在一端进行插入数据操作&#xff0c;在另一端…...

数据结构 (11)串的基本概念

一、串的定义 1.串是由一个或者多个字符组成的有限序列&#xff0c;一般记为&#xff1a;sa1a2…an&#xff08;n≥0&#xff09;。其中&#xff0c;s是串的名称&#xff0c;用单括号括起来的字符序列是串的值&#xff1b;ai&#xff08;1≤i≤n&#xff09;可以是字母、数字或…...

快速高效求素数|质数的方法—Java(模板)

判断素数|质数方法时间效率:线性筛法>埃氏筛法>试除法 在写算法题的时候&#xff0c;各种各样跟素数有关的题目非常常见&#xff0c;本文列出了三种常见的判断素数的方法 三种求素数方法的优缺点 一、试除法 试除法的基本思想是&#xff1a;判断一个数 x 是否为素数&…...

探秘嵌入式位运算:基础与高级技巧

目录 一、位运算基础知识 1.1. 位运算符 1.1.1. 与运算&#xff08;&&#xff09; 1.1.2. 或运算&#xff08;|&#xff09; 1.1.3. 异或运算&#xff08;^&#xff09; 1.1.4. 取反运算&#xff08;~&#xff09; 1.1.5. 双重按位取反运算符&#xff08;~~&#xf…...

iOS 17.4 Not Installed

0x00 系统警告 没有安装 17.4 的模拟器&#xff0c;任何操作都无法进行&#xff01; 点击 OK 去下载&#xff0c;完成之后&#xff0c;依旧是原样&#xff01; 0x01 解决办法 1、先去官网下载对应的模拟器&#xff1a; https://developer.apple.com/download/all/?q17.4 …...

RestTemplate 使用教程

RestTemplate 是 Spring 框架提供的一种用于执行HTTP请求的同步客户端。它简化了与HTTP服务器的交互&#xff0c;并支持RESTful Web服务。 1. 添加依赖 首先&#xff0c;确保你的项目中包含了Spring Web的支持。如果你使用的是Maven&#xff0c;在pom.xml文件中添加如下依赖&…...

windows下安装wsl的ubuntu,同时配置深度学习环境

写在前面&#xff0c;本次文章只是个人学习记录&#xff0c;不具备教程的作用。个别信息是网上的&#xff0c;我会标注&#xff0c;个人是gpt生成的 安装wsl 直接看这个就行&#xff1b;可以不用备份软件源。 https://blog.csdn.net/weixin_44301630/article/details/1223900…...

【贪心算法第五弹——300.最长递增子序列】

目录 1.题目解析 题目来源 测试用例 2.算法原理 3.实战代码 代码解析 注意本题还有一种动态规划的解决方法&#xff0c;贪心的方法就是从动态规划的方法总结而来&#xff0c;各位可以移步博主的另一篇博客先了解一下&#xff1a;动态规划-子序列问题——300.长递增子序列…...

【数据分析】基于GEE解析2000-2020年武汉市FVC时空变化特征

武汉市FVC时空变化特征解析 1. 写在前面2. 2000~2020年武汉市FVC时空变化特征解析2.1. 数据获取与预处理2.2. 辐射定标和大气校正2.3. 云层和云影去除2.4. FVC计算2.5. 时空分析2.6. 代码1. 写在前面 🌍✨在应对全球气候变化和环境监测的挑战中,植被盖度(Fraction Vegetati…...

springboot实战(19)(条件分页查询、PageHelper、MYBATIS动态SQL、mapper映射配置文件、自定义类封装分页查询数据集)

引言&#xff1a; 该类博客的学习是基于b站黑马视频springbootvue视频学习&#xff01;具体围绕项目——"大事件"进行实战学习。 目录 一、功能介绍&#xff08;需求&#xff09;。 1、文章列表功能基本介绍。 2、条件分页查询功能与注意。 3、前端页面效果。&#x…...

Mongo数据库 --- Mongo Pipeline

Mongo数据库 --- Mongo Pipeline 什么是Mongo PipelineMongo Pipeline常用的几个StageExplanation with example:MongoDB $matchMongoDB $projectMongoDB $groupMongoDB $unwindMongoDB $countMongoDB $addFields Some Query Examples在C#中使用Aggreagtion Pipeline**方法一: …...

Docker部署mysql:8.0.31+dbsyncer

Docker部署mysql8.0.31 创建本地mysql配置文件 mkdir -p /opt/mysql/log mkdir -p /opt/mysql/data mkdir -p /opt/mysql/conf cd /opt/mysql/conf touch my.config [mysql] #设置mysql客户端默认字符集 default-character-setUTF8MB4 [mysqld] #设置3306端口 port33…...