Đội Thiện Hữu tổ chức kỳ thi thử lần thứ hai trong chương trình đào tạo hè năm 2023:
Đa số các bài đều là đề đã làm qua, nhưng tôi chỉ giải được 320 điểm (buồn quá)
Bài 1: Bảng xếp hạng Bài cơ bản, giải ngay lập tức
#include <bits/stdc++.h>
using namespace std;
string ket_qua[105], ten[105], loai[105];
int da_gan[105];
int main(){
int n;
cin >> n;
memset(da_gan,0,sizeof da_gan);
for(int i = 1;i <= n;i++){
cin >> ten[i] >> loai[i];
if(loai[i]=="CUNG"){
ket_qua[i] = ten[i];
da_gan[i]=1;
}
}
for(int i = 1;i <= n;i++){
if(loai[i]=="XUONG"){
for(int j = 1;j <= i-1;j++){
if(!da_gan[j]){
ket_qua[j] = ten[i];
da_gan[j]=1;
break;
}
}
}
}
for(int i = n;i >= 1;i--){
if(loai[i]=="LEN"){
for(int j = n;j >= i+1;j--){
if(!da_gan[j]){
da_gan[j]=1;
ket_qua[j] = ten[i];
break;
}
}
}
}
for(int i = 1;i <= n;i++){
cout << ket_qua[i] << "\n";
}
return 0;
}
Bài 2: Ăn kem của Thiện Bài đơn giản, giải ngay lập tức
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,a,b,c;
ll so1[100005], so2[100005], so3[200005], ket_qua[200005];
bool cmp(ll x, ll y){
return x>y;
}
int main(){
cin >>n>>m>>a>>b>>c;
for(ll i = 1;i <=a;i++){
scanf("%lld",&so1[i]);
}
for(ll i = 1;i <=b;i++){
scanf("%lld",&so2[i]);
}
for(ll i = 1;i <= c;i++){
scanf("%lld",&so3[i]);
}
sort(so1+1,so1+a+1,cmp);
sort(so2+1,so2+b+1,cmp);
sort(so3+1,so3+c+1,cmp);
for(ll i=1;i<=n;i++){
ket_qua[i]=so1[i];
}
for(ll i=1;i<=m;i++){
ket_qua[i+n]=so2[i];
}
sort(ket_qua+1,ket_qua+n+m+1);
for(ll i =1;i<=min(c,n+m);i++){
if(so3[i]>=ket_qua[i]) ket_qua[i]=so3[i];
}
ll tong=0;
for(ll i = 1;i <= n+m;i++){
tong+=ket_qua[i];
}
cout<<tong;
return 0;
}
Bài 3: Thay thế chữ cái Bài tham lam cơ bản nhưng chọn sai chiến lược, bị lỗi 20 điểm
#include <bits/stdc++.h>
using namespace std;
int n,m;
string s, chuoi;
int main(){
cin >>n>> m;
cin >> chuoi;
int min_kq = 1e9;
for(char c='a';c<='z';c++){
int vt = -1;
int dem=0;
string t = chuoi + c;
for(int i = 0 ;i < t.size();i++){
if(i==0 && t[i] == c){
vt=i;
}else if(t[i]==c && i - vt >1){
vt=i;
dem++;
}else if(i-vt > m){
vt=i;
dem++;
}
}
min_kq=min(min_kq,dem);
}
cout << min_kq;
return 0;
}
Bài 4: Zeze ở Brazil Sửa rất lâu, gần như mất phương hướng trong thi đấu, sau khi thi xong mới phát hiện thiếu nhân đôi tốc độ cửa lưới, cần đọc đề cẩn thận. Mặc dù sửa lại được 70 điểm nhưng vẫn cần kiểm tra kỹ lưỡng.
#include<bits/stdc++.h>
using namespace std;
int dx, dy, n, m;
int zx[305], zy[305];
double kc[305][305];
int lx[305], ly[305];
bool kiem_tra(int x,int y,int z){
double a =sqrt((zx[x]-zx[y])*(zx[x]-zx[y]) +(zy[x]-zy[y])*(zy[x]-zy[y]));
double b =sqrt((zx[x]-lx[z])*(zx[x]-lx[z]) +(zy[x]-ly[z])*(zy[x]-ly[z]));
double c =sqrt((zx[y]-lx[z])*(zx[y]-lx[z]) +(zy[y]-ly[z])*(zy[y]-ly[z]));
if(abs(a-b-c) > 1e-4) return true;
return false;
}
int main(){
cin >> dx >> dy >> n >>m;
for(int i = 1;i <= n;i++){
cin >> zx[i] >> zy[i];
}
for(int i = 1;i <= m;i++){
cin >> lx[i] >> ly[i];
}
memset(kc,0x3f,sizeof kc);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
for(int k = 1;k <= m;k++){
if(i==j) continue;
if(kiem_tra(i,j,k)){
// có thể tạo cạnh
kc[i][j]=sqrt((zx[i]-zx[j])*(zx[i]-zx[j])+(zy[i]-zy[j])*(zy[i]-zy[j]));
kc[j][i]=sqrt((zx[i]-zx[j])*(zx[i]-zx[j])+(zy[i]-zy[j])*(zy[i]-zy[j]));
}
}
}
}
for(int i=1;i<=n;i++){
kc[i][n+1] = sqrt((dx-zx[i])*(dx-zx[i])+(dy-zy[i])*(dy-zy[i]));
}
for(int k =1;k <= n+1;k++){
for(int i = 1;i <= n+1;i++){
if(i == k) continue;
for(int j = 1;j <= n+1;j++){
if(j == i || j == k) continue;
kc[i][j] = min(kc[i][j],kc[i][k]+kc[k][j]);
}
}
}
printf("%.0lf",kc[1][n+1]);
return 0;
}
Bài 5: Thành phố quan trọng Độ phức tạp O(n^4), dùng Floyd, giải ngay lập tức
#include <bits/stdc++.h>
using namespace std;
int n,m;
int u,v,w;
int khoang_cach[205][205];
int ket_qua[205], dem;
int ids[205][205];
int da_kiem[205][205];
int main(){
cin >>n >>m;
memset(khoang_cach,0x3f,sizeof khoang_cach);
memset(ids,0x3f,sizeof ids);
memset(da_kiem,0x3f,sizeof da_kiem);
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
khoang_cach[u][v]=w;
ids[u][v]=w;
khoang_cach[v][u]=w;
ids[v][u]=w;
da_kiem[v][u]=w;
da_kiem[u][v]=w;
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
if(k==i)continue;
for(int j = 1;j <= n;j++){
if(j==i||j==k)continue;
khoang_cach[i][j]=min(khoang_cach[i][j],khoang_cach[i][k]+khoang_cach[k][j]);
}
}
}
for(int x = 1 ; x <= n;x++){
for(int i = 1;i <= n;i++){
for(int j =1;j <= n;j++){
ids[i][j]=da_kiem[i][j];
}
}
for(int k = 1;k <= n;k++){
if(k==x)continue;
for(int i = 1;i <= n;i++){
if(i==x)continue;
if(k==i)continue;
for(int j = 1;j <= n;j++){
if(j==x)continue;
if(j==i||j==k)continue;
ids[i][j]=min(ids[i][j],ids[i][k]+ids[k][j]);
}
}
}
int flag=0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(i==j||i==x||j==x) continue;
if(ids[i][j] > khoang_cach[i][j]) flag=1;
}
}
if(flag){
ket_qua[++dem] = x;
}
}
if(dem==0) cout<<"Không có thành phố quan trọng.";
else for(int i = 1;i <= dem;i++){
cout << ket_qua[i] << " ";
}
return 0;
}
Bài 6: Vì bài 4 chưa sửa xong, không muốn viết tiếp. Lúc đó rất mệt mỏi, chỉ muốn ngồi nhìn màn hình và sửa.