bài toán tạo số lớn nhất:

L

lamdetien36

thienvamai said:
về cơ bản thuật toán là đúng nhưng vẫn cần sửa lại, bạn cần xét trường hợp đầy đủ vì những test sau bạn vẫn sai:
4 1
1102
và
4 1
4321

p.s: thuật toán của mình như sau: có 1 stack s, khi xét tới chữ số a nếu a > đỉnh stack và k>0 thì pop đỉnh stack và giảm k đi 1 lặp lại đến khi nào stack rỗng, hoặc a<=đỉnh stack hoặc k<=0;
đến cuối nếu k>0 thì xóa k phần tử cuối stack
sau đó in các phần tử trong stack ra theo thứ tự cho vào stack
Bấm để xem đầy đủ nội dung ...

Anh có thể VD rõ hơn không ? Em không hiểu rõ về stack.
 
C

cuong276

thienvamai said:
về cơ bản thuật toán là đúng nhưng vẫn cần sửa lại, bạn cần xét trường hợp đầy đủ vì những test sau bạn vẫn sai:
4 1
1102
và
4 1
4321

p.s: thuật toán của mình như sau: có 1 stack s, khi xét tới chữ số a nếu a > đỉnh stack và k>0 thì pop đỉnh stack và giảm k đi 1 lặp lại đến khi nào stack rỗng, hoặc a<=đỉnh stack hoặc k<=0;
đến cuối nếu k>0 thì xóa k phần tử cuối stack
sau đó in các phần tử trong stack ra theo thứ tự cho vào stack
Bấm để xem đầy đủ nội dung ...


Tung code ra đê. Nói suông thế thôi thì chưa đủ thuyết phục đâu .
 
T

thienvamai

ví dụ :
4 2
1102
xét đến phần tử thứ 1:
stack rỗng -> nhét 1 vào stack
xét phần tử thứ 2:
đỉnh stack là 1 =1 -> nhét 1 vào stack
xét phần tử thứ 3:
đỉnh stack là 1 >0 -> nhét 0 vào stack
xét phẩn tử thứ 4:
đỉnh stack là 0 <2 -> xoá 0; k còn 1;
đỉnh stack là 1<2 -> xoá 1, k còn 0;
đỉnh stack là 1<2 nhưng vì k = 0 nên ko xét nữa
đẩy 2 vào stack
giờ stack có 2 phần tử là 1 và 2
in ra 12
 
T

thienvamai

cuong276 said:
Tung code ra đê. Nói suông thế thôi thì chưa đủ thuyết phục đâu .
Bấm để xem đầy đủ nội dung ...
nếu bạn đã nói vậy, dưới đây là code C++ cho bài này , sử dụng cấu trúc dữ liệu deque (stack 2 đầu)
PHP: 
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<climits>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <utility>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>
#include <deque>
#define elif else if
#define nd second
#define st first
using namespace std;
typedef long long int li;
typedef unsigned long long int lu;
typedef pair <li,li> pll;
typedef pair <int,int> pii;
typedef pair <double,double> pdd;
typedef vector<int> vi;
typedef vector <li> vli;
const int N=611963;
char c[N],a[N];
main() {
    deque <int> ans;
    int i,j,l=0;
    int n,k,maxx=0,z;
    scanf("%d%d",&n,&k);
    scanf("%s",c);
    for(i=0; i<n; i++) {
            while(!ans.empty()&&k>0) {
                if(c[i]>ans.back()) {
                    ans.pop_back();
                    k--;
                }
                else break;
            }
            ans.push_back(c[i]);
        }
    while(k>0) {
        k--;
        ans.pop_back();
        }
    while(!ans.empty()) {
        printf("%c",ans.front());
        ans.pop_front();
        }
    }
 
M

myokicrystal

thienvamai said:
nếu bạn đã nói vậy, dưới đây là code C++ cho bài này , sử dụng cấu trúc dữ liệu deque (stack 2 đầu)
PHP: 
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<climits>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <utility>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>
#include <deque>
#define elif else if
#define nd second
#define st first
using namespace std;
typedef long long int li;
typedef unsigned long long int lu;
typedef pair <li,li> pll;
typedef pair <int,int> pii;
typedef pair <double,double> pdd;
typedef vector<int> vi;
typedef vector <li> vli;
const int N=611963;
char c[N],a[N];
main() {
    deque <int> ans;
    int i,j,l=0;
    int n,k,maxx=0,z;
    scanf("%d%d",&n,&k);
    scanf("%s",c);
    for(i=0; i<n; i++) {
            while(!ans.empty()&&k>0) {
                if(c[i]>ans.back()) {
                    ans.pop_back();
                    k--;
                }
                else break;
            }
            ans.push_back(c[i]);
        }
    while(k>0) {
        k--;
        ans.pop_back();
        }
    while(!ans.empty()) {
        printf("%c",ans.front());
        ans.pop_front();
        }
    }
Bấm để xem đầy đủ nội dung ...

dùng c++ dọa người hả thím :v :)|
dùng python đi :v :v
 
M

megamanxza

Nãy giờ thấy các thánh chém code dữ quá (nhất là thím thienvamai) nên cho em hỏi tí: thi Tin học trẻ mà cũng có lập trình C++ nữa hả?
 
M

megamanxza

lamdetien36 said:
Bạn cho mình xin cái test lớn với. Cóp về cho khỏe chứ ngồi tự viết test ra mệt lắm :D.
Bấm để xem đầy đủ nội dung ...

Nếu thím muốn tạo file Number.inp thì em đây mới làm chương trình tạo file đó!
Hây daaaaa! Chỉ trong 1 phút nông nổi, không tự kiềm chế được nên bần tăng đã http://www.mediafire.com/?kvrawawiw8qr5mp
À quên! Máy các bác có nhanh không?

Troll_Face_kindleDX.png


Bài này khá troll, các bác đừng ném đá nhá!
 
Last edited by a moderator:
T

thienvamai

L

lamdetien36

megamanxza said:
Nếu thím muốn tạo file Number.inp thì em đây mới làm chương trình tạo file đó!
Hây daaaaa! Chỉ trong 1 phút nông nổi, không tự kiềm chế được nên bần tăng đã http://www.mediafire.com/?kvrawawiw8qr5mp
À quên! Máy các bác có nhanh không?


Bài này khá troll, các bác đừng ném đá nhá!
Bấm để xem đầy đủ nội dung ...
Random(10) chứ nhỉ.


Mà trong tờ đăng ký của mình có chon NNLT nữa mà. Nó cho chọn Pascal hoặc C :)
 
L

lamdetien36

Nó chỉ ghi là C thôi anh à. Mà với lại đề THT thì dùng C thôi chứ C++ làm gì cho phức tạp.
 
T

thienvamai

C++ bổ sung thiếu sót của C, ko có 2 dấu cộng đằng sau thì C cũng chỉ tương đương với pascal mà thôi.
 
You must log in or register to reply here.
Top Bottom