SEARCH1 - Tìm kiếm nhị phân 1
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho hai dãy số nguyên ~a_1, a_2, …, a_n~ và ~b_1, b_2, …, b_m~ trong đó dãy số ~a_1, a_2, …, a_n~ đã được sắp xếp không giảm (tức là ~a_1 ≤ a_2 ≤ … ≤ a_n~). Với mỗi chỉ số ~i~ ~(1 ≤ i ≤ m)~ hãy tìm sự xuất hiện của ~b_i~ trong dãy ~a_1, a_2, …, a_n~.
Input
- Dòng đầu ghi hai số nguyên dương ~n~ và ~m~;
- Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, …, a_n~;
- Dòng thứ ba ghi ~m~ số nguyên ~b_1, b_2, …, b_m~.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Giới hạn:
- ~1 ≤ n, m ≤ 10^5; |a_i|, |b_i| ≤ 10^9~.
Output
- Một xâu nhị phân độ dài ~m~, trong đó ký tự thứ ~i~ ~(1 ≤ i ≤ m)~ là
1nếu ~b_i~ có xuất hiện trong dãy ~a_1, a_2, …, a_n~, và là0nếu ngược lại.
Sample
Input #1
7 5
1 2 3 4 4 6 7
3 1 5 4 8
Output #1
11010
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
using namespace std; int b[100002]; int n,m; int main(){ cin>>n>>m; set<int> s1; for(int i=0; i<n; i++){ int x; cin>>x; s1.insert(x); } for(int i=0; i<m; i++){ cin>>b[i]; } for(int i=0; i<m; i++){ set<int>::iterator it = s1.find(b[i]); if(it != s1.end()){ cout<<1; }else{ cout<<0; } } return 0; }
include <bits/stdc++.h>
using namespace std; int b[100002]; int n,m; int main(){ cin>>n>>m; set<int> s1; for(int i=0; i<n; i++){ int x; cin>>x; s1.insert(x); } for(int i=0; i<m; i++){ cin>>b[i]; } for(int i=0; i<m; i++){ set<int>::iterator it = s1.find(b[i]); if(it != s1.end()){ cout<<1; }else{ cout<<0; } } return 0; }
include <bits/stdc++.h>
using namespace std; long long a[10000000],b[10000000],n,m,i; int main() { cin>> n>>m; for (i=0;i<n;i++) cin>> a[i]; for (i=0;i<m;i++) cin>> b[i]; sort(a,a+n); for (i=0;i<m;i++) { cout << bool(binary_search(a,a+n,b[i])); } } code này nhanh và acp hết nha
include <iostream>
include <vector>
include <algorithm>
using namespace std;
int main() { int n, m; cin >> n >> m;
// Đọc dãy số a vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; }
// Đọc dãy số b vector<int> b(m); for (int i = 0; i < m; ++i) { cin >> b[i]; }
// Sắp xếp dãy số a sort(a.begin(), a.end());
// Tìm kiếm sự xuất hiện của các số trong dãy a và xuất kết quả for (int i = 0; i < m; ++i) { if (binary_search(a.begin(), a.end(), b[i])) { cout << "1"; } else { cout << "0"; } }
return 0; }
include<stdio.h>
void NhiPhan01 (int a[], int n, int b[], int m) { for (int i = 0; i < m; i++) { int found = 0; for (int j = 0; j < n; j++) { if (b[i] == a[j]) { found = 1; break; } } printf("%d", found); } } void NhapMang (int a[], int n) { for (int i=0; i<n; i++) { scanf("%d",&a[i]); } }
int main(int argc, const char * argv[]){ int n,m; scanf("%d%d",&n,&m); int a[n],b[m]; NhapMang(a, n); NhapMang(b, m); for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { if (a[i]==a[j]) { for (int k=j+1; k<n; k++) { a[k-1]=a[k]; } n--; j--; } } } NhiPhan01(a, n, b, m); return 0; } //Em bị out time ở test case 4 ạ. Mọi người cho em hỏi cách tối ưu đoạn code này của em với ạ. Em cũng đã tham khảo qua ChatGPT nhưng không được. Em cảm ơn mọi người.
chatgpt ngu lam :))
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
nó gửi link gì mak mn downvote nó nhiều tek?