Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký
Thảo luận
Khu vực thảo luận

Solution contest #3 csloj

Nguyễn Hoàng Sơn 2022-01-02 5:44:34 2022-01-02 6:38:09

[A] PHOTO - Chụp ảnh

Submit: http://csloj.ddns.net/problem/1020

Hits:
- Mỗi học sinh chỉ đổi chỗ nhiều nhất 1 lần
- Có 5 bức ảnh chụp

Solution

  • Vì mỗi học sinh chỉ đổi chỗ nhiều nhất 1 lần nên khi xét 2 học sinh bất kỳ thì chỉ có nhiều nhất 2 bức ảnh sẽ có cách xếp khác với cách xếp cô giáo mong muốn
  • Từ đây khi xét 2 học sinh ta muốn biết học sinh nào đứng bên trái, bên phải ta chỉ cần tìm cách xếp có xuất hiện trong ít nhất 3 bức ảnh
  • Ta có thể dùng thuật toán sắp xếp học sinh trong O(n*log(n)*log(n))
  • Để giảm độ phức tạp ta có thể đánh số lại học sinh để thuật trở thành O(n*log(n))

Code

//Hoang Son WIBU lolicon codeforces rate 1704 khong cay
#include <bits/stdc++.h>
#define F first
#define S second
#define times double stime = clock();
#define gettime cout << "\nTime executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
const ll mod = 1000000007;
const double epsilon = 1e-8;
//1000000007 998244353
bool debug_on = false, debug_test = false;

int n;
int a[6][100005], soa[100005], idex[6][100005];
int b[100005];
map<int, int> id;
int revid[100005];
void process(){
  int tcase = 1;
  //cin >> tcase;
  for(int ttcase = 1; ttcase <= tcase; ttcase++){
    cin >> n;
    for(int i = 1; i<=5; i++){
      for(int j = 1; j<=n; j++){
        cin >> a[i][j];
        soa[j] = a[i][j];
      }
      if(i == 1){
        sort(soa + 1, soa + n + 1);
        id.clear(); int cnt = 0;
        for(int j = 1; j<=n; j++){
          id[soa[j]] = ++cnt;
          revid[cnt] = soa[j];
        }
      }
      for(int j = 1; j<=n; j++){
        a[i][j] = id[a[i][j]];
        idex[i][a[i][j]] = j;
      }
    }
    for(int j = 1; j<=n; j++){
      b[j] = a[1][j];
    }
    sort(b + 1, b + n + 1, [](int &ax, int &bx){
      int l = 0;
      for(int i = 1; i<=5; i++){
        if(idex[i][ax] < idex[i][bx]) l++;
      }
      return (l >= 3);
    });
    for(int j = 1; j<=n; j++) cout << revid[b[j]] << " ";
    //cout << "\n";
  }
}

int online = 2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (online == 0) {
        freopen("in.inp", "r", stdin);
        freopen("out.out", "w", stdout);
    } else if (online == 1) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    //times
    process();
    //gettime
    return 0;
}

[B] TRACTOR - Máy kéo

Hits:
- Phạm vi cỏ khô 1...1000
- Anh ta chỉ có thể di chuyển theo bốn hướng (đông, tây, nam, bắc)
- Chiếc máy kéo không thể đi lên vị trí có bó cỏ khô
- Di chuyển quãng đường theo một hướng luôn là số nguyên

Solution

  • Ta nhận thấy rằng xe máy kéo sẽ không phải dọn đống cỏ trong bất kỳ trường nào khi máy kéo đó nằm ngoài phạm vi 1...1000
  • Từ đây là có thể dùng thuật toán tìm đường đi ngắn nhất (với trọng số tăng khi đi qua một đống cỏ) để tìm cách đi qua số đống cỏ ít nhất mà vẫn có thể ra được ngoài với độ phức tạp O(10^6*log(10^6) + n) chạy all test trong 591 ms
  • Ta có thể nhận thấy rằng, ta không cần dùng đến cấu trúc heap để tìm đường ngắn nhất, ta chỉ cần gỡ bỏ từng lớp bao quanh máy kéo cho tới khi không cần gỡ bỏ lớp ngoai nào mà vẫn có thể đi ra ngoài phạm vi và độ phức chỉ còn O(10^6 + n) chạy all test trong 94 ms, test lâu nhất mất 19ms

Code

//Hoang Son WIBU lolicon codeforces rate 1704 khong cay
#include <bits/stdc++.h>
#define F first
#define S second
#define times double stime = clock();
#define gettime cout << "\nTime executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
const ll mod = 1000000007;
const double epsilon = 1e-8;
//1000000007 998244353
bool debug_on = false, debug_test = false;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n;
pii poscar;
bool pos[1005][1005], okpos[1005][1005];
queue<pii> q[2];
void process(){
  int tcase = 1;
  //cin >> tcase;
  for(int ttcase = 1; ttcase <= tcase; ttcase++){
    cin >> n >> poscar.F >> poscar.S;
    for(int i = 1, x, y; i<=n; i++){
      cin >> x >> y;
      pos[x][y] = true;
    }
    int res = 165;
    int id = 0, cnt = 0;
    q[0].push(poscar);
    bool ok = false;
    while(!ok){
      while(!q[id].empty()){
        pii u = q[id].front(); q[id].pop();
        for(int c = 0; c<4; c++){
          pii nu = u;
          nu.F += dx[c];
          nu.S += dy[c];
          if(okpos[nu.F][nu.S] == false){
            okpos[nu.F][nu.S] = true;
            if(nu.F >= 1 && nu.F <= 1000 && nu.S >= 1 && nu.S <= 1000){
              if(!pos[nu.F][nu.S]) q[id].push(nu);
              else q[id^1].push(nu);
            } else {
              ok = true;
              break;
            }
          }
        }
        if(ok) break;
      }
      if(ok){
        res = cnt;
        break;
      }
      cnt++; id^=1;
    }
    cout << res;
  }
}

int online = 2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (online == 0) {
        freopen("in.inp", "r", stdin);
        freopen("out.out", "w", stdout);
    } else if (online == 1) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    //times
    process();
    //gettime
    return 0;
}

[C] ESCAPE - Chạy trốn

Hits:
- Một phép cộng có nhớ (trong cơ số ) đàn bò sẽ bỏ cuộc nên thứ tự chọn bò không quan trọng

Solution

  • Vì thứ tự chọn không quan trọng nên ta có thể thử mọi cách chọn, với mỗi cách chọn ta for qua từng số, với mỗi số ta for từng chữ số với độ phức tạp O(8 * n * 2^n) chạy all test trong 246ms
  • Ta có thể nhận thấy rằng, việc for qua từng số là không cần thiết khi ta có thể quy hoạch động để lưu lại giá trị trước đó, độ phức tạp còn O(8 * 2^n) chạy all test trong 40ms

Code

//Hoang Son WIBU lolicon codeforces rate 1704 khong cay
#include <bits/stdc++.h>
#define F first
#define S second
#define times double stime = clock();
#define gettime cout << "\nTime executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
const ll mod = 1000000007;
const double epsilon = 1e-8;
//1000000007 998244353
bool debug_on = false, debug_test = false;

int n;
int w[25];
bool ff[1 << 20];
int sumg[1 << 20];
void process(){
  int tcase = 1;
  //cin >> tcase;
  for(int ttcase = 1; ttcase <= tcase; ttcase++){
    cin >> n;
    for(int i = 1; i<=n; i++) cin >> w[i];
    int res = 1;
    ff[0] = true;
    sumg[0] = 0;
    for(int mask = 1; mask < (1 << n); mask++){
      int posrr = __builtin_ctz(mask) + 1;
      int sum = sumg[mask ^ (1 << (posrr - 1))];
      bool ok = ff[mask ^ (1 << (posrr - 1))];
      if(ok == true){
        int sumbe = sum, wbe = w[posrr];
        while(sumbe > 0 && wbe > 0){
          if((sumbe%10) + (wbe%10) > 9){
            ok = false;
            break;
          }
          sumbe /= 10;
          wbe /= 10;
        }
        sumg[mask] = sum + w[posrr];
        ff[mask] = ok;
        if(ok) res = max(res, __builtin_popcount(mask));
      }
    }
    cout << res;
  }
}

int online = 2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (online == 0) {
        freopen("in.inp", "r", stdin);
        freopen("out.out", "w", stdout);
    } else if (online == 1) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    //times
    process();
    //gettime
    return 0;
}

Tổng cộng 2 trả lời

Trương Tuấn Tú
2022-01-02 8:55:51

A viết solution contest 1, 2 nữa được không ạ ...

Trương Tuấn Tú
2022-01-02 8:55:22

Hay quá anh !

Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS