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

L

lamdetien36

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

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

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

cuong276

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

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


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

Tung code ra đê. Nói suông thế thôi thì chưa đủ thuyết phục đâu .
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

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();
        }
    }

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

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.

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

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á!
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.
 
Top Bottom