XP03笔记
2025-08-21 09:47:39
发布于：广东
186阅读
0回复
0点赞
XP03 - day 01
时间复杂度
二分查找元素 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 if(a[mid] < x){
left = mid + 1;
}
else{ // a[mid] > x
ans = mid;
right = 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){
left = mid + 1; // 往右边找
}
else if(a[mid] < x){
left = mid + 1;
}
else{ // a[mid] > x
ans = mid;
right = 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 = 0, r = 0;
bool check(int h){
int ans = 0;
for(int i = 1; i <= n; ++ i ){
if(a[i] > h) ans += a[i] - h;
}
if(ans >= m) return true;
else return false;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
r = max(r, a[i]);
}
// 枚举锯子高度 锯子最低 0, 最高 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 << -1 << 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 = 0, r = 0;
bool check(int h){
long long ans = 0;
for(int i = 1; i <= n; ++ i ){
if(a[i] > h) ans += a[i] - h;
}
if(ans >= m) return true;
else return false;
}
int bf(int left, int right){
int ans = -1;
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]);
}
// 1 1 1 1 1 1 1 0 0 0 0
// 0 1 2 3 4 ... h-1 h h+1 h+2 ... r
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]
01DFS
概念：使用 DFS 去枚举数字或者数组元素，0 表示不选，1 表示选，最后对选择出来的方案进行判断。
#include <bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int N = 20;
LL n, a[N], ans;
bool is_prime(int x){
if(x <= 1) return false;
// 也可以写成 i <= sqrt(x)
for(int i = 2; i <= x/i; ++ i ){
if(x % i == 0) return false;
}
return true;
}
// 决定第i个数是否选择
// 当前已选数字总和为 sum
void dfs(int i, int sum){
if(i == n + 1){
if(is_prime(sum)) ++ ans;
return ;
}
dfs(i + 1, sum); // 第i个数不选, 接着判断i+1
dfs(i + 1, sum + a[i]); // 第i个数选择, 接着判断i+1
}
int main() {
cin >> n;
for(int i = 1; i <= n; ++ i ) cin >> a[i];
dfs(1, 0);
cout << ans << endl;
return 0;
}
二进制枚举
通过枚举数字，使用数字的二进制位去决定某个数字选还是不选。
例: 1011 第 1,2,4 个数选, 第 3 个数不选。
#include <bits/stdc++.h>
using namespace std;
int n, ans, a[20];
bool is_prime(int x){
if(x <= 1) return false;
for(int i = 2; i <= sqrt(x); ++ i ){
if(x % i == 0) return false;
}
return true;
}
int main() {
cin >> n;
for(int i = 0; i < n; ++ i ) cin >> a[i];
// 例: 1011 第1,2,4个数选, 第3个数不选
for(int i = 0; i < 1 << n; ++ i ){ // 二进制枚举
int sum = 0;
for(int j = 0; j < n; ++ j ){ // 枚举二进制位
if(i & (1 << j)){ // 判断二进制位是否为 1
sum += a[j]; // 累加数字
}
}
if(is_prime(sum)) ++ ans; // 质数判断
}
cout << ans << endl;
return 0;
}
连通块问题
邻接矩阵存图
#include <bits/stdc++.h>
#define LL long long
#define endl '\n'
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>
#define LL long long
#define endl '\n'
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>
#define LL long long
#define endl '\n'
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;
}
结构体排序
结构体的定义
关键词: struct
结构体里的变量称为成员变量，如果要使用成员变量，需要用 .
struct Student{
int en, chi, ma;
int id, sum;
};
结构体变量的定义
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;
}
快速幂
分治做法
#include <iostream>
#include <cassert>
using namespace std;
typedef long long ll;
ll a, b, p;
ll quick_power(ll a,ll b){ //计算a的b次方
if(b == 0) return 1;
ll ans = quick_power(a,b/2); //先计算a的（b / 2）次方
ans = ans * ans % p;
if(b % 2 == 1){ //如果 b 是奇数，则 a ^ b = (a ^ (b / 2)) * (a ^ (b / 2)) * a
return ans * a % p;
}
return ans;
}
int main() {
cin >> a >> b >> p;
cout << a << "^" << b << " mod " << p << "=" << quick_power(a,b);
return 0;
}
最大公约数
辗转相除法
int gcd(int a, int b){
if(a % b == 0) return b;
return gcd(b, a % b);
}
algorithm 自带函数
__gcd(a, b);
八皇后问题
使用多个标记数组记录列和斜线的情况。
#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0;
int lie[20], xie1[30], xie2[30];
int ans[20];
void dfs(int i){ // 放第i个皇后
if(i == n + 1){
++ cnt;
if(cnt <= 3){ // 只输出前3组方案
for(int j = 1; j <= n; ++ j ) cout << ans[j] << " ";
cout << endl;
}
return;
}
for(int j = 1; j <= n; ++ j ){ // 枚举列
if(lie[j] == 0 && xie1[i - j + n] == 0 && xie2[i + j] == 0){
lie[j] = 1; // 第j列放皇后
xie1[i - j + n] = 1; // 行-列
xie2[i + j] = 1; // 行+列
ans[i] = j; // 第i行皇后在第j列
dfs(i + 1); // 去放下一个皇后
lie[j] = 0; // 第j列没皇后了
xie1[i - j + n] = 0; // 行-列
xie2[i + j] = 0; // 行+列
ans[i] = 0; // 取走皇后
}
}
}
int main() {
cin >> n;
dfs(1);
cout << cnt << endl;
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;
}
dijkstra
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define LL long long
using namespace std;
const int N = 1e6 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct node{
int v;
LL w;
bool operator < (const node &x) const {
return x.w < w; // 按w从小到大排
}
};
int n, m, s;
vector<node > g[N];
LL st[N], d[N];
void dijkstra(){
memset(d, INF, sizeof(d));
priority_queue<node > q;
q.push({s, 0});
while(!q.empty()){
node k = q.top();
q.pop();
if(st[k.v] == 1) continue;
st[k.v] = 1;
d[k.v] = k.w;
for(node &it : g[k.v]){
q.push({it.v, k.w + it.w});
}
/*
另一种枚举邻接点
for(int i = 0; i < g[k.v].size(); i ++ ){
node it = g[k.v][i];
q.push({it.v, k.w + it.w});
}
*/
}
}
int main(){
cin >> n >> m >> s;
for(int i = 1; i <= m; ++ i ){
int x, y, z;
cin >> x >> y >> z;
g[x].push_back({y, z});
}
dijkstra();
for(int i = 1; i <= n; ++ i ){
cout << (d[i] != INF ? d[i] : -1) << " ";
}
return 0;
}
有帮助，赞一个