Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, x;
    scanf("%d", &n);
    int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
    while (n--) {
        scanf("%d", &x);
        if (x == 1) {
            s1 = s1 + 1;
            s3 = max(s3 + 1, s2 + 1);
        } else {
            s2 = max(s2 + 1, s1 + 1);
            s4 = max(s4 + 1, s3 + 1);
        }
    }
    printf("%d\n", max(s3, s4));
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int main() {
    cin >> n;
    int x = 0, y = 0, t;
    while (n--) {
        cin >> t;
        x = max(x, t);
    }
    cin >> n;
    while (n--) {
        cin >> t;
        y = max(y, t);
    }
    cout << x << ' ' << y << endl;
    return 0;
}

Posted on Edited on In 
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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, k;
int a[N];
bool check(int mid) {
    LL cnt = 0;
    for (int i = n / 2; i < n; ++i)
        if (a[i] < mid)
            cnt += mid - a[i];
    return cnt <= k;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    int l = 0, r = 2e9;
    while (l < r) {
        int mid = (LL) l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", r);
    return 0;
}

Posted on Edited on In 
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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int T, n;
int p[N], s[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) p[i] = i, s[i] = 1;
        for (int i = 1; i <= n; ++i) {
            int j;
            scanf("%d", &j);
            if (find(i) != find(j)) {
                s[find(j)] += s[find(i)];
                p[find(i)] = find(j);
            }
        }
        for (int i = 1; i <= n; ++i)
            printf("%d ", s[find(i)]);
        puts("");
    }
    return 0;
}

Posted on Edited on In 
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
#include <iostream>
#include <string>
using namespace std;
int N;
string S;
int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> S;
        int cnt = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == '1') {
                ++cnt;
            } else {
                int t = cnt;
                cnt = 0;
                if (t == 5) {
                    continue;
                }
            }
            cout << S[i];
        }
        cout << endl;
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int T, n, m;
int main() {
    cin >> T;
    for (int i = 0; i < T; ++i) {
        cin >> n >> m;
        int cnt = 0;
        for (int i = 0; i < n;) {
            ++i;
            if (m % i == 0 && m / i <= n)
                ++cnt;
        }
        cout << cnt << endl;
    }
    return 0;
}

Posted on Edited on In 
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
#include <iostream>
#include <string>
using namespace std;
string s, t, op;
int m, l, r;
int main() {
    cin >> s;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> op;
        if (op == "PASTE") {
            cin >> l;
            s.insert(l + 1, t);
        } else {
            cin >> l >> r;
            if (op == "CUT") {
                t = s.substr(l, r - l + 1);
                s.erase(s.begin() + l, s.begin() + r + 1);
            } else {
                t = s.substr(l, r - l + 1);
            }
        }
        cout << s << endl;
    }
    return 0;
}

Posted on Edited on In 
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
class Trie {
public:
    const int L = 30;
    Trie* children[2] = {};
    int min = INT_MAX;
    void insert(int val) {
        Trie* node = this;
        node->min = std::min(node->min, val);
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit] == nullptr)
                node->children[bit] = new Trie();
            node = node->children[bit];
            node->min = std::min(node->min, val);
        }
    }
    int getMaxXorWithLimit(int val, int limit) {
        Trie* node = this;
        if (node->min > limit)
            return -1;
        int ans = 0;
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->min <= limit) {
                ans |= 1 << i;
                bit ^= 1;
            }
            node = node->children[bit];
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
        Trie* t = new Trie();
        for (int num : nums)
            t->insert(num);
        const int n = queries.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i)
            ans[i] = t->getMaxXorWithLimit(queries[i][0], queries[i][1]);
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        const int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            int num1 = nums1[i - 1];
            for (int j = 1; j <= n; ++j) {
                int num2 = nums2[j - 1];
                if (num1 == num2)
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
};
0%