部分参照 SDNU_ACM_ICPC_2020_Winter_Practice_2nd【解题报告】– The__Flash。
欢迎评论提问， 纠错

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

专题链接： SDNU_ACM_ICPC_2020_Winter_Practice_2nd

A HDU 1559 【The__Flash】的矩阵

1. 题目大意

给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。

2. 分析

一开始我以为是最大子矩阵和, 做了几个题回来发现就是个二维前缀和.

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
#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 pair<ll, ll> P;
const int N = 1e5 + 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 a[1003][1003];
int m, n, x, y;
int main() {
    int t;
    read(t);
    while(t--){
        read(m), read(n), read(x), read(y);
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                read(a[i][j]);
                if (i == 0 && j != 0){
                    a[i][j] += a[i][j - 1];
                }
                if (i != 0 && j == 0){
                    a[i][j] += a[i - 1][j];
                }
                if (i != 0 && j != 0){
                    a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
                }
            }
        }
        int ans = 0, temp;
        x--, y--;
        for (int i = 0; i < m - x; ++i){
            for (int j = 0; j < n - y; ++j){
                temp = a[i + x][j + y];
                if (i)
                    temp -= a[i - 1][j + y];
                if (j)
                    temp -= a[i + x][j - 1];
                if (i && j)
                    temp += a[i - 1][j - 1];
                ans = max(ans, temp);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B HDU 3790 【The__Flash】的疑惑

1. 题目大意

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

2. 分析

就是个最短路, 需要维护两个东西, 最短距离和花费.

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
#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 = 1e3 + 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;
}

struct edge{
    int v, w, c, ne;
}ed[200005];
int head[N], dis[N], dis1[N], vis[N], cnt;
inline void init(){
    ms(head, -1);
    ms(dis, INF);
    ms(dis1, INF);
    ms(vis, 0);
    cnt = 0;
}
inline void add(int u, int v, int w, int c){
    ed[cnt] = {v, w, c, head[u]};
    head[u] = cnt++;
}

priority_queue<P, vector<P>, greater<P> > q;

void dijk(int u){
    dis[u] = 0;
    dis1[u] = 0;
    q.push(P(0, u));
    while(!q.empty()){
         u = q.top().second;
         q.pop();
         if (vis[u]) continue;
         vis[u] = 1;
         for (int i = head[u]; ~i; i = ed[i].ne){
             int v = ed[i].v, w = ed[i].w, c = ed[i].c;
             // 维护dis 和 dis1
             if (dis[v] > dis[u] + w){
                 dis[v] = dis[u] + w;
                 dis1[v] = dis1[u] + c;
                 q.push(P(dis[v], v));
             }
             else if (dis[v] == dis[u] + w){
                 dis1[v] = min(dis1[v], dis1[u] + c);
                 q.push(P(dis[v], v));
             }

         }
    }
}

int n, m, u, v, w, c, s, t;
int main() {
    while(~scanf("%d%d", &n, &m)){
        if (m == 0 && n == 0) break;
        init();
        for (int i = 0; i < m; ++i){
            read(u), read(v), read(w), read(c);
            add(u, v, w, c);
            add(v, u, w, c);
        }
        read(s), read(t);
        dijk(s);
        cout << dis[t] << ' ' << dis1[t] << "\n";
    }


    return 0;
}

C CodeForces 670C 【The__Flash】的电影

1. 题目大意

有n个人， 每个人只会一种语言， 然后有m场电影， 电影的声音和字幕是两种不同的语言， 问 选择哪一场电影， 使得能听懂的人最多， 如果能听懂的一样多， 那么就使能看懂的人最多， 如果听懂的和看懂的都一样多， 输出其中任何一场电影都行。

2. 分析

比较直观的想法， 统计每个语言会的人数， 遍历m场电影， 选择能听懂的最大的， 如果能听懂的一样多， 选择能看懂的最大的。（由于数据太大进行离散化处理）

我当时没直接离散化，偷懒用的map， wa了两次，最后 还是用map， set卡过了(*^▽^*)

下面贴离散化的做法

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

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int N = 2e5 + 20;
const int M = 1e6 + 20;
const int INF = 0x3f3f3f3f;
const ll llINF = 4611686018427387903;
const int mod = 10007;

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 a[N], b[N], c[N], d[N * 3], num[N];
int len;

inline int f(int x){
    return lower_bound(d + 1, d + len + 1, x) - d;
}
int main(){
    int n, m;
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    m = read();
    for (int i = 1; i <= m; ++i) b[i] = read();
    for (int i = 1; i <= m; ++i) c[i] = read();
    for (int i = 1; i <= n; ++i) d[++len] = a[i];
    for (int i = 1; i <= m; ++i) d[++len] = b[i];
    for (int i = 1; i <= m; ++i) d[++len] = c[i];
    sort(d + 1, d + len + 1);
    len = unique(d + 1, d + len + 1) - (d + 1);
    for (int i = 1; i <= n; ++i) num[f(a[i])]++;
    int mx1 = -1, mx2 = -1, id;
    for (int i = 1; i <= m; ++i){
        b[i] = f(b[i]) ,c[i] = f(c[i]);
        if (mx1 < num[b[i]] || mx1 == num[b[i]] && mx2 < num[c[i]]){
            mx1 = num[b[i]];
            mx2 = num[c[i]];
            id = i;
        }
    }
    cout << id << "\n";
    return 0;
}

4. 后继

打算写一篇关于 unique 用法的博客， 写完了回来补上。

D UVA 10305 【The__Flash】的排序

1. 题目大意

拓扑排序裸题

2. 分析

拓扑排序裸题

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

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, m, a, b, in[102];
vector<int>ve[N];
queue<int>q;
vector<int>ans;
inline void init(){
    for (int i = 0; i <= n; ++i){
        ve[i].clear();
        in[i] = 0;
        ans.clear();
    }
}

int main() {
    while(~scanf("%d%d", &n, &m) && (m || n)){
        init();
        while(m--){
            read(a), read(b);
            ve[a].push_back(b);
            in[b]++;
        }
        for (int i = 1; i <= n; ++i){
            if (in[i] == 0) q.push(i);
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            ans.push_back(u);
            for (int i = 0; i < ve[u].size(); ++i){
                int v = ve[u][i];
                in[v]--;
                if(in[v] == 0) q.push(v);
            }
        }
        for (int i = 0; i < ans.size() - 1; ++i)
            cout << ans[i] << " ";
        cout << ans.back() << "\n";
    }
    return 0;
}

E HDU 4578 【The__Flash】的操作

1. 题目大意

裸线段树， 就是有些许麻烦。4个操作

1
2
3
4
1 x y c 将[x, y]区间的数加c
2 x y c 将[x, y]区间的数乘c
3 x y c 将[x, y]区间的数重置为c
4 x y p 输出[x, y]区间的数的 p次方和

2. 分析

两种做法， 先说第一种也是通俗易懂的一种但是代码写起来很抓狂。。。
3个lazy数组， 3个存值数组

1
2
3
4
5
6
add[i] 加标记
mul[i] 乘标记
sett[i] 重置标记
sum[i] 1次方和
sum2[i] 2次方和
sum3[i] 3次方和

难弄的是add[i] 的 二、三次方和 怎么求。酱紫

1
2
3
4
5
6
7
sum2[rt] = (a + add) ^ 2 + (b + add) ^ 2 + (c + add) ^ 2
= (a^2 + b^2 + c^2) + 2 * add * (a + b + c) + 3 * val ^ 2
= sum2[rt] + 2 * add[rt] * sum[rt] + (r - l + 1) * add[rt] * add[rt]

sum3[rt] = (a + add) ^ 3 + (b + add) ^ 3 + (c + add) ^ 3
= (a^3 + b^3 + c ^ 3) + 3 * add * (a^2 + b^2 + c^2) + 3 * add * add * (a + b + c) + 3 * add * add * add
 = sum3[rt] + 3 * add[rt] * sum2[rt] + 3 * add[rt] * add[rt] + sum[rt] + (r - l + 1) * add[rt] * add[rt] * add[rt]

然后就是快乐了写代码时间了， 记得注意取余（因为取余我debug了2小时+ o(╥﹏╥)o）

第二种， 只用一个lazy数组， 太妙了， 它是以区间里的数是否相等作为lazy数组

1
2
flag[i] i表示的区间里的数是否相等
val[i] 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
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int N = 1e5 + 20;
const int M = 1e6 + 20;
const int INF = 0x3f3f3f3f;
const ll llINF = 4611686018427387903;
const int mod = 10007;

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 mul[N << 2], sett[N << 2], add[N << 2], sum[N << 2], sum2[N << 2], sum3[N << 2];


void pushup(int rt) {
    sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % mod;
    sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % mod;
    sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;
}

void build(int l, int r, int rt) {
    sett[rt] = add[rt] = 0;
    mul[rt] = 1;
    if (l == r) {
        sum[rt] = sum2[rt] = sum3[rt] = 0;
        return;
    }
    int m = l + r >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}


void pushdown(int rt, int len) {
    if (sett[rt]) {
        sett[rt << 1] = sett[rt << 1 | 1] = sett[rt];
        add[rt << 1] = add[rt << 1 | 1] = 0;    //注意这个也要下放
        mul[rt << 1] = mul[rt << 1 | 1] = 1;
        int tmp = ((sett[rt] * sett[rt]) % mod) * sett[rt] % mod;
        sum[rt << 1] = ((len - (len >> 1)) % mod) * (sett[rt]) % mod;
        sum[rt << 1 | 1] = ((len >> 1) % mod) * (sett[rt]) % mod;
        sum2[rt << 1] = ((len - (len >> 1)) % mod) * ((sett[rt] * sett[rt]) % mod) % mod;
        sum2[rt << 1 | 1] = ((len >> 1) % mod) * ((sett[rt] * sett[rt]) % mod) % mod;
        sum3[rt << 1] = ((len - (len >> 1)) % mod) * tmp % mod;
        sum3[rt << 1 | 1] = ((len >> 1) % mod) * tmp % mod;
        sett[rt] = 0;
    }
    if (mul[rt] != 1) {    //这个就是mul[rt] != 1 ， 当时我这里没注意所以TLE了
        mul[rt << 1] = (mul[rt << 1] * mul[rt]) % mod;
        mul[rt << 1 | 1] = (mul[rt << 1 | 1] * mul[rt]) % mod;
        add[rt << 1] = (add[rt << 1] * mul[rt]) % mod;
        add[rt << 1 | 1] = (add[rt << 1 | 1] * mul[rt]) % mod;
        int tmp = (((mul[rt] * mul[rt]) % mod * mul[rt]) % mod);
        sum[rt << 1] = (sum[rt << 1] * mul[rt]) % mod;
        sum[rt << 1 | 1] = (sum[rt << 1 | 1] * mul[rt]) % mod;
        sum2[rt << 1] = (sum2[rt << 1] % mod) * ((mul[rt] * mul[rt]) % mod) % mod;
        sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] % mod) * ((mul[rt] * mul[rt]) % mod) % mod;
        sum3[rt << 1] = (sum3[rt << 1] % mod) * tmp % mod;
        sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] % mod) * tmp % mod;
        mul[rt] = 1;
    }
    if (add[rt]) {
        add[rt << 1] = (add[rt << 1] + add[rt]) % mod;
        add[rt << 1 | 1] = (add[rt << 1 | 1] + add[rt]) % mod;
        int tmp = (add[rt] * add[rt] % mod) * add[rt] % mod;        //注意sum3 , sum2 , sum的先后顺序
        sum3[rt << 1] = (sum3[rt << 1] + tmp * (len - (len >> 1) % mod) % mod + 3 * add[rt] * sum2[rt << 1] % mod +
                 3 * add[rt] * add[rt] % mod * sum[rt << 1]) % mod;
        sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] + tmp * ((len >> 1) % mod) % mod + 3 * add[rt] * sum2[rt << 1 | 1] % mod +
                         3 * add[rt] * add[rt] % mod * sum[rt << 1 | 1]) % mod;
        sum2[rt << 1] = (sum2[rt << 1] + ((add[rt] * add[rt] % mod) * ((len - (len >> 1)) % mod)) % mod +
                         (2 * sum[rt << 1] * add[rt] % mod)) % mod;
        sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] + (((add[rt] * add[rt] % mod) * ((len >> 1)) % mod)) % mod +
                             (2 * sum[rt << 1 | 1] * add[rt] % mod)) % mod;

        sum[rt << 1] = (sum[rt << 1] + ((len - (len >> 1)) % mod) * add[rt] % mod) % mod;
        sum[rt << 1 | 1] = (sum[rt << 1 | 1] + ((len >> 1) % mod) * add[rt] % mod) % mod;
        add[rt] = 0;
    }

}

void update(int op, int L, int R, int c, int l, int r, int rt) {
    if (l >= L && r <= R) {
        if (op == 3) {
            sett[rt] = c;
            add[rt] = 0;
            mul[rt] = 1;
            sum[rt] = ((r - l + 1) % mod * c) % mod;
            sum2[rt] = ((r - l + 1) % mod * ((c * c) % mod)) % mod;
            sum3[rt] = ((r - l + 1) % mod * (((c * c) % mod) * c % mod)) % mod;
        } else if (op == 2) {
            mul[rt] = (mul[rt] * c) % mod;
            add[rt] = (add[rt] * c) % mod;
            sum[rt] = (sum[rt] * c) % mod;
            sum2[rt] = sum2[rt] * (c * c % mod) % mod;
            sum3[rt] = sum3[rt] * ((c * c % mod) * c % mod) % mod;
        } else if (op == 1) {
            add[rt] = (add[rt] + c) % mod;
            int tmp = (((c * c) % mod * c) % mod * (r - l + 1) % mod) % mod;
            sum3[rt] = (sum3[rt] + tmp + 3 * c * sum2[rt] % mod + 3 * c * c % mod * sum[rt]) % mod;
            sum2[rt] = (sum2[rt] + (c * c % mod * ((r - l + 1) % mod)) % mod + 2 * sum[rt] * c % mod) % mod;
            sum[rt] = (sum[rt] + (r - l + 1) % mod * c % mod) % mod;
        }

        return;
    }
    pushdown(rt, r - l + 1);
    int m = l + r >> 1;
    if (m >= L) update(op, L, R, c, l, m, rt << 1);
    if (m < R) update(op, L, R, c, m + 1, r, rt << 1 | 1);
    pushup(rt);
}

int query(int L, int R, int p, int l, int r, int rt) {
    if (l >= L && r <= R) {
        if (p == 1)
            return sum[rt];
        if (p == 2)
            return sum2[rt];
        if (p == 3)
            return sum3[rt];
    }
    pushdown(rt, r - l + 1);
    int ans = 0;
    int m = l + r >> 1;
    if (m >= L)
        ans = (ans + query(L, R, p, l, m, rt << 1)) % mod;
    if (m < R)
        ans = (ans + query(L, R, p, m + 1, r, rt << 1 | 1)) % mod;
    return ans;
}

int n, m, op, x, y, c;

int main() {
    while (~scanf("%d%d", &n, &m)) {
        if (!m && !n) break;
        build(1, n, 1);
        while (m--) {
            op = read(), x = read(), y = read(), c = read();
            if (op <= 3)
                update(op, x, y, c, 1, n, 1);
            else
                printf("%d\n", query(x, y, c, 1, n, 1));
        }
    }
    return 0;
}

第二种方法

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
#include <bits/stdc++.h>
#define eps 1e-7
#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 + 20;
const int M = 1e6 + 20;
const int INF = 0x3f3f3f3f;
const ll llINF = 4611686018427387903;
const int mod = 10007;

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

bool flag[N << 2];
int val[N << 2];

void init(){
    ms(flag, true);
    ms(val, 0);
}

void update(int op, int L, int R, int c, int l, int r, int rt){
    if (l >= L && r <= R && flag[rt]){
        if (op == 1)
            val[rt] = (val[rt] + c) % mod;
        else if (op == 2)
            val[rt] = (val[rt] * c) % mod;
        else if (op == 3)
            val[rt] = c;
        return ;
    }
    if (flag[rt]){ // pushdown
        flag[rt << 1] = flag[rt << 1 | 1] = 1;
        flag[rt] = 0;
        val[rt << 1] = val[rt << 1 | 1] = val[rt];
    }
    int m = l + (r - l) / 2;
    if (m >= L)
        update(op, L, R, c, l, m, rt << 1);
    if (m < R)
        update(op, L, R, c, m + 1, r, rt << 1 | 1);
    if (flag[rt << 1] && flag[rt << 1 | 1]){
        if (val[rt << 1] == val[rt << 1 | 1]){
            flag[rt] = 1;
            val[rt] = val[rt << 1];
        } else flag[rt] = 0;
    }
    else flag[rt] = 0;
}

int query(int L, int R, int p, int l, int r, int rt){
    if (l >= L && r <= R && flag[rt]){
        int ans = 1;
        for (int i = 1; i <= p; ++i){
            ans = (ans * val[rt]) % mod;
        }
        ans = ans * (r - l + 1) % mod;
        return ans;
    }
    if (flag[rt]){
        flag[rt << 1] = flag[rt << 1 | 1] = 1;
        flag[rt] = 0;
        val[rt << 1] = val[rt << 1 | 1] = val[rt];
    }
    int m = l + (r - l) / 2;
    int ans = 0;
    if (m >= L)
        ans += query(L, R, p, l, m, rt << 1) % mod;
    if (m < R)
        ans += query(L, R, p, m + 1, r, rt << 1 | 1) % mod;
    return ans % mod;
}
int n, m;
int main(){
    while(~scanf("%d%d", &n, &m)){
        if (n == 0 && m == 0) break;
        int x, y, op, c;
        init();
        while(m--){
            op = read(), x = read(), y = read(), c = read();
            if (op <= 3)
                update(op, x, y, c, 1, n, 1);
            else
                printf("%d\n", query(x, y, c, 1, n, 1));
        }
    }
    return 0;
}

4. 后继

  1. 线段树要开4倍空间, 为什么
  2. 传lazy数组时， 不仅值要更新， lazy数组也要更新
  3. update， build操作完， 别忘了pushup
  4. uodate操作更新lazy数组时， 别忘了更新值。
  5. 左子树的区间长度(len - (len >> 1))>= 右子树的区间长度 (len >> 1)

F CodeForces 797B 【The__Flash】的序列

1. 题目大意

给你一个序列， 找出一个子序列， 使得其和为奇数且最大。

2. 分析

先求出最大和， 也就是把大于0的数都加起来， 如果是奇数就输出， 如果是偶数就减去绝对值最小的奇数。

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

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 a[N];
int main() {
    int n;
    read(n);
    int sum = 0;
    int flag = 100000;
    for (int i = 0; i < n; ++i){
        read(a[i]);
        if (a[i] > 0){
            sum += a[i];
        }
        if (a[i] & 1)
            flag = min(flag, abs(a[i]));
    }
    if (sum & 1) cout << sum << "\n";
    else cout << sum - flag << "\n";
    return 0;
}

G CodeForces 1223B 【The__Flash】的水题

1. 题目大意

字符串可以进行这样一个操作， 将相邻的字符（a ， b）变成（a， a）或者 （b， b）
可以进行任意次这种操作

2. 分析

进行任意次操作后， 字符串里的字符就全一样了， 所以只需要判断两个字符串中是否有相同的字符即可。
把第一个字符串所有字符塞到set<char>里， 然后遍历第二个字符串， 看看能不能从里面找出一样的。

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

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


string a, b;
set<char>se;
int main() {
    int t;
    read(t);
    while(t--){
        se.clear();
        cin >> a >> b;
        for (int i = 0; i < a.length(); ++i) se.insert(a[i]);
        int flag = 0;
        for (int i = 0; i < b.length(); ++i){
            if (se.find(b[i]) != se.end()){
                flag = 1;
                break;
            }
        }
        if (flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

H CodeForces 960B 【The__Flash】的赠予

1. 题目大意

给你两个序列a, b， 定义E = (ai - bi) ^ 2 | i : 1 - n , 每一次操作可以使序列中的某个数加1或者减1， 问对序列a进行k1次操作， b进行k2次操作后E的最小值。

2. 分析

每一次操作就是使 |ai - bi|的值减小1， 因为要求最小值， 所以对|ai - bi|的值越大的 操作 越值得。 例如： 对9 减1后， 实际减小的值为 9 ^ 2 - 8 ^ 2 = 17, 对8 减1后， 实际减小的值为 8 ^ 2 - 7 ^ 2 = 15, 可见对|ai - bi|的值越大的 操作 越值得。
然后就是把|ai - bi|塞进优先队列里， 每次取top 对其减一， 执行k1 + k2次即可。

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

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;
}
priority_queue<int> q;
int a[1003], b[1003];
int main() {
    int n, k1, k2;
    read(n), read(k1), read(k2);
    for (int i = 0; i < n; ++i)
        read(a[i]);
    for (int i = 0; i < n; ++i){
        read(b[i]);
        q.push(abs(a[i] - b[i]));
    }
    int k = k1 + k2;
    while(k--){
        int u = q.top();
        q.pop();
        q.push(abs(u - 1));
    }
    ll ans = 0;
    while(!q.empty()){
        int u = q.top();
        q.pop();
        ans += 1ll * u * u; // 注意会爆long long
    }
    cout << ans << "\n";
    return 0;
}

4. 后继

  1. 会爆ll， 前面 * 1ll。

I SCU 4444 【The__Flash】的旅行

1. 题目大意

n个城市（1 - n）， 有n * (n - 1) / 2条路， 其中有m条路权值为a（具体哪m条已给出）， 剩下的权值为b， 无向图， 问城市1到城市n的最短路。

2. 分析

打比赛的时候想的有点多， 其中有一个情况没想出来，o(╥﹏╥)o

肯定要分为 a <= b 和 a > b

当a <= b时， 如果dis[1][n] == a, 那就是a。 否则跑a的最短路dis[1][n], 答案就是min(dis[1][n], b)。
当a > b时， 如果dis[1][n] == b , 那就是b。
否则， 判断m条a边是不是把 城市1 或 城市n 堵上， 换句话说， 判断城市1 或者城市n所连的所有边是不是都是权值为a的边， 如果 城市1 或者城市n全是， 那么答案就是a， 因为 如果被全堵上， 走两条边的话， 其中一条边肯定是a边， 那就不如直接走1-n了。 如果都没被堵上， 答案就是走一条a边和走2条b边的最小值 min(a, 2 * b)。

如果不会自定义优先队列优先级， 请戳 优先队列定义优先级的方法

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

#define eps 1e-7
#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 = 4611686018427387903;
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;
}

struct edge{
    int v, w, ne;
}ed[M];

int head[N], vis[N], cnt;
ll dis[N];
int n, m, a, b;
inline void init(){
    for (int i = 0; i <= n; ++i){
        head[i] = -1, vis[i] = 0, dis[i] = llINF;
    }
    cnt = 0;
}

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

priority_queue<P, vector<P> , greater<P> >q;
void dijk(int u){
    dis[u] = 0;
    q.push(P(0, u));
    while(!q.empty()){
        u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; ~i; i = ed[i].ne){
            int v = ed[i].v, w = ed[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.push(P(dis[v], v));
            }
        }
    }
}

int main(){
    int u, v, dis1n, in1, in2;
    while(~scanf("%d%d%d%d", &n, &m, &a, &b)){
        init();
        dis1n = b;
        in1 = in2 = 0;
        while(m--){
            read(u), read(v);
            if (u > v) swap(u, v);
            add(u, v, a);
            add(v, u, a);
            if (u == 1) in1++;
            if (v == n) in2++;
            if (u == 1 && v == n) dis1n = a;
        }
        if (a <= b){
            if (dis1n == a) cout << a << "\n";
            else{
                dijk(1);
                if (dis[n] <= b) cout << dis[n] << "\n";
                else cout << b << "\n";
            }
        }
        else{
            if (dis1n == b){
                cout << b << "\n";
                continue;
            }
            int sum = 0;
            if (in1 == n - 1) sum++;
            if (in2 == n - 1) sum++;
            if (sum >= 1) cout << a << "\n";
            else cout << min(a, 2 * b) << "\n";
            
        }
    }
}

J HDU 1556 【The__Flash】的球球

1. 题目大意

中文题， qaq
N个气球排成一排，从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

2. 分析

差分模板题。

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

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, l, r;
int diff[N], ans[N];
int main() {
    while(~scanf("%d", &n) && n){
        ms(diff, 0);
        for (int i = 0; i < n; ++i){
            read(l), read(r);
            diff[l] ++;
            diff[r + 1]--;
        }
        int add = 0;
        for (int i = 1; i <= n; ++i){
            add += diff[i];
            ans[i] = add;
        }
        for (int i = 1; i < n; ++i)
            cout << ans[i] << " ";
        cout << ans[n] << "\n";
    }


    return 0;
}

K POJ 2018 【The__Flash】的牛牛

1. 题目大意

给你一个长为n（n <= 1e5）的序列， 求其长度至少为F区间， 其平均值*1000的最大值。

2. 分析

一开始以为是dp， 然后没思路qaq

二分答案qaq， tql

没想到居然是二分答案， qaq。

关键是如何以更小的时间判断二分出来的值 （mid）是不是符合要求的，也就是 判断 长度至少为F的区间的平均值， 有没有大于mid的。

先说二分， 我要求最大的满足条件的数， 所以就是从后向前查询。 从后向前详情请点击 二分总结

然后如何判断呢， 那就把区间都减去mid， 就变成找一段区间[l, r]， 使 sum[r] - sum[l - 1] >= 0 , 这样记录 sum[l - 1]的最小值即可。

还有一种做法， 请参考 POJ2018 Best Cow Fences (二分答案+类前缀和)

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
#include <cstdio>
#include <iostream>
#include <cmath>
#define eps 1e-7
#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 = 4611686018427387903;
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, k;
double sum[N];
int a[N];
inline bool is(double x){
    for (int i = 1; i <= n; ++i)
        sum[i] = a[i] - x;
    for (int i = 1; i <= n; ++i)
        sum[i] += sum[i - 1];
    double mi = INF * 1.0;
    for(int i = k; i <= n; ++i){
        mi = min(mi, sum[i - k]);
        if (sum[i] - mi >= -eps) // 特别注意这里。。
            return 1;
    }
    return 0;
}

int main(){
    read(n), read(k);
    for (int i = 1; i <= n; ++i){
        read(a[i]);
    }
    int l = 0, r = 2000000, m;
    while(l < r){
        m = l + (r - l + 1) / 2;
        if (is(1.0 * m / 1000))
            l = m;
        else r = m - 1;
    }
    cout << l << "\n";
    return 0;
}

第二种做法

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
#include <cstdio>
#include <iostream>

#define eps 1e-7
#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 = 4611686018427387903;
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, k;
int sum[N];
int a[N];
double rsum[N];
inline bool is(double x){
    rsum[n] = a[n] - x;
    for (int i = n - 1; i >= 1; --i){
        rsum[i] = a[i] - x;
        if (rsum[i + 1] > 0) rsum[i] += rsum[i + 1];
    }
    for (int i = 1; i <= n - k + 1; ++i){
        if (sum[i + k - 1] - sum[i - 1] >= x * k)
            return true;
        if (sum[i + k - 1] - sum[i - 1] - x * k + rsum[i + k] >= 0)
            return true;
    }
    return false;
}

int main(){
    read(n), read(k);
    for (int i = 1; i <= n; ++i){
        read(a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    int l = 0, r = 2000000, m;
    while(l < r){
        m = l + (r - l + 1) / 2;
        if (is(1.0 * m / 1000))
            l = m;
        else r = m - 1;
    }
    cout << l << "\n";


    return 0;
}

4. 后继

  1. 知道如何在O(n)求 长度至少为k的 区间和的最大值

L CodeForces 621B 【The__Flash】的鲨鲨

1. 题目大意

1000 * 1000 的网格中， 处于对角线上的鲨鲨会互相打架， 求有对少对鲨鲨会打架。

2. 分析

画图可分析， 处于对角线上的鲨鲨满足 x + y = t (0<= t <= 2000) 或者满足 x - y = t (-1000 <= t <= 1000)， 分别用两个数组储存在每一条对角线上的个数， 然后n * (n - 1) / 2 计算即可， 注意x - y的范围， 可以化成 x - y + 1000 = t (0 <= t <= 2000) ， 因为这个我re了两次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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

#define eps 1e-7
#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 = 4611686018427387903;
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;
}

struct node{
    int hp, atk;
    double v;
}a[N];

bool cmp(node x, node y){
    if (fabs(x.v - y.v) <= eps)
        return x.hp > y.hp;
    return x.v > y.v;
}
int a1[10003], a2[10003];
int main() {
    int n, x, y;
    read(n);
    for (int i = 0; i < n; ++i){
        read(x), read(y);
        a1[x + y]++;
        a2[x - y + 1000]++;
    }
    ll ans = 0;
    for (int i = 0; i <= 2000; ++i){
        if (a1[i] > 1){
            ans += ll(a1[i]) * ll(a1[i] - 1) / 2;
        }
        if (a2[i] > 1){
            ans += ll(a2[i]) * ll(a2[i] - 1) / 2;
        }
    }
    cout << ans << "\n";
    return 0;
}

4. 后继

  1. 注意数组下标是不是负数 o(╥﹏╥)o

M Gym 102222H 【The__Flash】的达拉崩吧斑得贝迪卜多比鲁翁

1. 题目大意

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
很久很久以前

巨龙突然出现

带来灾难带走了公主又消失不见

王国十分危险

世间谁最勇敢

一位勇者赶来大声喊

“我要带上最好的剑

翻过最高的山

闯进最深的森林

把公主带回到面前”

国王非常高兴忙问他的姓名

年轻人想了想

他说

“陛下我叫达拉崩吧斑得贝迪卜多比鲁翁

再来一次

达拉崩巴斑得贝迪卜多比鲁翁”

“是不是达拉崩吧斑得贝迪卜多比鲁翁”

“对对达拉崩巴斑得贝迪卜多比鲁翁”

...

幽幽小路上，英雄达拉崩吧遇到 n 只怪兽

每只怪兽有其相应的体力值 HP 和 攻击值 ATK

达拉崩吧每次可对怪物造成一次伤害，伤害值为 K（其中，K 在数值上为达拉崩吧攻击这只怪兽的次数）

然鹅，每次存活的怪兽都可以攻击我们的英雄达拉崩吧

当怪兽的体力值小于等于时，怪兽死亡.

现请你选择一种打怪兽的顺序，使得达拉崩吧收到的伤害和最小，并输出收到最小的伤害和.
————————————————
版权声明：本文为CSDN博主「The___Flash」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/The___Flash/article/details/103939876

2. 分析

显而易见， 贪心， 但是当时没会用理解的思维推理， 而是臆测， 不过差一点（很多）就猜对了QAQ

最优情况肯定是把一只怪兽打到死。先只考虑攻击两只怪兽的优先级问题。

设t[i] 是把第i只怪兽打死需要的次数， sum是所有怪兽的总攻击力和

先进攻第一只 所受的攻击 是 sum * t[1] + (sum - atk[1]) * t[2]
先进攻第二只 所受的攻击 是 sum * t[2] + (sum - atk[2]) * t[1]

如果要先攻击第二只

1
2
3
4
sum * t[1] + (sum - atk[1]) * t[2] >= sum * t[2] + (sum - atk[2]) * t[1]
sum * t[1] + sum * t[2] - atk[1] * t[2] >= sum * t[2] + sum * t[1] - atk[2] * t[1]
atk[2] * t[1] >= atk[1] * t[2]
atk[2] / t[2] >= atk[1] / t[1]

所以按照 atk[i] / t[i]排序就行。

那么怎么求把第i只怪兽打死需要的次数呢， 二分次数就行了。

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

#define eps 1e-7
#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 = 4611686018427387903;
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;
}

struct node{
    int hp, atk;
    double v;
}a[N];

bool cmp(node x, node y){
    if (fabs(x.v - y.v) <= eps)
        return x.hp > y.hp;
    return x.v > y.v;
}

int search(int x){
    int low = 0, high = 500, m;
    while(low < high){
        m = low + (high - low) / 2;
        if (m * (m + 1) / 2 >= x)
            high = m;
        else low = m + 1;
    }
    return low;
}

int main() {
    int t, n;
    ll ans, sum;
    read(t);
    for (int tt = 1; tt <= t; ++tt){
        read(n);
        sum = 0;
        for (int i = 0; i < n; ++i){
            read(a[i].hp), read(a[i].atk);
            a[i].hp = search(a[i].hp);
            a[i].v = 1.0 * a[i].atk / a[i].hp; // 这里也可以不用v ， 而直接用 atk[2] * search(hp[1]) >= atk[1] * search(hp[2]) 也行
            sum += a[i].atk;
        }
        ans = 0;
        sort(a, a + n, cmp);
        for (int i = 0; i < n; ++i){
            ans += sum * (a[i].hp);
            sum -= a[i].atk;
        }
        printf("Case #%d: %lld\n", tt, ans);

    }

    return 0;
}

4. 后继

常见贪心证明手段：

  1. 临项交换：

证明在任何局面下，任何对局部最优策略的微小改变都会造成整体结果变差，经常用于以“排序”为贪心策略的证明.

  1. 范围缩放：

证明任何对局面最优策略作用范围的拓展都不会造成整体结果变差.

  1. 决策包容性：

证明在任意局面下，作出局部最优决策以后，在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之，这个局部最优策略提供的可能性包含其他所有策略提供的可能性.

  1. 反证法

  2. 数学归纳法

例题：

POJ-3614

POJ-3190

POJ-1328

国王游戏

POJ-2054

恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

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