"Cắp ba" lô vô biển lớn - Thử thách Debugging
Đường đi ngắn nhất
Nộp bàiPoint: 1
Đề bài: Cho đồ thị gồm ~n~ (~1 \leq n \leq 10^5~) đỉnh và ~m~ (~1 \leq m \leq 2 \cdot 10^5~) cạnh có trọng số, có hướng. Tìm đường đi ngắn nhất từ 1 đến mọi đỉnh từ ~1~ đến ~n~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<pair<int,long long>> adj[N];
long long dist[N];
bool vis[N];
int n;
void dijkstra (int source) {
for (int i = 1; i <= n; i++)
dist[i] = LLONG_MAX, vis[i] = 0;
priority_queue<pair<long long,int>> pq;
pq.emplace(0, source);
dist[source] = 0;
while (pq.size()) {
int u = pq.top().second;
if (vis[u]) continue;
vis[u] = 1;
for (pair<int,long long> it : adj[u]) {
int v; long long w; tie(v, w) = it;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.emplace(-dist[v], v);
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m; cin >> n >> m;
while (m--) {
int a, b, c; cin >> a >> b >> c;
adj[a].emplace_back(b, c);
}
dijkstra(1);
for (int i = 1; i <= n; i++) cout << dist[i] << " ";
return 0;
}
Tìm kiếm nhị phân
Nộp bàiPoint: 1
Đề bài: Cho dãy ~a~ gồm ~n~ (~1 \leq n \leq 3 \cdot 10^5~, ~1 \leq a_i \leq 10^9~) phần tử và một số nguyên ~x~ (~1 \leq x \leq 10^9~). Với mọi ~i~ từ ~1~ đến n, tìm phần tử bé nhất ~\geq x~ trong đoạn tiền tố gồm các phần tử từ ~1~ đến ~i~. Nếu không có phần tử nào ~\geq x~ thì in ra ~-1~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, targ; cin >> n >> targ;
set<int> s;
for (int i = 1; i <= n; i++) {
int a; cin >> a;
s.insert(a);
auto it = lower_bound(s.begin(), s.end(), targ);
if (it != s.end()) cout << *it << " ";
else cout << -1 << " ";
}
return 0;
}
Đếm bit
Nộp bàiPoint: 1
Đề bài: Cho một số nguyên ~x~ (~0 \leq x < 2^{60}~). Đếm số lượng chữ số ~1~ trong biểu diễn nhị phân của ~x~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long n; cin >> n;
cout << __builtin_popcount(n); // count the number of 1-bit in binary
// representation of n
return 0;
}
Tách dãy
Nộp bàiPoint: 1
Đề bài: Cho mảng ~a~ gồm ~n~ phần tử (~1 \leq n \leq 3 \cdot 10^6~, ~1 \leq a_i \leq 2 \cdot 10^9~) và một số nguyên ~x~ (~1 \leq x \leq 10^9~). Sắp xếp các phần tử mảng ~a~ và tách ra thành hai phần:
- Phần
Leftgồm các phần tử ~\leq x~. - Phần
Rightgồm các phần tử ~> x~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int x; cin >> x;
int n; cin >> n;
vector<int> L; // element less than or equal to x
vector<int> R; // element greater than x
for(int i = 1; i <= n; i++){
int y; cin >> y;
if(y <= x) L.push_back(y);
if(y > x) R.push_back(y);
}
sort(L.begin(), L.end());
sort(R.begin(), R.end());
cout << "Left: ";
for(int i=0; i<=L.size() - 1; i++) cout << L[i] << ' ';
cout << endl;
cout << "Right: ";
for(int i=0; i<=R.size() - 1; i++) cout << R[i] << ' ';
return 0;
}
Lũy thừa
Nộp bàiPoint: 1
Đề bài: Cho hai số nguyên ~a~ và ~b~ (~1 \leq a \leq 10^{18}~, ~1 \leq b \leq 10^9~). Hãy tính ~a^b \bmod (10^9 + 7)~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
// calculate a * b % MOD
long long mul(long long a, long long b) {
return a * b % MOD;
}
// calculate a^b % MOD
long long Pow (long long a, long long b) {
long long res = 1;
for(; b; b/=2, a=mul(a, a)) if(b%2 == 1) res = mul(res, a);
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
long long a, b;
cin >> a >> b;
cout << Pow(a, b);
return 0;
}
Đếm ước nguyên dương
Nộp bàiPoint: 1
Đề bài: Cho số nguyên ~n~ (~1 \leq n \leq 10^{12}~), đếm số ước nguyên dương của ~n~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
int cntDiv (long long n) {
int cnt = 0;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
if (i != n / i) cnt += 2;
else cnt++;
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long n; cin >> n;
cout << cntDiv(n);
return 0;
}
Sàng nguyên tố
Nộp bàiPoint: 1
Đề bài: Cho số nguyên ~n~ (~1 \leq n \leq 10^6~), in ra tất cả các số nguyên tố không quá ~n~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 1;
bitset<maxN> isPrime;
vector<int> primes;
void eratos() {
for (int i = 2; i < maxN; i++) isPrime[i] = 1;
for (int i = 2; i * i < maxN; i++) {
if (!isPrime[i]) continue;
for (int j = i * i; j < maxN; j += i) isPrime[j] = false;
primes.push_back(i);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
eratos();
for (int i = 0; i < primes.size() && primes[i] <= n; i++) cout << primes[i] << " ";
return 0;
}
Duyệt cây
Nộp bàiPoint: 1
Đề bài: Cho cây gồm ~n~ (~1 \leq n \leq 10^5~) đỉnh và ~n - 1~ cạnh có gốc là đỉnh ~1~. In ra thứ tự thăm các đỉnh nếu bắt đầu DFS từ gốc và ta ưu tiên các cạnh xuất hiện trước trong input khi duyệt.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
vector<int> adj[maxN];
void dfs (int u) {
cout << u << " ";
for (int v : adj[u]) dfs(v);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
for (int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 1);
return 0;
}
Tìm MEX của dãy
Nộp bàiPoint: 1
Đề bài: Cho một dãy ~a~ gồm ~n~ phần tử (~1 \leq n \leq 10^5~, ~1 \leq a_i \leq 10^9~). Tìm ~\text{MEX}(a)^\dagger~.
~\dagger~ MEX (minimum excluded integer) của 1 dãy là số nguyên không âm nhỏ nhất không xuất hiện trong dãy đó. Ví dụ: MEX của ~[0;1;4;5]~ là ~2~, MEX của ~[2;0;3;4]~ là ~1~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
int mex (vector<int> &a, int n) {
vector<bool> check(n + 1);
for (int i : a)
if (i <= n) check[i] = 1;
for (int i = 1; i <= n; i++)
if (!check[i]) return i;
return n + 1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> a(n);
for (int &i : a) cin >> i;
cout << mex(a, n);
return 0;
}