ZBCPSS250093 笔记
2026-03-07 20:37:32
发布于：浙江
19阅读
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;
}
这里空空如也
有帮助，赞一个