A. Robin Helps

模拟

code:

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 <bits/stdc++.h>

using namespace std;

const int N = 55;

int T;
int n, k;
int a[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int res = 0, sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] >= k) sum += a[i];
            else if (!a[i] && sum) res++, sum--;
        }
                
        cout << res << endl;
    }

    return 0;
}

B. Robin Hood and the Major Oak

\(i^i\) 的奇偶性与 \(i\) 相同，因此，要判断，第 \(n\) 年叶子个数的奇偶性，只需要计算出 \([n-k+1,n]\) 中奇数的个数 \(cnt\) 即可，若 \(cnt\%2=0\)，由奇偶数的性质可以得出叶子总数是偶数，反之奇数

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int T;
int n, k;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        
        int cnt = 0;
        if (k % 2 && n % 2) cnt++;
        if ((k / 2 + cnt) % 2) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

C. Robin Hood in Town

二分答案，注意上界的范围

code:

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200010;

int T;
int n;
int a[N];
int sum, maxv;

bool check(int x)
{
    int res = 0;
    bool flag = false;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == maxv && !flag)
        {
            flag = true;
            continue;
        }
        if (a[i] < (sum + x + n * 2 - 1) / (n * 2)) res++;
    }
    return res > n / 2;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        sum = maxv = 0;
        for (int i = 0; i < n; i++) 
        {
            sum += a[i];
            maxv = max(maxv, a[i]);
        }
        
        int l = 0, r = 1e15;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (!check(mid)) l = mid + 1;
            else r = mid;
        }
        
        if (check(l)) cout << l << endl;
        else cout << -1 << endl;
    }

    return 0;
}

D. Robert Hood and Mrs Hood

滑动窗口，及时弹出时间不在 \([i-k+1,i]\) 之间的工作，动态更新最大最小工作数

code:

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
#include <bits/stdc++.h>

using namespace std;

int T;
int n, d, k;
map<int, int> L, R;

int main()
{
    cin >> T;
    while (T--)
    {
        L.clear(), R.clear();
        
        cin >> n >> d >> k;
        for (int i = 1; i <= k; i++)
        {
            int l, r;
            cin >> l >> r;
            L[l]++, R[r]++;
        }
        
        int sum = 0, maxv = 0, minv = 1e9, r1, r2;
        for (int i = 1; i <= n; i++)
        {
            sum += L[i];
            if (i < d) continue;
            if (i > d) sum -= R[i - d];
            if (maxv < sum) maxv = sum, r1 = i - d + 1;
            if (minv > sum) minv = sum, r2 = i - d + 1;
        }
        
        cout << r1 << ' ' << r2 << endl;
    }

    return 0;
}

E. Rendez-vous de Marian et Robin

最短路问题

  • \(d1[0][i]\) 表示从 \(1\) 到 \(i\) 不骑马花费的最短时间
  • \(d1[1][i]\) 表示从 \(1\) 到 \(i\) 骑马花费的最短时间
  • \(d2[0][i]\) 表示从 \(n\) 到 \(i\) 不骑马花费的最小时间
  • \(d2[1][i]\) 表示从 \(n\) 到 \(i\) 骑马花费的最小时间

可以用堆优化 \(dijkstra\) 来计算

计算出每个点的最短时间后，遍历所有顶点，两人在每个顶点相遇花费的最短时间就是两人中最晚到达这个点的人所花的时间

code:

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
110
111
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

struct Node
{
    int x, y, z;
};

struct cmp
{
    bool operator()(const Node A, const Node B) const
    {
        return A.z > B.z;
    }
};

int T;
int n, m, k;
map<int, int> p;
vector<PII> h[N];
int d1[2][N], d2[2][N];

void dijkstra(int bg, int d[][N])
{
    bool st[2][N];
    for (int i = 1; i <= n; i++) st[0][i] = st[1][i] = false;

    priority_queue<Node, vector<Node>, cmp> heap;
    heap.push({bg, p[bg], 0});
    d[p[bg]][bg] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        if (st[t.y][t.x]) continue;
        st[t.y][t.x] = 1;
        
        for (int i = 0; i < h[t.x].size(); i++)
        {
            int j = h[t.x][i].x, dist = t.y? h[t.x][i].y / 2 : h[t.x][i].y;
            if (d[t.y][j] > d[t.y][t.x] + dist)
            {
                d[t.y][j] = d[t.y][t.x] + dist;
                heap.push({j, t.y, d[t.y][j]});
            }
            if (!t.y && p[j] && d[1][j] > d[0][t.x] + dist)
            {
                d[1][j] = d[0][t.x] + dist;
                heap.push({j, 1, d[1][j]});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        p.clear();
        
        cin >> n >> m >> k;
        while (k--)
        {
            int x;
            cin >> x;
            p[x]++;
        }
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            h[u].push_back({v, w});
            h[v].push_back({u, w});
        }
        
        for (int i = 0; i < 2; i++)
            for (int j = 1; j <= n; j++)
                d1[i][j] = d2[i][j] = 1e18;
        
        dijkstra(1, d1);
        dijkstra(n, d2);
        
        int res = 1e18;
        for (int i = 1; i <= n; i++)
            if ((d1[0][i] < 1e18 || d1[1][i] < 1e18) && (d2[0][i] < 1e18 || d2[1][i] < 1e18))
                res = min(res, max(min(d1[0][i], d1[1][i]), min(d2[0][i], d2[1][i])));
        
        if (res == 1e18) cout << -1 << endl;
        else cout << res << endl;
        
        for (int i = 1; i <= n; i++) h[i].clear();
    }

    return 0;
}

F. Sheriff's Defense

树型 \(dp\)

\(f[u][0]\) 表示 以 \(u\) 为根节点的子树中，\(u\) 被摧毁所能留下来黄金的最大数量

\(f[u][1]\) 表示 以 \(u\) 为根节点的子树中，\(u\) 幸存下来所能留下黄金的最大数量

设 \(v\) 是 \(u\) 的儿子节点，则可以很轻易列出状态转移方程

  • \(f[u][0]=f[u][0]+max(f[v][0], f[v][1])\)
  • \(f[u][1]=f[u][1]+max(f[v][0], f[v][1] - c * 2)\)

code:

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
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, c;
int a[N];
vector<int> h[N];
int f[N][2];

void dfs(int u, int father)
{
    f[u][0] = 0, f[u][1] = a[u];
    for (int i = 0; i < h[u].size(); i++)
    {
        int v = h[u][i];
        if (v == father) continue;
        dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += max(f[v][0], f[v][1] - c * 2);
    }
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> c;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 0; i < n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            h[u].push_back(v);
            h[v].push_back(u);
        }
        
        dfs(1, 0);
        
        cout << max(f[1][0], f[1][1]) << endl;
        
        for (int i = 1; i <= n; i++) h[i].clear();
    }

    return 0;
}

H. Robin Hood Archery

莫队

code:

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
#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

struct Q
{
    int id, l, r;
}qry[N];

int T;
int n, q;
int len, sum;
int a[N], b[N], c[N];
int res[N];

bool cmp(Q A, Q B)
{
    if ((A.l + len - 1) / len != (B.l + len - 1) / len) return A.l < B.l;
    if ((A.l + len - 1) / len & 1) return A.r < B.r;
    return A.r > B.r;
}

void change(int x)
{
    if (c[x] & 1) sum--;
    else sum++;
    c[x] ^= 1;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= q; i++)
        {
            int l, r;
            cin >> l >> r;
            qry[i] = {i, l, r};	
        }
        
        for (int i = 1; i <= n; i++) b[i] = a[i];
        sort(b + 1, b + 1 + n);
        
        int bn = unique(b + 1, b + 1 + n) - b - 1;
        for (int i = 1; i <= n; i++)
        {
            int l = 1, r = bn;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (b[mid] < a[i]) l = mid + 1;
                else r = mid;
            }
            a[i] = l;
        }
        
        len = sqrt(n);
        sort(qry + 1, qry + q + 1, cmp);
        
        sum = 0;
        for (int i = 1, l = 1, r = 0; i <= q; i++)
        {
            while (l > qry[i].l) change(a[--l]);
            while (r < qry[i].r) change(a[++r]);
            while (l < qry[i].l) change(a[l++]);
            while (r > qry[i].r) change(a[r--]);
            res[qry[i].id] = sum;
        }
        
        for (int i = 1; i <= q; i++)
        {
            if (res[i]) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        
        for (int i = 1; i <= bn; i++) c[i] = 0;
    }

    return 0;
}