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

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

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

tag:
博弈论，模拟

思路：我觉得比起博弈论，更像是模拟题。这道题先是判断黑色三角形的位置，通过判断是不是有两条边为多边形的边界，如果是，说明先手可以直接切。如果不是，就继续判断n-5的奇偶性，n-5是三角形的个数，表示切了n-5个，这个数是因为一种特殊情况，当场上只有三个三角形的时候，且黑色不是在外层，这个时候如果先手切了一个，那么后手必胜，反之后手切了一个则先手必胜。一共有n-2个三角形，除去最后3个，一共是n-5个，表示进行了n-5次操作，如果为偶数次，说明第n-5次操作是后手，那么第n-4次就是先手，后手必胜，反之如果是奇数次，说是第n-5次操作时先手，那么第n-4次就是后手，先手必胜。总结一下就是当n-5为偶数后手胜，为奇数先手胜。

代码：

#include <iostream>
#include <cmath>
using namespace std;
int n, x, y, z;
int main()
{
    cin >> n;
    cin >> x >> y >> z;
    int cnt = 0;
    if (abs(x - y) == 1 || abs(x - y) == n - 1) cnt ++;
    if (abs(x - z) == 1 || abs(x - z) == n - 1) cnt ++;
    if (abs(y - z) == 1 || abs(y - z) == n - 1) cnt ++;
    if (cnt == 2)
    {
        cout << "JMcat Win";
        return 0;
    }
    if ((n - 5) % 2) cout << "JMcat Win";
    else cout << "PZ Win";
    return 0;
}