url: https://www.luogu.com.cn/problem/CF149D

tag:
搜索，记忆化搜索，区间DP

思路：
使用 f[l][r][i][j] 表示区间l和r之间l为i色，r为j色时的染色方案数。有两种情况，当 l 和 r 配对时，可以由 l + 1 到 r - 1更新过来。如果不配对，由 l 到 第一个配对的括号这段区间和由那个括号后面的括号到 r 这段区间的方案数相乘。注意如果相邻的括号都有染色且颜色一样需要跳过。初始化是当 l + 1 == r 时，此时区间只有两个括号，对应的四个情况都只有一种方案。最后dfs之后将所有可能的答案相加并取模，然后输出即可。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <stack>  
using namespace std;  
const int N = 800;  
const int mod = 1000000007;  
char s[N];  
stack<int> stk;  
int rightt[N];  
int f[N][N][5][5];  
void dfs(int l, int r)  
{  
    if (l + 1 == r)  
    {  
        f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1;  
        return;  
    }  
    if (r == rightt[l])  
    {  
        dfs(l + 1, r - 1);  
        for (int i = 0; i <= 2; i ++)  
            for (int j = 0; j <= 2; j ++)  
            {  
                if (j != 1) f[l][r][0][1] += f[l + 1][r - 1][i][j], f[l][r][0][1] %= mod;  
                if (j != 2) f[l][r][0][2] += f[l + 1][r - 1][i][j], f[l][r][0][2] %= mod;  
                if (i != 1) f[l][r][1][0] += f[l + 1][r - 1][i][j], f[l][r][1][0] %= mod;  
                if (i != 2) f[l][r][2][0] += f[l + 1][r - 1][i][j], f[l][r][2][0] %= mod;  
            }  
    }  
    else  
    {  
        dfs(l, rightt[l]), dfs(rightt[l] + 1, r);  
        for (int i = 0; i <= 2; i ++)  
            for (int j = 0; j <= 2; j ++)  
                for (int p = 0; p <= 2; p ++)  
                    for (int q= 0; q <= 2; q ++)  
                    {  
                        if (j == 1 && p == 1 || j == 2 && p == 2) continue;  
                        f[l][r][i][q] += (f[l][rightt[l]][i][j] * f[rightt[l] + 1][r][p][q] % mod);  
                        f[l][r][i][q] %= mod;  
                    }  
    }  
}  
int main() {  
    scanf("%s", s + 1);  
    int n = strlen(s + 1);  
    for (int i = 1; i <= n; i++)  
    {  
        if (s[i] == '(') stk.push(i);  
        else  
        {  
            rightt[i] = stk.top();  
            rightt[stk.top()] = i;  
            stk.pop();  
        }  
    }  
    dfs(1, n);  
    int res = 0;  
    for (int i = 0; i <= 2; i ++)  
        for (int j = 0; j <= 2; j ++)  
            res += f[1][n][i][j], res %= mod;  
    cout << res << endl;  
    return 0;  
}

url: https://www.luogu.com.cn/problem/P1074

tag:
NOIP2009 提高组，搜索，剪枝，位运算，NOIP提高组，2009

思路：

1. 核心变量解析

• a[10][10]：存储数独棋盘，ai表示第i行第j格的数字（0表示空格）
• r[10]：行约束，r[i]的二进制第k位表示第i行能否填数字k+1（1表示可用）
• c[10]：列约束，c[j]的二进制第k位表示第j列能否填数字k+1
• e[5][5]：九宫格约束，ex的二进制第k位表示第x行第y列九宫格能否填k+1
• p[1<<11]：位掩码到数字的映射，p[1<<k]=k+1（快速获取候选数字）
• o[1<<10]：预计算二进制中1的个数，o[mask]表示mask的候选数字个数
• ans：存储最终的最大得分

2. 关键函数解析

• gs()：根据位置计算得分，边缘得分低，中心得分高（计算公式：值*(6+距边缘距离)）
• init()：初始化约束为全可用状态，预处理o[]和p[]的映射关系
• dfs()：采用最小候选数优先的回溯算法，通过位运算快速枚举候选值

3. 算法流程

• 预处理所有约束条件
• 优先选择候选数最少的格子进行填充（剪枝优化）
• 用位运算快速遍历所有候选数字
• 递归搜索时动态更新约束条件
• 达到填满状态时更新最大得分

4. 位运算优化点

• 用异或操作快速增删约束条件（r[i]^=mask）
• 用lowbit技巧遍历候选数字（t&-t获取最低位的1）
• 预计算o[]避免重复计算候选数个数

参考： https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路，爱了爱了。

代码：

#include <iostream>
using namespace std;
int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
int o[1 << 10];
int gs(int i, int j)
{
    return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
}
void init()
{
    for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
    for (int i = 0; i < (1 << 9); i ++)
    {
        int t = i;
        while (t)
        {
            t &= t -1;
            o[i] ++;
        }
    }
    for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
}
void dfs(int cnt, int sum)
{
    if (cnt == 0)
    {
        ans = max(ans, sum);
    }
    int mi = 10, x, y;
    for (int i = 0;  i< 9; i++)
        for (int j = 0; j < 9; j ++)
        {
            if (!a[i][j])
            {
                int t = r[i] & c[j] & e[i / 3][j / 3];
                if (o[t] < mi)
                {
                    mi = o[t], x = i, y = j;
                }
            }
        }
    int t = r[x] & c[y] & e[x / 3][y / 3];
    while (t)
    {
        int l = (t & -t);
        t -= l;
        a[x][y] = p[l];
        r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
        dfs(cnt -1, sum + gs(x, y));
        a[x][y] = 0;
        r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
    }
}
int main()
{
    init();
    int cnt = 0, sum = 0;
    for (int i = 0; i < 9;  i++)
        for (int j = 0; j < 9; j ++)
        {
            cin >> a[i][j];
            if (a[i][j])
            {
                r[i] -= 1 << a[i][j] - 1;
                c[j] -= 1 << a[i][j] - 1;
                e[i / 3][j / 3] -= 1 << a[i][j] -1;
                sum += gs(i, j);
            }else cnt ++;
        }
    dfs(cnt, sum);
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2476

tag:
SCOI2008，动态规划，搜索，记忆化搜索

思路：
开一个6维的数组来表示状态（因为每种情况有多种，所以不能用压位bit），分别表示足够涂1， 2， 3， 4， 5块木头的颜色有几种，最后一维表示上一种颜色的种类。然后用记忆化搜索来做。参考： https://www.luogu.com.cn/article/fhusu9wq

代码：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll MOD = 1e9 + 7;
int n, t[6];
ll dp[16][16][16][16][16][6];
ll dfs(int a, int b, int c, int d, int e, int last)
{
    if (dp[a][b][c][d][e][last] != -1) return dp[a][b][c][d][e][last];
    if (a + b + c + d + e == 0) return 1;
    ll res = 0;
    if (a) res += (a - (last == 2)) * dfs(a - 1, b, c, d, e, 1);
    if (b) res += (b - (last == 3)) * dfs(a + 1, b - 1, c, d, e, 2);
    if (c) res += (c - (last == 4)) * dfs(a, b + 1, c - 1, d, e, 3);
    if (d) res += (d - (last == 5)) * dfs(a, b, c + 1, d - 1, e, 4);
    if (e) res += e * dfs(a, b, c, d + 1, e - 1, 5);
    dp[a][b][c][d][e][last] = res % MOD;
    return dp[a][b][c][d][e][last];
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        t[a] ++;
    }
    memset(dp, -1, sizeof dp);
    ll ans = dfs(t[1], t[2], t[3], t[4], t[5], 0);
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1120

tag:
枚举，搜索，剪枝，dfs

思路：
先从大到小排序，并计算全部木棍长度的和。之后从最长的木棍长开始一直到和的一半枚举，作为原来木棍的长度。然后拿到这个原来的长度之后dfs一下看在有限段的情况下能不能拼凑出全部木棍，可以就输出。最后枚举完全部可能结果后都没答案，就输出长度和作为结果，表示原来只有一根木棍。参考： https://www.luogu.com.cn/article/fxoshw2y

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70;
int n, len, m, sum;
int a[N];
int nxt[N];
bool flag = false;
bool st[N];
bool cmp (int &a, int &b)
{
    return a > b;
}
void dfs(int k, int last, int rest)
{
    int i;
    if (!rest) {
        if (k == m)
        {
            flag = true;
            return;
        }
        for (i = 0; i < n; i ++) if (!st[i]) break;
        st[i] = true;
        dfs(k + 1, i, len - a[i]);
        st[i] = false;
        if (flag) return;
    }
    int l = last + 1, r = n - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] <= rest) r = mid;
        else l = mid + 1;
    }
    for (i = l; i < n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs(k, i, rest - a[i]);
            st[i] = false;
            if (flag) return;

            if (rest == a[i] || rest == len) return;
            i = nxt[i];
            if (i == n - 1) return;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + n, cmp);
    nxt[n - 1] = n;
    for (int i = n - 2; i >= 0; i --)
    {
        if (a [i] == a[i + 1]) nxt[i] = nxt[i + 1];
        else nxt[i] = i;
    }
    for (len = a[0]; len <= sum / 2; len ++)
    {
        if (sum % len != 0) continue;
        m = sum / len;
        st[0] = true;
        dfs(1, 0, len - a[0]);
        st[0] = false;
        if (flag)
        {
            cout << len << endl;
            return 0;
        }
    }
    cout << sum << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2195

tag:
树的直径，树形DP，dfs，搜索，并查集，图论

思路：
先用树形DP求出每棵树的直径，并用并查集维护联通情况。用数组c来维护树的直径。对于询问1，直接输出直径，对于询问2，如果不在一个集合中，直径可能是原来两棵树的直径和 + 1，和原来两棵树的直径取一个最大值。参考： https://www.luogu.com.cn/article/o2yhg6cs

代码：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 3e5 + 20;
int n, m, q, len;
int d[N], g[N];
int f[N], c[N];
vector<int> e[N];
bool st[N];
int find(int x)
{
    if (f[x] != x) return f[x] = find(f[x]);
    return x;
}
void dfs(int x, int fa)
{
    int m1 = -1, m2 = -1;
    for (int i = 0; i < e[x].size(); i ++)
    {
        int y = e[x][i];
        if (y == fa) continue;
        dfs(y, x);
        int tmp = d[y] + 1;
        d[x] = max(d[x], tmp);
        if (tmp > m1) m2 = m1, m1 = tmp;
        else if (tmp > m2) m2 = tmp;
    }
    g[x] = max(max(0, m1 + m2), max(m1, m2));
    len = max(len, g[x]);
}
void calc(int x)
{
    len = 0;
    dfs(x, 0);
    c[x] = len;
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++) f[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        f[find(a)] = find(b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (f[i] != i || st[i]) continue;
        calc(i);
        st[i] = 1;
    }
    while (q --)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
        {
            printf("%d\n", c[find(x)]);
            continue;
        }
        int y;
        scanf("%d", &y);
        x = find(x), y = find(y);
        if (x == y) continue;
        int tmp = ((c[x] + 1) >> 1) + ((c[y] + 1) >> 1) + 1;
        tmp = max(tmp, max(c[x], c[y]));
        f[find(x)] = find(y);
        c[find(x)] = tmp;
    }
    return 0;
}