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
#include <iostream>
using namespace std;
int T;
int n;
int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                cout << (r == c || c == r + 1 || (r == n - 1 && c == 0) ? 1 : 0) << " ";
            }
            cout << endl;
        }
        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
#include <iostream>
using namespace std;
int T;
int n;
int x;
int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        int flag = 0, cnt = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            cin >> x;
            if (x) {
                if (!flag) ++flag;
                else {
                    ans += cnt;
                    cnt = 0;
                }
            } else if (flag) {
                ++cnt;
            }
        }
        cout << ans << 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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5001;
int T;
int n;
int p[N];
int x;
bool ans;
int main() {
    cin >> T;
    while (T--) {
        ans = false;
        cin >> n;
        memset(p, 0, sizeof p);
        for (int i = 1; i <= n; ++i) {
            cin >> x;
            if (p[x]) {
                if (i - p[x] > 1) {
                    ans = true;
                    cin.ignore(numeric_limits<streamsize>::max(), '\n');
                    break;
                }
            } else {
                p[x] = i;
            }
        }
        cout << (ans ? "YES" : "NO") << endl;
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
char c;
int n, a, b;
int main() {
    cin >> n;
    a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
        cin >> c;
        if (c == 'A') a++;
        else b++;
    }
    cout << (a == b ? "T" : (a > b ? "A" : "B")) << endl;
}

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>
#include <math.h>
using namespace std;
typedef long long LL;
int n;
LL k;
vector<LL> v{0};
int dfs(int r, LL k) {
    auto it = lower_bound(v.begin(), v.begin() + r, k);
    int idx = it - v.begin();
    if (*it == k) return idx;
    return dfs(idx, v[idx - 1] * 2 - k);
}
int main() {
    cin >> n >> k;
    for (int i = 0; i <= n; ++i) v.emplace_back(pow(2, i));
    int ans = dfs(n + 1, k);
    cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
int n;
LL k;
int dfs(int n, LL k) {
    LL mid = 1ll << n - 1;
    if (k == mid) return n;
    if (k < mid) return dfs(n - 1, k);
    return dfs(n - 1, k - mid);
}
int main() {
    cin >> n >> k;
    cout << dfs(n, k) << endl;
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200001, M = 200001;
int T;
int n, m, k;
int h[N], e[M], ne[M], idx;
int d[N], q[N];
int pos[N];
struct Edge {
    int a, b;
} edge[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}  
bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; ++i)
        if (!d[i])
            q[++tt] = i;
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }
    return tt == n - 1;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        memset(h, -1, (n + 1) * 4);
        memset(d, 0, (n + 1) * 4);
        idx = k = 0;
        while (m--) {
            int t, a, b;
            scanf("%d%d%d", &t, &a, &b);
            if (!t) edge[k++] = {a, b};
            else {
                add(a, b);
                ++d[b];
            }
        }
        if (!topsort()) puts("NO");
        else {
            puts("YES");
            for (int i = 1; i <= n; ++i)
                for (int j = h[i]; ~j; j = ne[j])
                    printf("%d %d\n", i, e[j]);
            for (int i = 0; i < n; ++i) pos[q[i]] = i;
            for (int i = 0; i < k; ++i) {
                int a = edge[i].a, b = edge[i].b;
                if (pos[a] > pos[b]) swap(a, b);
                printf("%d %d\n", a, b);
            }
        }
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string largestOddNumber(string num) {
        const int n = num.size();
        int i = n - 1;
        for(; i >= 0; --i) {
            // if ((num[i] - '0') & 1) break;
             if (num[i] & 1) break; // ASCII code of an odd/even is also an odd/even.
        }
        return num.substr(0, i + 1);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
class Solution {
public:
    int numberOfRounds(string startTime, string finishTime) {
        int start = 60 * stoi(startTime.substr(0, 2)) + stoi(startTime.substr(3)),
            finish = 60 * stoi(finishTime.substr(0, 2)) + stoi(finishTime.substr(3));
        if (start > finish) finish += 60 * 24;
        return max(0, finish / 15 - (start + 14) / 15); // max(0, floor(finish / 15) - ceil(start / 15))
};

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
class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        const int n = grid1.size(), m = grid1[0].size();
        int ds[] = {1, 0, -1, 0, 1};
        function<bool(int, int)> dfs = [&](int x, int y) {
            grid2[x][y] = 0;
            bool ans = true;
            if (!grid1[x][y]) ans = false;
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i], ny = y + ds[i + 1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid2[nx][ny] && !dfs(nx, ny))
                    ans = false;
            }
            return ans;
        };
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (grid2[i][j] && dfs(i, j))
                    ++ans;
        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
19
20
21
22
23
24
const int N = 100001, M = 101;
int s[N][M];
class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size(), m = queries.size();
        for (int i = 1; i <= nums.size(); ++i)
            for (int j = 1; j <= 100; ++j) {
                s[i][j] = s[i - 1][j];
                if (nums[i - 1] == j) ++s[i][j];
            }
        vector<int> ans(m);
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0] + 1, r = queries[i][1] + 1, pre = 0, res = M;
            for (int j = 1; j <= 100; ++j)
                if (s[r][j] > s[l - 1][j]) {
                    if (pre) res = min(res, j - pre);
                    pre = j;
                }
            ans[i] = res == M ? -1 : res;
        }
        return ans;
    }
};
0%