[POI 2012] BON-Vouchers

考慮從倍數出發，如果值域是 \(m\)，\(mH(m)\)，是 \(O(m \ln)\) 的。

那么本題是否可以直接做？答案是不行，對于一個倍數 \(k\)，之前 \(k\) 的倍數取到的數可能再次枚舉到，無法拿走（不計入貢獻），因此復雜度是不對的。

我們只需要去除 \(k\) 枚舉之前 \(k\) 取到的數即可，這樣對于對于 \(k\) 最多枚舉 \(\lfloor m/k \rfloor\) 次。

具體實現是記錄一下上一個同樣的 \(k\) 枚舉到幾倍了。

[POI 2012] HUR-Warehouse Store

沒什么好說的，貪心直接做完。

[POI 2005] SUM-Fibonacci Sums

好題。

考慮如果沒有同一位 \(a,b\) 都是 \(1\) 是好處理的。

于是我們考慮如何處理加完之后是 \(2\)。

首先考慮如果是 \(2\)，如何變換使得至少這一位不是 \(2\)，我們設 \(now\) 為當前和串。容易發現 \(now_{i} -2 \to now_{i},now_{i-2} +1 \to now_{i-2},now_{i+1}+1 \to now_{i+1}\) 是一種方法。

同時，這可能導致 \(3\) 的產生，先不管。

對于一個 \(2\) 的處理，我們有兩種選擇，一種是讓左邊繼續合法，不管右邊，反之為另一種。應該選擇后者，因為 \(now_{i+1}\) 會加一，如果從 \(i\) 到最右邊都不存在能夠進位的數，可以直接作用且不會使右邊產生 \(2\)。

現在確定目標，我們希望從右到左，調整使得全體合法，現在開始討論。

• 若 \(now_{i}\) 為 \(0\)，\(i\) 減一下一位。

• 若 \(now_{i}\) 為 \(1\)，將 \(i\) 及后進位（可以證明不會產生 \(2\)）。

• 若 \(now_{i}\) 為 \(2\)，若 \(now_{i+1}\) 為 \(1\)，對 \(i\) 及后進位（可以證明不會產生 \(2\)）。否則對 \(i\) 作用變換后對 \(i+1\) 及后進位。

• 若 \(now_{i}\) 為 \(3\)，若 \(now_{i+1}\) 為 \(1\)，對 \(i\) 及后進位，然后轉化為 \(now_{i}=2\) 的第二種情況。否則對 \(i\) 作用變換后對 \(i+1\) 及后進位，之后轉化為情況 \(now_{i}=1\)。

OK！做完了，為了方便我們可以尋找這些討論的共通性，若 \(now_{i},now_{i+1}\) 其中一個為 \(0\)，那么 \(i\) 進位操作不會影響任何東西。我們現在處理完了 \(1,2.1\) 情況，考慮 \(2.2,3.1,3.2\) 情況，特點是仍然 \(now_{i} \le 2\)，之后做共通的操作，也就是對 \(i\) 作用變換后對 \(i+1\) 后進位，此時 \(3.2\) 還需要一個 \(i\) 及后進位。總結：

• 對 \(i\) 及后進位。

• 若 \(now_{i} \le 2\)，對 \(i\) 作用變換后對 \(i+1\) 后進位。

• 對 \(i\) 及后進位。

注意 \(i<3\) 要特判。

// Problem: P3424 [POI 2005] SUM-Fibonacci Sums
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3424
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 1e6 + 10;
int now[N];
int n;
void flush(int x) {
    while (now[x] && now[x + 1]) now[x]--, now[x + 1]--, now[x + 2]++, x += 2;
}
void solve() {
    int x;
    cin >> x;
    n = x;
    upp(i, 1, x) cin >> now[i];
    cin >> x;
    n = max(n, x);
    upp(i, 1, x) {
        int c;
        cin >> c;
        now[i] += c;
    }
    dww(i, n, 1) {
        flush(i);
        if (now[i] >= 2) {
            now[i] -= 2, now[i + 1]++;
            if (i >= 2) now[max(i - 2, (int)1)]++;
            flush(i + 1);
        }
        flush(i);
    }
    dww(i, n + 2, 1) if (now[i]) {
        cout << (n = i) << ' ';
        break;
    }
    upp(i, 1, n) cout << now[i] << ' ';
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int tt = 1;
    while (tt--) solve();
    return 0;
}

[POI 2007] BIU-Offices

求補圖的連通塊個數。

先講一個并查集不動腦子的做法，考慮用并查集維護連通塊個數，原圖中連一條邊 \((x,y)\) 相當于將 \(x\) 要連的邊，其中一段隔開分成兩段。所以我們最多會處理 \(O(n+m)\) 次，形如合并 \(x\) 和 \([l,r]\) 這段區間里面的所有點的操作。最后查詢有多少個點祖先是自己。這個是萌萌噠。可以 \(O(n\log n + m)\) 的做（忽略反阿克曼函數）。

考慮遍歷補圖，那么是 \(O(n^2)\) 的。但是這個圖太完全了，肯定有很多的邊沒有用。

考慮如果在樸圖里，\(x,y\) 已經屬于同一個連通塊，那么 \((x,y)\) 的邊就是沒有用的，我們實在是不應該遍歷到。

我們可以建立一個表，表示目前沒有進入連通塊的點，對于所有 \(x\) 連接到的點，打上標記，那么所有表中沒有標記的點就會加入連通塊，最后清理標記。

至于這個表要支持隨機刪除，順序遍歷。無疑是鏈表了。

對于一條邊，讓一個點在一輪被遍歷一次，打一次標記，所以總復雜度是 \(O(m)\) 的。

每個點最多刪一次，清理一次標記，所以總復雜度是 \(O(n)\) 的。

時間復雜度 \(O(n+m)\)。

具體實現可以使用隊列。

[POI 2007] MEG-Megalopolis

樹上查詢到 \(1\) 點路徑上的邊權和，改變一條邊的權值。

轉化一下，查詢一個點的點權，將一棵子樹里每個點的點權加一。

變成 dfn 序之后區間修改單點查詢即可。

[POI 2008] POD-Subdivision of Kingdom

注意到 \(26\choose 13\) 大約是 1e7 的。直接搜索第一個集合的點，搜索的同時記錄邊的數量，可以 \(n/2\) 的記錄。這個時候發現只能記錄第一個集合里面的。沒關系，我們將選的點的狀態存起來，下次如果遇到搜到的集合是這個集合的補集的時候在合并信息記錄答案就行了。時間復雜度 \(O({n\choose n/2}n)\)。

[POI 2009] KON-Ticket Inspector

考慮分段 DP，然后從大到小枚舉 \(j\)，同時更新轉移代價即可 \(O(n^2k)\)。