欢迎评论提问， 纠错

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

专题链接： SDNU_ACM_ICPC_2020_Winter_Practice_3rd

A HDU 1364 lzwの玩耍

1. 题目大意

题意超级超级超级恶心。！！！！

大意就是， 给你一个01 图， 问机器人能从那些点开始， 进行一系列操作之后， 不撞墙也不跑出图， 问开始点的个数。

2. 分析

dfs暴力暴力！！

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

#include <bits/stdc++.h>

#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = 1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        res = (res << 3) + (res << 1) + ch - '0';
        ch = getchar();
    }
    return f ? (~res + 1) : res;
}

int ma[102][102];
struct node {
    int x1, x2;
    char c;
} a[N];

int n, m;
int cntt;


inline bool dfs(int x, int y, int cnt) {
    if (cnt == cntt) return 1;
    if (a[cnt].c == 'R') {
        for (int i = 0; i < a[cnt].x1; ++i)
            if (y + i >= m || ma[x][y + i]) return 0;

        for (int i = a[cnt].x1; i <= a[cnt].x2; ++i) {
            if (y + i >= m || ma[x][y + i]) break;
            if (dfs(x, y + i, cnt + 1)) return 1;
        }
    }
    if (a[cnt].c == 'L') {
        for (int i = 0; i < a[cnt].x1; ++i)
            if (y - i < 0 || ma[x][y - i]) return 0;

        for (int i = a[cnt].x1; i <= a[cnt].x2; ++i) {
            if (y - i < 0 || ma[x][y - i]) break;
            if (dfs(x, y - i, cnt + 1)) return 1;
        }
    }
    if (a[cnt].c == 'U') {
        for (int i = 0; i < a[cnt].x1; ++i)
            if (x - i < 0 || ma[x - i][y]) return 0;
        for (int i = a[cnt].x1; i <= a[cnt].x2; ++i) {
            if (x - i < 0 || ma[x - i][y]) break;
            if (dfs(x - i, y, cnt + 1)) return 1;
        }
    }
    if (a[cnt].c == 'D') {
        for (int i = 0; i < a[cnt].x1; ++i)
            if (x + i >= n || ma[x + i][y]) return 0;
        for (int i = a[cnt].x1; i <= a[cnt].x2; ++i) {
            if (x + i >= n || ma[x + i][y]) break;
            if (dfs(x + i, y, cnt + 1)) return 1;
        }
    }
    return 0;
}


int main() {
    int t, x, y;
    cin >> t;
    while (t--) {
        cntt = 0;
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> ma[i][j];
            }
        }
        while (1) {
            cin >> x >> y;
            if (!x && !y) break;
            a[cntt].x1 = x;
            a[cntt].x2 = y;
            cin >> a[cntt++].c;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!ma[i][j] && dfs(i, j, 0)) ans++;
            }
        }
        cout << ans << "\n";


    }
    return 0;
}

4. 后继

  1. 读题能力有待提升QAQ。

B CodeForces 1242B lzwの作业

1. 题目大意

完全图， 给出权值为1的边， 其余边都是0， 求最小生成树。

2. 分析

求补图连通块的个数-1。

待补~

先贴上一个题解 Codeforces 1242B0-1 MST

C UVA 12879 lzwの高尔夫

1. 题目大意

先给你n个能行走的距离， 再给你m个距离， 问最多走两次（不能向回走）能走到的数量。

2. 分析

看着有求卷积， 还有个位运算， 卷积不先搞， 位运算看不懂。

卷积

位运算

待补~

D UVA 806 lzwの图片

待补~

E CodeForces 489C lzwの数值

1. 题目大意

给你一个数的位数n， 和所有位数的和s，输出满足要求的最小的数和最大的数。没有输出-1 -1

2. 分析

水题
先说3种特殊情况

1
2
3
n = 1 && s = 0  答案 0 0
n > 1 && s = 0  答案 -1 -1
n * 9 < s       答案 -1 -1

最小值就是先确定首位是1， 从末尾开始向前， 每个都补9， 不足9补剩下的， 全补完了还有剩的加在首位。
最大值就是从前向后， 每个都补9 ， 不足9补剩下的

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

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0; bool f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res  + 1) : res;
}

int a[1000];
int main(){
    int n, m;
    n = read(), m = read();
    if (n == 1 && m == 0){
        puts("0 0");
        return 0;
    }
    if (!m || n * 9 < m){
        puts("-1 -1");
        return 0;
    }

    int s1 = m;
    a[1] = 1;
    s1 -= a[1];
    for (int i = n; i >= 2; --i){
        if (s1 >= 9){
            a[i] = 9;
            s1 -= 9;
        }
        else{
            a[i] = s1;
            s1 = 0;
        }
//        cout << s1 << "\n";
    }
    a[1] += s1;
    for (int i = 1; i <= n; ++i)
        cout << a[i];
    putchar(' ');
    s1 = m;
    ms(a, 0);
    a[1] = min(9, s1);
    s1 -= a[1];
    for (int i = 2; i <= n; ++i){
        if (s1 >= 9){
            a[i] = 9;
            s1 -= 9;
        }
        else{
            a[i] = s1;
            s1 = 0;
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << a[i];
    putchar(10);

    return 0;
}

4. 后继

  1. 当时忘了 n = 1 s = 0 的情况， wa了一发，。。

F POJ 1364 lzwの王座

1. 题目大意

题意巨巨巨巨巨巨巨恶心， 翻译都看不懂题意， 只能看题解才知道的题意，英语好差QAQ

输入4个东东， si, ni, oi, ki， 即 a[si] + ... + a[si + ni] > ki || a[si] + ... + a[si + ni] < ki ， oi是gt为大于， lt为小于。

2. 分析

差分约束， spfa判负环即可， 因为可能不连通需要一个超级源点。

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

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>


#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = 1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        res = (res << 3) + (res << 1) + ch - '0';
        ch = getchar();
    }
    return f ? (~res + 1) : res;
}

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

int head[N], vis[N], dis[N];
int cnt;
int tim[N];
inline void init() {
    ms(head, -1);
    ms(vis, 0);
    ms(dis, INF);
    ms(tim, 0);
    cnt = 0;
}

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

int n, m;

inline bool spfa(int u) {
    dis[u] = 0;
    queue<int>q;
    q.push(u);
    while(!q.empty()){
        u = q.front();
        q.pop();
        vis[u] = 0;
        tim[u]++;
        if (tim[u] > n + 1) return 0; // 注意这里是大于点的个数
        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;
                if (!vis[v]){
                    q.push(v), vis[v] = 1;
                }
            }
        }
    }
    return 1;
}

int a, b, d;
char c[10];

int main() {
    while (~scanf("%d", &n) && n) {
        m = read();
        init();
        while (m--) {
            a = read(), b = read();
            scanf("%s", c);
            d = read();
            if (c[0] == 'g')
                add(b + a, a - 1, - d - 1);
            else if (c[0] == 'l') add(a - 1, b + a, d - 1);
        }
        for (int i = 0; i <= n; ++i){
            add(n + 1, i, 0);
        }
        if (spfa(n + 1)) puts("lamentable kingdom");
        else puts("successful conspiracy");
    }
    return 0;
}

4. 后继

  1. 超级恶心恶心恶心的题意呜呜呜了。

G CodeForces 787D lzwの穿越

1. 题目大意

给你3种操作。

1
2
3
1. 给你一条 u->v的单向边
2. 给你v -> [l, r]的单向边
3. 给你 [l, r] -> v 的单向边

求s到t的最短路

2. 分析

线段树建图+最短路

待补

H UVA 12118 lzwの交通

1. 题目大意

给你一个n个点的完全图，每条边的长度都为t， 再给你m条边， 求经过这m条边的最短路， 起点任意。

2. 分析

经过m条边的最短路， 这样想到了欧拉路， 把每个连通块补成欧拉路， 然后把两连通块用一条边相连，每个连通块奇度顶点的数肯定为偶数， 欧拉路要求奇度顶点个数为2 或者0， 所以需要补边数为max(0, (sum - 2) / 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

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>


#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = 1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        res = (res << 3) + (res << 1) + ch - '0';
        ch = getchar();
    }
    return f ? (~res + 1) : res;
}

int n, m, t, a, b, cnt;

vector<int>ve[1003];

int ans, vis[1003];

void dfs(int x){
    if (ve[x].size() & 1) ans += 1;
    vis[x] = 1;
    for (auto c : ve[x]){
        if (!vis[c]) dfs(c);
    }
}

int main(){
    while(~scanf("%d%d%d", &n, &m, &t)){
        if (!n && !m && !t) break;
        for (int i = 0; i <= n; ++i){
            ve[i].clear();
            vis[i] = 0;
        }
        for (int i = 0; i < m; ++i){
            a = read(), b = read();
            ve[a].push_back(b);
            ve[b].push_back(a);
        }
        int res = 0;
        for (int i = 1; i <= n; ++i){
            // 对每个连通块求需要的边数
            if (!ve[i].empty() && !vis[i]){
                ans = 0;
                dfs(i);
                // +1 是因为 n个连通块需要n - 1条边， 所以我为每个连通块都加1
                res += max(0, (ans - 2) / 2) + 1;
            }
        }
        // 这个我万万没想到， 边数可以是0.。。。
        if (res) res--;
        printf("Case %d: %d\n", ++cnt, (res + m) * t);
    }
    return 0;
}

4. 后继

  1. 万万没想到， m可以为0 。。
  2. 一开始我想着直接把所有奇度顶点求出来直接计算不就好了嘛， 才发现，这样做最后的图可能是不连通滴！

I CodeForces 479C lzwの试炼

1. 题目大意

给出n组(a, b)， b < a， a为出成绩的时间， a， b为可以参加考试的时间， 问怎么安排考试顺序能使得他尽早完成考试并且 出成绩的顺序和考试的顺序要一样。

2. 分析

水题， 结构体排序， 按照a从小到大排序， 如果a一样b从小到大排序， 初始化last = 0 每次取 (a , b)中小的切大于等于last的， 最后last就是答案。

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

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0; bool f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res  + 1) : res;
}

struct node{
    int a, b;
}m[5003];
bool cmp(node x, node y){
    if (x.a != y.a)
        return x.a < y.a;
    return x.b < y.b;
}
int main(){
    int n;
    n = read();
    for (int i = 1; i <= n; ++i){
        m[i].a = read(), m[i].b = read();
    }
    sort(m + 1, m + 1 + n, cmp);
    int last = min(m[1].a, m[1].b);
    for (int i = 2; i <= n; ++i){
        if (m[i].b >= last)
            last = m[i].b;
        else last = m[i].a;
    }
    cout << last << "\n";
    return 0;
}

4. 后继

  1. 没按b从小到大排序， wa了一发， 呜呜呜

J UVA 10410 lzwの建造

1. 题目大意

给你树节点的个数以及 bfs和dfs的遍历顺序， 每一层先遍历节点编号小的。

2. 分析

通过bfs可以知道每个节点到根结点的距离。
遍历dfs， 可以发现， 如果后面节点的到根结点的距离大于前面节点到根结点的距离， 那么后面节点就是前面节点的子节点， 有个特殊情况就是 后面节点的到根结点的距离等于前面节点到根结点的距离， 那么说明这两个节点就是同级节点。所以上面的描述换为 如果后面节点的到根结点的距离大于前面节点到根结点的距离 + 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

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>


#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = 1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        res = (res << 3) + (res << 1) + ch - '0';
        ch = getchar();
    }
    return f ? (~res + 1) : res;
}

int bs[1003], ds[1003], st[1003];
int n, x;
vector<int>ve[1003];

int main(){
    while(~scanf("%d", &n)){
        for (int i = 1; i <= n; ++i)
            bs[read()] = i;
        for (int i = 1; i <= n; ++i)
            ds[i] = read();
        int po = 1;
        st[po] = ds[1];
        st[++po] = ds[2];
        ve[ds[1]].push_back(ds[2]);
        int cnt = 3;
        while(cnt <= n){
            if (bs[ds[cnt]] > bs[st[po]] + 1){
                ve[st[po]].push_back(ds[cnt]);
                st[++po] = ds[cnt];
                cnt++;
            }
            else po--;
        }
        for (int i = 1; i <= n; ++i){
            cout << i << ": ";
            if (!ve[i].empty()){
                for (int j = 0; j < ve[i].size() - 1; ++j){
                    cout << ve[i][j] << " ";
                }
                cout << ve[i].back();
            }
            putchar(10);
            ve[i].clear();
        }

    }

    return 0;
}

4. 后继

  1. 比赛的时候前面思想都想到了， 就是没想到用栈处理， 难受qaq

K HYSBZ 1036 lzwの树

1. 题目大意

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身

2. 分析

树剖裸题？ 待补~

L HYSBZ 1935 lzwの花园

1. 题目大意

第一行有两个整数n，m（0≤n≤500000，1≤m≤500000）。n代表的树木的总数，m代表询问的次数。 接下来的n行，每行都有两个整数xi，yi，代表第i棵树的坐标（0≤xi，yi≤10000000）。 最后m行，每行都有四个整数aj，bj，cj，dj，表示第j次询问，其中所问的矩形以（aj，bj）为左下坐标，以（cj，dj）为右上坐标。 输出每次询问矩形内树木的数量。

2. 分析

待补。

M CodeForces 50A lzwの广场

1. 题目大意

给你一个矩形长宽， 问最多能放下多少个 1 * 2 或者 2 * 1 的矩阵。

2. 分析

水题， 先求最多能放多少 1 * 2 的， 最后可能会剩一列， 都放 2 * 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

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll res = 0; bool f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res  + 1) : res;
}

int n, m;



int main(){
    n = read(), m = read();
    int ans = 0;
    ans += m / 2 * n;
    if (m & 1){
        ans += n / 2;
    }
    cout << ans << "\n";

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

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