洛谷刷题笔记 其一

洛谷算法刷题整集2025.2.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
#include <stdio.h>

int main() {
    unsigned int a=5; // 二进制 0101
    unsigned int b=3; // 二进制 0011
    //与(&)
    printf("a & b = %u\n", a & b); // 0001 → 1//对于1而言
    //或(|)
    printf("a | b = %u\n", a | b); // 0111 → 7//对于1而言
    //异或(^)
    printf("a ^ b = %u\n", a ^ b); // 0110 → 6//想通为0，不同为1
    //取反(~)（结果与类型位数有关）
    printf("~a = %u\n", ~a); // 1111 1010（假设32位）→ 4294967290
    //左移(<<)
    printf("a << 1 = %u\n", a << 1); // 1010 → 10
    //右移(>>)
    printf("a >> 1 = %u\n", a >> 1); // 0010 → 2
    //判断奇偶
    int num = 7;
    if (num & 1) {
        printf("%d 是奇数\n", num);
    }
    return 0;
}

2.差分

差分常用于对一个数组的区间进行频繁操作修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int s[]={-1,0,5,2,3,4};//原数组
int d[6];
int s1[6];
d[0]=s[0];//-1
for(int i=1;i<n;++i){
    d[i]=s[i]-s[i-1];
}
//现在的d={-1,1,5,-3,1,1}假如要对[1,3]区间(对于d数组的形式)进行操作+1；
d[1]+=1;
d[3+1]-=1;//-1的原因是因为要覆盖到区间，所以出了区间立马加1,如果大于区间，就不管

//现在d={-1,2,5,-3,0,1}
//然后对差分数组d进行前缀和操作还原

s1[0]=d[0];
for(int i=1;i<n;++i){
    s1[i]=d[i]+s1[i-1];
}
//s1={-1,1,6,3,3,4}

3.质数筛

埃氏筛：因为如果一般双循环找质数（素数）可能查找有重复部分，时间就会大大增长，这时，可以用以下办法：

1
2
3
4
5
6
7
8
9
void sieve(bool is_prime[], int n) {
    for (int i = 2; i * i <= n; i++) {//对于一个数n来说，如果它能被某个数i整除，那么i必定小于等于√n，否则i和n/i会互换角色。因此，只需要检查到i的平方大于n，即可确保所有可能的因数都已被检查。
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {//从i*i开始是因为如果i是倍数，那么他所有的倍数就都是合数即非质数
                is_prime[j] = false;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
    int n = 30;
    bool is_prime[100];
    //初始化数组，假设所有数都是质数
    for (int i = 0; i <= 100; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;

    sieve(is_prime, n);

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) printf("%d ", i);
    }
    return 0;
}

4.哈希表

hash表用于频繁查找的操作，适合需要快速查找，删除，增加的操作，常用于缓存，便于快速查找，提高性能

但是，注意：与链表不能完全用途重合，链表适用于频繁地删除和修改操作，是动态的，而hash是固定的，有时修改需要改变函数

实现的话说白了，就是开一个数组，数组的索引就是我们需要查找的元素，对应索引的值就是我们需要进行操作的数值（次数，标记）

唯一细节的是，要根据开的hash数组的大小z，对每个我们要查找的元素%z来构成索引

下面以一个字符数组为例：

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
#include <stdio.h>
#include <string.h>

#define SIZE 10//哈希表大小

//简单哈希函数：将字符串的每个字符的 ASCII 值加起来，并取模
int hash(char* str) {
    int hashValue = 0;
    while (*str) {
        hashValue += *str;
        str++;
    }
    return hashValue % SIZE;  //对哈希表大小取模，得到索引


int main() {
    char* keys[] = {"apple", "banana", "orange", "apple"};
    int counts[SIZE] = {0};  //这是存次数的，hash函数是用于专门对目标元素转换成索引的
    //统计每个字符串出现的次数
    for (int i = 0; i < 4; i++) {
        int index = hash(keys[i]);
        counts[index]++;
    }
    for (int i = 0; i < SIZE; i++) {
        if (counts[i] > 0) {
            printf("Index %d: %d times\n", i, counts[i]);
        }
    }
    return 0;
}

但是当2个不同的元素余数相同时，就会引发哈希冲突，这是不可避免的，这时，可以用链地址法：就是把这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
#define SIZE 5  // 哈希表大小
// 链表节点结构
typedef struct Node {
    char word[50];
    int count;
    struct Node* next;
} Node;

// 哈希表结构
Node* hashTable[SIZE];

int hash(char* str) {
    int hashValue = 0;
    while (*str) {
        hashValue += *str;  // 计算字符的ASCII值之和
        str++;
    }
    return hashValue % SIZE;  // 取模得到哈希值
}

// 插入元素
void insert(char* word) {
    int index = hash(word);  // 计算哈希值
    Node* temp = hashTable[index];
    
    // 遍历链表，查找是否已经有相同的单词
    while (temp != NULL) {
        if (strcmp(temp->word, word) == 0) {  // 如果找到相同的单词
            temp->count++;  // 增加出现次数
            return;
        }
        temp = temp->next;
    }
    
    // 如果没有找到，插入新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->word, word);
    newNode->count = 1;  // 初始出现次数为1
    newNode->next = hashTable[index];  // 将新节点插入到链表头部
    hashTable[index] = newNode;  // 更新哈希表
}

5.链表

链表由多个节点组成，这一个个节点中又有数据域（存数据的）和指针域（用于指向链表的下一个节点地址，通常最后一个节点指向NULL）

在上一个哈希表中，遇到的哈希冲突问题，就可以用链表解决，当不同元素的余数相同时，我们就可以把他存入这个哈希槽位的链表中

1
2
3
4
5
6
//这是一个节点的构造：
typedef struct Node {
    char word[50];  //存储字符串
    struct Node* next;  //指向下一个节点的指针
} Node;

插入操作：

1
2
3
4
5
6
7
void insertAtHead(Node** head, char* word) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->word, word);
    newNode->count = 1;
    newNode->next = *head;  // 新节点指向原来的头节点
    *head = newNode;        // 更新头指针
}

如果要删除则是把该节点的next指针指向当前的next指针

6.文件操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FILE *fp;//创一个存储文件的指针变量，存文件地址的
//写入文件
fp = fopen("test.txt", "w"); 
if (fp == NULL) {
    printf("无法打开文件\n");
    return 1;
}
fprintf(fp, "Hello, World!\n");
fclose(fp);//关闭
//读取文件
fp = fopen("test.txt", "r");
char buffer[100];
while (fgets(buffer, 100, fp) != NULL) {
    printf("%s", buffer);
}
fclose(fp);

7.DFS深度搜索

构造基本就是标记再加上递归回溯：

1.遍历数组的所有的数，以n个每行输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int path[6];//k是最大数
void dfs(int x,int n,int k){
	if(x>n){//n是每行最大列数
		for(int i=1;i<=n;++i){//只要>n或者改为==n就开始输出
			printf("%d ",path[i]);
			
		}
		printf("\n");
		return ;
	}
	for(int i=1;i<=k;++i){
		path[x]=i;//这是回溯部分
		dfs(x+1,n,k);

	}
}

2.带有标记性质的dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,-1},{-1,1},{1,1},{-1,-1}};
char s[110][110];
int visited[110][110];
int dfs(int x,int y,int n,int m){//n是行，m是列 
	visited[x][y]=1;//一旦符合条件就进行标记
	int count=1;
	for(int i=0;i<8;++i){
		int nx=x+dir[i][0];
		int ny=y+dir[i][1];
		if(s[nx][ny]=='W' && !visited[nx][ny] && nx>=0 && nx<n && ny>=0 && ny<m){
			count+=dfs(nx,ny,n,m);
		} 
	}
	return count;
}

8.二维矩阵压缩为一维–最大加权矩形

矩阵压缩问题常用于找最大子矩阵的和：

因为如果用循环，4个for的时间复杂度过于大

通过矩阵压缩，一个n*n的矩阵，可以把他通过i到j行的数据加起来压缩一下，变成1维问题，再来找最大的和

1
2
3
4
5
6
7
8
9
//假如3*3的数组
1  2  3
4  5  6
7  8  9
//选择[1,2]行
temp[0] = 1 + 4 = 5
temp[1] = 2 + 5 = 7
temp[2] = 3 + 6 = 9
//此时再在这个基础上进行最大和的寻找

9.二分–查找

前提：单调序列

原理：通过不断找中间索引，看看中间值是否等于所要值，如果并不是，那更新左右边界，并且再次中间插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;//脑子中想象下他的边界情况
        }
        else right = mid - 1;
    }
    return -1;
}

10.队列：先进先出

（想象成一个U型通道dui）

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
#include <stdio.h>
#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = 0, rear = 0;
void enqueue(int x) {
    if (rear == MAX_SIZE) {
        printf("队列已满\n");
        return;
    }
    queue[rear++] = x;
}
int dequeue() {
    if (front == rear) {
        printf("队列为空\n");
        return -1;
    }
    return queue[front++];
}
int main() {
    enqueue(10);
    enqueue(20);
    printf("出队元素: %d\n", dequeue()); // 输出 10
    printf("出队元素: %d\n", dequeue()); // 输出 20
    return 0;
}

11.栈：后进先出

（想象成一个I型通道，堵了）

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
#include <stdio.h>
#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

void push(int x) {
    if (top == MAX_SIZE - 1) {
        printf("栈已满\n");
        return;
    }
    stack[++top] = x;
}

int pop() {
    if (top == -1) {
        printf("栈为空\n");
        return -1;
    }
    return stack[top--];
}

int main() {
    push(10);
    push(20);
    printf("出栈元素: %d\n", pop()); // 输出 20
    return 0;
}

12.保留最后n个数字：

1.字符串*10^位数

2.数字%10^4

同余与二维前缀和问题移步北航刷题整集