基本算法（一）

前缀和

Acwing121

const int maxn = 1000 + 10;
int C, n;

class A {
public:
    int x, y;
} a[maxn];

map<int, int> got;
vector<int> nums;
int sum[maxn][maxn];

// discrete
void discrete() {
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (auto x : nums) got[x] = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

// prework
void prework() {
    _rep(i, 1, n) {
        int x = got[a[i].x], y = got[a[i].y];
        sum[x][y]++;
    }

    _for(i, 1, nums.size()) _for(j, 1, nums.size()) {
        sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
    }
}

// check
inline bool check(int R) {
    for (int x2 = 1, x1 = 0; x2 < nums.size(); x2++) {
        while (nums[x2] - nums[x1+1] + 1 > R) x1++;
        for(int y2 = 1, y1 = 0; y2 < nums.size(); y2++) {
            while (nums[y2] - nums[y1+1] + 1 > R) y1++;
            int cnt = sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
            if (cnt >= C) return true;
        }
    }
    return false;
}

void solve() {
    int l = 1, r = 10000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", r);
}

void init() {
    got.clear();
    nums.clear();
    nums.push_back(0);

    memset(sum, 0, sizeof sum);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    scanf("%d%d", &C, &n);
    _rep(i, 1, n) {
        int x, y;
        scanf("%d%d", &x, &y);
        nums.push_back(x), nums.push_back(y);
        a[i].x = x, a[i].y = y;
    }

    // discrete
    discrete();

    // prework
    prework();

    // check and binary search
    solve();
}

取整函数

取整函数的性质如下

$$\lceil \frac{m}{n} \rceil = \lfloor \frac{m-1}{n}\rfloor + 1$$

等价于鸽巢原理
将 $m$ 个球放入 $n$ 个盒子
存在一个盒子里至少有 $\textbf{ceil}(m/n)$ 个球
存在一个盒子里至多有 $\textbf{floor}(m/n)$ 个球

在算法竞赛中，经常出现的是
对区间 $[l, r]$ 进行 $(\cdots) / k$ 取整操作

下取整 floor
(l+r) / k

上取整 ceil
(l+r-1) / k + 1

特别地，如果是中位数，即 $k=2$

$$\frac{l+r-1}{2} + 1 = \frac{l+r-1+2}{2} = \frac{l+r+1}{2}$$

下取整 floor
(l+r) >> 1;

上取整 ceil
(l+r+1) >> 1;

数的进制转换

Acwing124

int a, b;

void solve(const string& str) {
    vector<int> nums;
    for (auto c : str) {
        if (c <= '9') nums.push_back(c-'0');
        if (c >= 'A' && c <= 'Z') nums.push_back(c-'A' + 10);
        if (c >= 'a' && c <= 'z') nums.push_back(c-'a' + 36);
    }
    reverse(nums.begin(), nums.end());

    vector<int> ans;
    while (nums.size()) {
        int r = 0;
        for (int i = nums.size()-1; i >= 0; i--) {
            nums[i] += r * a;
            r = nums[i] % b;
            nums[i] /= b;
        }
        ans.push_back(r);
        while (nums.size() && nums.back() == 0) nums.pop_back();
    }

    reverse(ans.begin(), ans.end());
    string str_b;
    for (auto c : ans) {
        if (c <= 9) str_b += char(c+'0');
        if (c >= 10 && c <= 35) str_b += char(c - 10 + 'A');
        if (c >= 36 && c <= 61) str_b += char(c - 36 + 'a');
    }

    cout << str_b << endl;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        string str_a;
        cin >> a >> b >> str_a;
        cout << a << " " << str_a << endl;
        cout << b << " ";

        // then solve
        solve(str_a);
        cout << endl;
    }
}

邻项交换求解贪心最优化

Acwing125

贪心问题，扫描法

Acwing127

const int maxn = 100000 + 10;
int n, m;
// m tasks  n machine

class A {
public:
    int x, y;
    bool operator< (const A &rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
} T[maxn], M[maxn];

void solve() {
    sort(T, T+m);
    sort(M, M+n);
    multiset<int> st;

    ll ans = 0;
    ll cnt = 0;
    for (int i = m-1, j = n-1; i >= 0; i--) {
        while (j >= 0 && M[j].x >= T[i].x) st.insert(M[j--].y);
        auto it = lower_bound(st.begin(), st.end(), T[i].y);
        if (it != st.end()) {
            cnt++;
            ans += T[i].x * 500 + T[i].y * 2;
            st.erase(it);
        }
    }
    printf("%lld %lld\n", cnt, ans);
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    scanf("%d%d", &n, &m);
    _for(i, 0, n) scanf("%d%d", &M[i].x, &M[i].y);
    _for(i, 0, m) scanf("%d%d", &T[i].x, &T[i].y);

    // then solve
    solve();
}