魔版笔记

userId_undefined
得去搞点吃的

2026-03-21 09:29:03

发布于：浙江

56阅读
0回复
0点赞

最大公约数

辗转相除法
int gcd(int a, int b){
	if(a % b == 0) return b;
	return gcd(b, a % b);
}
algorithm 自带函数
__gcd(a, b);
结构体变量的定义
struct Student{
	int en, chi, ma;
	int id, sum;
}a1, b1[310];			// 定义一个结构体变量 a1 和 一个结构体数组 b1 

Student a2, b2[310];	// 定义一个结构体变量 a2 和 一个结构体数组 b2
结构体排序

sort(起始地址, 结束的下一个地址, 排序函数);

/*
靠前的元素x,  靠后的元素y
排序规则:
	1. 总分不同, 按总分从大到小排
	2. 总分相同, 语文不同, 按语文从大到小排
	3. 总分相同, 语文相同, 按学号从小到大排
*/
bool cmp(Student x, Student y){
	if(x.sum != y.sum) return x.sum > y.sum;
	if(x.chi != y.chi) return x.chi > y.chi;
	return x.id < y.id;
}
例题代码（奖学金）
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 310;

struct Student{
	int en, chi, ma;
	int id, sum;
};

Student a[N];
int n;

// 靠前的元素x,  靠后的元素y
bool cmp(Student x, Student y){
	if(x.sum != y.sum) return x.sum > y.sum;	// 总分不同, 总分从大到小排序
	if(x.chi != y.chi) return x.chi > y.chi;	// 总分相同, 语文不同, 语文从大到小排序
	return x.id < y.id;	// 总分相同, 语文相同, 学号从小到大排序
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; ++ i ){
		cin >> a[i].chi >> a[i].ma >> a[i].en;
		a[i].id = i;
		a[i].sum = a[i].chi + a[i].ma + a[i].en;
	}
	
	sort(a + 1, a + n + 1, cmp);
	
	for(int i = 1; i <= 5; ++ i ) 
		cout << a[i].id << " " << a[i].sum << endl;
	return 0;
}

二分查找元素 x 是否存在

前置要求: 数组从小到大排序

int bf(int left, int right, int x){
	while(left <= right){
		// [left, right]
		//   小于a[mid]          大于a[mid]
		// [left, mid-1]  mid  [mid+1, right]
		int mid = (left + right) / 2;
		if(a[mid] == x){
			return mid;
		}
		else if(a[mid] < x){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
	}
	return -1;
}

二分查找大于等于 x 的第一个元素

前置条件：数组从小到大排序

int bf(int left, int right, int x){
	int ans = n + 1;
	while(left <= right){		// 循环从 left 到 right 找某个元素
		//   小于a[mid]          大于a[mid]
		// [left, mid-1]  mid  [mid+1, right]
		int mid = (left + right) / 2;
		if(a[mid] >= x){
			ans = mid;			// 记录答案
			right = mid - 1;  	// 往左边找
		}
		else {
			left = mid + 1;
		}
	}
	return ans;
}

二分查找大于 x 的第一个元素

前置条件：数组从小到大排序

int bf(int left, int right, int x){
	int ans = n + 1;
	while(left <= right){		// 循环从 left 到 right 找某个元素
		//   小于a[mid]          大于a[mid]
		// [left, mid-1]  mid  [mid+1, right]
		int mid = (left + right) / 2;
		if(a[mid] > x){
			ans = mid;
			right = mid - 1; 	
		}
		else{
			left = mid + 1;    // 往右边找
		}
	}
	return ans;
}

二分答案

TLE 代码（非模板）
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;	 // 2*10^5 + 10

int n, a[N], m, h;
int l = 1, r = 0;

bool check(int h){
	int cnt = 0;
	for(int i = 1; i <= n; ++ i ){
		cnt += a[i] / h;
	}
	return cnt >= m;
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];
		r = max(r, a[i]);
	}
	// 木材长度  长度最低 1, 最高 max{a[i]}
	// 1 1 1 1 1 1 0 0 0   (长度从小到大)
	//           ↑
	//           h
	for(int h = r; h >= l; -- h ){
		if(check(h)){
			cout << h << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	return 0;
}
二分答案代码
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;	 // 2*10^5 + 10

int n, a[N], m, h;
int l = 1, r = 0;

bool check(int h){
	int cnt = 0;
	for(int i = 1; i <= n; ++ i ){
		cnt += a[i] / h;
	}
	return cnt >= m;
}

int bf(int left, int right){
	int ans = 0;				// 没答案的时候输出什么
	while(left <= right){
		int mid = (left + right) / 2;
		if(check(mid)){			// 符合要求
			ans = mid;			// 记录答案
			left = mid + 1;		// 往后找, 尝试更长长度
		}
		else{
			right = mid - 1;	// 往前找, 尝试更短长度
		}
	}
	return ans;
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];
		r = max(r, a[i]);
	}
	
	cout << bf(l, r);
	return 0;
}

前缀和

已经有一个 a 数组。

创建 pre 数组，pre[i] 的定义 a 数组前 i 项元素之和。

定义：pre[i] = a[1] + a[2] + ... + a[i]

求前缀和：pre[i] = pre[i-1] + a[i] ，前 i 项之和 = 前 i-1 项之和 + 第 i 项。

求 [l, r] 区间的和：pre[r] - pre[l-1] ，注意！！！不能写成 pre[r] - pre[l]

差分模板题
#include <bits/stdc++.h>
using namespace std;

int n, d[100010], m, a[100010], c[100010];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		d[i] = a[i] - a[i - 1];		// 差分数组
	}
	
	for (int i = 1; i <= m; i++) {
		int l, r, c;
		cin >> l >> r >> c;
		d[l] += c;		// 下标 l   以及之后所有元素都会增加c
		d[r + 1] -= c;	// 下标 r+1 以及之后所有元素都会减少c
	}
	
	// 求d数组前缀和
	for (int i = 1; i <= n; i++) {
		c[i] = c[i - 1] + d[i];
		cout << c[i] << " ";
	}
	return 0;
}

连通块问题

邻接矩阵存图
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 10;

int n, m, x, y;
int mp[N][N], vis[N];
int cnt = 0;

void dfs(int now){
	vis[now] = 1;
	cnt ++ ;
	for(int i = 1; i <= n; ++ i ){	// 枚举所有点
        // now能到i去 并且 i没搜过
		if(mp[now][i] == 1 && vis[i] == 0){
			dfs(i);
		}
	}
}

int main() {
	cin >> n >> m;
	while(m -- ){
		int u, v;
		cin >> u >> v;
		mp[u][v] = 1;	// u->v 正边
		mp[v][u] = 1;	// v->u	反边
	}
	cin >> x >> y;
	dfs(x);
	if(vis[y] == 1) cout << cnt;
	else cout << 0;
	return 0;
}
邻接表存图

深搜实现连通块

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, x, y;
int vis[N];
int cnt = 0;
vector<int > mp[N]; // 一维的动态数组
// mp[x] 这个一维数组存的就是以 x 为起点能到的终点有哪些

// 当前点是 now
void dfs(int now){
	vis[now] = 1;	// now标记为搜过
	cnt ++ ;		// 标一个加一个
    // 枚举now的边
	for(int i = 0; i < mp[now].size(); ++ i ){	
		int nxt = mp[now][i];	// 当前边的终点
		if(vis[nxt] == 0){		// 判断终点是否搜过
			dfs(nxt);			// 没有搜过继续往下搜索
		}
	}
}

int main() {
	cin >> n >> m;
	while(m -- ){
		int u, v;
		cin >> u >> v;
		mp[u].push_back(v);	// u->v 正边
		mp[v].push_back(u);	// v->u	反边
	}
	cin >> x >> y;
	dfs(x);
	if(vis[y] == 1) cout << cnt;
	else cout << 0;
	return 0;
}

广搜实现连通块

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, x, y;
int vis[N];
int cnt = 0;
vector<int > mp[N]; // 一维的动态数组
// mp[x] 这个一维数组存的就是以 x 为起点能到的终点有哪些

void bfs(int sx){
	queue<int > q;		// 定义队列
	q.push(sx);			// 头节点入队
	while(!q.empty()){
		int now = q.front();	// 获取队首
		q.pop();				// 删除队首
		if(vis[now] == 1) continue;
		vis[now] = 1;			// 标记为走过
		++ cnt;					// 标一个加一个
		for(int i = 0; i < mp[now].size(); ++ i ){
			int nxt = mp[now][i];
			if(vis[nxt] == 0){
				q.push(nxt);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	while(m -- ){
		int u, v;
		cin >> u >> v;
		mp[u].push_back(v);	// u->v 正边
		mp[v].push_back(u);	// v->u	反边
	}
	cin >> x >> y;
	bfs(x);
	if(vis[y] == 1) cout << cnt;
	else cout << 0;
	return 0;
}

充满希望的骑士与棋盘

🐎 跳跃坐标的变化

int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int n, m, sx, sy; // startX startY
int ans[1010][1010];
int vis[1010][1010];

int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

struct Node{
	int x, y;
	int step;
};

void bfs(){
	memset(ans, -1, sizeof(ans));		// 数组初始化为 -1
	queue<Node> q;						// 结构体队列
	q.push({sx, sy, 0});				// 起点 + 步数
	while(!q.empty()){
		Node now = q.front();			// 获取队首
		q.pop();						// 删除队首
		if(vis[now.x][now.y] == 1) continue;
		vis[now.x][now.y] = 1;			// 标记走过
		ans[now.x][now.y] = now.step;	// 记录步数
		for(int i = 0; i < 8; ++ i ){	// 八个方向
			int tx = now.x + dx[i];		// 计算新坐标
			int ty = now.y + dy[i];
			int ts = now.step + 1;		// 计算步数
			// 行范围 && 列范围 && 没被标记过
			if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0){
				q.push({tx, ty, ts}); 	// 邻接点入队
			}
		}
	}
}

int main(){
	cin >> n >> m >> sx >> sy;
	bfs();
	for(int i = 1; i <= n; ++ i ){
		for(int j = 1; j <= m; ++ j ){
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 4

  • userId_undefined
    不知道

    可别在学牲考试时找到了

    1周前 来自 浙江

    1
  • userId_undefined
    不知道

    ycy牛福

    1周前 来自 浙江

    1
  • userId_undefined
    暗夜枪神
    空间掌握者分治·分治练习生模拟·模拟练习生枚举·枚举小能手贪心·贪心尝试者

    可别在学牲考试时找到了假笑

    1周前 来自 浙江

    0
  • userId_undefined
    Eucatastrophe‌
    禁言
    GESP6级

    orz 我不会二分

    1周前 来自 浙江

    0

热门讨论