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

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

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