stack(栈),priority_queue(堆/优先队列),map,set(集合),bitset

栈:

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

意思为:从进站口先进火车站,再进出站口,而火车站是一个栈,要求顺序出栈

// 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 + 9;
int a[N];

void solve() {
  int n;
  cin >> n;
  int pos = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];//进站
  }
  stack<int> train;//火车站
  for (int i = 1; i <= n; i++) {//for循环的意思是从1找到n的所有可进列车,若其中一个不可进则为No,否则为Yes
    while (pos <= n && (train.empty() || train.top() != i)) {//用while循环来模拟不符合要求火车的过,若不符合,则进火车站,直到找到复合的
      train.push(a[pos++]);
    }
    if (train.top() == i)//找到符合的,出栈
      train.pop();
    else {
      cout << "No";
      return;
    }
  }
  cout << "Yes";
}

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

堆:

最大的作用是可以将其代替找最大值和最小值的过程,因为堆自带维护,可以更快的找最小值/最大值,实例请见:最短路径的第二题

默认是大根堆

内置参数变为小根堆:

仿函数模拟大根堆:

仿函数模拟小根堆:

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

// 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() {
  priority_queue<int> pq;
  int q;
  cin >> q;
  int weight = 0;
  for (int i = 1; i <= q; i++) {
    int q_i;
    cin >> q_i;
    if (q_i == 1) {
      int q_in;
      cin >> q_in;
      pq.push(q_in);
      weight += q_in;
    } else {
      if (pq.size()) {//在进行取头和弹出数据的时候必须判断堆是否为空
        weight -= pq.top();
        pq.pop();
      }
    }
  }
  cout << weight;
}

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

map:

可以用auto取map的元素,用.first/.second取键/值

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

// 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;
  map<string, int> col;
  vector<string> ve;//使用一个vector来存储字符串第一次出现的顺序
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    if (col.count(s)) {//如果再col里存在s
      col[s]++;
    } else {//如果再col里没有s
      ve.push_back(s);//将s存到ve里
      col[s] = 1;//是col里的s出现次数为1
    }
  }
  for (auto &i : ve) {
    cout << i << " " << col[i] << "\n";
  }
}

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

set:

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;
  set<int> a;
  for (int i = 1; i <= n; i++) {
    int a_i;
    cin >> a_i;
    a.insert(a_i);
  }
  for (auto& i : a) {
    cout << i << " ";
  }
}

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

bitset:

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

递归回溯:
能解,但是很慢,超时了

// 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;
// vector<int> a;
// set<int> res;
// void backtracking(int sum, int startindex, int n) {
// res.insert(sum);
// for (int i = startindex; i < n; i++) {
// sum += a[i];
// if (i + 1 <= n) {
// backtracking(sum, i + 1, n);  // 递归
// }
// sum -= a[i];
// }
// }
// void solve() {
// int n;
// cin >> n;
// for (int i = 1; i <= n; i++) {
// int n_i;
// cin >> n_i;
// a.push_back(n_i);
// }
// backtracking(0, 0, n);
// cout << res.size();
// }
signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int _ = 1;
  while (_--) solve();
  return 0;
}

dp:

'// 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 = 5e3 + 10, M = 5e5 + 10;
int a[N];
bool dp[M];

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  dp[0] = true;
  for (int i = 1; i <= n; i++) {
    for (int j = 5e5; j >= a[i]; j--) {
      dp[j] |= dp[j - a[i]];
    }
  }
  int ans = 0;
  for (int i = 0; i <= 5e5; i++) {
    if (dp[i]) {
      ans++;
    }
  }
  cout << ans;
}
signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int _ = 1;
  while (_--) solve();
  return 0;
}

bitset:

// 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 = 5e3 + 10, M = 5e5 + 10;

void solve() {
  int n;
  cin >> n;
  bitset<M> bs;
  bs[0] = 1;
  for (int i = 1; i <= n; i++) {
    int a_i;
    cin >> a_i;
    bs |= (bs << a_i);
  }
  cout << bs.count();
}
signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int _ = 1;
  while (_--) solve();
  return 0;
}

有点nb,建议掌握,看看其函数与用法

如:

bitset<32>(x);//可以将x转化为bitset,以使用其内置函数

发表评论 取消回复

发表评论取消回复