ACM►数学►数论

LightOJ1370 - Bi-shoe and Phi-shoe（欧拉函数+打表）

题目链接：

https://vjudge.net/problem/LightOJ-1370

题目大意：

给出 $N$ 个数$a_1,a_2\dots a_n$，求对每一个 $a_i$ 找出最小的 $k_i$ 使得 $\phi(k_i) \ge a_i$，输出 $\sum_1^n k_i$ 。

解题过程：

因为是数论的题，显然题目是要用欧拉函数，于是特意去翻了一下紫书的欧拉函数。想假期在家里做的，然后咸鱼了，想在来学校补得，也算是目前数论里面唯一一个自己做出的题了…

题目分析：

首先打表求出欧拉函数的值，用紫书上类似素数筛的方式，可以$O(n\log \log n)$的时间内求出。

然后需要解决的问题是，假设对于 2 这个数，那么用欧拉函数值为 $2$ 的 $k$ 并不一定是最优的，可能有一个 $m < k$ 但是 $\phi(m) > \phi(k)$。
这里一个解决方式是，找出每一个$a_i$的$k_i$打一张表，从1开始枚举$k$，先枚举到的k一定比后枚举到的优。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1123456;

typedef long long LL;

int phi[MAX];
int cost[MAX];

void init() {
    //对欧拉函数打表
    phi[1] = 0;
    for (int i = 2; i <= MAX; i++) {
        if (phi[i]) continue;
        for (int j = i; j <= MAX; j+= i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i-1);
        }
    }

    //枚举每一个的花费k
    for (int i = 1; i <= MAX; i++) {
        int x = phi[i];
        for (int j = x; j >= 1; j--) {
            //如果当前为空，那么他的花费为i
            //否则之前已经有更优的解，直接break
            if (cost[j]) break;
            cost[j] = i;
        }
    }
}

int main() {
//    freopen("out", "w", stdout);
    init();
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases++) {
        int n;
        LL ans = 0;
        scanf("%d", &n);
        while (n--) {
            int t;
            scanf("%d", &t);
            ans += cost[t];
        }
        printf("Case %d: %lld Xukha\n", cases, ans);
    }

}
ACM►DP

POJ1015 - Jury Compromise（DP+计算顺序）

题目链接：

http://poj.org/problem?id=1015

题目大意：

现在两个长度相等的序列，$D$和$P$，现在要构造一个新的序列$A = \lbrace a_1, a_2, a_3 \cdots a_k\rbrace$使得$\big|\sum_{i=1}^kD[a_i]-\sum_{i=1}^kP[a_i]\big|$尽量的小，如果有多解，要求$\sum_{i=1}^k(D[a_i]+P[a_i])$尽量的大。

解题过程：

历经两天才A掉的这个题，刚开始定义的三维的状态，果断超时了，后来建去以为，以当前差值的绝对值为状态，但是这样好像会失解，最后看了下博客，发现不用取绝对值可以了。

但是这题要求输出路径，于是纠结好久如何输出路径，要保证一个元素不难重复使用的话，只能从后往前递推，如何这样之前的路径就可能被之后更新掉，原因应该是，以这样DP，不符合最优子结构，全局最优解不是局部最优解，然后局部的解被更新掉之后，输出路径的时候就错了。

最后又去看了下博客，发现别人都是从前往后递推，并且转移的时候检查下当前元素有没有被用过。从前往后推的话，就能保证当前状态向后找的路径是确定不变的了。

题目分析：

定义状态$dp[i][j]$为$\sum_{i=1}^jD[a_i]-\sum_{i=1}^jP[a_i]$的结果为$i$时最大的$\sum_{i=1}^kD[a_i]+P[a_i]$。

那么状态之间转移为：
设当前已选的元素的集合为$D$

$$dp[i+D[k]-P[k]][j+1] = max(dp[i][j]+D[k]+P[k]) \wedge 1 \le k \le n\wedge k\notin D$$

关键在于如何判断$k\notin D$，这里只需要去递归访问路径，查看$k$是否在当前状态的路径中。

做这道题的时候，真的意识到写递推$DP$时计算顺序是多么重要，要考虑循环的嵌套顺序，是循环变量从前往后还是从后向前，一个不同，含义就改变了许多。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int reserve1[3123][30], reserve2[3123][30];
int (*dp)[30] = reserve1+1512;
int (*pre)[30] = reserve2+1512;
int D[212], P[212];

//判断k是否已经被选择
bool is_select(int i, int j, int k) {
    while (~pre[i][j]) {
        int t = pre[i][j];
        if (t == k)
            return true;
        t = D[t]-P[t];
        i -= t;
        j--;
    }
    return false;
}

int main() {
    int n, m, cases = 0;
    while (~scanf("%d %d", &n, &m) && (n+m)) {
        for (int i = 0; i < n; i++) {
            scanf("%d %d", D+i, P+i);
        }
        memset(reserve1, 0x80, sizeof(reserve1));
        memset(reserve2, -1, sizeof(reserve2));
        //初始化边界状态
        dp[0][0] = 0;

        //记录答案
        int ans_diff, ans_sum;
        vector<int> ans_path;
        ans_diff = INF, ans_sum = -INF;

        for (int i = -1000; i <= 1000; i++) {
            for (int j = 0; j < m; j++) {
                //如果当前为负数，表示当前状态不可到达
                if (dp[i][j] < 0) continue;
                for (int k = 0; k < n; k++) {
                    int t1 = D[k]+P[k];
                    int t2 = D[k]-P[k];
                    if (!is_select(i, j, k) && (dp[i][j] + t1 > dp[i+t2][j+1])) {
                        dp[i+t2][j+1] = dp[i][j] + t1;
                        pre[i+t2][j+1] = k;
                        //当j等于m时更新答案
                        if (j+1 == m && (abs(i+t2) < abs(ans_diff) || abs(i+t2) == abs(ans_diff) && dp[i+t2][j+1] > ans_sum)) {
                            ans_diff = i+t2;
                            ans_sum = dp[i+t2][j+1];
                        }
                    }
                }
            }
        }

        int sum1, sum2;
        sum1 = sum2 = 0;
        int pos = m;
        //递归的去寻找路径
        while (~pre[ans_diff][pos]) {
            int t = pre[ans_diff][pos];
            ans_path.push_back(t);
            sum1 += D[t];
            sum2 += P[t];
            t = D[t]-P[t];
            ans_diff -= t;
            pos--;
        }

        sort(ans_path.begin(), ans_path.end());
        printf("Jury #%d\n", ++cases);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sum1, sum2);
        for (int i = 0; i < ans_path.size(); i++)
            printf(" %d", ans_path[i]+1);
        printf("\n\n");
    }
}
ACM►DP

HDU1024 - Max Sum Plus Plus（DP+降维优化）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1024

题目大意：

给定一个长度为n的序列，一个数m，求m段不相交的区间和的最大值。

解题过程：

自己好菜啊，简单的状态转移方程都没推出来，值得以后注意的是，以后定义状态不要太”松“了。比如刚开始定义的状态$dp[i][j]$前$i$个数构成的$j$个区间和的最大值，然后发现不会转移。最后看了博客才发现别人不光是前$i$个数还要以$i$结尾，这样就转移方程就任意写出来了，虽说转移操作的复杂度增加了不少。

题目分析：

首先定义状态$dp[i][j]$含义是前$i$个数以第$i$个数结尾分了$j$个区间的最大和。
那么有两种转移方式，一是把第$i$个数加到第$i-1$个数所在的区间里面，二是第$i$个数单独为一个区间，那么状态转移方程为。

$$dp[i][j] = max(dp[i-1][j], dp[k][j-1],\quad 0 < k < i,\; i \le j$$

然后这个转移方程，一个直观的写法是这样的：

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i][j] = dp[i-1][j];
        for (int k = 1; k < i; k++) {
            dp[i][j] = max(dp[i][j], dp[k][j-1]);
        }
    }
}

显然这样时间上会超时，复杂度高达$O(n^2m)$。

这时候需要观察下上面写的代码，发现可以把n和m的循环交换顺序。

1
2
3
4
5
6
7
8
for (int j = 1; j <= m; j++) {
    for (int i = j; i <= n; i++) {
        dp[i][j] = dp[i-1][j];
        for (int k = 1; k < i; k++) {
            dp[i][j] = max(dp[i][j], dp[k][j-1]);
        }
    }
}

然后发现，最内层的$k$次循环其实是没有必要的，因为对于每一趟内$i$循环，都可以在上一趟循环中预处理出来最大的$k$。

1
2
3
4
5
6
7
8
for (int j = 1; j <= m; j++) {
    maxn = -INF;
    for (int i = j; i <= n; i++) {
        dp[i] = max(dp[i-1], pre[i-1]) + data[i];
        pre[i-1] = maxn;
        maxn = max(maxn, dp[i]);
    }
}

这里$pre$数组的含义是，$pre[i]$为从$1$到i中，最大的$dp[k][j-1]$。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1123456;
const int INF = 0x7fffffff;

int data[MAX], dp[MAX], pre[MAX];

int main() {
    int m, n;
    while (~scanf("%d %d", &m, &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", data + i);
            dp[i] = pre[i] = 0;
        }
        int maxn;
        for (int j = 1; j <= m; j++) {
            maxn = -INF;
            for (int i = j; i <= n; i++) {
                dp[i] = max(dp[i-1], pre[i-1]) + data[i];
                pre[i-1] = maxn;
                maxn = max(maxn, dp[i]);
            }
        }
        printf("%d\n", maxn);
    }

    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            dp[i][j] = dp[i-1][j];
            for (int k = 1; k < i; k++) {
                dp[i][j] = max(dp[i][j], dp[k][j-1]);
            }
        }
    }
}
ACM►DP►树型DP

HDU2196 - Computer（树的直径+DP）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2196

题目大意：

给定一个无向连通无环图，求每个节点到达的最远的节点的距离。

解题过程：

上午看了一下DP进阶之路的PDF，突然想学树型DP。然后找到了这个题，之前做了一个POJ的BFS求树的直径的，这次再来一发DP的。

题目分析：

由于题目给的是无向连通无环图，这里构造出一颗树来，不妨假设节点$1$为根。

那么对于任意一个节点，他能到达的最远的节点一定是他子树中的一个节点，或者经过他父亲到达的一个节点。

这里可以经过一次DFS求出每个节点到他子树中最远的节点的距离。

然后第二次DFS的时候求出每个节点经过他根节点能到达的最远的距离，求经过根节点能到达的最远的距离时，需要当前节点到根节点的距离加上根节点到最远的节点的距离。不过要注意的是，可能当前节点在根节点最远距离的路径上。

这里解决的方法是，求出每个节点最远的距离和次远的距离，如果当前节点在最远的距离路径上那么就选择次远的距离，判断是否在路径上需要记录下最远的距离是由那个儿子求出来的。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

const int MAX = 11234;
const int INF = 0x3f3f3f3f;

int n;
vector<pair<int, int> > edge[MAX];

//dis1记录最远距离，dis2记录次远距离，num用来标记最远距离由那个节点而来的
int num[MAX], dis1[MAX], dis2[MAX], dp[MAX];


void read() {
    for (int i = 1; i <= n; i++) {
        edge[i].clear();
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 2; i <= n; i++) {
        int v, w;
        scanf("%d %d", &v, &w);
        edge[v].push_back(make_pair(i, w));
    }
}

void dfs1(int u) {
    dis1[u] = 0;
    //这里的含义是，对于每个节点求他所有儿子节点的最远距离，那么当前节点的最远距离就是到儿子节点的距离加上儿子节点的最远距离
    //显然对于一个叶子节点，最远距离是0
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i].first;
        int w = edge[u][i].second;
        dfs1(v);
        if (dis1[v] + w > dis1[u]) {
            dis1[u] = dis1[v] + w;
            num[u] = v;
        }
    }
    //和上一步相似，求次远距离
    dis2[u] = -INF;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i].first;
        int w = edge[u][i].second;
        //当前距离不能是最远距离
        if (v != num[u] && dis1[v] + w > dis2[u]) {
            dis2[u] = dis1[v] + w;
        }
    }
}

void dfs2(int u) {
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i].first;
        int w = edge[u][i].second;
        //dp[u]的含义是，当前节点经过父节点能到达的最远的距离
        //如果当前节点在最远距离的路径上，那么用次远距离，否则用最远距离
        if (v == num[u])
            dp[v] = max(dp[u], dis2[u]) + w;
        else
            dp[v] = max(dp[u], dis1[u]) + w;
        dfs2(v);
    }
}

void go() {
    dfs1(1);
    dfs2(1);
    //输出每个点的最远距离
    for (int i = 1; i <= n; i++) {
        printf("%d\n", max(dp[i], dis1[i]));
    }
}

int main() {
    while (~scanf("%d", &n)) {
        read();
        go();
    }
}
ACM►数据结构►线段树

UVA11235 - Frequent values（游程编码+线段树）

题目链接：

https://vjudge.net/problem/UVA-11235

题目大意：

给定一个递增序列，询问一段区间内出现频率最多的数出现的次数。

解题过程：

之前图灵杯比赛的题，当时照着板子敲A的，现在突发奇想补一下题，感觉还是挺简单的，就是用到了游程编码。

题目分析：

由于题目是有序的，那么可以很方便的将一段相同的数合为一个区间，data[i]表示第i段区间元素个数，lb[i]记录第i段区间的左边界，rb[i]记录第i段区间的右边界，用id[i]表示原序列的第i个数处于哪个区间。

那么对于查询l到r的区间，如果l和r在同一段区间内，那么显然答案就是r-l+1。
如果l和r不在同一段区间，那么答案为以下三个中的最大值，rb[id[l]] - l + 1,r - lb[id[r]] + 1, id[l]+1区间到id[r]-1区间中的最大值`。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

const int MAX = 112345;

int tree[MAX<<2];
int data[MAX];

#define lson o<<1
#define rson o<<1|1
#define MID int m = (l+r)/2

void build(int o, int l, int r) {
    if (l == r) {
        tree[o] = data[l];
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[o] = max(tree[lson], tree[rson]);
}

int query(int o, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) {
        return tree[o];
    }
    MID;
    return max(query(lson, l, m, ql, qr), query(rson, m+1, r, ql, qr));
}

int raw_data[MAX], n, q, lb[MAX], rb[MAX], id[MAX], top;

void init() {
    top = 1;
    lb[top] = data[top] = id[1] = 1;
    for (int i = 2; i <= n+1; i++) {
        if (raw_data[i] != raw_data[i-1] || i == n+1) {
            rb[top++] = i-1;
            lb[top] = i;
        }
        data[top]++;
        id[i] = top;
    }
}

int main() {
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
    while (~scanf("%d", &n) && n) {
        scanf("%d", &q);
        for (int i = 1; i <= n; i++) {
            scanf("%d", raw_data+i);
        }
        memset(data, 0, sizeof(data));
        init();
        n = top-1;
        build(1, 1, n);
        int l, r;
        while (q--) {
            scanf("%d %d", &l, &r);
            //如果l和r在同一个区间内
            if (id[l] == id[r]) {
                printf("%d\n", r-l+1);
                continue;
            }
            //l和r不在一个区间内
            int a = id[l], b = id[r];
            a = rb[a] - l + 1;
            b = r - lb[b] + 1;
            int t = max(a, b);
            a = id[l] + 1, b = id[r] - 1;
            if (a <= b) {
                //查询id[l]+1区间到id[r]-1区间中的最大值
                t = max(t, query(1, 1, n, a, b));
            }
            printf("%d\n", t);
        }
    }
}
ACM►DP►树型DP

CodeForces743D - Chloe and pleasant prizes（树型DP）

题目链接：

https://vjudge.net/problem/CodeForces-743D

题目大意：

给定一颗树，每个节点上有一个权值，求找出两颗不相交子树，使两颗子树的权值和最大。

解题过程：

好久好久好久之前CF比赛的题，当时好像是没读懂题意，虽然说现在也有点读不懂，最后看了下别人的博客才知道题意。看到下面的标签上有DFS和DP，于是往树型DP上想，不过没系统的学过，之前只写过一个求树的重心的，于是照着那个思路想，没想到还真的可以做。

题目分析：

定义状态$dp[u]$表示以节点$u$的所有子树（包括他自身）的最大权值和，$sum(u)$表示以$u$为根节点的树的权值和显然有：
$dp[u] = max(dp[v], sum(u))$
这里的$v$是$u$的儿子节点。

然后要求不相交的两个子树，对于一个节点，他的两个儿子构成的子树一定是不相交的，这样遍历一下所有的节点就好了。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int MAX = 212345;
const LL INF = 0x3f3f3f3f3f3f3f3f;

vector<int> edge[MAX];
int data[MAX];
bool vis[MAX];

int fat[MAX];
LL sum[MAX], dp[MAX];

//DFS求出DP数组
LL dfs(int u) {
    vis[u] = true;
    //sum记录以当前节点为根节点的权值和
    LL & temp = sum[u];
    temp += data[u];
    //枚举所有的儿子节点，更新DP数组和计算当前树的权值和
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        if (!vis[v]) {
            fat[v] = u;
            LL t = dfs(v);
            temp += t;
            dp[u] = max(dp[v], dp[u]);
        }
    }
    //最后用当前树的权值和更新一下DP数组
    dp[u] = max(dp[u], temp);
    return temp;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        dp[i] = -INF;
        cin >> data[i];
    }
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1);
    LL ans = -INF;
    for (int i = 1; i <= n; i++) {
        if (edge[i].size() < 2)
            continue;
        LL a, b;
        a = b = -INF;
        //枚举每个节点，找出最大的两个儿子节点
        for (int j = 0; j < edge[i].size(); j++) {
            int v = edge[i][j];
            if (fat[v] != i)
                continue;
            if (a < dp[v]) {
                a = dp[v];
                if (b < a)
                    swap(a, b);
            }
        }
        if (a == -INF || b == -INF)
            continue;
        ans = max(ans, a + b);
    }

    if (ans <= -INF)
        printf("Impossible\n");
    else
        printf("%lld\n", ans);
}
ACM►搜索►BFS

CodeForces734E - Anton and Tree（缩点+树的直径）

题目链接：

http://codeforces.com/problemset/problem/734/E

题目大意：

给定一棵无根数，每个节点有黑白两种颜色，现在有一种涂色操作，一次可以将一块连通的同色区域涂为一个颜色，现在求最少操作几次可以将整棵树涂成黑色或白色。

解题过程：

因为之前做过一个涂板子的题，进行的操作和这个一样，也是先缩点。不过那个数据范围比较小，枚举所有点BFS一次，求最长路即可，但是做过数据范围比较大，所以用到了树的某些性质。

题目分析：

关于树的直径的介绍和BFS的求法，建议看这篇博客，也有详细证明。

如果之前做过这道题的话，那么这个题的思路不难想，就是缩点然后再求一下树的直径就好了。

树的直径有一个性质，以树的直径中点上的一点为根，将这颗无根树转化为有根树的话，这样做会使树的深度最小，且为树的直径的一半（向上取整），因为如果有一个叶子节点比直径更深的话，那么就可以构成一个更长的直径，与假设矛盾。

另外在树上缩点，构成的新的图也是一棵树。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

const int MAX = 212345;

int color[MAX], n, vis[MAX], top;
vector<int> raw_edge[MAX], edge[MAX];

//用DFS染色缩点
void dfs(int u) {
    vis[u] = top;
    for (int i = 0; i < raw_edge[u].size(); i++) {
        int v = raw_edge[u][i];
        if (!vis[v] && color[u] == color[v]) {
            //如果颜色相同，并且没访问过那么缩成一个点
            dfs(v);
        }
        else if (vis[v] && color[u] != color[v]){
            //如果颜色不同，并且访问过，那么就建边
            edge[top].push_back(vis[v]);
            edge[vis[v]].push_back(top);
        }
    }
}

void build() {
    top = 1;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
            top++;
        }
    }
}

//BFS求最长路
int bfs(int u) {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(u);
    vis[u] = 1;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i];
            if (!vis[v]) {
                vis[v] = vis[u] + 1;
                q.push(v);
            }
        }
    }
    int pos = 1;
    for (int i = 1; i < top; i++) {
        if (vis[i] > vis[pos])
            pos = i;
    }
    return pos;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
    }
    for (int i = 0; i < n-1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        raw_edge[u].push_back(v);
        raw_edge[v].push_back(u);
    }
    build();
    //先确定直径的一个端点
    int x = bfs(1);
    //然后从端点跑最长路求出直径长度，这里距离求出来的是比实际距离大1，所以默认向上取整
    printf("%d\n", vis[bfs(x)]/2);
}
ACM►数学

HackerRank - pairs-again（暴力+预处理）

题目链接：

https://www.hackerrank.com/contests/w26/challenges/pairs-again

题目大意：

给定一个数n，问有多少对$a,b$满足$xa+by=n$至少有一个解，$a<b$并且$0 < b, 0 < y$，且$x,y$是整数。

解题过程：

比赛时候的题，当初那场比赛运气还不错，这道题看到一堆人WA了60多发，于是没敢去做，后来去补了，也算是学下如何预处理约数。

题目分析：

这题的时限很奇怪，都能跑到59秒。

这里要预处理出来前n个数的所有约数。然后枚举$a$和$x$，$n-xa$为$bx$，把$bx$的约数当做$b$，记录下$bx$大于$a$的约数，不过对于$ax+by = cx + by = n$的情况要去一下重。

预处理约数可以类比下欧拉筛法的思想。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

const int MAX = 312345;

vector<int> divisor[MAX];
int flag[MAX];

int main() {
    int n;
    cin >> n;
    //预处理前n个数的约数，类比欧拉筛法
    for (int i = 2; i < n; i++) {
        for (int j = i; j < n; j += i) {
            divisor[j].push_back(i);
        }
    }
    int ans = 0;
    memset(flag, 0, sizeof(flag));
    for (int a = 1; a < n; a++) {
        for (int xa = a; xa < n; xa += a) {
            int yb = n - xa;
            for (int i = 0; i < divisor[yb].size(); i++) {
                int t = divisor[yb][i];
                //让每个t对于每个a只用一次，并且保证t > a
                if (flag[t] == a || t <= a) continue;
                flag[t] = a;
                ans++;
            }
        }
    }
    cout << ans;
}
ACM►贪心

ZOJ3385 - Hanami Party （贪心）

题目链接：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3385

题目大意：

妖梦要准备一个party，所以需要许多食物，初始化妖梦的烹饪技能为$L$，每天妖梦有两种选择，一是选择当天做$L$个食物，二是提升自己的烹饪技能为$L+1$。

但是幽幽子非常能吃，每天幽幽子都要吃$A_i$的食物，当没食物吃后幽幽子会非常生气，甚至想把妖梦批判一番。所以现在妖梦要保证做出的食物每天够幽幽子吃的情况下尽量的多。

解题过程：

好久好久之前比赛的题，一直没补，当初知道是贪心和栈，感觉这样的思维题加简单的数据结构的题非常难……也可能是直接接触的题太少吧。

题目分析：

首先用栈去贪心的模拟，在能保证够幽幽子吃的情况下，最多能够将技能提高到几级。

假设每天都提高等级并且将天数入栈，当当前剩下的食物不够幽幽子吃的话，将上一次提升等级的地方换成做食物。如果还是不够幽幽子吃的话，那么就是无解的。

因为提高等级是一个持久性的加成，当然是越早提升越好，所以每次将提高等级换做做食物的地方都是最晚的地方。

这样求解出最高可以升到几级后，再去求下最大能达到多少食物。

同样效仿上面的操作，每次取出最近的提升等级的地方换成做食物，去维护一个最大值。

不过有可能有这样的一个情况，在租个替换掉提升等级时，可能某个地方替换掉提升等级后食物就不够幽幽子吃了。但是这种情况，求出的结果肯定比维护的最大值要小，因为现在食物不够吃了，并且等级还低了，那么最后算出的剩余一定是更小的。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <stack>
using namespace std;

typedef long long LL;

int main() {
    LL N, L;
    while (~scanf("%lld %lld", &N, &L)) {
        LL sum = 0;
        bool flag = true;
        stack<LL> ss;
        for (int i = 1; i <= N; i++) {
            LL eat;
            //每天要吃的食物数
            scanf("%lld", &eat);
            if (!flag)
                continue;
            ss.push(i);
            L++;

            //如果当前剩余的食物不够的话，去替换掉之前提升等级
            while (sum < eat && !ss.empty()) {
                LL t = ss.top();
                L--;
                ss.pop();
                //将提升等级替换成做食物是很容易维护的，首先让等级减一，加上等级，然后当从提升等级那天到至今的提升等级的加成减去
                sum += L - (i-t);
            }
            if (sum < eat) {
                flag = false;
                continue;
            }
            sum -= eat;
        }
        if (!flag) {
            printf("Myon\n");
            continue;
        }
        LL ans = sum;


        //求出最大值，类似上面的过程
        while (!ss.empty()) {
            LL t = ss.top();
            L--;
            ss.pop();
            sum += L - (N - t);
            ans = max(ans, sum);
        }
        printf("%lld\n", ans);
    }
}
ACM►贪心

HDU5527 - Too Rich（贪心）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5527

题目大意：

现在你有$P$元钱，有$10$种不同面值的硬币，每种硬币有一定的数量，求用尽量多的硬币凑出P元钱，有可能凑不出。

解题过程：

当初比赛没看这道题，最近才补，看起来挺简单的，实际知道思路上也不难……

题目分析：

要用尽量多的硬币凑$P$元钱，假设我现在硬币总共的面值和为$M$，那么换个思路，我现在要从总共的硬币中拿走尽量少的硬币，使剩下的硬币为P元。

那么问题转化成了，用尽量少的硬币去凑出$M-P$元，这个题目就有点熟悉了，不过这里有两个特殊的地方，一个是每种硬币都有数量限制，一个是面值大的硬币并不是面值小的硬币的整数倍。

假设没有数量限制，那么就是简单的贪心，尽量用面值大的硬币去凑出$M-P$元就好了。但是这个题用这个思路的话，会有这种情况。

假设现在有$20,20,20,50 $这四个硬币，要去凑$60$元，如果以之前的思路贪心的话，那么是无解的，但是这里可以不用$50$元这个硬币，而用$3$个$20$元的去凑出$60$元。

那么对于这种情况，就要尝试一下，对于每种硬币，去掉一个这种硬币后的解。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL INF = 0x3f3f3f3f3f3f3f3f;

LL coin[] = {1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};
LL num[10], c[10];

LL ans = INF;

void dfs(int i, LL sum, LL t) {
    //sum == 0 表示找到了一个解
    if (sum == 0) {
        ans = min(ans, t);
        return;
    }
    //sum == -1 时需要返回，已经没有面值更小的硬币了
    if (i < 0)
        return;

    //计算出来当前硬币最多取多少
    c[i] = min(num[i], sum/coin[i]);
    dfs(i-1, sum - coin[i] * c[i], t + c[i]);

    //尝试少拿一个硬币
    if (c[i] > 0) {
        c[i]--;
        dfs(i-1, sum - coin[i] * c[i], t + c[i]);
    }
}

int main() {
    LL n;
    scanf("%lld", &n);
    while (n--) {
        LL p;
        LL total, sum;
        total = sum = 0;
        scanf("%lld", &p);
        for (int i = 0; i < 10; i++) {
            scanf("%lld", num + i);
            //sum计算所有硬币总共的价值
            sum += coin[i]*num[i];
            //total计算总共的硬币数
            total += num[i];
        }

        //计算出需要拿走多少钱
        sum -= p;

        if (sum < 0) {
            printf("-1\n");
            continue;
        }

        ans = INF;
        dfs(9, sum, 0);

        //如果ans == INF 表示一个解都没有
        if (ans == INF)
            printf("-1\n");
        else
            printf("%lld\n", total - ans);
    }
}