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;
}

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

tag:
NOI1999，dfs，剪枝，搜索

思路：
使用dfs和剪枝。dfs有四个参数，分别表示第几层，剩余体积，当前的面积，剩余层数。剪枝是有两个，第一个，如果当前的表面积加上之后最小的面积大于当前的面积，就return，第二个，之后最大的体积小于剩余的体积就return。边界情况是当剩余体积v小于0，return；当前层数超过m，return；当前的面积大于最小面积，return。终止条件是当剩余体积v == 0，然后层数等于m时表面积加上每层的上表面积（其实就是第一层蛋糕的顶层表面积），然后更新minv。考虑特殊情况，如果层数为1则直接遍历半径r，然后找到一个最小的表面积。

代码：

#include <iostream>
#include <cmath>
using namespace std;
int n, m, minv = 0x3f3f3f3f;
int r[20], h[20];
void dfs(int u, int v, int c, int p)
{
    if (v < 0) return;
    if (u > m + 1) return;
    if (c >= minv) return;

    if (v == 0 && u == m + 1)
    {
        c += r[1] * r[1];
        minv = min(minv, c);
        return;
    }

    if (c + p + r[1] * r[1] > minv) return;

    if (v - (r[u - 1] * r[u - 1] * h[u - 1] * p) > 0) return;

    for (int i = r[u - 1] - 1; i >= p; i--)
    {
        for (int j = h[u - 1] - 1; j >= p; j --)
        {
            if (v - i * i * j >= 0 && u + 1 <= m + 1)
            {
                r[u] = i;
                h[u] = j;

                dfs(u + 1, v - i * i * j, c + 2 * i * j, p - 1);

                r[u] = 0;
                h[u] = 0;
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    if (m == 1)
    {
        for (int r = 1; r <= sqrt(n); r ++)
        {
            if (n % (r * r) == 0)
            {
                int h = n / (r * r);
                int tmp = 2 * r * h + r * r;
                minv = min(minv, tmp);
            }
        }
        if (minv == 0x3f3f3f3f) cout << 0;
        else cout << minv;
        return 0;
    }
    r[0] = (int)sqrt(n);
    h[0] = (int)sqrt(n);
    dfs(1, n, 0, m);
    if (minv == 0x3f3f3f3f) cout << 0;
    else cout << minv;
    return 0;
}

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

tag:
USACO05DEC，dfs，剪枝，搜索

思路：
先按照从大到小排序，然后计算前缀和。之后每次dfs，先判断上一个累加的结果有没有超过w，如果有就return，否则就更新res，然后判断是不是所有点都判断完了，如果是，则return。之后计算一下剩余的值之和，如果剩余的值之和加上当前累加的值比res小就直接return。否则就判断下一个值加上累加的值会不会超过w如果没有加加上那个值，然后递归dfs，最后再dfs没有加上这个值的情况。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
long long n, w;
long long d[1010], sum[1010];
long long res = -1;
bool st[1010];
void dfs(int u, long long tmp)
{
    if (tmp > w) return;
    res = max(res, tmp);
    if (u == n) return;
    long long remain = sum[n] - sum[u];
    if (remain + tmp <= res) return;
    if (tmp + d[u + 1] <= w) dfs(u + 1, tmp + d[u + 1]);
    dfs(u + 1, tmp);

}
bool cmp (long long &a, long long &b)
{
    return a > b;
}
int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; i ++)
    {
        cin >> d[i];
    }
    sort(d + 1, d + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + d[i];
    dfs(0, 0);
    cout << res;
    return 0;
}

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

tag:
动态规划，状压DP，dfs，记忆化搜索

思路：
可以是状态压缩dp，也可以是用dfs加上记忆化搜索。这里就用dfs加上记忆化搜索。用二进制来存储每一种状态，每次访问一个点就将那个点异或一下。最后每次都是返回一个答案。dp中存的是从x点开始走走到最后一个点的最短路径。

代码：

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
typedef pair<double, double> PII;
int n;
PII d[20];
bool st[20];
double dp[20][1 << 16];
double dfs(int x, int u, double step, int path)
{
    double res = 1e9;
    if (u == n)
    {
        return step;
    }
    if (dp[x][path]) return dp[x][path] + step;

    for (int i = 1; i <= n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            double tmp = sqrt(pow(d[i].first - d[x].first, 2) + pow(d[i].second - d[x].second, 2));
            res = min(res, dfs(i, u + 1, step + tmp, path | (1 << i)));
            st[i] = false;
        }
    }

    dp[x][path] = res - step;
    return res;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> d[i].first >> d[i].second;
    double res = dfs(0, 0, 0.0, 0);
    printf("%.2lf", res);
    return 0;
}

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

tag:
NOIP2002 提高组，字符串，bfs

思路：
因为是求最少的变换次数，所以可以用bfs。每次搜索都遍历字符串的每一个位置，将可以替换的地方都替换，然后判断是否出现过，没有出现过就加入队列。最后第一次出现字符串b的时候步数就是答案。

代码：

#include <iostream>
#include <queue>
#include <map>
#include <unordered_set>
using namespace std;

typedef pair<string, string> PSS;
typedef pair<string, int> PSI;

PSS mp[6];
string a, b;
queue<PSI> q;
unordered_set<string> st;
int idx = 0;

int bfs()
{
    q.push({a, 0});
    st.insert(a);

    while (!q.empty())
    {
        auto [current, step] = q.front(); q.pop();

        if (current == b) return step;

        if (step >= 10) continue;

        for (int i = 0; i < idx; i++)
        {
            string from = mp[i].first;
            string to = mp[i].second;
            size_t pos = current.find(from);
            while (pos != string::npos)
            {
                string newstr = current.substr(0, pos) + to + current.substr(pos + from.size());
                if (newstr.size() <= 20)
                {
                    if (!st.count(newstr))
                    {
                        st.insert(newstr);
                        q.push({newstr, step + 1});
                    }
                }
                pos = current.find(from, pos + 1);
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    string c, d;
    while (cin >> c >> d)
    {
        if (!c.empty() && idx < 6)
        {
            mp[idx++] = {c, d};
        }
    }
    int res = bfs();

    if (res != -1 && res <= 10)
        cout << res;
    else
        cout << "NO ANSWER!";

    return 0;
}