上午的模拟赛
题解
迷宫问题（依然没找到原题
【问题描述】
设有一个$NN(2\leqslant N \lt10)$方格的迷宫，人口和出口分别在左上角和*右上角。迷宫格子中分别放0和1，0表示可通，1表示不能，入口和出口处保证为0.迷宫走的规则如下所示：从某点开始，有八个方向可走，前进方格中数字为0表示可通过，为1表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径，不能重复。输出路径总数，若无法到达则输出0.
【输入样例】
3
0 0 0
0 1 1
1 0 0
【输出样例】
2
深搜就行
但是因为目标在右上角，所以向右、向上的操作应该优先（即排在前面
1
2
3
4
5
6
7
8
9
10
11
12
13
14void Search(int x,int y){
if(B[x][y] || A[x][y]) return;
if(x == 1 && y == n){cnt++;return;}
B[x][y] = 1;
Search(x+1,y+1);
Search(x+1,y);
Search(x+1,y-1);
Search(x,y+1);
Search(x,y-1);
Search(x-1,y+1);
Search(x-1,y);
Search(x-1,y-1);
B[x][y] = 0;
}-
卡了快4个小时思路是没太大问题，就是存仇敌之后深搜
但是重点在于如何优化（其实如果思路对的话没必要优化就能过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//判断第x个人是否有仇敌
bool hc(int x){
for(int i = 1;i<x;i++){
if(A[i] == 1 && cd[i][x] == 1) return true;
}
return false;
}
void Search(int k,int sum){
//k是第k个人，sum是目前选了的人数
if(k > n){
if(sum <= ma) return;
ma = sum;
for(int i = 1;i<=n;i++) fa[i] = A[i];
return;
}
//如果没有仇敌就可以选
if(!hc(k)){
A[k] = 1;
Search(k+1,sum+1);
A[k] = 0;
}
//没有仇敌可以不选，有仇敌一定不选
Search(k+1,sum);
} 最佳调度问题
【问题描述】
假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。
【编程任务】
对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1~n。编程计算完成这n个任务的最佳调度。
【输入样例】
7 3
2 14 4 16 6 5 3
【输出样例】
17笑死了老师发的标准程序交上去也TLE1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//分配第x个任务，目前共耗时sum
void Search(int x,int sum){
//剪枝
if(sum >= sumM) return;
//任务分配完成，看是否短于目前最短时间
if(x > n){
if(sum < sumM) sumM = sum;
return;
}
//第x项任务可以分配给第1~k号机器去做
for(int i = 1;i<=k;i++){
//如果第i台机器完成第x项任务后耗时长于目前耗时最大值就不行，需要跳过
if(B[i] + A[x] >= sumM) continue;
//第i台机器完成第x项任务后
//这台机器到目前为止总耗时为B[i]+A[x]
B[i] = B[i]+A[x];
//搜索下一个任务
//因为是k台机器在做，所以可能会出现各台机器耗时不同的情况
//所以当前耗时是原耗时与第i台机器目前耗时的最大值
Search(x+1,max(sum,B[i]));
//回溯
B[i] = B[i]-A[x];
}
}太离谱了从大到小排遍序再搜就过了
优先做耗时长的任务，所以要排序
（感谢!hhs!巨佬的题解（
-
和第二题很类似（指在第二题码的基础上改改就过了）
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
28bool pd(int x){
for(int i = 1;i<x;i++){
//判断是否与一个已染色的点相连
//重点是“已染色的点”而不是“相连”，因为题面已经说了这是一个连通图
if(A[i] == 1 && cd[i][x] == 1){
//判断二者颜色是否相同
if(B[x] == B[i]) return true;
}
}
return false;
}
void Search(int k){
if(k > n){ma++;return;}
//m种颜色轮流染
for(int i = 1;i<=m;i++){
//染色
B[k] = i;
//判断是否与一个相连的已染色的点颜色相同
if(!pd(k)){
//若不同则标记这个点已染色，再去染下一个点
A[k] = 1;
Search(k+1);
A[k] = 0;
}
}
}
- 总之又是TLE的一天（
队列（Queue）
“先进先出”
需要一个头指针用于出队
需要一个尾指针用于入队
无论是出队还是入队，指针都是自增
int queue_[100100]; int head_ = 0; int tail_ = 0; void push(int a){ queue_[tail_++] = a; } void pop(){ head_++; } int front(){ return queue_[head_]; }出队之后会造成空间的浪费（假溢出
所以可以用循环队列，及指针假溢出时重新放到队首
当首尾指针重合时，队列满。