本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷CF149D Coloring Brackets - 洛谷【题目描述】给出一个配对的括号序列如 “(())() \texttt{(())()}(())()”、“() \texttt{()}()” 等“)() \texttt{)()})()”、“(() \texttt{(()}(()”是不符合要求的对该序列按照以下方法染色。一个括号可以染成红色、蓝色或者不染色。一对匹配的括号需要且只能将其中一个染色。相邻两个括号颜色不能相同但都可以不染色。求符合条件的染色方案数对1000000007 10000000071000000007取模。【输入】一行一个字符串s ss表示括号序列2 ⩽ ∣ s ∣ ⩽ 700 2 \leqslant |s| \leqslant 7002⩽∣s∣⩽700。【输出】一个数字表示染色的方案数对1000000007 10000000071000000007取模。【输入样例】(())【输出样例】12【算法标签】#提高plus #区间DP【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN705,mod1e97;// 定义常量和模数intn,match[N],ans;// n: 括号序列长度match: 匹配括号的位置ans: 答案intf[N][N][3][3];// DP数组f[i][j][x][y]表示区间[i,j]的染色方案数i染x色j染y色string s;// 括号序列stackintstk;// 用于括号匹配的栈signedmain(){cins;// 输入括号序列ns.length();// 获取长度s s;// 在字符串前加空格使下标从1开始for(inti1;in;i)// 括号匹配{if(s[i]()// 左括号入栈stk.push(i);else{// 右括号匹配match[stk.top()]i;// 记录匹配位置match[i]stk.top();stk.pop();// 弹出栈顶左括号}}// 区间DPfor(intlen2;lenn;len)// 枚举区间长度for(inti1;ilen-1n;i)// 枚举区间起点{intjilen-1;// 区间终点if(i1j)// 区间长度为2即一对括号{// 相邻括号的合法染色方案f[i][j][0][1]f[i][j][0][2]f[i][j][1][0]f[i][j][2][0]1;continue;}if(match[i]j)// i和j是匹配的括号{for(intx0;x2;x)for(inty0;y2;y){// 枚举内部区间的染色if(y!1)// 右括号不能染1f[i][j][0][1](f[i][j][0][1]f[i1][j-1][x][y])%mod;if(y!2)// 右括号不能染2f[i][j][0][2](f[i][j][0][2]f[i1][j-1][x][y])%mod;if(x!1)// 左括号不能染1f[i][j][1][0](f[i][j][1][0]f[i1][j-1][x][y])%mod;if(x!2)// 左括号不能染2f[i][j][2][0](f[i][j][2][0]f[i1][j-1][x][y])%mod;}}else// i和j不匹配{intkmatch[i];// i的匹配位置for(intx0;x2;x)for(inty0;y2;y)for(intp0;p2;p)for(intq0;q2;q){// 枚举四个端点的颜色if((p1q1)||(p2q2))// 相邻颜色不能相同continue;f[i][j][x][y](f[i][j][x][y]f[i][k][x][p]*f[k1][j][q][y]%mod)%mod;}}}// 统计答案for(inti0;i2;i)for(intj0;j2;j)ans(ansf[1][n][i][j])%mod;// 累加所有染色方案coutansendl;// 输出答案return0;}【运行结果】(()) 12
