北航刷题笔记 其一

北航刷题笔记

2.1.15,14,12，9

1.判断2的幂次数

1
2
3
4
5
6
7
8
9
10
//关键是搞出一个数组，把这个数转换为一个二进制数，数组s[32]
//如果数组中只有1个1，那就是2的幂
int n;//这个数
int s[32];
int i=0;
while(n>0){
    s[i]=n%2;//自己脑中想一想，二进制每一位都是当前的余数，想一想二进制的运算过程
    i++;
    n/=2;
}

2.直线与圆

1
2
3
4
5
6
//这题首先就是直线方程的构造有点麻烦
a(x1,y1)b(x2,y2)
(y2-y1)x+(x1-x2)y+x2*y1-x1*y2=0;
d=|ax3+by3+c|
  -----------
  根号(a^2+b^2)

3.方向判断

1
//关键是atan2(y,x)返回的是弧度，而且是[-pi,pi]

4.重逢时刻

1
2
3
4
5
6
7
8
9
10
11
int h = n % 12;
double total_minutes = (30.0 * h) / 5.5; //分针追赶时针所需时间，这里可以看成60/11
int min = (int)total_minutes;           //整数部分是分钟
double sec = (total_minutes - min) * 60.0; //小数部分转为秒
if(min==60){
    min=0;
    h++;
    if(h==12){
        h=0;
    }
}

3.1.7，11，14,15,16

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
//关键是动态规划，把种类用dp[i][j]来表示，数i划分数中不超过j时的最大方案数有多少
//动态规划带有连续性，是在上一个的基础上的
//直接理解可能有亿点麻烦，就像之前高中的概率步数题一样，可以锚定一个n，针对n的形成可能来写动态规划问题

//这个问题一个数i在构成数最大为j时的方案数可以分为2个：
//1.最大数不为j，为j-1的时候的方案数dp[i][j-1](即不使用j)+最大数为j时候的方案数dp[j-i][j](使用j)

int dp[105][105];
int slove(int n){
	for(int i=0;i<=n;++i){
        dp[i][0]=0;
        dp[0][i]=1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i>=j){
                dp[i][j]=dp[i][j-1]+dp[i-j][j];
            }
            else{
                dp[i][j]=dp[i][j-1];//继承上一状态
            }
        }
    }
    return dp[n][n];
}

2.送快递

1
2
3
4
5
6
7
8
9
10
11
//这题说每个快递都送错的次数，典型的全错位排序
//num=(n-1)*(d(n-1)+d(n-2))

int q(int n){
	if(n==0) return 1;
    else if(n==1) return 0;
    else{
        return (n-1)*(q(n-1)+q(n-2));
    }
}

3.找迷宫

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
//这道题是一个类似于dfs 的，关键都是标记走过的地方和控制方向。注意标记的时候要考虑范围
//n*m的，然后，走到x行y列
int n, m, p, q;
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 右、下、左、上四个方向
int matrix[5000][5000];

int find_steps() {
    int x = 1, y = 1;  // 从左上角出发
    int direction = 0;  // 初始方向是右
    int step = 1;  // 从1开始步数
    matrix[x][y] = step;  // 标记起点
    
    while (1) {
        int nx = x + directions[direction][0];  // 计算下一个位置
        int ny = y + directions[direction][1];
        
        // 判断下一个位置是否越界，或已经访问过
        if (nx < 1 || ny < 1 || nx > n || ny > m || matrix[nx][ny] != 0) {
            // 改变方向
            direction = (direction + 1) % 4;
            nx = x + directions[direction][0];
            ny = y + directions[direction][1];
        }
        
        step++;
        matrix[nx][ny] = step;  // 标记当前位置
        
        // 到达目标位置
        if (nx == p && ny == q) {
            return step;
        }
        
        // 更新当前位置
        x = nx;
        y = ny;
    }
}

4.递归汉诺塔

1
2
3
4
5
6
7
8
9
10
//这道题求的是汉诺塔移动的次数，关键在于n和n-1时的递归，脑中根据题目限制的条件想想公式

int hanoi(int n){
    if(n==1){
        return 2;//这道题的条件让连续
    }
    else{
        return 3*hanoi(n-1)+2;
    }
}

5.熊猫序列

1
2
3
4
5
6
7
8
9
10
//联想斐波那契数列求解
//他是在第五年生宝宝，即
int panda(int n){
    if(n<5){
        return 1;
    }
    else{
        return panda(n-1)+panda(n-4);
    }
}

3.2.24，25,27,28,18 *,14,9

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
//这个题就是一个dfs搜索的题，关键他说外围假设都是水，那开数组的时候开大一圈，外围都用水代替就好
//在dfs的时候，如果是没有标记但是实际是1的就是新大陆，反之就不是
#include<stdio.h>

int m,n;
char s[25][25]={'0'};
int visited[25][25]={0};
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int dfs(int x,int y){
    visited[x][y]=1;
    for(int i=0;i<4;++i){
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>0 && nx<m+1 && ny>0 && ny<n+1 && !visited[nx][ny] && s[nx][ny]=='1'){
            visited[nx][ny]=1;
            dfs(nx,ny);
        }
    }

}
int main(){
    int sum=0;
    scanf("%d %d",&m,&n);
    for(int i=1;i<m+1;++i){
    	for(int j=1;j<n+1;++j){
    		scanf(" %c",&s[i][j]);
		}
	}
    for(int i=1;i<m+1;++i){
        for(int j=1;j<n+1;++j){
            if(!visited[i][j] && s[i][j]=='1'){//寻找没有连接在一块的，通过下面的dfs把他连一块
                sum++;
                dfs(i,j);
            }
                
        }
    }
    /*
    for(int i=0;i<m+2;++i){
    	for(int j=0;j<n+2;++j){
    		printf("%d",visited[i][j]);
		}
		printf("\n");
	}
	*/
    printf("%d",sum);
    return 0;
}

image-20250213094008093

2.蛇形矩阵

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
//也是一道dfs题，和上文找迷宫类似，同样要用到方向，这道题关键要保证退出的条件合法
int n;
int s[25][25] = {0};
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; // 右，下，左，上
int step = 1; // 起点

void dfs(int x, int y) {
    s[x][y] = step;
    step++;
    int d = 2; // 起始方向：右
    
    while (1) {
        int nx = x + dir[d][0];
        int ny = y + dir[d][1];
        
        // 检查是否越界或者已经被访问过
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || s[nx][ny] != 0) {
            d = (d + 1) % 4; // 转到下一个方向
        } else {
            // 更新位置并标记访问
            s[nx][ny] = step;
            step++;
            x = nx;
            y = ny;
        }
        
        // 判断是否四个方向都无法继续
        int blocked = 1;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            // 只有合法且未访问的点才认为是可以继续的
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && s[nx][ny] == 0) {
                blocked = 0;
                break;
            }
        }
        if (blocked) {
            break; // 四个方向都被访问过，退出
        }
    }
}

3.求相反数

1
//就是检查最后一位，他给的是补码，就最后一位如果是1就为0，如果是0就为1，并且前一位为0

4.火柴拼图

1
//关键是把每个数字所需火柴数给列出来

5.狐狸抓兔子

1
//和约瑟夫问题同理，下标，然后标记

6.字符串纠错

1
//关键是把键盘转化为二维数组的形式

7.阿狄的冒险

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
//用到队列，先进先出，每次满了或者不够，就把最开始的那个放入仓库
int main(){
    int M, N;
    int materials[1010];  //存放所有需要的素材
    int backpack[110];    //存放背包中的素材
    int front = 0, size = 0;  //front表示队列头，size表示背包中元素个数
    int warehouse_count = 0;  //记录返回仓库的次数
    scanf("%d %d", &M, &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &materials[i]);
    }
    for (int i = 0; i < N; i++) {
        int material = materials[i];
        bool found = false;
        // 检查背包中是否已有该素材
        for (int j = 0; j < size; j++) {
            if (backpack[(front + j) % M] == material) {
                found = true;
                break;
            }
        }

        //如果背包中没有该素材，则需要去仓库取
        if (!found) {
            warehouse_count++;
            //背包已满，移除最早放入的素材
            if (size == M) {
                front = (front + 1) % M;//队列头部出队
                size--;
            }
            // 将新素材放入背包
            backpack[(front + size) % M] = material;
            size++;
        }
    }
    printf("%d\n", warehouse_count);
    return 0;
}

5.1.16 ,2

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
//这道题除了策略最小战最大，最小战最小，最大战最大之外，还用到了双指针，不过不是传统意义上的，只是同时遍历数组
#include<stdio.h>
#include<stdlib.h>

int compare(const void*x,const void*y){
    return *(int *)x-*(int *y);
}

int main(){
    int n;
    int win=0;//赢数
    scanf("%d",&n);
    int me[n],op[n];
    for(int i=0;i<n;++i){
        scanf(" %d",&me[i]);
    }
    for(int i=0;i<n;++i){
        scanf(" %d",&op[i]);
    }
    qsort(me,n,sizeof(int),compare);
    qsort(op,n,sizeof(int),compare);
    int i=0,j=0;
    while(i<n && j<n){
        if(me[i]>op[j]){//这里的过程，看似是战了，实际上，如果没有胜就没有战
            j++;//只有我们赢了才会让敌方下一个上，不然我们就一直模拟下一个马，看看能不能赢，如果以后一直都没赢，最大的都没赢这个，后面就不用看了。
            win++；
        }
        i++;
    }
    printf("%d",win);
    return 0;
}

2.矩阵变换

1
2
3
4
5
6
7
8
9
10
//这题包括前面几道的关键的数组的翻转；
void reverse(int l,int r){
    while(r<l){
        int tmp=s[l];
        s[l]=s[r];
        s[r]=tmp;
        l++;
        r--;
    }
}

6.1.1，6

1.工作ddl

1
//对截止时间排序，他要求保证完成，完不成就下一个，那就从最短的一个个来

2.导员的生日推送

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
//对于结构体中多个成员的排序
typedef struct {
    char id[55];
    int y;
    int m;
    int d;
}stu;

int compare(const void *x,const void *y){
    stu *dx=(stu *)x;
    stu *dy=(stu *)y;
    if(dx->m!=dy->m) return dx->m-dy->m;
    if(dx->d!=dx->d) return dx->d-dy->d;
    return strncmp(dx->id,dy->id,55);

}

int main(){
    int n;
    scanf("%d",&n);
    stu s[n];
    for(int i=0;i<n;++i){
        scanf("%s %d:%d:%d",&s[i].id,&s[i].y,&s[i].m,&s[i].d);
    }
    qsort(s,n,sizeof(stu),compare);
    int m=-2;
    for(int i=0;i<n;++i){
        if(s[i].m==s[i+1].m && s[i].d==s[i+1].d){
            printf("%d:%d %s",s[i].m,s[i].d,s[i].id);
            printf(" %s\n",s[i+1].id);
            m=i;
        }
        else if(i!=m && i!=m+1){
            printf("%d:%d %s\n",s[i].m,s[i].d,s[i].id);
        }

        
    }
    return 0;
}