首页 > 代码库 > Codeforces #256 Div.2

Codeforces #256 Div.2

2024-07-13 08:59:27   225人阅读

B. Suffix Structure

1. 先判断s去掉一些元素是否能构成t，如果可以就是automaton

判断的方法也很简单，two pointer，相同元素同时++，不相同s的指针++，如果t能全找到，那么s能够去掉元素构成t。

bool f(string s, string t) {    int i = 0, j = 0;    while (i < s.size() && j < t.size()) {        if (s[i] == t[j]) {            i++;            j++;        } else {            i++;        }    }    if (j == t.size()) return true;    else return false;}

2. 对s和t排序，如果s和t相等，那么就是array

3. 如果s和t排序之后还是不相等，但是s可以通过去掉一些元素构成t，那么就是both

4. 否则，就是need tree

 

C. Painting Fence

 

 

D. Multiplication Table

矩阵，第(i, j)格子中是i*j，求在矩阵中的第k大数。

通过二分答案来实现，假设第k个数的值为val，我们可以发现对于矩阵来说，每一行也都是有序的，所以我们用O(min(m,n))的遍历可以找到所有行(列)中，小于等于val的数之和。

具体对于第 r 行来说，这一行小于等于val值的数量为min(val/r, 列的个数).

那么二分的具体过程如下：

int64 lo = 1, hi = n*m;while (lo <= hi) {    int64 md = lo + (hi-lo)/2;    if (f(md) < k) lo = md+1;    else hi = md-1;}cout << lo << endl;

进行判断的方法：

int64 f(int64 k) {    int64 r, w;    if (n < m) {r = n; w = m;}    else {r = m; w = n;}    int64 cnt = 0;    for (int64 i = 1; i <= r; i++) {        cnt += min(k / i, w);    }    return cnt;}


联系
我们