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

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

tag:
动态规划

思路：
问题1就是求最长下降子序列。问题2可以用c[i] 来表示以i为结尾长度为f[i] 的所有下降子序列，然后属性是数量。他可以由倒数第二个数的情况来转移，初始化是当长度为1时数量为1，之后遍历j从1到i，如果满足长度比f[j]大1，然后d[j] > d[i]，就说明可以由c[j] 转移过来，就让c[i] += c[j]，如果长度相同且大小相同，说明之前被计算过了，就让c[i] = 0，最后求答案时判断长度是否为最长，即答案1，如果为最长，则让res2 += c[i]。

代码：

#include <unordered_set>
#include <iostream>
using namespace std;
const int N = 5050;
int d[N], f[N], c[N];
int n, res1, res2;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> d[i];
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (d[j] > d[i]) f[i] = max(f[i], f[j] + 1);
        }
        res1 = max(res1, f[i]);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (f[i] == 1) c[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (f[i] == f[j] + 1 && d[j] > d[i]) c[i] += c[j];
            if (f[i] == f[j] && d[j] == d[i]) c[i] = 0;
        }
        if (f[i] == res1) res2 += c[i];
    }
    cout << res1 << ' ' << res2 << endl;
    return 0;
}

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

tag:
NOI Online 2021 提高组，字符串，哈希

思路：
用双重循环枚举每一个b中的字串，对于每一个枚举的字串，扫描一遍a，找出a中相同的子序，然后计算哈希值并存储，最后遍历结束，对哈希数组去重得出答案。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010, BASE = 51971;
const long long M = 2005091020050911;
int n;
char a[N], b[N];
long long t[N * N];
int main()
{
    cin >> n >> a + 1 >> b + 1;
    for (int i = 1; i <= n ; i++)
    {
        long long v = 0; int p = 1;
        for (int j = i; j <= n; j ++)
        {
            while(p <= n && a[p] != b[j]) p ++;
            if (p > n) break;
            p ++;
            v = (1LL * v * BASE + b[j] - 'a' + 1) % M;
            t[++t[0]] = v;
        }
    }
    sort(t + 1, t + t[0] + 1);
    cout << unique(t + 1, t + t[0] + 1) - t - 1;
    return 0;
}

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

tag:
枚举，构造，动态规划

思路：
看了题解好像是可以用动态规划中的求最大子矩阵来做，但是这里用了很暴力的写法，加上前缀和优化也能过。这个做法本质上就是不断地枚举每一个矩形然后判断四条边是不是满足条件，然后再更新最大值就好了。

代码：

#include <iostream>
using namespace std;
const int N = 220;
int n, m;
int d[N][N], s[N][N], col[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '.') d[i][j] ++;
            s[i][j] = s[i][j - 1] + d[i][j];
            col[i][j] = col[i - 1][j] + d[i][j];
        }

    int res = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        {
            for (int k = 1; k <= m; k ++)
            {
                for (int l = k; l <= m; l ++)
                {
                    if (
                            col[j][k] - col[i - 1][k] == j - i + 1
                            && col[j][l] - col[i - 1][l] == j - i + 1
                            && s[i][l] - s[i][k - 1]  == l - k + 1
                            && s[j][l] - s[j][k - 1] == l - k + 1)
                        res = max(res, (j - i + 1) * (l - k + 1));
                }
            }
        }
    cout << res << endl;
    return 0;
}