Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int l, int r) {
        for (int i = l; i <= r; ++i) {
            bool ans = false;
            for (const auto& x : ranges)
                if (x[0] <= i && i <= x[1]) {
                    ans = true;
                    break;
                }
            if (!ans)
                return ans;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        int n = ranges.size(), s = 0;
        int diff[52] = {0};
        for (auto &r : ranges) ++diff[r[0]], --diff[r[1] + 1];
        for (int i = 1; i < left; ++i) s += diff[i];
        for (int i = left; i <= right; ++i)
            if ((s += diff[i]) == 0)
                return false;
        return true;
    }
};

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 100010;
int n, w[N];
LL tr[N], f[N];
vector<int> xs;
int get(int x) {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
}
int lowbit(int x) {
    return x & -x;
}
void add(int i, LL v) {
    for (; i <= n; i += lowbit(i))
        tr[i] = max(tr[i], v);
}
LL query(int i) {
    LL res = 0;
    for (; i; i -= lowbit(i))
        res = max(res, tr[i]);
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &w[i]);
        xs.push_back(w[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        int k = get(w[i]);
        f[i] = query(k) + w[i];
        ans = max(ans, f[i]);
        add(k + 1, f[i]);
    }
    printf("%lld\n", ans);
    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
#include <iostream>
using namespace std;
const int N = 1000000;
int T;
int n, k;
int a[N];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 0 ; i < n; ++i) scanf("%d", &a[i]);
        int ans = n;
        for (int i = 1; i <= 100; ++i) {
            int cnt = 0;
            for (int j = 0; j < n;)
                if (a[j] != i) {
                    ++cnt;
                    j += k;
                } else {
                    ++j;
                }
            ans = min(ans, cnt);
        }   
        printf("%d\n", ans);
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>
using namespace std;
int T;
int n, m, r, c;
int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m >> r >> c;
        cout << max({r + c - 2, n - r + c - 1, r + m - c - 1, n - r + m - c}) << 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
class Solution {
public:
    int numSquares(int n) {
        if (n < 2) return n;
        vector<int> v;
        for (int x = 1; x * x <= n; ++x)
            v.emplace_back(x * x);
        if (v.back() == n) return 1;
        queue<int> q;
        vector<bool> visited(n);
        for (auto x : v) {
            q.push(x);
            visited[x] = true;
        }
        int steps = 1;
        while (!q.empty()) {
            ++steps;
            int size = q.size();
            while (size--) {
                int x = q.front(); q.pop();
                for (auto y : v) {
                    int next = x + y;
                    if (next == n) {
                        return steps;
                    } else if (next < n && !visited[next]) {
                        q.push(next);
                        visited[next] = true;
                    } else if (next > n) {
                        break;
                    }
                }
            }
        }
        return 0;
    }
};
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
class Solution {
public:
    int numSquares(int n) {
        vector<int> v;
        int t = 1;
        while (t * t <= n) {
            v.emplace_back(t * t);
            ++t;
        }
        int m = v.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, n));
        f[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            int x = v[i - 1];
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * x <= j; ++k) {
                    if (f[i - 1][j - k * x] != n) {
                        f[i][j] = min(f[i][j], f[i - 1][j - k * x] + k);
                    }
                }
            }
        }
        return f[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        f[0] = 0;
        for (int t = 1; t * t <= n; ++t) {
            int x = t * t;
            for (int j = x; j <= n; ++j)
                f[j] = min(f[j], f[j - x] + 1);
        }
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isPerfectSquare(int n) {
        int x = sqrt(n);
        return x * x == n;
    }
    bool checkAnswer4(int n) {
        while (n % 4 == 0)
            n /= 4;
        return n % 8 == 7;
    }
    int numSquares(int n) {
        if (isPerfectSquare(n)) return 1;
        if (checkAnswer4(n)) return 4;
        for (int i = 1; i * i <= n; ++i)
            if (isPerfectSquare(n - i * i))
                return 2;
        return 3;
    }
}; // Lagrange's Four-Square Theorem

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
#include <iostream>
#include <algorithm>
using namespace std;
int n, k, p, x, y;
int main() {
    cin >> n >> k >> p >> x >> y;
    int sum = 0;
    vector<int> a(k);
    for (int i = 0; i < k; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    x -= sum;
    if (x < n - k) cout << -1;
    else {
        sort(a.begin(), a.end());
        int mid = lower_bound(a.begin(), a.end(), y) - a.begin();
        int s1 = min(n / 2 - mid, n - k);
        int s2 = n - s1 - k;
        if (s1 + s2 * y > x || (s2 && y > p)) {
            cout << -1;
        } else {
            for (int i = 0; i < s1; ++i) {
                cout << 1 << " ";
            }
            for (int i = 0; i < s2; ++i) {
                cout << y << " ";
            }
        }
    }
    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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
int T;
int a, b, c;
int s[7][3] = {
    {0, 0, 1},
    {0, 1, 0},
    {1, 0, 0},
    {0, 1, 1},
    {1, 0, 1},
    {1, 1, 0},
    {1, 1, 1}
};
int main() {
    cin >> T;
    while (T--) {
        int ans = 0;
        cin >> a >> b >> c;
        for (int i = 1; i < 1 << 7; ++i) {
            int sa = 0, sb = 0, sc = 0, cnt = 0;
            for (int j = 0; j < 7; ++j) {
                if (i >> j & 1) {
                    sa += s[j][0];
                    sb += s[j][1];
                    sc += s[j][2];
                    ++cnt;
                }
            }
            if (sa <= a && sb <= b && sc <= c)
                ans = max(ans, cnt);
        }
        cout << ans << endl;
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main() {
    int T, n, x;
    cin >> T;
    while (T--) {
        cin >> n >> x;
        cout << (n <= 2 ? 1 : (n - 3 + x) / x + 1) << 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
#include <iostream>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    for (int r = 0; r < 2 * n + 1; ++r) {
        int d = abs(r - n);
        if (d)
            printf("%*s", 2 * d, "");
        int c = 0;
        while (c < n - d)
            printf("%d ", c++);
        printf("%d", c--);
        while (c >= 0)
            printf(" %d", c--);
        printf("\n");
    }
    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
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        const int n = coins.size();
        vector<vector<int>> f(n + 1, vector<int>(amount + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int val = coins[i - 1];
            for (int j = 0; j <= amount; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * val <= j; ++k) {
                    f[i][j] += f[i - 1][j - k * val];
                }
            }
        }
        return f[n][amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        const int n = coins.size();
        vector<int> f(amount + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int val = coins[i - 1];
            for (int j = val; j <= amount; ++j) {
                f[j] += f[j - val];
            }
        }
        return f[amount];
    }
};
0%