位运算双指针排序二分

诗 槐作者： • 2025-03-14 • 算法

位运算:

知识点:

在C/C++ 中天然的支持除10进制之外的三种进制的表示, 其前缀分别为:

二进制: 0b
八进制: 0
十六进制: 0x

1.二进制

例: int x = 0b1001; // x = 9

2.八进制

例：int y = 074; // x = 60

3.十六进制

例: int z = 0xa3; // x = 163

https://www.starrycoding.com/problem/51

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    int sum = 0;
    while (a) {
      if ((a & 0b1) == 1) {
        sum++;
      }
      a = a >> 1;
    }
    cout << sum << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

https://www.starrycoding.com/problem/52

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void solve() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int x = 0;
    while (n--) {
      int a;
      cin >> a;
      x = x ^ a;
    }
    cout << x << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

https://www.starrycoding.com/problem/53

过于巧妙:

使用异或快速算法

这里的异或乘法也可以使用前缀和来计算,即(典型的空间换时间)

for(int i=1 ;i<=2e5 ;i++){
  mex_a[i]=mex_a[i-1]^i;
}
// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void solve() {
  int MEX, XOR;
  cin >> MEX >> XOR;
  int mex_a = (MEX % 4 == 0)   ? 0
              : (MEX % 4 == 1) ? MEX - 1
              : (MEX % 4 == 2) ? 1
                               : MEX;
  if (mex_a == XOR) {
    cout << MEX << endl;
  } else if ((mex_a ^ XOR) == MEX) {
    cout << MEX + 2 << endl;
  } else {
    cout << MEX + 1 << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int _;
  cin >> _;
  while (_--) solve();
  return 0;
}

排序:

去重排序模板:

一定要先对数组进行排序才可以使用unique函数

unique函数的返回值是去重之后第一个重复值的迭代器,即返回值地带其之前的已是排序好的且已去重的,unique会将重复的元素放置到尾地址之后,故用erase擦除这段范围,使size变化,其中存储的为所需

sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());

https://www.starrycoding.com/problem/54

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    a.push_back(x);
  }
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
  for (auto& i : a) cout << i << " ";
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

多关键字排序:

将关键字作为类的元素,通过重载运算符来指定排序规则/制定排序规则函数,再调用排序函数,排序函数隐性调用重载运算符/显式调用函数达成排序的目的

https://www.starrycoding.com/problem/55

隐性调用:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;

class Book {
 public:
  int a, b, c;
  bool operator<(const Book &u) const {//模板
    if (a == u.a && b == u.b) return c > u.c;
    if (a == u.a) return b > u.b;
    return a > u.a;
  }
} p[N];

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].a >> p[i].b >> p[i].c;
  }
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; i++) {
    cout << p[i].a << " " << p[i].b << " " << p[i].c << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

显性调用

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;

class Book {
 public:
  int a, b, c;
} p[N];

bool cmp(const Book &u, const Book &v) {
  if (u.a == v.a && u.b == v.b) return u.c > v.c;
  if (u.a == v.a) return u.b > v.b;
  return u.a > v.a;
}

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].a >> p[i].b >> p[i].c;
  }
  sort(p + 1, p + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    cout << p[i].a << " " << p[i].b << " " << p[i].c << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

https://www.starrycoding.com/problem/56

因为数据量比较大,用STL容易超时,所以使用桶排序

桶排序就是经典的空间换时间的排序算法,根据下标的自带顺序,将元素的值作为下标(有点像哈希呢),并从头到尾输出

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int c[N];
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    c[x]++;
  }
  for (int i = 0; i < 2e5; i++) {
    for (int j = 0; j < c[i]; j++) {
      cout << i << " ";
    }
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

双指针:

https://www.starrycoding.com/problem/36

判断最长不重复连续子段,思路为:利用双指针,i指针作用为当前范围的起始位置,j为当前范围的结束位置,每次判断j后面的一个元素是否在范围内出现,如果出现,则将起始位置替换成范围内的重复元素的下一个,随后判断长度最值(感觉我这个有点像贪心)

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N];
void solve() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    int l_max = 0;
    for (int i = 1, j = 1; i <= n && j < n; j++) {
      for (int k = i; k <= j; k++) {
        if (a[j + 1] == a[k]) {
          i = k + 1;
        }
      }
      l_max = max(l_max, j - i + 1);
    }
    cout << l_max + 1 << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

二分:

https://www.starrycoding.com/problem/57

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 10, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  while (q--) {
    int x;
    cin >> x;
    int l = 0, r = n;
    while (l + 1 != r) {
      int mid = ((l + r) >> 1);
      if (x > a[mid]) {
        l = mid;
      } else {
        r = mid;
      }
    }
    if (a[r] == x)
      cout << r << " ";
    else
      cout << "-1 ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

若你所见,这里我还不知道加什么
要不要加个彩蛋呢

滚动至顶部