HaretaLeila

Think different

发表于

2023.6.27 完成作业时记录的笔记
上传留档

Click to open

CS50’s Introduction to Artificial Intelligence with Python Ep.5 Note

Constraints Satisfaction Problem: 约束满足问题

Constraints

hard / soft constraints: must be satisfied in the solution / preferred in the solution

unary constraint: just involves one single variable

binary constraint: two variables

node consistency: all the elements in the domain satisfies the variable’s unary constraints

  • when dealing with problems, conSsider unary constraints first to reach node consistency, through (for example) removing elements from the domain

arc consistency: satisfy the binary constraints

To max $X$ arc consistent with respect to $Y$, remove elements from $X$’s domain until every choice for $X$ has a possible chice for $Y$

max: some times we can’t reach it from one side

When choosing A.Wed, there’s no remaining choices for B in B’s domain, so remove Wed from A

Algorithm to enforce arc consistency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def REVISE(csp, X, Y):
    revised = False
    # True if revised else ramain false
    for x in X.domain:
        if no y in Y.domain satisfies constraint of (X, Y):
            delete x from x.domain
            revised = True
    return revised



def AC_3(csp):
    queue = all arcs in csp
    while not queue.empty:
        (X, Y)=dequeue(queue)
        if REVISE(csp, X, Y):
            if X.domain.size==0:
                return False # nothing left in X.domain, so we can't solve the problem
            for Z in X.neighbors-{Y}:
                euqueue(queue, (Z, X))
    return true

Search Problems

csp and search problems

  • initial state: empty assignment
  • actions: add a variable-value pair to assignment
  • transition model: hwo adding an assignment changes the assignment
  • goal test: constraints all satisfied or not
  • path cost function: cost = constant(in this problem)
1
2
3
4
5
6
7
8
9
10
11
def BACKTRACK(assignment, csp):
    # 对于元素选择有要求的的回溯算法
    if assignment completed: return assignment
    var=select-unassigned-var(assignment, csp)
    for value in domain-values(var, assignment, csp):
        if value consistent with assignment:
            add {var=value} to assignment
            result=BACKTRACK(assignment, csp)
            if result!=False: return result
        remove {var=value} from assignment
    return False

发表于 更新于

前言

本文章发布SJTU-CS1601H-数据结构(荣誉) 2022-2023-2学期部分作业题目的AC代码及题解

部分题写的太臭就不放了

另外有一部分题目本身或多或少地存在一些争议, 会在讲解中表明或者选择不发布

本文较长, 一次放出, 请善用浏览器与博客的搜索功能

代码已上传GitHub: Code Repo

Click to open

第一次作业

1058

本题没有什么好解释的, 按照要求实现链表即可
值得注意的点是理解好给出的move()函数的作用

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
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <cstdio>
using namespace std;

namespace LIST
{

    struct NODE {
        int val;
        NODE* next;
    };
    NODE* head = nullptr;
    int len = 0;

    void init() {
        head = nullptr;
        return;
    }

    NODE* move(int i) { //移动i次后的节点, head为移动0次, tail为移动len-1次, LIST[i]移动[i]次
        NODE* ptr = head;
        for (int k = 0; k < i; k++) {
            ptr = ptr->next;
        }
        return ptr;
    }

    void insert(int i, int x) {
        if (len == 0) {
            init();
            head = new NODE;
            head->val = x;
            head->next = head;
            len = 1;
            return;
        }
        if (i == 0) {
            NODE* tail = move(len - 1);
            NODE* tmp = new NODE;
            tmp->val = x;
            tmp->next = head;
            head = tmp;
            tail->next = head;
            len++;
            return;
        }
        NODE* tmp = move(i - 1);
        NODE* a = new NODE;
        a->val = x;
        a->next = tmp->next;
        tmp->next = a;
        len++;
        return;
    }

    void remove(int i) {
        if (i == 0) {
            if (len == 0) return;
            NODE* tail = move(len - 1);
            NODE* tmp = head;
            head = head->next;
            tail->next = head;
            len--;
            if (len == 0) init();
            delete tmp;
            return;
        }
        NODE* tmp = move(i - 1);
        NODE* tmpNext = tmp->next;
        tmp->next = tmp->next->next;
        len--;
        delete tmpNext;
        if (len == 0) init();
        return;
    }

    void remove_insert(int i) {
        if (len == 0) return;
        if (i == 0) {
            head = head->next;
            return;
        }
        if (i == len - 1) return;
        NODE* target = move(i);
        NODE* pre = move(i - 1);
        NODE* tail = move(len - 1);
        NODE* back = target->next;
        pre->next = back;
        tail->next = target;
        target->next = head;
        return;
    }

    void get_length() {
        cout << len << endl;
        return;
    }

    void query(int i) {
        if (i < 0 || i >= len) {
            cout << -1 << endl;
            return;
        }
        cout << move(i)->val << endl;
        return;
    }

    void get_max() {
        if (len == 0) {
            cout << -1 << endl;
            return;
        }
        int m = -1;
        NODE* ptr = head;
        for (int k = 0; k < len; k++) {
            ptr = ptr->next;
            m = max(m, ptr->val);
        }
        cout << m << endl;
        return;
    }

    void clear() {
        if (len == 0) return;
        if (len == 1) {
            delete head;
            return;
        }
        if (len == 2) {
            delete head->next;
            delete head;
        }
        NODE* tmp = head->next;
        delete head;
        for (int i = 0; i < len - 2; i++) {
            head = tmp;
            tmp = tmp->next;
            delete head;
        }
        delete tmp;
    }
}
int n;
int main()
{
    cin >> n;
    int op, x, p;
    LIST::init();
    for (int _ = 0; _ < n; ++_)
    {
        cin >> op;
        switch (op) {
        case 0:
            LIST::get_length();
            break;
        case 1:
            cin >> p >> x;
            LIST::insert(p, x);
            break;
        case 2:
            cin >> p;
            LIST::query(p);
            break;
        case 3:
            cin >> p;
            LIST::remove(p);
            break;
        case 4:
            cin >> p;
            LIST::remove_insert(p);
            break;
        case 5:
            LIST::get_max();
            break;
        }
    }
    LIST::clear();
    return 0;
}

11038

本写法为模拟,直接按照题意写

此题和普通的约瑟夫环一样也可以直接数学方法算,这里暂且不表

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
#include <iostream>
using namespace std;
struct node {
    int val;
    node* next;
};
int main() {
    int M;
	cin >> M;
	node* head = new node;
	head->val = 1;
	node* ptr = head;
	int size = M;
	for (int i = 2; i <= M; i++) {
		ptr->next = new node;
		ptr = ptr->next;
		ptr->val = i;
	}
	ptr->next = head;
	for (int i = 0; i < M - 1; i++) {
		int k;
		cin >> k;
		k %= size;
		if (k == 0) k = size;
		for (int i = 0; i < k - 1; i++) {
			head = head->next;
			ptr = ptr->next;
		}
		ptr->next = head->next;
		delete head;
		head = ptr->next;
		size--;
	}
	cout << (ptr->val);
	delete ptr;
	return 0;
}

第二次作业

1216

括号栈, 但与普通括号匹配不同, 额外要求删除功能
所以本题的难点就落在如何实现删除的同时做到括号栈的匹配查询
首先, 需要一个栈s来如实记录所有push与pop操作
朴素的想法是每次查询是否匹配时将栈中所有元素进行一次普通括号匹配的检查, 时间复杂度为O(n^2)
但是本题数据集过大, 这样的做法会导致超时, 需要转换思路
额外增添一个栈check来时刻维护括号是否匹配, check空等价于当前状态的所有括号为匹配状态
思考push的过程中做了什么操作：在右括号匹配左括号时将左括号弹出
在删除时, 就有两种操作：
如实记录的栈s顶为左括号时, 如实弹出check
如实记录的栈s顶为右括号时, 此时如果这个右括号 被匹配成功并且没有进入过check 则需要向check补充左括号, 反之说明右括号没有正确匹配, 只需直接弹出check栈顶即可
有关如何确定右括号状态, 可以通过在链式结构栈的节点结构体内增加一个bool类型的flag用于判断, 在push时决定flag的取值
这种做法的时间复杂度为O(n)

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
#include <cstdio>
using namespace std;
struct node {
	char val;
	bool flag;
	node* next;
};
class Stack {
private:
	node* head;
public:
	Stack() {
		head = nullptr;
	}
	void push(char c) {
		node* tmp = new node;
		tmp->val = c;
		tmp->flag = 0;
		tmp->next = head;
		head = tmp;
		return;
	}
	void pop() {
		if (head == nullptr) return;
		node* tmp = head->next;
		delete head;
		head = tmp;
		return;
	}
	node* top() {
		if (head == nullptr) return 0;
		return head;
	}
	bool empty() {
		return head == nullptr;
	}
	void clear() {
		while (head != nullptr) {
			pop();
		}
		return;
	}
};

int main() {
	Stack s;
	Stack check;
	int n = 0;
	scanf("%d", &n);
	char C = 'a';
	bool f = 0;
	int op = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &op);
		switch (op) {
		case 1:
			char c;
			char tool[10];
			scanf("%s", tool);
			c = tool[0];
			s.push(c);
			if (check.empty()) {
				check.push(c);
				break;
			}
			if (c == '[' || c == '{' || c == '(') {
				check.push(c);
				s.top()->flag = 0;
				break;
			}
			switch (c) {
			case ')':
				if (check.top()->val == '(') {
					check.pop();
					s.top()->flag = 1;
				}
				else {
					check.push(c);
					s.top()->flag = 0;
				}
				break;
			case ']':
				if (check.top()->val == '[') {
					check.pop();
					s.top()->flag = 1;
				}
				else {
					check.push(c);
					s.top()->flag = 0;
				}
				break;
			case '}':
				if (check.top()->val == '{') {
					check.pop();
					s.top()->flag = 1;
				}
				else {
					check.push(c);
					s.top()->flag = 0;
				}
				break;
			}
			break;
		case 2:
			if (s.empty()) break;
			C = s.top()->val;
			f = s.top()->flag;
			s.pop();
			switch (C) {
			case '{':
			case '[':
			case '(':
				check.pop();
				break;
			default:
				if (f) {
					if (C == ')') check.push('(');
					if (C == ']') check.push('[');
					if (C == '}') check.push('{');
				}
				else check.pop();
			}
			break;
		case 3:
			if (s.empty()) break;
			printf("%c\n", s.top()->val);
			break;
		case 4:
			if (check.empty()) printf("YES\n");
			else printf("NO\n");
			break;
		}
	}
	s.clear();
	return 0;
}

第三次作业

1049

简单想法, 按照递归恢复二叉树并层序遍历即可, 注意处理输出状态, 需要从后向前寻找最后一个需要输出的元素

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
#include <iostream>
#include <cstring>
using namespace std;

struct node {
	char val;
	node* left;
	node* right;
	node(char v) {
		val = v;
		left = nullptr;
		right = nullptr;
	}
};
node* root = nullptr;
node* build(char pre[], int pl, int pr, char mid[], int ml, int mr) {
	if (pl > pr) return nullptr;
	node* p = new node(pre[pl]);
	if (!root) root = p;
	int pos = 0;
	int i = 0;
	int num = 0;
	for (i = ml; i <= mr; i++) {
		if (mid[i] == pre[pl]) break;
	}
	pos = i;
	num = pos - ml;
	p->left = build(pre, pl + 1, pl + num, mid, ml, pos - 1);
	p->right = build(pre, pl + num + 1, pr, mid, pos + 1, mr);
	return p;
}
int main() {
	char pre[30];
	char mid[30];
	cin >> pre >> mid;
	int size = strlen(pre);
	build(pre, 0, size-1, mid, 0, size-1);
	node* res[5000]{ nullptr };
	res[0] = root;
	int fast = 0;
	int slow = 0;
	bool flag = 1;
	while (flag && fast < 2000) {
		fast = fast * 2 + 1;
		flag = 0;
		for (int i = slow; i < fast; i++) {
			if (res[i] == nullptr) continue;
			flag = 1;
			node* tmp = res[i];
			if (tmp->left != nullptr) res[i * 2 + 1] = tmp->left;
			if (tmp->right != nullptr) res[i * 2 + 2] = tmp->right;
		}
		slow = fast;
	}
	int lim = 1500;
	while (res[lim] == nullptr) lim--;
	for (int i = 0; i <= lim; i++) {
		if (res[i] == nullptr) cout << "NULL" << ' ';
		else cout << res[i]->val << ' ';
	}
	return 0;
}

1125

本题只需要维护一个优先队列即可, 建议自己写, 不过使用stl queue中的priority_queue也没有扣分
不过数据集相当弱, 优先队列挨个比较然后插入O(n^2)都能过(from 舍友)

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
#include <iostream>
#include <stdio.h>
#define init 20
using namespace std;
class Vector {
public:
	int* storage;
	int size = 0;
	int maxsize = 20;
	void doubleSpace() {
		maxsize *= 2;
		int* tmp = new int[maxsize];
		for (int i = 0; i < size; i++) {
			tmp[i] = storage[i];
		}
		delete[] storage;
		storage = tmp;
		return;
	}
	Vector(int s = 20) {
		size = 0;
		maxsize = s;
		storage = new int[maxsize];
	}
	int Size() {
		return size;
	}
	bool empty() {
		return size == 0;
	}
	void push_back(int elem) {
		if (size == maxsize) doubleSpace();
		storage[size] = elem;
		size++;
	}
	void pop_back() {
		if (empty()) {
			return;
		}
		size--;
		return;
	}
	int& operator [] (int index) {
		return storage[index];
	}
	void goDown() {
		int index = 0;
		swap(storage[size - 1], storage[0]);
		pop_back();
		while (index * 2 + 1 < size) {
			int tmp = index * 2 + 1;
			if (tmp + 1 < size && storage[tmp + 1] < storage[tmp]) tmp++;
			if (storage[tmp] >= storage[index]) break;
			swap(storage[tmp], storage[index]);
			index = tmp;
		}
		return;
	}
	void goUp(int val) {
		push_back(val);
		int index = size - 1;
		int father = (index - 1) / 2;
		while (index > 0) {
			if (storage[index] < storage[father]) {
				swap(storage[index], storage[father]);
				index = father;
				father = (father - 1) / 2;
			}
			else break;
		}
	}
};
int main() {
	int n = 0;
	int m = 0;
	scanf("%d %d", &n, &m);
	Vector** v = new Vector*[n];
	int val;
	for (int i = 0; i < n; i++) {
		scanf("%d", &val);
		v[i] = new Vector();
		v[i]->push_back(val);
	}
	int op = 0;
	while (m--) {
		cin >> op;
		switch (op) {
		case 0: {
			int a;
			int b;
			bool flag = 0;
			scanf("%d %d", &a, &b);// merge b into a
			if (v[a]->Size() < v[b]->Size()) {
				swap(v[a], v[b]);
				flag = 1;
			}
			for (int i = 0; i < v[b]->Size(); i++) {
				v[a]->goUp((*v[b])[i]);
			}
			break;
		}
		case 1: {
			int a;
			scanf("%d", &a);
			if (v[a]->empty()) {
				printf("-1\n");
				break;
			}
			printf("%d\n", (*v[a])[0]);
			v[a]->goDown();
			break;
		}
		case 2: {
			int a;
			int b;
			scanf("%d %d", &a, &b);
			v[a]->goUp(b);
			break;
		}
		}
	}
	return 0;
}

第四次作业

14315

后序遍历, 指的是中间的根最后搜, 先搜左右再搜中间

镜像是左右交换

所以题目中所谓镜像一个树再后序遍历, 实际上直接右->左->中深搜即可, 注意建树方式, v[i][0,1,2]分别表示节点i的值, 左子节点和右子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int v[10005][2];
void dfs(int node) {
	if (node <= 0) return;
	dfs(v[node][1]);
	dfs(v[node][0]);
	cout << node << ' ';
}
int main() {
	int n, a, root = 114514;
	cin >> n;
	while(n--) {
		cin >> a >> v[a][0] >> v[a][1];
		if (root == 114514) root = a;
	}
	dfs(root);
	return 0;
}

第五次作业

1008

本题有多种可AC写法
以下链接给出二维前缀和的解法, 时间复杂度O(n^2 logn)
（新版）SJTU-OJ-1008. LSZ的雪地脚印

此处给出动态规划解法, 时间O(n^2) 空间O(n)
dp[i][j]表示以(i,j)为右下角的空白矩形的最大高度
转移方程dp[i][j]=min{dp[i-1][j], dp[i][j-2], dp[i-1][j-2]}+1
对于dp[i][j]本身不可放或i-1与j-2越界的情况特判
只用到当前行和前一行数据, 所以可以滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int n=0, m=0, ans=0;
    scanf("%d %d",&n,&m);
    int dp[2][m];
    char line[m];
    for(int i=0; i<n; i++) {
        scanf("%s",line);
        for(int j=0; j<m; j++) {
            if (j==0 || line[j-1]!='-' || line[j]!='-') dp[i%2][j]=0;
            else if (i<1 || j<2) dp[i%2][j]=1;
            else dp[i%2][j]=min(dp[i%2][j-2], min(dp[(i+1)%2][j], dp[(i+1)%2][j-2]))+1;
            ans=max(ans, dp[i%2][j]);
        }
    }
    printf("%d", ans*ans*2);
    return 0;
}

1010

本题主要卡时间, 只需要想到二分查找降复杂度就可以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
#include <stdio.h>
using namespace std;
int main() {
    int prev = 0, cur = 0;
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    int* preSum = new int[n+5];
    preSum[0]=0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cur);
        prev += cur;
        preSum[i] = prev;
    }

    int target = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d", &target);
        int left=0, right=n; // binary search [left, right];
        int mid;
        while(left<=right) {
            if (preSum[right]<target) {
                mid=right+1;
                break;
            }
            mid=(left+right)/2;
            if (preSum[mid]>=target) right=mid-1;
            else left=mid+1;
        }
        printf("%d %d\n", mid, target-preSum[mid-1]);
    }
    return 0;
}

1387

本题测试集有问题, 第三个爆int, 第四个爆long long, 答案按照long long下给出, 使用unsigned long long会WA
有关哈夫曼树权值和计算方法可以参考 哈夫曼树带权路径长度(WPL)计算
可以直接算而不是真的去建树, 一个节点每次被当作子树合并的时候相当于它底下的所有叶节点权重+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
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
#include <iostream>
#include <stdio.h>
#define ll long long
using namespace std;
// 简略实现优先队列
class priority_Queue {
public:
	ll* storage;
	int size = 0;
	int maxsize = 20;
	void doubleSpace() {
		maxsize *= 2;
		ll* tmp = new ll[maxsize];
		for (int i = 0; i < size; i++) {
			tmp[i] = storage[i];
		}
		delete[] storage;
		storage = tmp;
		return;
	}
	priority_Queue(int s = 20) {
		size = 0;
		maxsize = s;
		storage = new ull[maxsize];
	}
	bool empty() {
		return size == 0;
	}
    ull front() {
        return storage[0];
    }
	void push(ull elem) {
		if (size == maxsize) doubleSpace();
		storage[size] = elem;
		size++;
        int index = size - 1;
		int father = (index - 1) / 2;
		while (index > 0) {
			if (storage[index] < storage[father]) {
				swap(storage[index], storage[father]);
				index = father;
				father = (father - 1) / 2;
			}
			else break;
		}
	}
	void pop() {
		swap(storage[size - 1], storage[0]);
        size--;
        int index = 0;
		while (index * 2 + 1 < size) {
			int tmp = index * 2 + 1;
			if (tmp + 1 < size && storage[tmp + 1] < storage[tmp]) tmp++;
			if (storage[tmp] >= storage[index]) break;
			swap(storage[tmp], storage[index]);
			index = tmp;
		}
		return;
	}
};

int main() {
    int n=0;
    cin >> n;
    priority_Queue q;
    for(int i=0; i<n; i++) {
        ll val;
        cin >> val;
        q.push(val);
    }
    ll ans=0;
    for(int i=0; i<n-1; i++) {
        ll a=q.front();
        q.pop();
        ll b=q.front();
        q.pop();
        ll c=a+b;
        q.push(c);
        ans+=c;
    }
    cout << ans << endl;
    return 0;
}

第六次作业

1146

本题因为未知原因必须增加一个find()函数才可以通过
直接删除会导致WA
大概率为出题问题

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 <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int val[100005], rc[100005], lc[100005];
// rc: right child, lc:left child
int cnt=1;
int ptr=0;
char output[100005];
bool search(int x, int cur) {
    if (cur==0) {
        return 0;
    }
    else if (x==val[cur]) {
        output[ptr]='\n';
        return 1;
    }
    else if(x>val[cur]) {
        output[ptr++]='r';
        return search(x, rc[cur]);
    }
    else {
        output[ptr++]='l';
        return search(x, lc[cur]);
    }
}
void insert(int x, int& cur) {
    if (cur==0) {
        cur=cnt;
        return;
    }
    if (x==val[cur]) return;
    else if(x>val[cur]) insert(x, rc[cur]);
    else insert(x, lc[cur]);
}
void find(int x, int& cur) {
    if (val[cur]>x) find(x, lc[cur]);
    if (val[cur]<x) find(x, rc[cur]);
    if (x==val[cur]) cur=rc[cur];
}
void erase(int x, int& cur) {
    if (cur==0) return;
    if (x<val[cur]) erase(x, lc[cur]);
    else if(x>val[cur]) erase(x, rc[cur]);
    else {
        if (rc[cur]==0 && lc[cur]==0) cur=0;
        else if (rc[cur]==0) {
            cur=lc[cur];
        }
        else {
            int tmp=rc[cur];
            while(lc[tmp]!=0) tmp=lc[tmp];
            val[cur]=val[tmp];
            find(val[cur], rc[cur]);
        }
    }
}
int main() {
    int n=0;
    int root=0;
    scanf("%d\n", &n);
    while(n--) {
        char op, s[10];
        scanf("%s", s);
        op=s[0];
        int x=0;
        scanf("%d", &x);
        if (op=='+') {
            val[++cnt]=x;
            insert(x, root);
        }
        else if (op=='-') {
            erase(x, root);
        }
        else {
            output[0]='*';
            ptr=1;
            if (search(x, root)) {
                for(int i=0; i<=ptr; i++) printf("%c", output[i]);
            }
            else printf("Nothing.\n");
        }
    }
    return 0;
}

1141

双哈希, 没做冲突处理, 建议还是自己做一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
int hash_table_1[2000300];
int hash_table_2[2000300];
char c[2000];
#define i64 unsigned long long
int main() {
    int res=0;
    int n=0;
    scanf("%d\n", &n);
    for(int i=0; i<n; i++) {
        cin.getline(c, 2000, '\n');
        i64 hash1=0, hash2=0;
        int n=strlen(c);
        for(int i=0; i<n; i++) hash1=(hash1*13331)%(2000003)+c[i];
        for(int i=0; i<n; i++) hash2=(hash2*131)%(2000083)+c[i];
        if (hash_table_1[hash1]!=0 && hash_table_2[hash2]!=0) continue;
        hash_table_1[hash1]=1, hash_table_2[hash2]=1;
        res++;
    }
    cout << res;
}

第七次作业

1174

主要难点在于 corner cases 和溢出
以高度排序增加水的容积, 每次增加的容积是[已数的完全覆盖的地块数量]*[这个地块和上个地块的高度差]
当容积增加到大于水的体积, 回退一步并计算小数点部分的值

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
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define ull unsigned long long
inline int read() {
	int x=0, f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
    return x*f;
}
inline ull max(ull a, ull b){return a>b?a:b;};
inline ull min(ull a, ull b){return a<b?a:b;};
ull* num;
ull* tmp;

// 排序采用归并的板子, 这里为了省事直接用了全局数组
void merge(int l, int m, int h) {
    int i=l, j=m+1, k=l;
    while(i<=m && j<=h) {
        if (num[i]<num[j]) tmp[k++]=num[i++];
        else tmp[k++]=num[j++];
    }
    while(i<=m) tmp[k++]=num[i++];
    while(j<=h) tmp[k++]=num[j++];
    for(int i=l; i<=h; i++) num[i]=tmp[i];
}
void merge_sort(int l, int r) { //merge_sort for array:[l, r]
    if (l>=r) return;
    int m=(l+r)/2;
    merge_sort(l, m);
    merge_sort(m+1, r);
    merge(l, m, r);
}

int main() {
    int m=read(), n=read();
    num=new ull[m*n+5];
    tmp=new ull[m*n+5];
    ull Min=INT64_MAX;
    for(int i=0; i<m*n; i++) {
        num[i]=read();
        Min=min(Min, num[i]);
    }
    ull v;
    cin >> v;
    if (v==0) {
        printf("%.2f\n", double(Min));
        printf("0.00");
        return 0;
    }
    merge_sort(0, m*n-1);
    int i=1; //完全覆盖了i个地块
    int curheight=Min;
    num[m*n]=num[m*n-1]+v;
    while(i<=m*n) {
        int layerVolume=(num[i]-num[i-1])*i;
        if (layerVolume>=v) break;
        v-=layerVolume;
        curheight=num[i];
        i++;
    }
    double h=double(curheight)+double(v)/double(i);
    double percent=100.0*double(i)/double(m*n);
    printf("%.2f\n%.2f", h, percent);
}

1175

本题与另一个排队题一样, 只需排序即可
这里用了优先队列, 和排序是一样的效果, 可能会慢一点不过不会慢太多

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 <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
#define ull unsigned long long
inline ull max(ull a, ull b){return a>b?a:b;};
inline ull min(ull a, ull b){return a<b?a:b;};
inline int read() {
	int x=0, f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
    return x*f;
}
int main() {
    int N=read();
    int li[N+5];
    for(int i=0; i<N; i++) li[i]=read();
    int M=read();
    int sex=0;
    priority_queue<int, vector<int>, greater<int>> q0, q1;
    for(int i=0; i<M; i++) {
        sex=read();
        if (sex==1) q0.push(read());
        else q1.push(read());
    }
    int male_cnt=q0.size();
    int female_cnt=q1.size();
    queue<int> Q0, Q1;
    int time=0;
    ull male_total_wait_time=0;
    ull female_total_wait_time=0;
    for(int i=0; i<N; i++) {
        while(!q0.empty() && q0.top()<=time) {
            int a=q0.top();
            q0.pop();
            Q0.push(a);
        }
        while(!q1.empty() && q1.top()<=time) {
            int a=q1.top();
            q1.pop();
            Q1.push(a);
        }
        while(!Q0.empty() && !Q1.empty()) {
            int a=Q0.front();
            Q0.pop();
            int b=Q1.front();
            Q1.pop();
            male_total_wait_time+=time-a;
            female_total_wait_time+=time-b;
        }
        time+=li[i];
    }
    time-=li[N-1];
    while(!q0.empty()) {
        male_total_wait_time+=time-q0.top();
        q0.pop();
    }
    while(!q1.empty()) {
        female_total_wait_time+=time-q1.top();
        q1.pop();
    }
    while(!Q0.empty()) {
        male_total_wait_time+=time-Q0.front();
        Q0.pop();
    }
    while(!Q1.empty()) {
        female_total_wait_time+=time-Q1.front();
        Q1.pop();
    }
    printf("%.2f %.2f", double(male_total_wait_time)/double(male_cnt), double(female_total_wait_time)/double(female_cnt));
    return 0;
}

第八次作业

11606

在接受输入的同时统计陆地的数量cnt。并记录一个任意的陆地地块作为dfs的起点start point (i, j) -> si, sj
深搜搜索到的陆地数量为_cnt, cnt==_cnt等价于该状态连通

对于无解的情况：
如果所有未知地块全部被看作陆地后, 从(si, sj)开始dfs, 记录下搜索经过的陆地数量_cnt
如果cnt!=_cnt, 则可以充分断定无解(以最可能连通的方式去检测仍然不能连通)
反之如果cnt==_cnt则可以确定至少有一解, 从而达成对无解的判定

对于多解的情况：
先把所有未知地块看作陆地, 如果多解, 则必定存在未知地块x, 当x被设置回湖泊时, 仍然从(si, sj)开始dfs
只需要遍历全图->
遇到未知地块, 设为湖泊->
dfs一次记录_cnt->
判断_cnt==cnt是否成立即可

如果存在一个地块x, 设回湖泊时陆地仍然连通, 则说明该地块是多余的, 因而该图有多解, 此时直接输出并return 0即可

对于单解的情况：
到此处应该注意到visited1[][]这个数组
该数组在初次dfs时标识了所有途径的点, 并且在后续dfs中没有改变过(后边的dfs搜到的范围是从初次dfs中移除部分元素的, 因为将未知区域设为湖泊后搜到的地块只会变少)
它只会在非无解的情况发挥作用(因为无解直接return了, 后续没有再用到visited1[][])
一是在判断多解的时候排除孤立的由未知区域组成的地区：
假设在陆地之外存在一个独立的未知地块, 如果我们尝试把这个地块设置为湖泊, 这时再深搜是会出问题的！
例如下图的测试案例, 如果不跳过孤立的由未知区域组成的地区, 则会得到多解的结果, 但是实际上这个图是唯一解

1
2
3
4
5
#####
#...#
#####
##?##
#####

解决这个问题的方法就是初次深搜时标定visited1[][], 在设未知区域为湖泊时跳过没有被初次深搜标定的地块, 即可避免
二是用于输出单解的图
首先, 单解的图内只有'.'和'#'
到这里应该能够理解, 只需要把visited1[][]中1当作'.', 0当作'#'输出就是单解的答案
多解的搜索过程中, 看作湖泊的都是visited1[][]标记过的未知地块, 这些地块都会导致cnt!=_cnt, 也就是说这些地块对于陆地的连通都是必要的
同时, 初次深搜未标记过的未知区域肯定不会设为陆地

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
#include <stdio.h>
#include <string.h>
using namespace std;
int n, m, cnt=0, _cnt=0, N=0, si, sj;
int M[60][60], visited[60][60], visited1[60][60];
int di[]={1, 0, -1, 0}, dj[]={0, 1, 0, -1};
void dfs(int i, int j) {
    if (visited[i][j] || M[i][j]==0) return;
    visited[i][j]=visited1[i][j]=1;
    if (M[i][j]==1) _cnt++;
    for(int t=0; t<4; t++) {
        int fi=i+di[t], fj=j+dj[t];
        if (!(fi>=0 && fj>=0 && fi<n && fj<m)) continue;
        dfs(fi, fj);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++) {
        char s[100];
        scanf("%s", s);
        for(int j=0; j<m; j++) {
            if (s[j]=='#') M[i][j]=0;
            else if (s[j]=='.') {
                M[i][j]=1;
                cnt++;
                si=i, sj=j; // 此处si, sj用于标识深搜的起点
            }
            else M[i][j]=2;
        }
    }
    dfs(si, sj);
    if (_cnt!=cnt) {
        printf("Impossible");
        return 0;
    } // 判断无解结束
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if (M[i][j]!=2 || visited1[i][j]==0) continue;
            _cnt=0;
            memset(visited, 0, sizeof(visited));
            M[i][j]=0;
            dfs(si, sj);
            if (_cnt==cnt) {
                printf("Ambiguous");
                return 0;
            }
            M[i][j]=2;
        }
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++)
            printf(visited1[i][j]?".":"#");
        printf("\n");
    }
    return 0;
}

11281

典中典的下象棋问马能到哪的问题
使用bfs, 每次向外延展一层, 只需要记录搜的层数, 搜到目标点直接输出并返回令程序结束即可

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
#include <iostream>
#include <queue>
using namespace std;
int mp[40][40];
int vis[40][40];
struct p {
    int x, y;
    p(int _x, int _y):x(_x), y(_y){};
};
int main() {
    int n, m;
    cin >> m >> n;
    int m1, m2;
    cin >> m1 >> m2;
    int dx[]={-m1, -m1, -m2, -m2, m2, m2, m1, m1};
    int dy[]={m2, -m2, m1, -m1, m1, -m1, m2, -m2};
    int si, sj, ei, ej;
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            int a;
            cin >> a;
            if (a==1 || a==3 || a==4) mp[i][j]=1;
            if (a==3) si=i, sj=j;
            if (a==4) ei=i, ej=j;
        }
    }
    vis[si][sj]=1;
    queue<p> q;
    int ans=0;
    q.push(p(si, sj));
    auto isLegal=[&](int x, int y)->bool {
        return x>=0 && x<m && y>=0 && y<n;
    };
    while(!q.empty()) {
        ans++;
        int N=q.size();
        while(N--) {
            auto p1=q.front();
            q.pop();
            int x=p1.x, y=p1.y;
            for(int i=0; i<8; i++) {
                int xx=x+dx[i], yy=y+dy[i];
                if (!isLegal(xx, yy) || vis[xx][yy]==1 || mp[xx][yy]!=1) continue;
                if (xx==ei && yy==ej) {
                    cout << ans;
                    return 0;
                }
                q.push(p(xx, yy));
                vis[xx][yy]=1;
            }
        }
    }
    return 0;
}
0%