thảo luận [Học Tập] Topic thuật toán

[Ai rồi cũng sẽ khát]

#include <stdio.h>
#include <stdbool.h>
void main() {
    int number = 0;
    int count = 0;
    int max_length = 0;
    bool isChanged = false;
    printf("Nhap so dang thap phann");
    scanf("%d", &number);
    if (number == 0) {
        max_length = 1;
    }
    while (number != 0) {
        if (number % 2 == 1) {
            count++;   // bit 1
        } else {
            if (isChanged) {
                // 2 bit 0 lien tiep thi reset counting
                isChanged = false;
                if (max_length < count) {
                    max_length = count;
                }
                count = 0;
            } else {
                // Bit 0 dau tien, lat bit
                isChanged = true;
                count++;
            }
        }
        number = number >> 1;
    }
    if (max_length < count) {
        max_length = count;
    }
    printf("Max = %d\n", max_length);
}

TEST:
1831935: 110111111001111111111 => 11
28623: 110111111001111 => 9

 

[hadata]

#include <stdio.h>
#include <stdbool.h>
void main() {
int number = 0;
int count = 0;
int max_length = 0;
bool isChanged = false;
printf("Nhap so dang thap phann");
scanf("%d", &number);
if (number == 0) {
max_length = 1;
}
while (number != 0) {
if (number % 2 == 1) {
count++; // bit 1
} else {
if (isChanged) {
// 2 bit 0 lien tiep thi reset counting
isChanged = false;
if (max_length < count) {
max_length = count;
}
count = 0;
} else {
// Bit 0 dau tien, lat bit
isChanged = true;
count++;
}
}
number = number >> 1;
}
if (max_length < count) {
max_length = count;
}
printf("Max = %d\n", max_length);
}

TEST:
1831935: 110111111001111111111 => 11
28623: 110111111001111 => 9

Em học cho biết giải thuật mà bác làm như này thì chết em rồi.

 

[Ai rồi cũng sẽ khát]

Em học cho biết giải thuật mà bác làm như này thì chết em rồi.

Su dung chia lay du "%" de test bit ben phai ngoai cung la bit 0 hay 1
Neu la bit 1 thi count ++
Neu la bit 0:
- Neu la bit 0 dau tien gap thi lat bit, count ++
- Neu la bit 0 lan thu 2 thi ko lat bit nua, ma reset count, neu count ma lon hon max thi update

 

[T.Dark]

Su dung chia lay du "%" de test bit ben phai ngoai cung la bit 0 hay 1
Neu la bit 1 thi count ++
Neu la bit 0:
- Neu la bit 0 dau tien gap thi lat bit, count ++
- Neu la bit 0 lan thu 2 thi ko lat bit nua, ma reset count, neu count ma lon hon max thi update

Sai đề bài rồi fen, thớt yêu cầu là lật 1 bit để tạo ra dãy 1 bit dài nhất có thể, không phải tìm dãy bit 1 dài nhất

 

[qkhanhpro]

Bác rảnh không giải thích giùm em với ạ. Ngu quá.

https://dotnetfiddle.net/WQAslu

using System;

namespace Flip1
{
    public class Program
    {
        static int max = 0;
        static int temp = 0;
        static bool flip = false;
        static int recent = 0; // Nhóm 1s gần nhất

        public static void Main()
        {

            var input = new int[] { 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
            foreach (var x in input)
            {
                Console.WriteLine(String.Format("Temp: {0} , Max: {1}, RecentGroup: {2}",temp,max,recent));
                if (x == 1)
                {
                    temp += 1;
                    CompareAndAssign();
                    recent += 1;
                }
                else
                {
                    if (!flip)
                    {
                        flip = true;
                        recent = 0;
                        temp += 1;
                        CompareAndAssign();
                    }
                    else
                    {
                        flip = false;
                        temp = recent + 1;
                        recent = 0;
                        CompareAndAssign();
                    }
                }
            };
            Console.WriteLine(String.Format("Finally Temp: {0} , Max: {1}, RecentGroup: {2}",temp,max,recent));
        }

        public static void CompareAndAssign()
        {
            if (temp >= max)
            {
                max = temp;
            }
        }
    }
}

Đây nhé bạn
Duyệt

Thấy 1 ? Cộng thêm vào Temp. So sánh với Max
Thấy 0 ?
=> Chưa lật cờ ? lật cờ, cộng thêm vào Temp. So sánh với Max
=> Đã lật cờ (chốt kết quả nhóm cũ) ? trả cờ, lấy temp = nhóm 1s trướt khi chốt. đi tiếp

 

[Ai rồi cũng sẽ khát]

Sai đề bài rồi fen, thớt yêu cầu là lật 1 bit để tạo ra dãy 1 bit dài nhất có thể, không phải tìm dãy bit 1 dài nhất

Khi gap bit 0 dau tien thi count++
Khi gap bit 1 sau bit 0 do thi cout van ++ ma. Chi reset khi gap bit 0 thu 2 thoi
Vi du: 10111 thi count = 5; dung nhu de bai yeu cau

 

[hadata]

Em cám ơn, các bác nhiệt tình quá. Nhân tiện cho em hỏi làm nhúng thì nên học phần nào của C ạ?

 

[hadata]

Khi gap bit 0 dau tien thi count++
Khi gap bit 1 sau bit 0 do thi cout van ++ ma. Chi reset khi gap bit 0 thu 2 thoi
Vi du: 10111 thi count = 5; dung nhu de bai yeu cau

Trường hơp 1110011 chưa đúng bác ạ, ra kết quả = 3.

 

[hadata]

https://dotnetfiddle.net/WQAslu



Đây nhé bạn
Duyệt

Thấy 1 ? Cộng thêm vào Temp. So sánh với Max
Thấy 0 ?
=> Chưa lật cờ ? lật cờ, cộng thêm vào Temp. So sánh với Max
=> Đã lật cờ (chốt kết quả nhóm cũ) ? trả cờ, lấy temp = nhóm 1s trướt khi chốt. đi tiếp

Để em thử code lại = C ạ.

 

[22mario9x]

def get_max(val):
    """
    """
    compareVal = 1
    bitOneCount = 0
    currentMax = 0
    isMeetZero = False

    while compareVal < val:
        if compareVal & val == compareVal:
            bitOneCount += 1
        else:
            if isMeetZero:
                if currentMax < bitOneCount:
                    currentMax = bitOneCount
                    bitOneCount = 0
                isMeetZero = False
            else:
                if bitOneCount != 0:
                    isMeetZero = True

        compareVal = compareVal << 1

    if currentMax < bitOneCount:
        currentMax = bitOneCount

    return currentMax + 1


print(get_max(1775))

Không biết có sai chổ nào k

 

[luiz]

Bài này giải thuật O(n) thôi
Bước 1: khai váo mảng mới để lưu trữ phần tử 0 và số lượng phần tử 1 liên tiếp, lần đầu duyệt cả mảng, gặp phần tử 0 thì push vào mảng mới, gặp 1 thì đếm chuỗi liên tiếp rồi mới push độ dài chuỗi vào mảng mới
Bước 2: duyệt mảng mới tạo, từ đầu đến cuối, tính tổng 3 số liên tiếp rồi lấy max 3 số liên tiếp của mảng, kết quả trả ra là max + 1

 

[luiz]

Bài này giải thuật O(n) thôi
Bước 1: khai váo mảng mới để lưu trữ phần tử 0 và số lượng phần tử 1 liên tiếp, lần đầu duyệt cả mảng, gặp phần tử 0 thì push vào mảng mới, gặp 1 thì đếm chuỗi liên tiếp rồi mới push độ dài chuỗi vào mảng mới
Bước 2: duyệt mảng mới tạo, từ đầu đến cuối, tính tổng 3 số liên tiếp rồi lấy max 3 số liên tiếp của mảng, kết quả trả ra là max + 1

Thớt cứ làm theo cách này yên tâm là k sót case nào cả, bước 2 có thể tối ưu chút nhưng cũng k giảm đáng kể đâu

 

[Pianist]

Bài này giải thuật O(n) thôi
Bước 1: khai váo mảng mới để lưu trữ phần tử 0 và số lượng phần tử 1 liên tiếp, lần đầu duyệt cả mảng, gặp phần tử 0 thì push vào mảng mới, gặp 1 thì đếm chuỗi liên tiếp rồi mới push độ dài chuỗi vào mảng mới
Bước 2: duyệt mảng mới tạo, từ đầu đến cuối, tính tổng 3 số liên tiếp rồi lấy max 3 số liên tiếp của mảng, kết quả trả ra là max + 1

Lằng nhằng vl, nghĩ lắm mệt não Cứ vét cạn như này:
Đổi số N kia ra mảng bit 0/1. Int64 cũng chỉ tầm 18 số, gọi độ dài là L đi.

for i từ 0 -> L. Nếu gặp bit i = 0. thì vét về 2 phía đếm số bit 1 liên tục. Kết quả ở vị trí này là trái + phải + 1.
Nhìn là 2 vòng lặp lồng nhau. Nhưng tổng độ phức tạp ko quá 2L.
Dễ hiểu dễ viết vcl

 

[hehehe000]

em bế tắc với bài này quá các bác, các bác giúp em thuật toán làm bài này như thế nào với ạ

 

[nipevt]

em bế tắc với bài này quá các bác, các bác giúp em thuật toán làm bài này như thế nào với ạ

View attachment 244345

dùng std::map, map đếm số lần xuất hiện của một phần tử, rồi chạy 2 vòng tính k = X - a_i - a_j, rồi cộng kết quả với map[k].

hoặc: sort mảng tăng dần, chạy 2 vòng for i, j, tính k = X - a_i - a_j, rồi áp dụng chặt nhị phân để tính số lần xuất hiện của phần tử k.


mấy cái này đưa lên VNOI hỏi chứ trên này ít ai rep lắm.

 

[hehehe000]

dùng std::map, map đếm số lần xuất hiện của một phần tử, rồi chạy 2 vòng tính k = X - a_i - a_j, rồi cộng kết quả với map[k].

hoặc: sort mảng tăng dần, chạy 2 vòng for i, j, tính k = X - a_i - a_j, rồi áp dụng chặt nhị phân để tính số lần xuất hiện của phần tử k.

chặt nhị phân xong bị quá thời gian bác ơi :<

 

[nipevt]

chặt nhị phân xong bị quá thời gian bác ơi :<

vây thì thay vì chặt nhị phân thì dùng interpolation search để giảm đpt xuống O(n^2). giữ một biến t chạy ngược từ n, với một k = X - a_i - a_j thì chạy ngược t từ n về để tính ra được số lần xuất hiện của k cần tim.

 

[hehehe000]

vây thì thay vì chặt nhị phân thì dùng interpolation search để giảm đpt xuống O(n^2). giữ một biến t chạy ngược từ n, với một k = X - a_i - a_j thì chạy ngược t từ n về để tính ra được số lần xuất hiện của k cần tim.

cái này chắc là chạy đc đó bác, để em thử

 

[SoftwareEngineer]

Bài này dùng 3 pointers để giải được không nhỉ? i chạy từ 0 đến cuối, lúc chạy sẽ tạo ra thêm 2 biến là left = i + 1 và right = length() - 1 rồi bắt đầu tính sum.

Time chắc là O(n^2)

 

[Pianist]

1. Dùng cốc cốc k muốn giúp
2. Đề output sai ví dụ.