XP03笔记
2025-08-12 17:09:55
发布于：广东
77阅读
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
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;
}
连通块问题
邻接矩阵存图
#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;
}
有帮助，赞一个