Archives for Tháng Bảy 2017


Cấu trúc dữ liệu Heap và ứng dụng

Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với Heap là O(logN). CTDL Heap được áp dụng nhiều trong các bài toán tìm đường đi ngắn nhất, tìm phần tử max, min… và trong lập trình thi đấu. Vậy Heap là gì? Cài đặt Heap như thế nào?

Heap là gì?

Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau

  • Một nút có không quá 2 nút con.
  • Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại.

Mặc dù được mô tả như cây nhưng Heap có thể được biểu diễn bằng mảng. Nút con của nút i là 2*i và 2*i+1. Do Heap là cây cân bằng nên độ cao của 1 nút luôn <= logN.

Ứng dụng chủ yếu của Heap là tìm Min, Max trong 1 tập hợp động (có thể thay đổi, thêm, bớt các phần tử) nhưng như vậy đã là quá đủ.

heap-yeulaptrinh

(Mô hình biểu diễn Heap bằng cây nhị phân và bằng mảng)

Các thao tác với Heap

Ở đây mình hướng dẫn các bạn với Heap Max còn với Heap Min thì tương tự

Khai báo

Ở ví dụ này, Heap sẽ là mảng một chiều kiểu LongInt, nHeap là số phần tử của mảng.

Const
  maxn = 100000;
Var
  nHeap : LongInt;
  Heap : array[0..maxn] of LongInt;

1. UpHeap

Nếu 1 nút lớn hơn nút cha của nó thì di chuyển nó lên trên:
upheap-yeulaptrinh

Procedure UpHeap(i : LongInt);
Begin
  if (i = 1) or (Heap[i] < Heap[i div 2]) then exit; // Nếu i là nút gốc hoặc  nhỏ hơn nút cha thì không làm việc
  swap(Heap[i] , Heap[i div 2]); // Đổi chỗ 2 phần tử trong Heap;
  UpHeap(i div 2); // Tiếp tục di chuyển lên trên
end;

2. DownHeap

downheap-1downheap-2

downheap-3

Procedure DownHeap(i : LongInt);
  Var
    j : LongInt;
  Begin
    j := i*2;
    if j > nHeap then exit; // Nếu i không có nút con thì không làm việc
    if (j < nHeap) and (Heap[j] < Heap[j+1]) then Inc(j); // Nếu i có 2 nút con thì chọn nút ưu tiên hơn
    if Heap[i] < Heap[j] then // Nếu nút cha nhỏ hơn nút con
      begin
        swap(Heap[i] , Heap[j]); // Đổi chỗ 2 phần tử trong Heap
        DownHeap(j); // Tiếp tục di chuyển xuống dưới
      end;
  end;

3. Push

Đưa 1 phần tử mới vào Heap: Thêm 1 nút vào cuối Heap và tiến hành UpHeap từ đây:

Procedure Push(x : LongInt);
  Begin
    Inc(nHeap); // Tăng số phần tử của Heap
    Heap[nHeap] := x; // Thêm x vào Heap
    UpHeap(nHeap);
  End;

4. Pop

Rút ra 1 phần tử ở vị trí v trong Heap: Gán Heap[v] := Heap[nHeap] rồi tiến hành chỉnh lại Heap:

Function Pop(v : LongInt) : LongInt;
  Begin
    Pop := Heap[v]; // Lấy phần tử ở vị trí v ra khỏi Heap
    Heap[v] := Heap[nHeap]; // Đưa phần tử ở cuối Heap vào vị trí v
    Dec(nHeap); // Giảm số phần tử của Heap đi 1
    {Chỉnh lại Heap}
    UpHeap(v);
    DownHeap(v);
  End;

Nguồn: không rõ

Tổng hợp đề thi HSGQG môn Tin học các năm

YeuLapTrinh xin được tổng hợp lại đề thi HSGQG các năm để các bạn tiện tham khảo:

 

 

++++++++++++++

(đang tiếp tục cập nhập)

Tạo form trong HTML

FORM được sử dụng để chuyển dữ liệu liệu từ người dùng nhập vào đến web server.
Form bao gồm các thành phần nhập liệu (input elements) như: Text box, hộp kiểm, nút tùy chọn, Submit…
Bài viết này mình sẽ hướng dẫn các bạn một số các thành phần của Form hay được sử dụng nhất. Mình sẽ cố gắng giải thích để mọi người có thể hiểu.
Trong tài liệu HTML form được định nghĩa bằng cặp thẻ <form></form>
Các thẻ nằm giữa cặp thẻ <form></form> được gọi là các thành phần của Form

Các thành phần Form

Thành phần được sử dụng nhiều nhất trong form là thẻ <input />. Ta sử dụng <input /> để định nghĩa các thành phần của form như: Trường nhập liệu Text, các hộp kiểm, các nút tùy chọn, trường password, thành phần submit, các button, File upload.

1. Trường text
User name:

Code:

<input type="text" name="username" size="30" />

2. Trường password
Pass:

Code:

<input name="pass" size="30" type="password" />

3. Checkbox (Hộp kiểm)

Cho phép chọn nhiều thành phần từ danh sách đưa ra

Send my to email
Send my to phone

<input name="opt" type="checkbox" /> Send my to email
<input name="opt" type="checkbox" />Send my to phone

4. Radio button

Khác với checkbox, Radio chỉ phép phép chọn một thành phần từ danh sách đưa ra, các phần tử trong danh sách phải có cùng tên, như ví dụ sau ta
sẽ tạo ra hai thành phần Radio button có cùng tên là name=”gender”

Male
Female

<input type="radio" name="gender" checked /> Male 
<input type="radio" name="gender" /> Female

5. File upload

<input type="file" name="FILE" size="40" />

6. Button

Tạo ra một nút bấm trên form

<input type="button" name="button" value="Click me" />

7. Submit Button

Tạo nút submit trên form. Khi nút Submit được nhấn, dữ liệu trên form sẽ đuợc xử lý và gửi đi

<input type="submit" name="submit" value="Submit" />

8. Reset Button

Tạo nút Reset trên form. Khi nhấn nút Reset dữ liệu nhập vào form sẽ được reset về giá trị ban đầu của form

<input type="reset" name="cancel" value="Reset" />

Ta nhận thấy sự khác biệt giữa các thành phần input là thuộc tính type. Thuộc tính type sẽ quy định thành phần input này là Text, password, checkbox, hay button …

9. Dropdown list

Student
Bussiness
Manager
Other…

<select name="job">
      <option value="Student">Student</option>
      <option value="Bussiness">Bussiness</option>
      <option value="Manager">Manager</option>
      <option value="Other">Other...</option>
</select>

KẾT LUẬN

– Mỗi thành phần form đều được gán một tên (name=”ten_thanh_phan”): đây chính là tên biến được sử dụng trong các ngôn ngữ lập trình web như php hay asp.net…, Riêng thành phần Radio trong cùng một nhóm sẽ được đặt cùng tên.

– Thuộc tính value=”Giá trị”: đây là giá trị (dữ liệu) ban đầu của thành phần form, các thành phần không có thuộc tính value giá có giá trị ban đầu là rỗng (null).

– Các Phương thức hoạt động của form bạn có thể xem ở các bài tiếp thep.

Margin và Padding trong CSS

1. Margin

Khi ta khai báo thuộc tính Margin (canh lề) cho một thành phần nào đó, thì nó sẽ tạo ra một khoảng cách giữa thành phần đó với các thành phần xung quanh nó (top, right, bottom và left). Tạo ra sự phân chia giữa các thành phần trong trang web được thể hiện rõ ràng hơn.

Giá trị của margin

  • auto: tự động canh đều 2 bên left và right, thường được sử dụng để canh giữa màn hình cho toàn bộ trang web.
  • Kích thước (pixels, pt, em . . .)
  • % kích thước của thành phần chứa nó.

Cách khai báo margin

Ví dụ bên dưới sẽ khai báo margin (top, right, left, bottom) cho thành phần <p> có class=”first”
CSS:

p.first{
  margin-top:10px;
  margin-right:10px;
  margin-bottom:15px;
  margin-left:15px;
}

HTML:

<p class="first">
  Đoạn văn bản này cách phía trên 10px, bên trái 15px, bên phải 10px; phía dưới 15px, không có padding
</p>

Kết quả

Đoạn văn bản này cách phía trên 10px, bên trái 15px, bên phải 10px; phía dưới 15px, không có padding

2. Padding

Padding là phần nằm giữa phần hiển thị nội dung và đường viền (border). Khi một thành phần được khai báo padding thì sẽ tạo ra một khoảng trống với dường viền giúp nội dung dễ nhìn hơn.
Giá trị của padding

  • Kích thước (pixels, pt, em . . .)
  • % kích thước của thành phần chứa nó.

Cách khai báo padding

Ví dụ sau khai báo padding cho thành phần <p> có class=”two”

p.two{
  padding-top:2px;
  padding-right: 3px;
  padding-bottom:4px;
  padding-left:5px
}

Đoạn văn bản này có padding-top:5px, padding-bottom:5px, padding-right: 5px, padding-left:5px và không có margin.

Ta thấy giữa đoạn văn bản và đường viền có một khoảng cách là 5px nên dễ nhìn hơn đoạn văn bản thứ nhất, không có padding.

3. Cách viết tắt đối với Margin và Padding

ở các ví dụ trên ta nhận thấy, margin và padding được khai báo cho từng cạnh (top, right, bottom, left) riêng biệt. Để đơn giản hơn chúng ta gộp chung tất cả các cạnh lại, đây chính là cách viết tắt đối với margin và padding.
Giả sử bây giờ ta viết margin cho thành phần p, chúng ta có thể viết đầy đủ như sau:

p{ 
  margin-top: 10px; 
  margin-right: 10px; 
  margin-left: 15px; 
  margin-bottom: 15px
}

Nhưng để đơn giản hơn chúng ta có thể viết như sau:

p { 
  margin: 10px 10px 15px 15px
}

Thứ tự của các cạnh ở cách viết này tuân theo chiều kim đồng hồ bắt dầu từ : top – right – bottom – left.
Tuy nhiên chúng ta có thể không cần phải viết đầy đủ giá trị cho bốn cạnh mà có thể viết 3, hoặc 2, hay thậm chí chỉ một giá trị. Nếu một trong 4 giá trị bị thiếu, thì nó sẽ lấy giá trị của cạnh đối diện.
Ví dụ

p { 
  margin: 10px 10px 7px
}

ở ví dụ này ta thấy bị thiếu một giá trị của cạnh bên trái, do đó nó sẽ lấy giá trị của cạnh bên phải, do đó có giá trị là 10px.

p { 
margin: 10px 5px
}

ở ví dụ này ta thấy thiếu cạnh bên trái và cạnh dưới, do đó cạnh dưới sẽ lấy giá trị của cạnh trên (10px), cạnh bên trái sẽ lấy giá trị của cạnh bên phải (5px).
Trong trường hợp chỉ có một giá trị được khai báo:

p {  
  margin: 5px
}

Thì tất cả các cạnh đều có margin là 5px.
Cách viết tắt cho padding cũng tương tự đối với margin.

10 lời khuyên cho người mới học PHP

PHP là ngôn ngữ đằng sau một số ứng dụng web mạnh mẽ và phổ biến nhất hiện nay, trong đó có thể kể đến Facebook và WordPress.

Học một ngôn ngữ mới có thể khá khó khăn với nhiều người. Bài viết này giới thiệu với bạn đọc một số lời khuyên quý báu của các chuyên gia PHP dành cho người mới bước chân vào thế giới PHP.

1. Elizabeth Naramore: Bắt đầu với OOP

Naramore hiện đang là nhân viên của SourceForge và người sáng lập trang PHPWomen.org. Đối với người vừa mới bắt đầu học PHP, Naramore cho rằng nên có một nền tảng vững chắc trong việc lập trình hướng đối tượng (OOP) trước khi tìm hiểu sâu hơn vào PHP.

“Nếu bạn vốn không xuất thân từ lĩnh vực lập trình, hãy dành thời gian để tìm hiểu nguyên tắc căn bản của phát triển phần mềm. Những vấn đề cần chú ý như lập trình hướng đối tượng (OOP), phát triển hướng kiểm thử (test driven development), quản lí phiên bản (version control), gỡ lỗi (debugging), các mẫu thiết kế (design pattern), vv).

“Nếu bạn đã thử và không thể giải quyết vấn đề của bạn, đừng ngại hỏi. Các cộng đồng PHP nói chung rất hữu ích và thân thiện. Có vô số tài nguyên cho những người mới trên mạng. Nhờ đến sự trợ giúp của cộng đồng, cho dù đó là một nhóm người dùng địa phương, một dự án mã nguồn mở của cộng đồng, hay một kênh IRC như #phpc trên freenode”.

2. Keith Casey: Hãy Google trước khi hỏi

Casey là chủ của một cửa hàng bán phần mềm và là một diễn giả rất có tiếng trong các cuộc hội thảo lớn về PHP.

Lời khuyên của ông nhấn mạnh việc hãy biết mình đang ở đâu trong cộng đồng PHP cùng với một câu châm ngôn đang ngày càng trở nên quan trọng: Google trước khi hỏi.

“Hãy tham gia ngay vào một nhóm người dùng PHP (PHP User’s Group). Có vô số nhóm người dùng PHP ở mọi nơi trên thế giới. Đó là nơi những người thông minh tập hợp để thảo luận, khám phá những ý tưởng, và giúp đỡ lẫn nhau.

“Hãy nhớ thử tìm kiếm trên Google trước khi đặt câu hỏi. Chẳng có ai thích những kẻ lười biếng cả”.

3. Eamon Leonard: Tham gia các dự án mã nguồn mở

Leonard điều hành một công ti phần mềm đặt tại Ireland và là đồng sáng lập CloudSplit, một dịch vụ phân tích thời gian thực cho công nghệ điện toán đám mây. Giống như nhiều đồng nghiệp của mình, ông khuyên rằng hãy cố gắng tham gia các dự án mã nguồn mở ngay cả khi mới bắt đầu học PHP.

“Hãy tham gia vào các dự án mã nguồn mở ngay sau khi bạn nắm bắt được các vấn đề cơ bản… Việc này khiến bạn có thể truy cập vào mã nguồn của các dự án và là một cơ hội rất lớn để học hỏi từ các chuyên gia kì cựu trong ngành”.

“Tìm và lập tài liệu cho các lỗi có thể tái phát sinh là một nhiệm vụ rất tốn thời gian và được đánh giá cao bởi bất kỳ nhóm phát triển mã nguồn mở nào… Khi thuê các nhà phát triển để làm việc với chúng tôi, chúng tôi sẽ dành nhiều sự ưu ái hơn cho những ai đã từng làm việc trên một dự án phần mềm mã nguồn mở”.

4. Lorna Jane Mitchell: Hãy bắt tay vào làm (Just do it)

“Lornajane” là tên gọi phổ biến hơn của Mitchell trên cộng đồng trực tuyến, là một nhà cố vấn, nhà phát triển phần mềm, một tác giả và diễn giả về PHP.

Cô đưa ra một lời khuyên khá nổi tiếng trong giới chuyên môn: Hãy bắt tay vào làm (Just do it).

“Muốn biết bơi thì phải nhảy xuống nước! PHP là một ngôn ngữ rất dễ học. Cách tốt nhất để tìm hiểu xem cái gì đó hoạt động như thế nào là bắt tay vào làm thử.

“Bất cứ ai cũng có thể lập trình PHP. Ít khó khăn khi tham gia có nghĩa là có rất nhiều code PHP tồi trên thế giới. Nhưng những đoạn code PHP tồi mà chạy tốt thì cũng vẫn hữu ích. Cá nhân tôi nghĩ rằng nếu bạn có thể giải quyết vấn đề của bạn với PHP thì cứ mạnh dạn bắt tay vào code ngay cả khi nó chưa hoàn hảo”.

5. Chris Cornutt: Tránh những đoạn code rối rắm

Cornutt điều hành PHPDeveloper.org và Joind.in. Ông đã bắt đầu lập trình PHP từ năm 1998. Trong lời khuyên của ông dành những người mới bắt đầu phát triển PHP, ông cảnh báo về những đoạn code rối rắm.

“Tôi nghĩ rằng những phát triển mới sẽ dễ dàng bị chán nản với những đoạn code rối rắm, đau đầu… Những người mới bắt đầu và có một chút thích thú với ngôn ngữ PHP thường rất hăng hái viết code với tâm lí là chỉ cần code chạy được là được, nhưng tôi dám chắc rằng hơn một nửa trong số họ sẽ bỏ cuộc”.

“Hãy thử tìm một người cố vấn có thể hướng dẫn bạn một số bước đi ban đầu. Bạn sẽ cảm nhận được một sự khác biệt rất lớn khi bạn có một người nào đó để bàn luận. IRC là một lựa chọn tốt, nhưng một người để có thể gặp mặt để học hỏi sẽ tốt hơn rất nhiều.

Thường họ có rất nhiều các trang web với vô số các đoạn code và các ví dụ PHP đã giúp họ vượt qua những tình huống khó khăn. Một số ví dụ rất hay, một số không có ích nhiều lắm nhưng hãy học chúng một cách dần dần. Phát triển PHP cũng giống như bất cứ điều gì khác, là một kỹ năng mà cần phải được mài giũa – bạn không thể nhảy bụp vào và trở thành một chuyên gia sau một đêm được”.

6. Abraham Williams: Học Drupal

Williams là một nhà phát triển và tự gọi mình là một “người ủng hộ các hacker” (hacker advocate). Ông cũng khuyên những người mới lập trình PHP nên tham gia vào các dự án lập trình mã nguồn mở.

“Tìm một dự án hoặc cộng đồng chất lượng (tốt nhất là các dự án phát triển theo định hướng mã nguồn mở) để đóng góp vào. Tìm hiểu về các đoạn mã, con người và văn hóa riêng của dự án đó. Bạn sẽ học hỏi được từ các nhà phát triển có kinh nghiệm, niềm đam mê với những đoạn code chất lượng cùng với một cộng đồng thân thiện. Những người mới sẽ nhận được nhiều hơn từ việc đề xuất các đoạn code cải tiến trong các bản vá và thậm chí từ việc làm thế nào để là một thành viên cộng đồng tốt hơn”.

“Tôi cho rằng các dự án Drupal là một điểm khởi đầu tốt. Đó là một cộng đồng trưởng thành và hùng hậu, có tốc độ tăng trưởng mạnh mẽ. Ngoài ra, có rất nhiều cơ hội việc làm đối với các nhà phát triển Drupal giỏi”.

7. Demian Turner: Học hỏi từ các coder nhiều kinh nghiệm

Turner đã làm việc với các web và các dự án mã nguồn mở từ năm 1996. Ông điều hành PHPKitchen.com và gần đây là một trong những người lọt vào chung kết cuộc thi doanh nhân khởi nghiệp Seedcamp.

Ông đã đưa ra một lời khuyên vô cùng quý báu cho những người mới phát triển PHP để tiết kiệm thời gian, cải thiện các đoạn code tốt hơn và giúp duy trì được sự yêu thích viết code.

“Đọc các code của các nhà phát triển dày dạn kinh nghiệm. Đó luôn là những cách tốt hơn, sáng sủa hơn để giải quyết các vấn đề bạn gặp phải. Đừng phát minh lại bánh xe, bạn sẽ luôn có thừa các công cụ, thư viện sẵn có để lập trình. Hãy sử dụng các thư viện có uy tín bất cứ khi nào bạn có thể thay vì tự viết code từ đầu”.

“Đảm bảo rằng code của bạn thật dễ hiểu. Nếu chính bạn cũng không thể hiểu được code mà bạn viết ra sau sáu tháng sau thì làm sao các nhà phát triển khác có thể hiểu nổi?”.

“Luôn cố gắng đơn giản hóa các đoạn code. Sẽ vất vả hơn để viết các đoạn code đơn giản hơn nhưng một cấu trúc code nhất quán sẽ giúp bạn tiết kiệm rất nhiều thời gian và công sức hơn khi phải bảo trì”.

“Cuối cùng, tìm hiểu về một số các lập trình viên xuất sắc và cách làm thế nào họ giữ được niềm đam mê về nghệ thuật lập trình trong nhiều năm như vậy”.

8. Stuart Herbert:

Tìm hiểu về phát triển hướng kiểm thử (test-driven development), tính đóng gói (encapsulation) và quản lí mã nguồn (source control)

Herbert đã bắt đầu code PHP kể từ năm 1999. Ông đã viết về PHP trong nhiều năm và đã đóng góp rất nhiều cho Gentoo Linux.

Đối với những người phát triển PHP, ông khuyên “Hãy tìm hiểu về việc phát triển hướng thử nghiệm và đóng gói. Một khi hiểu về nó, bạn sẽ viết code nhanh hơn. Và bất cứ ai phát triển kế thừa từ những đoạn code của bạn sẽ cảm ơn bạn rất nhiều”.

“Tìm hiểu về việc quản lí mã nguồn chưa bao giờ được xem nhẹ”.

Ông cũng nói rằng sức mạnh lớn nhất của ngôn ngữ PHP là bộ tài liệu tuyệt vời và hoàn toàn miễn phí tại PHP.net. Với một số ngôn ngữ khác, có thể bạn sẽ cần phải đi ra ngoài và mua các tài liệu như sách ngoại trừ với PHP”.

9. Maggie Nelson: Tìm hiểu về lưu trữ dữ liệu (data storage)

Nelson là một nhà phát triển PHP hiện đang làm việc cho Flickr.

Cô nói rằng những người mới học PHP nên bắt đầu học về lưu trữ dữ liệu ngay từ khi mới bắt đầu.

“Hầu như bạn sẽ sử dụng PHP cho các ứng dụng web. Các ứng dụng web nổi trội là những ứng dụng web sử dụng dữ liệu theo những cách không bình thường để giải quyết những vấn đề bình thường. Nếu bạn chỉ vừa bắt đầu với PHP và đây là ngôn ngữ lập trình đầu tiên của bạn, hãy dành một hoặc hai ngày để đọc về lưu trữ dữ liệu và một chút về SQL. PHP được biết đến là hoạt động rất tốt với các cơ sở dữ liệu. Hãy thử tìm hiểu về MySQL, các cơ sở dữ liệu quan hệ khác và một vài giải pháp lưu trữ NoSQL”.

“Hãy tự viết code cho ít nhất một ứng dụng mà không dùng bất cứ thư viện hay framework hỗ trợ nào. Thế giới PHP cung cấp rất nhiều các framework tuyệt vời và có thể dễ dàng trừu tượng hóa (abstract) việc truy cập dữ liệu, nhưng hãy luôn đảm bảo rằng bạn thực sự hiểu dữ liệu thực sự được thao tác ra sao đằng sau hậu trường!”.

10. Michael Maclean: Tìm hiểu về bảo mật

Maclean là một nhà phát triển PHP và Python tại Outer Hebrides, Scotland.

Ông nói: “Khá dễ dàng để có thể hiểu và code PHP, đó là lí do tại sao rất nhiều người sử dụng nó, nhưng tôi nghĩ điều quan trọng là phải xem trên thực tế mọi người đang dùng nó như thế nào. Thay vì viết tất cả mọi thứ từ đầu, hãy tìm hiểu một vài framework. Việc này sẽ giúp bạn có một điểm xuất phát thuận lợi hơn.

“Ngoài ra nên học thêm về bảo mật. Trong quá khứ, PHP đã bị nhiều chỉ trích về vấn đề này. Đó là mặt trái của tính dễ sử dụng của PHP. Có nhiều nguồn sách vở và tài nguyên trên mạng trình bày về cách tránh đối phó với các vấn đề bảo mật. Hãy tìm đọc những cuốn sách và thông tin trên mạng về chủ đề bảo mật của các tác giả Chris Shiflett và Ilia Alshanetsky”.

P171SUMB – ptit

Đề bài:

Thuật toán:

  • Gọi \(cnt[i]\) là số các số chia mod k = i trong tập \(S\).
  • Theo đề bài ta có: \(KQ = KQ + max(cnt[i], cnt[k-i])\) với \(i=1..k/2\).
    • Chú ý nếu n mod 2 = 0 thì ta không cộng \(cnt[n/2]\) vào KQ mà chỉ cộng 1 thôi.

Code:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int n, k, i, j, a[200004], cnt[500], ans;
int main() {
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) {
        a[i] = a[i] % k;
        ++cnt[a[i]];
    }
    for (int i=1; i<=k/2; i++) {
        ans = ans + max(cnt[i], cnt[k-i]);
    }
    if (k%2 == 0) {
        ans -= cnt[k/2];
        if (cnt[k/2]>0) ans++;
    }
    if (cnt[0] > 0) ans++;
    cout << ans;
	return 0;
}

P171SUMD – ptit

Đề bài:

Thuật toán:

  • Ưu tiên di chuyển hàng trước nếu m < n và ngược lại.
  • Sử dụng thuật toán tham lam trừ từng hàng và từng từng cột.

Code:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 200;
const int oo = 1000;
int m, n, i, j, g[MAXN][MAXN], kt, mi, tam, dadoi;
vector<int> H, C;
 
void xulyhang() {
    for (int i=1; i<=m; i++) {
        mi = oo;
        for (int j=1; j<=n; j++) mi = min(mi, g[i][j]);
        for (int j=1; j<=mi; j++) H.push_back(i);
        for (int j=1; j<=n; j++) g[i][j]-=mi;
    }
}
 
void xulycot() {
    for (int j=1; j<=n; j++) {
        mi = oo;
        for (int i=1; i<=m; i++) mi = min(mi, g[i][j]);
        for (int i=1; i<=mi; i++) C.push_back(j);
        for (int i=1; i<=m; i++) g[i][j]-=mi;
    }
}
 
int main() {
    cin >> m >> n;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++) cin >> g[i][j];
    kt = 1;
    if (m < n) {
        xulyhang();
        xulycot();
    }
    else {
        xulycot();
        xulyhang();
    }
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
        if (g[i][j]!=0) kt = 0;
    if (kt==0) cout << -1;
    else {
            cout << C.size()+H.size() << endl;
            for (int i=0; i<H.size(); i++) cout << "H " << H[i] << endl;
            for (int i=0; i<C.size(); i++) cout << "C " << C[i] << endl;
    }
	return 0;
}