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

1. 安装gcc

1. 搜索 gcc 包：
   运行以下命令查看可用的 gcc 包：

   choco search gcc

2. 安装 MinGW（推荐，包含 gcc）：
   使用以下命令安装 MinGW：

   choco install mingw -y

3. 验证安装：

   • 打开新终端（如 PowerShell 或 CMD）。

   • 输入以下命令验证 gcc 是否可用：

     gcc --version

2. 配置环境变量

1. 找到 MinGW 的安装路径：
   默认路径通常是 C:\tools\mingw64。

2. 添加路径到系统环境变量：

   • 搜索 环境变量，打开 编辑系统环境变量。
   • 在 系统属性 > 高级 > 环境变量 中，找到 Path。
   • 点击 编辑，添加 MinGW 的 bin 文件夹路径 C:\ProgramData\mingw64\mingw64\bin
3. 保存并重启终端。

3. 测试 gcc

编写一个简单的 C 文件（如 test.c）：

#include <stdio.h>

int main() {
    printf("Hello, GCC!\n");
    return 0;
}

在终端运行以下命令进行编译：

gcc test.c -o test.exe

执行生成的 test.exe 文件：

test.exe

如果输出 Hello, GCC!，说明安装成功。

这两天有点累。不知道是不是刷题刷的我有点抑郁。现在有点不想刷题了。忽然又回想起某次宿舍外面下雨，没有人，我坐在床边，觉得有点闷。出去走走，外面雨下的很大，打在过道边上，把地弄得很脏。不知道是初中还是高中，还是大学的回忆，都揉在了一起。一切好像都没有了意义。我怔怔的看着雨。雨就是雨。不管别人是怎么想它的，看它的，它都只管下。我好想变成雨。在我初中高中，年纪不大的时候就是雨。现在却只能看着雨了。好像是有点强迫症，想等到那雨下完，等到鸟都出来，等到温度上去，落单的雨滴，一点一点从窗户边上落下，但现在看来是等不到春暖花开了。等到来年春天，还要好久，好久，看不头了。