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!，说明安装成功。

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

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

tag:
NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。

思路：
思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输出即可。如何求呢？这里用动态规划和前缀和来求，具体可以看代码。看其他题解有用线段树来做，但是比较麻烦，就上动规和前缀和了。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
long long sum[N], c[N], h[N];
struct client {
    int s, a;
}Client[N];
bool cmp(client &a, client &b)
{
    return a.a > b.a;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) cin >> Client[i].s;
    for (int i = 1; i <= n; i ++) cin >> Client[i].a;
    sort(Client + 1, Client + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
    {
        sum[i] = sum[i - 1] + Client[i].a;
        h[i] = max(h[i - 1], (long long)Client[i].s * 2);
    }
    for (int i = n; i >= 1; i --)
    {
        c[i] = max(c[i + 1], 2LL * Client[i].s + Client[i].a);
    }
    for (int i = 1; i <= n; i ++)
    {
        cout << max(sum[i] + h[i], sum[i - 1] + c[i]) << '\n';
    }
    return 0;
}

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

tag:
数论，欧拉函数，筛法，前缀和

思路：
假设又两个互质的整数a, b，则gcd(a, b) = 1，那么对于任意的自然数p有gcd(a p, b p) = p。利用这个结论，对于这道题我们可以先求欧拉函数，然后求一遍gcd(a, b) = 1 的前缀和，这里求前缀和的时候注意对于1来说只有(1, 1)之后的其他组都有(a, b)和(b, a)。最后遍历每一个质数，用最大值求一个m，使得max(a, b)不超过m的每一对互质数都乘上一个质数得出一个可能的结果。将这个前缀和加到答案即可。

代码：

#include <iostream>  
#include <vector>  
using namespace std;  
const int N = 1e7 + 10;  
int n, phi[N];  
long long sum[N];  
bool st[N];  
long long res;  
vector<int> primes;  
int main()  
{  
    cin >> n;  
    for (int i = 1; i <= n; i ++) phi[i] = i;  
    st[0] = st[1] = true;  
    for (int i = 2; i <= n; i ++)  
    {  
        if (!st[i])  
        {  
            primes.push_back(i);  
            phi[i] = i - 1;  
        }  
        for (int p : primes)  
        {  
            if (p * i > n) break;  
            st[p * i] = true;  
            if (i % p == 0)  
            {  
                phi[i * p] = phi[i] * p;  
                break;  
            }  
            else  
            {  
                phi[i * p] = phi[i] * (p - 1);  
            }  
        }  
    }  
    sum[1] = 1;  
    for (int i = 2; i <= n; i ++)  
    {  
        sum[i] = sum[i - 1] + phi[i] * 2;  
    }  
    for (int p : primes)  
    {  
        int m = n / p;  
        res += sum[m];  
    }  
    cout << res << endl;  
}