220125总结

220125总结

上午的模拟赛

题解

  1. 迷宫问题(依然没找到原题

    【问题描述】

    设有一个\(N*N(2\leqslant N \lt10)\)方格的迷宫,人口和出口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通,1表示不能,入口和出口处保证为0.迷宫走的规则如下所示:从某点开始,有八个方向可走,前进方格中数字为0表示可通过,为1表示不可通过,要另找路径。找出所有从入口(左上角)到出口(右上角)的路径,不能重复。输出路径总数,若无法到达则输出0.

    【输入样例】

    3

    0 0 0

    0 1 1

    1 0 0

    【输出样例】

    2

    深搜就行

    但是因为目标在右上角,所以向右、向上的操作应该优先(即排在前面

    void 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;
    }
    
  2. P1692 部落卫队

    卡了快4个小时

    思路是没太大问题,就是存仇敌之后深搜

    但是重点在于如何优化(其实如果思路对的话没必要优化就能过

    //判断第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);
    }
    
  3. 最佳调度问题

    【问题描述】
    假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度,使得完成全部任务的时间最早。
    【编程任务】
    对任意给定的整数n和k,以及完成任务i需要的时间为ti,i=1~n。编程计算完成这n个任务的最佳调度。
    【输入样例】
    7 3
    2 14 4 16 6 5 3
    【输出样例】
    17

    笑死了老师发的标准程序交上去也TLE

    太离谱了从大到小排遍序再搜就过了

    (感谢!HHS!巨佬的参考代码(

  4. P2819 图的m着色问题

    和第二题很类似(指在第二题码的基础上改改就过了)

    bool 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_];
    }
    
  • 出队之后会造成空间的浪费(假溢出

    所以可以用循环队列,及指针假溢出时重新放到队首

    当首尾指针重合时,队列满。


今日代码

上一篇:CSS – Selector


下一篇:面试官问你JavaScript,直接把这篇文章甩给他