Bình luận

• 
  

  0

  

  deanqkhanh  đã bình luận lúc 2, Tháng 1, 2026, 12:25

  Nhận xét 1: Bản chất của phép thuật

  Mỗi lần phép thuật cho phép đổi dấu đồng thời hai ô kề nhau (chung cạnh). Do đó, trong mỗi thao tác:

  • Số lượng phần tử âm thay đổi đúng 0 hoặc ±2
  • ⇒ tính chẵn lẻ của số phần tử âm là bất biến

  Đây là ràng buộc duy nhất của bài toán.

  ---

  Nhận xét 2: Trạng thái “lý tưởng”

  Với mỗi ô có giá trị (x), đóng góp lớn nhất của nó vào tổng là (|x|). Nếu không có ràng buộc nào, tổng lớn nhất có thể đạt được là:

  S = sum(|A_{i,j}|)

  ---

  Nhận xét 3: Khả năng đạt trạng thái lý tưởng

  Xét hai trường hợp:

  🔹 Trường hợp 1: Số phần tử âm ban đầu là chẵn

  Do tính chẵn lẻ là bất biến, ta có thể thực hiện các phép đổi dấu để triệt tiêu toàn bộ số âm. Khi đó, tất cả các ô đều không âm và đạt trạng thái lý tưởng.

  Đáp án = S

  ---

  🔹 Trường hợp 2: Số phần tử âm ban đầu là lẻ

  Khi đó, bắt buộc phải tồn tại ít nhất một ô mang giá trị âm ở trạng thái cuối cùng.

  Giả sử ô này có giá trị (-k) với (k > 0). So với trạng thái lý tưởng (đóng góp (+k)), ô này chỉ đóng góp (-k).

  → Mức suy giảm của tổng là:

  (+k) - (-k) = 2k

  Để tổng cuối cùng là lớn nhất, ta cần giảm thiệt hại này xuống nhỏ nhất, tức là chọn ô có trị tuyệt đối nhỏ nhất.

  Gọi: mn = min(A_{i,j})

  Khi đó: Đáp án = S - 2 * mn

  ---

  Nhận xét 4: Điều kiện “kề nhau” không làm mất tính tổng quát

  Mặc dù mỗi phép thuật chỉ áp dụng cho hai ô kề nhau, nhưng:

  • Bàn cờ là một đồ thị lưới liên thông
  • Có thể “di chuyển” dấu âm qua các ô kề nhau bằng một chuỗi thao tác

  Do đó, ta có thể chọn bất kỳ ô nào để giữ dấu âm, miễn là tôn trọng tính chẵn lẻ.

  ---

  Thuật toán

  1. Duyệt toàn bộ bảng:

     • Tính (S = sum(|A_{i,j}))
     • Đếm số phần tử âm cntNeg
     • Tìm mn = min |A_{i,j}|
  2. Nếu cntNeg chẵn → in S
  3. Ngược lại → in S - 2 * mn

  ---

  Độ phức tạp

  • Thời gian: O(N·M)
  • Bộ nhớ phụ: O(1)

  Phù hợp với ràng buộc (N \cdot M \le 10^6).

  ---

  Code C++ (tham khảo)

  #pragma GCC optimize("Ofast")
  #pragma GCC optimize("unroll-loops")
  #include <bits/stdc++.h>
  using namespace std;
  
  int main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
  
      int n, m;
      cin >> n >> m;
  
      long long S = 0;
      int cntNeg = 0;
      int mn = INT_MAX;
  
      for(int i = 0; i < n; ++i){
          for(int j = 0; j < m; ++j){
              int x;
              cin >> x;
              if(x < 0) cntNeg++;
              S += abs(x);
              mn = min(mn, abs(x));
          }
      }
  
      if(cntNeg % 2 == 0)
          cout << S;
      else
          cout << S - 2LL * mn;
  
      return 0;
  }
  

  ---

  Kết luận

  Bài toán được giải bằng greedy dựa trên việc tối đa hóa tổng trị tuyệt đối, kết hợp với invariant về tính chẵn lẻ của số phần tử âm do mỗi phép đổi dấu tác động lên hai ô kề nhau.

• 
  

  -2

  

  nogo007akapkn  đã bình luận lúc 26, Tháng 10, 2023, 7:35 ← sửa 3 →

  xin ắp vốt