208.小红的二叉树构造✅

简单数学题：每一层的值是相同的，最小层值由节点最多的最后一行决定，即全被1填充，再乘以层数即可

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << pow(2, n - 1) * n << endl; 
    
    return 0;
}

※209.小红的节点染色❌

求方案数，想到回溯搜索，但是超时了

一般回溯深搜超时的，用DP解决

动态规划之状态机：定义dp[i][0/1]为前i个未染色的节点的能凑成和为偶数/奇数的方案数

状态转移公式：

• dp[i][0] =
  • dp[i-1][0] * 2 + 1（如果第i个节点权值为偶数）
  • dp[i-1][0] + dp[i-1][1]（如果第i个节点权值为奇数）
• dp[i][1] =
  • dp[i-1][1] * 2（如果第i个节点权值为偶数）
  • dp[i-1][0] + dp[i-1][1] + 1（如果第i个节点权值为奇数）

对于上面四个方程的解释：(光想明白状态转移公式想了一个小时)

1. 第i个节点权值为偶数，意味着：
   • 选择染色，加到偶数和方案（dp[i-1][0]），会变成偶数和方案；
   • 选择不染色，继承上一个偶数和方案（dp[i-1][0]），依然是偶数和方案；
   • 还可以选择单独这个节点开一个方案，也是偶数和方案，所以 +1
2. 第i个节点权值为奇数，意味着：
   • 选择染色，加到奇数和方案（dp[i-1][1]），会变成偶数和方案；
   • 选择不染色，继承上一个偶数和方案（dp[i-1][0]），依然是偶数和方案；
3. 第i个节点权值为偶数，意味着：
   • 选择染色，加到奇数和方案（dp[i-1][1]），会变成奇数和方案；
   • 选择不染色，继承上一个奇数和方案（dp[i-1][1]），依然是奇数和方案；
4. 第i个节点权值为奇数，意味着：
   • 选择染色，加到偶数和方案（dp[i-1][0]），会变成奇数和方案；
   • 选择不染色，继承上一个奇数和方案（dp[i-1][1]），依然是奇数和方案；
   • 还可以选择单独这个节点开一个方案，也是奇数和方案，所以 +1

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007; 
int main() {
    string str;
    cin >> str;
    int i = 1;
    vector<int> val;
    vector<int> tmp;
    for(; i < str.size(); i++) {
        tmp.push_back(str[i] - '0');
        i++;
        if(str[i] == ']') break;
    }
    i += 3;
    
    int k = 0, basic = 0, white = 0;
    val.push_back(0); // 为了循环dp时对齐下标
    for(; i < str.size() - 1; i++) {
        if(str[i] == 'R') basic += tmp[k];
        else {
            val.push_back(tmp[k]);
            white = 1; // 表明有未染色的节点
        }
        k++;
    }

    // 定义dp[i][0/1]为前i个未染色的节点的能凑成和为偶数/奇数的方案数
    vector<vector<int>> dp(val.size(), vector<int>(2, 0));
    // cout << "dp[0][0] = " << dp[0][0] << ", ";
    // cout << "dp[0][1] = " << dp[0][1] << endl;
    for(int i = 1; i < val.size(); i++) {
        if(val[i] % 2) { 
            dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD; // 注意一直取余，防止爆数
            dp[i][1] = (dp[i-1][0] + dp[i-1][1] + 1) % MOD;
        } else {
            dp[i][0] = (dp[i-1][0] * 2 + 1) % MOD;
            dp[i][1] = (dp[i-1][1] * 2) % MOD;
        }
        // cout << "dp[" << i << "][0] = " << dp[i][0] << ", ";
        // cout << "dp[" << i << "][1] = " << dp[i][1] << endl;
    }
    
    if(basic % 2) cout << dp[val.size()-1][1] % MOD << endl;
    else  cout << (dp[val.size()-1][0] + white) % MOD << endl;
 
    return 0;
}

210.最长合法子串长度❌