Star's Blog

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 410;
7
const int MOD = 1000000007;
8
long long f[N][N];
9

10
int main() {
11
    int T;
12
    scanf("%d", &T);
13
    while (T--) {
14
        memset(f, 0, sizeof(f));
15
        f[0][0] = 1;
16
        int n, m, v;
17
        scanf("%d%d%d", &n, &m, &v);
18
        for (int i = 1; i <= n; ++i) {
19
            int t;
20
            scanf("%d", &t);
21
            for (int j = 1; j <= m; ++j) {
22
                for (int k = t; k <= v; ++k) {
23
                    f[j][k] = (f[j][k] + f[j - 1][k - t]) % MOD;
24
                }
25
            }
26
        }
27
        long long res = 0;
28
        for (int i = 1; i <= v; ++i) {
29
            res = (res + f[m][i]) % MOD;
30
        }
31
        printf("%lld\n", res);
32
    }
33
    return 0;
34
}

1
#include <iostream>
2
#include <cmath>
3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        int d, r, x, y;
10
        scanf("%d%d%d%d", &d, &r, &x, &y);
11
        if (abs(y) <= d) printf("%d\n", abs(r - abs(x)));
12
        else printf("%d\n", (int)(0.5 + fabs((double)r - sqrt(x * x + (abs(y) - d) * (abs(y) - d)))));
13
    }
14
    return 0;
15
}

1
#include <iostream>
2
#include <vector>
3
#include <map>
4
#include <sstream>
5
#include <cstring>
6
#include <algorithm>
7

8
using namespace std;
9

10
const int N = 5010;
11

12
vector<vector<int>> fa;
13
bool vis[N];
14

15
bool check(int x, int t) { // x 的祖先是否包含 t
16
    if (vis[x]) return false;
17
    vis[x] = true;
18
    if (x == t) return true;
19
    else {
20
        for (int y : fa[x]) {
21
            if (check(y, t)) return true;
22
        }
23
        return false;
24
    }
25
}
26

27
int main() {
28
    ios::sync_with_stdio(0);
29
    cin.tie(0), cout.tie(0);
30
    int T;
31
    cin >> T;
32
    while (T--) {
33
        fa = vector<vector<int>>(2);
34
        map<string, int> mp = {{"main", 1}};
35
        int n;
36
        cin >> n;
37
        string cmd, cur = "main";
38
        getline(cin, cmd);
39
        while (n--) {
40
            getline(cin, cmd);
41
            stringstream ss(cmd);
42
            string bin;
43
            ss >> bin;
44
            if (bin == "commit") {
45
                fa.push_back(vector<int>({mp[cur]}));
46
                mp[cur] = fa.size() - 1;
47
            }
48
            else if (bin == "branch") {
49
                string s;
50
                ss >> s;
51
                if (s == "-d") { // 删除分支
52
                    ss >> s;
53
                    if (mp.find(s) != mp.end()) mp.erase(s);
54
                }
55
                else {
56
                    int node;
57
                    ss >> s;
58
                    if (mp.find(s) != mp.end()) continue; // 已经存在
59
                    else if (ss >> node) { // 如果有 [node]
60
                        mp[s] = node;
61
                    }
62
                    else { // 没有 id 当前分支指向节点
63
                        mp[s] = mp[cur];
64
                    }
65
                }
66
            }
67
            else if (bin == "merge") { // 合并分支
68
                string s;
69
                ss >> s;
70
                bool f1, f2;
71
                memset(vis, 0, sizeof(bool) * fa.size());
72
                f1 = check(mp[cur], mp[s]);
73
                memset(vis, 0, sizeof(bool) * fa.size());
74
                f2 = check(mp[s], mp[cur]);
75
                if (!f1 && !f2) { // 都不包含
76
                    fa.push_back(vector<int>({mp[cur], mp[s]}));
77
                    mp[cur] = fa.size() - 1;
78
                }
79
                else if (f2) { // 后者包含前者
80
                    mp[cur] = mp[s];
81
                }
82
            }
83
            else if (bin == "checkout") { // 切换分支
84
                ss >> cur;
85
            }
86
            else if (bin == "reset") {
87
                int node;
88
                if (ss >> node) { // 如果有 [node]
89
                    mp[cur] = node;
90
                }
91
            }
92
            else {
93
                cout << "qwq" << endl;
94
                return 123;
95
            }
96
        }
97
        cout << mp.size() << endl;
98
        for (auto [s, node] : mp) cout << s << ' ' << node << endl;
99
        cout << fa.size() - 1 << endl;
100
        for (int i = 1; i < fa.size(); ++i) {
101
            cout << fa[i].size() << ' ';
102
            sort(fa[i].begin(), fa[i].end());
103
            for (int node : fa[i]) cout << node << ' ';
104
            cout << endl;
105
        }
106
    }
107
    return 0;
108
}

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 500010;
7

8
int head[N], ne[N * 2], ver[N * 2], w[N * 2], tot;
9
int dis[N];
10

11
void add(int x, int y, int z) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
    w[tot] = z;
16
}
17

18
void dp(int x, int fa) {
19
    for (int i = head[x]; i; i = ne[i]) {
20
        int y = ver[i], val = w[i];
21
        if (y == fa) continue;
22
        dis[y] = dis[x] ^ val;
23
        dp(y, x);
24
    }
25
}
26

27
int main() {
28
    int T;
29
    scanf("%d", &T);
30
    while (T--) {
31
        int n;
32
        scanf("%d", &n);
33
        tot = 0;
34
        memset(head, 0, sizeof(int) * (n + 1));
35
        for (int i = 1; i < n; ++i) {
36
            int x, y, z;
37
            scanf("%d%d%d", &x, &y, &z);
38
            z = z & 1;
39
            add(x, y, z), add(y, x, z);
40
        }
41
        dis[1] = 0;
42
        dp(1, 0);
43
        long long cnt[2] = {};
44
        for (int i = 1; i <= n; ++i) cnt[dis[i]]++;
45
        printf("%lld\n", cnt[0] * cnt[0] * cnt[0] + cnt[1] * cnt[1] * cnt[1]);
46
    }
47
    return 0;
48
}