小花生

study & life record.

12月上旬算法题集

发表于 分类于 ，

12 月上旬算法题集。

First One

HDU - 5358

For each i, merge those j’s such that $[\log_2S(i, j)]$ get the same value. At most $\log_2(n·1e5)$ values will $[\log_2S(i, j)]$ have.

By using Prefix Sum and Binary Search, we can find those j’s in $O(log(n))$ .

The total time complexity is $O(n\log_2(n·1e5)log(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int lg(int x){
    if(x == 0) return 0;
    return 63 - __builtin_clzll(x);
} 

void solve(){
    int n = read(), res = 0;
    vector<int>v(n + 1, 0);
    for(int i = 1; i <= n; i++){
        v[i] = v[i - 1] + read();
    }
    
    for(int i = 1; i <= n; i++){
        int ll = i - 1;
        for(int k = lg(v[i] - v[i - 1]); k <= lg(v[n]); k++){
            int l = ll, r = n + 1;
            while(l + 1 != r){
                int mid = l + r >> 1;
                if(v[mid] - v[i - 1] < (1ll << (k + 1))) l = mid;
                else r = mid;
            }
            res += (k + 1) * (i * (l - ll) + (ll + l + 1) * (l - ll) / 2);
            ll = l;
        }
    }
    cout << res << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

Trapped in the Witch’s Labyrinth

Codeforces Round 989 div1+2 C

Let’s consider those cells that can definitely escape：there must be a path leading to the border.

Thus, we can use a DFS in a reversed way, starting from points on the border(artificially added), recursively finding all cells that can escape from the boundary points.

Don’t forget, if a unspecified cell is surrounded by four points that can escape, it will exit too.

It’s easy to prove that, there is always a way to make the remaining cells being trapped forever：
Two cells：point to each other. More cells：point to the two cells.

Implementation：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000;
vector<vector<char>>mp(N + 2, vector<char>(N + 2));
vector<vector<int>>vis(N + 2, vector<int>(N + 2, 0));

int cnt, n, m;
void dfs(int x, int y) {
    vis[x][y] = 1;
    if (x == 0) {
        if (mp[x + 1][y] == 'U' && !vis[x + 1][y]) dfs(x + 1, y);
    }
    else if (x == n + 1) {
        if (mp[x - 1][y] == 'D' && !vis[x - 1][y]) dfs(x - 1, y);
    }
    else if (y == 0) {
        if (mp[x][y + 1] == 'L' && !vis[x][y + 1]) dfs(x, y + 1);
    }
    else if (y == m + 1) {
        if (mp[x][y - 1] == 'R' && !vis[x][y - 1]) dfs(x, y - 1);
    }
    else {
        cnt++;
        if (mp[x + 1][y] == 'U' && !vis[x + 1][y]) dfs(x + 1, y);
        if (mp[x - 1][y] == 'D' && !vis[x - 1][y]) dfs(x - 1, y);
        if (mp[x][y + 1] == 'L' && !vis[x][y + 1]) dfs(x, y + 1);
        if (mp[x][y - 1] == 'R' && !vis[x][y - 1]) dfs(x, y - 1);
    }
}

void solve() {
    cnt = 0;
    cin >> n >> m;
    
    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= m + 1; j++){
            mp[i][j] = '0';
            vis[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            vis[i][j] = 0;
        }
    }

    for (int j = 1; j <= m; j++) {
        dfs(0, j), dfs(n + 1, j);
    }

    for (int i = 1; i <= n; i++) {
        dfs(i, 0), dfs(i, m + 1);
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '?' && vis[i - 1][j] && vis[i + 1][j] && vis[i][j - 1] && vis[i][j + 1])
                vis[i][j] = 1, cnt++;
        }
    }
    cout << n * m - cnt << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

Darius’ Wisdom

Codeforces Round 989 div1+2 D

Construction problem.

We can easily find the final condition of the array. Then do the following steps:

  1. Put every 0 in its right position. Since 1 always exsits, by using 1, it takes at most 2count(0) steps.
  2. The rest of array only contains 1 and 2. To sort this part of array, we need at most min(count(1), count(2)) steps.

2count(0) + min(count(1), count(2)) is certainly too much, we need to lower it to less than n.

Assume we have count(0) <= count(2)（0 and 2 are equivalent, if not satisfied, just exchange 0 and 2 is ok）

Through mathematical calculations 2count(0) + min(count(1), count(2)) <= count(0) + max(count(1), count(2)) + min(count(1) + count(2)) = count(0) + count(1) + count(2) = n

Implementation：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve() {
    int n = read(); 
    int x = 0, y = 0, z = 0, pos;
    vector<int>v(n + 1);
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        if(v[i] == 0) x++;
        if(v[i] == 1) y++, pos = i;
        if(v[i] == 2) z++;
    }
    int cnt = 0;
    vector<PII>res;
    
    if(x <= z){
        for(int i = 1, j = x + 1;;){
            while(i <= x && v[i] == 0){
                i++;
            }
            while(j <= n && v[j] != 0){
                j++;
            }
            if(i > x || j > n) break;
            if(v[i] == 1){
                cnt++;
                swap(v[i], v[j]);
                res.emplace_back(i, j);
                pos = j; 
            }
            else if(v[i] == 2){
                cnt += 2;
                swap(v[i], v[pos]);
                swap(v[i], v[j]);
                res.emplace_back(i, pos);
                res.emplace_back(i, j);
                pos = j;
            }
        }
        for(int i = x + 1, j = x + y + 1;;){
            while(i <= x + y && v[i] == 1){
                i++;
            }
            while(j <= n && v[j] == 2){
                j++;
            }
            if(i > x + y || j > n) break;
            cnt++;
            swap(v[i], v[j]);
            res.emplace_back(i, j);
        }
    }
    else{
        for(int i = x + y + 1, j = 1;;){
            while(i <= n && v[i] == 2){
                i++;
            }
            while(j <= x + y && v[j] != 2){
                j++;
            }
            if(i > n || j > x + y) break;
            if(v[i] == 1){
                cnt++;
                swap(v[i], v[j]);
                res.emplace_back(i, j);
                pos = j; 
            }
            else if(v[i] == 0){
                cnt += 2;
                swap(v[i], v[pos]);
                swap(v[i], v[j]);
                res.emplace_back(i, pos);
                res.emplace_back(i, j);
                pos = j;
            }
        }
        for(int i = x + 1, j = 1;;){
            while(i <= x + y && v[i] == 1){
                i++;
            }
            while(j <= x && v[j] == 0){
                j++;
            }
            if(i > x + y || j > x) break;
            cnt++;
            swap(v[i], v[j]);
            res.emplace_back(i, j);
        }
    }
    cout << cnt << '\n';
    for(auto &u : res){
        cout << u.first << ' ' << u.second << '\n';
    }
}

signed main() {
    int t = read();
    while (t--) solve();
    return 0;
}

Recommendations

Educational Codeforces Round 172 (div.2) D

For each segment, we need to find the minimum l and the maximum r of its predictor.

The first round, sort the segments in l ascending , r descending order. Using Binary Search to find the min{r} of one’s predictors. Then add its r into the set. In this way, we can always find the min{r} of each segment.

The second round, sort the segments in r descending, l ascending order. With similar handling method, we can find the max{l} of each segment.

Pay attention to the situation that serveral segments are exactly the same: we need to help the first handled segment to change its max{l} and min{r} to l and r of its own.

Implementation：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<int>l(n), r(n);
    for(int i = 0; i < n; i++){
        l[i] = read(), r[i] = read();
    }
    vector<int> L(n, -1), R(n, -1);
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    
    {
        sort(p.begin(), p.end(), [&](int i, int j){
            if(l[i] != l[j]) return l[i] < l[j];
            return r[i] > r[j];
        });
        
        set<int> s;
        for(int j = 0; j < n; j++){
            int i = p[j];
            auto it = s.lower_bound(r[i]);
            if(it != s.end()){
                R[i] = *it;
            }
            if(j + 1 < n && l[i] == l[p[j + 1]] && r[i] == r[p[j + 1]]){
                R[i] = r[i];
            }
            s.emplace(r[i]);
        }
    }
    
    {
        sort(p.begin(), p.end(), [&](int i, int j){
            if(r[i] != r[j]) return r[i] > r[j];
            return l[i] < l[j];
        });
        
        set<int> s;
        for(int j = 0; j < n; j++){
            int i = p[j];
            auto it = s.upper_bound(l[i]);
            if(it != s.begin()){
                L[i] = *prev(it);
            }
            if(j + 1 < n && l[i] == l[p[j + 1]] && r[i] == r[p[j + 1]]){
                L[i] = l[i];
            }
            s.emplace(l[i]);
        }
    }
    
    for(int i = 0; i < n; i++){
        if(L[i] == -1){
            cout << 0 << '\n';
        }
        else{
            cout << (R[i] - L[i]) - (r[i] - l[i]) << '\n'; 
        }
    }
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

Move Back at a Cost

Codeforces Round 990 div1 B (div2 D)

Ascending array (call it stk) should be saved.

The rest elements (call it b) should be put back in ascending order, and when the tail of stk is smaller then the head of b, it should also join b and finally be put in the back of array.

Implementation：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<int>a(n);
    for(auto &i : a) i = read();
    
    vector<int>stk, b;
    for(int i = 0; i < n; i++){
        while(!stk.empty() && stk.back() > a[i]){
            b.emplace_back(stk.back() + 1);
            stk.pop_back();
        }
        stk.emplace_back(a[i]);
    }
    sort(b.begin(), b.end());
    
    while(!b.empty() && stk.back() > b[0]){
        b.emplace_back(stk.back() + 1);
        stk.pop_back();
    }
    sort(b.begin(), b.end());
    
    a = stk;
    for(auto &i : b) a.emplace_back(i);
    for(int i = 0; i < n; i ++){
        cout << a[i] << " \n"[i == n - 1];
    }
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

Expansion Packs

Atcoder ABC 382 E

dp[i] means the probability to get i rare cards in one pack. Not difficult to update dp[i] by the given probabilities. (Refering the implementation)

f[x] means the expected number to get x rare cards.

If i <= 0 , f[i] = 0. The recurrence formula:
$$
f[x]=\sum_{i=0}^ndp[i]\times(1+f[x-i])
$$
That is:
$$
f[x]=\frac{1+\sum_{i=1}^ndp[i]\times f[x-i]}{1-dp[0]}
$$
Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n, x; cin >> n >> x;
    vector<double>dp(n + 1, 0); dp[0] = 1;
    for(int i = 0; i < n; i++){
        int q; cin >> q;
        double p = 0.01 * q;
        for(int j = i; j >= 0; j--){
            dp[j + 1] += dp[j] * p;
            dp[j] *= 1 - p;
        }
    }
    double s = 1 - dp[0];
      vector<double> f(x + 1);
      for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= n; j++) {
               f[i] += f[max(i - j, 0)] * dp[j];
        }
        f[i] += 1;
          f[i] /= 1 - dp[0];
    }
      cout << fixed << setprecision(17) << f[x] << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}

9 Divisors

Atcoder ABC 383 D

$9=(1+8)=(1+2)*(1+2)$

It means if a number has 9 divisors, it can be expressed by $p_1^8$ or $p_1^2p_2^2$

($p_i$ is a random prime number)

Init all the satisfied number and use binary search to get the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int MX = 4e12;
const int N = 2e6+5;
int primes[N], cnt;
bool comp[N];
vector<int>v;

void Euler(int n){
    for(int i = 2; i <= n; i++){
        if(!comp[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            comp[i * primes[j]] = 1;
            if(!(i % primes[j])) break;
        }
    }
}

void init(){
    Euler(2000000);
    for(int i = 2; i < 40; i++){
        if(comp[i]) continue;
        int u = i * i * i * i * i * i * i * i;
        if(u <= MX){
            v.emplace_back(u);
            //cout << u << '\n';
        }
    }
    for(int i = 0; i < cnt; i++){
        if(primes[i] > 2000) break;
        for(int j = i + 1; j < cnt; j++){
            int u = primes[i] * primes[i] * primes[j] * primes[j];
            if(u > MX) break;
            v.emplace_back(u);
            //cout << u << '\n';
        }
    }
    sort(v.begin(), v.end());
}

void solve(){
    int n = read();
    cout << upper_bound(v.begin(), v.end(), n) - v.begin();
}

signed main(){
    init(); 
    solve();
    return 0;
}

阿兔与种树

牛客 - 浙江机电职业技术大学第九届程序设计竞赛 J

每次修改在原序列 s 上放入一个等差数列 1, 2, ... , n。

不妨考察其差分形式 1, 1, ... , 1, -n

依然不方便整体修改，继续考察差分数列的差分 1, 0, ..., 0, -n - 1, n

这样，每次修改时在该二维差分上操作即可。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

signed main(){
    int n = read(), m = read();
    vector<int>dd(n + 3, 0), d(n + 3, 0), s(n + 3, 0);
    for(int i = 0; i < m; i++){
        int l = read(), r = read();
        dd[l]++;
        dd[r + 1] -= r - l + 2;
        dd[r + 2] += r - l + 1;
    }
    for(int i = 1; i <= n; i++){
        d[i] = d[i - 1] + dd[i];
    }
    for(int i = 1; i <= n; i++){
        s[i] = s[i - 1] + d[i];
    }
    for(int i = 1; i <= n; i++){
        cout << s[i] << ' ';
    }
    return 0;
}