Codeforces #256 Div.2

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;
}
上一篇:20145338 《Java程序设计》第1周学习总结


下一篇:Presto 学习