欢迎评论提问， 纠错

文章篇幅较长， 请参考右侧文章目录食用。

专题链接： SDNU_ACM_ICPC_2020_Winter_Practice_1st

A CodeForces 854A

1. 题目大意

把一个数n分成两个互质的数(a, b, a < b)， 使 a / b 最大。

2. 分析

从 i = n / 2 –> 1遍历， 如果 gcd(i, n - i) == 1 ， 输出i 和 n - i。

3. 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
#include <bits/stdc++.h>
#define eps 1e-8

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod =  998244353;
ll read() {
    ll x = 0, w = 1;char ch = 0;
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x * w; 
}

int main(){
	int n = read();
	for (int i = n / 2; i >= 1; --i){
		if (__gcd(i, n - i) == 1){
			cout << i << " " << n - i << "\n";
			return 0;
		}
	}

    return 0;
}

4. 后继

  1. QAQ， 当时没看到要两个数互质， wa了一发

B CodeForces 854B

1. 题目大意

公寓编号 1 - n ， 其中k间已经有人入住（不知道具体是哪k间）， 如果这个人入住了一间房子并且他的邻居有人入住， 他就会感到快乐， 问能让他感到快乐的位置数量的 最小值， 最大值。

2. 分析

最小值的情况肯定是 1-k入住， 答案为0 （住满）或 1（没住满） 。
最大值的情况是 入住一个人 会有两个位置使他感到愉悦的，但总位置不能超过 n-k， 答案就是min(2 * k, n - k)。

3. 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
#include <bits/stdc++.h>
#define eps 1e-8

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod =  998244353;
ll read() {
    ll x = 0, w = 1;char ch = 0;
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x * w; 
}

int main(){
	int n, k;
	n = read(), k = read();
	if (n == k || k == 0){
		cout << "0 0\n";
		return 0;
	}
	
	int mx = 2 * k;
	mx = min(mx, n - k);
	cout << "1 " << mx << "\n";

    return 0;
}

4. 后继

  1. 当时以为 2 4 6 这种空一个是最优的， 其实 2 5 8 这种空两个才是最优的， 然后就wa了两发。

C CodeForces 854C

1. 题目大意

给你n个飞机的花费和开始时间k， 第i个飞机的最早起飞时间是i， 要求飞机从 k + 1 到 k + n， 全都飞完， 求什么顺序能使总花费最小， 输出最小花费和n个飞机实际起飞的时间， 起飞花费的计算公式为 (实际起飞时间 - 要求起飞时间) * 这个飞机的花费

2. 分析

实际上就是求 [1, i] | k + 1 <= i <= k + n 区间内， 飞机花费的最大值， 就是第i时间应该起飞的飞机。 为什么不是求 (实际起飞时间 - 要求起飞时间) * 这个飞机的花费这个最大的呢， 因为， 第i + 1 下， 飞机的 花费大的 涨的多， 所以 应当取飞机花费的最大值。

用优先队列， 现在为cnt时， 把1-cnt的飞机都加进去， 然后取top为时间为cnt时应该起飞的飞机，pop（）， 再把cnt + 1的飞机加进去。

3. 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
#include <bits/stdc++.h>
#define eps 1e-8

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod =  998244353;
ll read() {
    ll x = 0, w = 1;char ch = 0;
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x * w;
}

struct node
{
    int c, j; // c 是花费， j 是起飞时间
    bool operator < (const node &x) const{
        return c < x.c;
    }
}a[N];
int ans[N]; // 第i个飞机的实际起飞时间
ll res;
priority_queue <node> q;
int main(){
    int n, k;
    n = read(), k = read();
    for (int i = 1; i <= n; ++i){
        a[i].c = read();
        a[i].j = i;
    }
    for (int i = 1; i <= k + 1; ++i){
        if (i > n) break;
        q.push(a[i]);
    }
    int cnt = k + 1;
    while(!q.empty()){
        res += (ll)(q.top().c) * (cnt - q.top().j);  // 计算总花费
        ans[q.top().j] = cnt++; // 第q.top().j个飞机的实际起飞时间
        q.pop();
        if (cnt <= n)
            q.push(a[cnt]);
    }
    cout << res << "\n";
    for (int i = 1; i <= n; ++i){
        cout << ans[i];
        if (i != n) cout << " ";
        else cout << "\n";
    }


    return 0;
}

D CodeForces 854D

1. 题目大意

一共有n+1个城市（0 - n）， 然后 1 - n 城市每个城市一个人， 要到0号城市去会晤， 这n个人至少要一起在0号城市待k天， 现给出 1 - n 城市到0号城市以及 0号城市到 1- n 城市的机票价钱，以及航班开始时间， 并且这一天一定能到达， 问如何安排能使总花费最少。

2. 分析

维护两个数组， sum1[i] 表示前i个（包括第i个）航班 能使 1 - n 号城市 到 0 号城市 的最小花费， sum2[i] 表示后i个（包括第i个）航班 能使 0 号城市 到 1 - n 号城市 的最小花费。

就是维护这两个数组有点小小麻烦。

全都求出来， 暴力求 sum1[i] + sum2[i + k + 1]的最小值即可。

具体如何维护。请看代码注释

3. 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>

#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

ll read() {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return  x * w;
}

struct node{
    int d, f, t, c; // 题意中的d, f, t, c
}a[N];

bool cmp(node x, node y){
    return x.d < y.d;
}

ll sum1[M], sum2[M];
ll val[N];
int main(){
    int n, m, k, d, f, t, c, en = 0;
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; ++i){
        d = read(), f = read(), t = read(), c = read();
        a[i] = {d, f, t, c};
        en = max(en, d);
    }
    sort(a + 1, a + m + 1, cmp); // 先按照飞机起飞时间排序
    ms(sum1, llINF);
    ms(sum2, llINF);
    // 下面3个是辅助维护的
    ms(val, llINF);
    ll sum = 0;
    int len = 0;
    // 下面是维护sum1
    for (int i = 1; i <= m; ++i){
        if (a[i].f == 0) continue;  // 剔除出发地是0号城市的
        // val[i]是储存，出发地是i的飞机票的最小价值
        if (val[a[i].f] == llINF){
            val[a[i].f] = a[i].c;
            sum += a[i].c; //  总价值
            len++;
        }
        else if (val[a[i].f] > a[i].c){
            sum += -val[a[i].f] + a[i].c;
            val[a[i].f] = a[i].c;
        }
        if (len == n){ // 如果n个城市都有航班飞向0城市了， 那就可以安排了
            sum1[a[i].d] = sum;
        }
    }
    // 由于上面循环并没有照顾到每一天的航班， 就是有的天， 没有航班， 不是真正的 sum1， 下面就是维护没有航班的天
    for (int i = 1; i <= en; ++i){
        if (sum1[i - 1] != llINF){
            sum1[i] = min(sum1[i - 1], sum1[i]);
        }
    }
    // 维护sum2， 同理
    len = 0;
    ms(val, llINF);
    sum = 0;
    for (int i = m; i >= 1; --i){
        if (a[i].t == 0) continue;
        if (val[a[i].t] == llINF){
            val[a[i].t] = a[i].c;
            sum += a[i].c;
            len++;
        }
        else if (val[a[i].t] > a[i].c){
            sum += -val[a[i].t] + a[i].c;
            val[a[i].t] = a[i].c;
        }
        if (len == n){
            sum2[a[i].d] = sum;
        }
    }
    for (int i = en - 1; i >= 1; --i){
        if (sum2[i + 1] != llINF){
            sum2[i] = min(sum2[i + 1], sum2[i]);
        }
    }

    ll ans = llINF;
    for (int i = 1; i <= en - k - 1; ++i){
        ans = min(ans, sum1[i] + sum2[i + k + 1]);
    }
    if (ans == llINF) puts("-1");
    else cout << ans << "\n";



    return 0;
}

4. 后继

  1. 这代码是我后来写的， 刚刚补题时的代码是用set维护的， 没用val， 感觉没这个好用， 也没这个简洁。
  2. 维护sum1/sum2 的时候别忘了照顾到没有航班的天， 最后的for循环至关重要。总之最后补题的时候debug de了一小时。详见哭o(╥﹏╥)o

E CodeForces 705B

1. 题目大意

n轮游戏， 第i轮游戏有前i个数， 没一轮一个人可以把一个大于2的数x拆成 p(p >= 1) ,x - p (x - p >= 1)， 如果最后没得拆， 就算那个人输。

2. 分析

博弈， 每个数被拆多少次是固定的， qaq， 这一轮的所有数能被拆的次数统计下， 奇数先手赢， 偶数先手输。

3. 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
#include <bits/stdc++.h>

#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

ll read() {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

int main() {
    int n = read();
    ll sum = 0, a;
    while(n--){
        a = read();
        sum += a - 1;
        if (sum & 1) puts("1");
        else puts("2");
    }

    return 0;
}

F CodeForces 705C

1. 题目大意

一共有n个app， 有q次操作。

1
2
3
1 x  app-x 产生一条通知
2 x  把所有 app-x 产生的通知标记为已读
3 t  把前t个产生的通知（不论已读未读）标记为已读

输出每一次操作后， 未读通知的数量

2. 分析

一开始真的是毫无头绪， 想着大暴力铁定超时， 后来看题解， 只想大喊一声 stlnb！

思想， 通知用cnt编号， 每次都放进set<int>se里， x产生的通知放进vector<int>ve[i] 里

1
2
3
4
5
6
7
8
9
10
11
// 操作一
ve[x].push_back(cnt);
se.insert(cnt++);
// 操作二
se.erase(ve[x][i]);
ve[x].clear();
// 操作三 做一个小优化， 否则会tle
last = 1;
for (int i = last; i <= t; ++i)
    se.erase(i);
last = max(last, t);

3. 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
#include <bits/stdc++.h>

#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

ll read() {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

vector<int> ve[N];
set<int> se;

int main() {
    int n, q, op, x;
    n = read(), q = read();
    int cnt = 1, last = 1;
    for (int i = 1; i <= q; ++i) {
        op = read();
        x = read();
        if (op == 1) {
            ve[x].push_back(cnt);
            se.insert(cnt++);
        } else if (op == 2) {
            for (int j = 0; j < ve[x].size(); ++j)
                se.erase(ve[x][j]);
            ve[x].clear();
        } else {
            // 此处可以换成后继部分优化代码， 稍微更优哦~
            for (int j = last; j <= x; ++j)
                se.erase(j);
            last = max(last, x);
        }
        printf("%d\n", se.size());
    }

    return 0;
}

4. 后继

  1. 在优化部分， 为什么我令last = *se.begin()， 他就会超时呢？ 求解决o(╥﹏╥)o

解决了QAQ， 原来当 se 为空时， 取 se.begin()会出错， QAQ， 优化部分代码， 这样更优化一点点

1
2
3
4
if (!se.empty()) last = *se.begin();
else last = x + 1;
for (int j = last; j <= x; ++j)
    se.erase(j);

G CodeForces 706C

1. 题目大意

给你n个字符串， 以及翻转字符串所需要的花费， 问要使得这n个字符串按字典序排序， 最小花费是多少， 如果没有， 输出-1.

2. 分析

简单的dp， 但我打比赛的时候没敢想。但也就4中情况， 前 翻转/没翻转 ，后 翻转/没翻转 ， 设f[i][0] / f[i][1] 没翻转， 翻转的最小花费。

3. 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
#include <bits/stdc++.h>

#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

ll read() {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
string s[N], ds[N];

int c[N];
ll f[N][2];

int main(){
    int n = read();
    for (int i = 1; i <= n; ++i) c[i] = read();
    for (int i = 1; i <= n; ++i){
        cin >> s[i];
        ds[i] = s[i];
        reverse(ds[i].begin(), ds[i].end());
    }
    ms(f, llINF);
    f[1][0] = 0, f[1][1] = c[1];
    for (int i = 2; i <= n; ++i){
        if (s[i] >= s[i - 1])
            f[i][0] = f[i - 1][0];
        if (s[i] >= ds[i - 1])
            f[i][0] = min(f[i][0], f[i - 1][1]);
        if (ds[i] >= s[i - 1])
            f[i][1] = min(f[i][1], f[i - 1][0] + c[i]);
        if (ds[i] >= ds[i - 1])
            f[i][1] = min(f[i][1], f[i - 1][1] + c[i]);
    }
    ll ans = min(f[n][1], f[n][0]);
    if (ans == llINF) puts("-1");
    else cout << ans << "\n";
    return 0;
}

H HYSBZ 4337

树哈希， 还没补，QAQ， 我打算把比较普通的哈希学完再来补这个题

I HDU 6638

最大字段和， 还没补， QAQ， 打算把线段树专题做一遍在补这个题

J HDU 6514

1. 题目大意

给一个n * m的矩阵， 然后给p个矩阵， 然后再给q个矩阵， 问着q个矩阵之一， 是否被那p个矩阵全覆盖。

2. 分析

把p个矩阵覆盖的区域全赋值1， 问题就转化成 q个矩阵之一 覆盖区域的和 是不是等于矩阵的面积。

如何把p个矩阵全赋值1， 二维差分。

如何求q个矩阵之一 覆盖区域之和， 二维前缀和。

对了， 这题特坑， 要把二维矩阵转化为一维。。

3. 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>

#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 1e7 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

ll read() {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
int m, n, p, q;
inline int _(int x, int y){  //二维矩阵转化为一维
    return (x - 1) * m + y - 1;
}
int diff[N];
int x1, x2, y, y2;
int main() {
    while(~scanf("%d%d", &n, &m)){
        p = read();
        ms(diff, 0);
        // 差分
        for (int i = 0; i < p; ++i){
            x1 = read(), y = read(), x2 = read(), y2 = read();
            diff[_(x1, y)] += 1;
            if (x2 + 1 <= n)
                diff[_(x2 + 1, y)] -= 1;
            if (y2 + 1 <= m)
                diff[_(x1, y2 + 1)] -= 1;
            if (x2 + 1 <= n && y2 + 1 <= m)
                diff[_(x2 + 1, y2 + 1)] += 1;
        }
        // 通过差分还原矩阵
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                if (i == 1 && j == 1) continue;
                else if (i == 1){
                    diff[_(i, j)] += diff[_(i, j - 1)];
                }
                else if (j == 1){
                    diff[_(i, j)] += diff[_(i - 1, j)];
                }
                else
                    diff[_(i, j)] += diff[_(i - 1, j)] + diff[_(i, j - 1)] - diff[_(i - 1, j - 1)];
            }
        }
        // 把被多次覆盖的变为1
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (diff[_(i, j)] >= 1) diff[_(i, j)] = 1;
            }
        }
        // 求前缀和
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                if (i == 1 && j == 1) continue;
                else if (i == 1){
                    diff[_(i, j)] += diff[_(i, j - 1)];
                }
                else if (j == 1){
                    diff[_(i, j)] += diff[_(i - 1, j)];
                }
                else
                    diff[_(i, j)] += diff[_(i - 1, j)] + diff[_(i, j - 1)] - diff[_(i - 1, j - 1)];
            }
        }


        q = read();
        int sum;
        for (int i = 0; i < q; ++i){
            // 每一次询问求前缀和， 与矩形面积进行比较
            x1 = read(), y = read(), x2 = read(), y2 = read();
            sum = diff[_(x2, y2)];
            if (y > 1) {
                sum -= diff[_(x2, y - 1)];
            }
            if (x1 > 1) {
                sum -= diff[_(x1 - 1, y2)];
            }
            if (y > 1 && x1 > 1) {
                sum += diff[_(x1 - 1, y - 1)];
            }
            if (sum == (x2 - x1 + 1) * (y2 - y + 1)) puts("YES");
            else puts("NO");
        }
    }

    return 0;
}

4. 后继

  1. 正是因为这个题我才开始学二维前缀和， 二维差分的。

K 计蒜客 A1951

状压Dp， 等着在补， 等着在补， QAQ

L HDU 1384

1. 题目大意

给你n个闭区间， 要求最后的集合中要包含这些区间[a, b]的至少c个数， 求最后集合的最小size。

2. 分析

差分约束。

推荐两篇博客

差分约束系统学习笔记

差分约束系统

设f[i]为[0, i]中在最后集合里的数的个数。
由题意可知 f[b] - f[a - 1] >= c， 求最小值要跑最长路。

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
86
87
88
89
#include <bits/stdc++.h>

#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 5e4 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

ll read() {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

struct edge {
    int u, v, w, ne;
} ed[4 * N];
int head[N], dis[N], vis[N], cnt;

inline void init() {
    ms(head, -1);
    ms(dis, -INF);
    ms(vis, 0);
    cnt = 0;
}

inline void add(int u, int v, int w) {
    ed[cnt] = {u, v, w, head[u]};
    head[u] = cnt++;
}

queue<int> q;

void spfa(int u) {
    vis[u] = 1;
    dis[u] = 0;
    q.push(u);
    while (!q.empty()) {
        u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = ed[i].ne) {
            int v = ed[i].v;
            if (dis[v] < dis[u] + ed[i].w) {
                dis[v] = dis[u] + ed[i].w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}


int a, b, c, n;

int main() {
    while (~scanf("%d", &n)) {
        init();
        int mx = 0, mi = INF;
        for (int i = 0; i < n; ++i) {
            a = read(), b = read(), c = read();
            add(a - 1, b, c);
            mx = max(mx, b);
            mi = min(mi, a);
        }
        for (int i = mi - 1; i < mx; ++i) {
            add(i + 1, i, -1);
            add(i, i + 1, 0);
        }
        spfa(mi - 1);
        printf("%d\n", dis[mx]);
    }
    return 0;
}

M POJ 3613

1. 题目大意

给出一张图， 求k边最短路， 即经过k条边的最短路。

2. 分析

思考一下：如果一个矩阵，表示走k条边后，一张图的点与点的最短路径，(a,b)表示从a到b的最短路径，然后我们把它与自己，按照矩阵乘法的格式“相乘”，把其中的乘改为取min，c.a[i][j] = min(c.a[i][j],x.a[i][k]+y.a[k][j]) ， 那么两个矩阵”相乘“之后的结果就是 经过k + k条边后的最短路。

c中的一个点(a,b)，当我们用x矩阵和y矩阵求它时，我们枚举了x矩阵的a行所有数，与y矩阵的b列所有数，并且他们的坐标只能是相对应的，比如x矩阵的(a,2)这个点，相应的y矩阵点就是(2,b)，那么放到图上去理解，即从a点经过2点到b点的距离，类似的点不只有2，把所有点枚举完后，c.a[a][b]就是从a到b的最短距离。（意会一下）

这样下来，会得到走k+k条边的最短路径，对于其他的矩阵这样操作，得到的是他们两个，经过的边数相加的结果。（一个经过a条边后的矩阵 与 一个经过b条边后的矩阵这样操作后，是经过a+b条边后的矩阵，矩阵中存的是最短路径）。解释一下：向上面的例子一样，(a,2)(2,b)，是即从a点经过2点到b点的距离,因为x矩阵和y矩阵都是走k条边后的最短路径，那么x矩阵中的(a,2)是走k步后的最短路径，(2,b)也是，那么他们相加不就是走k+k条边后的最短路径吗？其他的矩阵一样。

部分转自 https://www.cnblogs.com/mjtcn/p/7308870.html

因为就100头牛， 离散化一下。

那么就转化成矩阵快速幂问题了。

3. 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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#define eps 1e-8
#define ms(a, b) memset((a), (b), sizeof (a))

using namespace std;
typedef long long ll;
typedef std::pair<ll, ll> P;
const int N = 5e4 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;

void read(int &ans) {
    ll x = 0, w = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    ans = x * w;
}
int n;
struct matrix{
    int m[205][205];
    matrix(){
        ms(m, INF);
    }
    matrix operator * (const matrix & x) const{
        matrix c;
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= n; ++j){
                for (int k = 1; k <= n; ++k){
                    c.m[i][j] = min(c.m[i][j], m[i][k] + x.m[k][j]);
                }
            }
        }
        return c;
    }
}x;

matrix qpow(matrix a, int b){
    matrix ans = a;
    b--;
    while(b){
        if (b & 1) ans = ans * a;
        b >>= 1;
        a = a * a;
    }
    return ans;
}
map<int, int>ma;
int k, t, s, e, a, b, c;

int main() {
    int cnt = 0;
    scanf("%d%d%d%d", &k, &t, &s, &e);
    while(t--){
        scanf("%d%d%d", &c, &a, &b);
        if (ma[a]) a = ma[a]; else a = ma[a] = ++cnt;
        if (ma[b]) b = ma[b]; else b = ma[b] = ++cnt;
        x.m[a][b] = x.m[b][a] = c;
    }
    n = cnt;
    x = qpow(x, k);
    printf("%d\n", x.m[ma[s]][ma[e]]);
    return 0;
}

4. 后继

  1. 矩阵快速幂居然还能用重载 * 来写， 太美妙了。
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。