Codeforces Round 974 (Div. 3)

A Robin Helps

按题意模拟

 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;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n,ans,a[N],cnt,k;

void solve(){
    cnt=ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>=k)cnt+=a[i];
        if(!a[i]&&cnt)cnt--,ans++;
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Robin Hood and the Major Oak

显然只有最后 $k$ 个点有效，$i^i$ 的奇偶性只和 $i$ 有关，公式加和即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;

ll n, k;

void solve() {
    cin >> n >> k;
    ll s = (n - k + 1 + n) * k / 2;
    if (s % 2 == 1) cout << "NO" << '\n';
    else cout << "YES" << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C. Robin Hood in Town

二分答案，每次都把加的金钱给到当前钱最多的人，一定是最小答案，再二分查找数组中大于等于当前平均值的位置，看是否在中间即可

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 2e5 + 7;

int n, a[N];

bool check(ll f,ll sum) {
    a[n]+=f;
    if(lower_bound(a+1,a+1+n,(sum+f)/2.0/n)-a-1>(n>>1)){
        a[n]-=f;
        return true;
    }
    a[n]-=f;
    return false;
}

void solve() {
    ll sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    if (n < 3) {
        cout << "-1\n";
        return;
    }
    sort(a + 1, a + 1 + n);
    ll l = 0, r = 1e18, ans = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid, sum)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

D. Robert Hood and Mrs Hood

巨眼熟题，但还是想了半天

先排序 $l,r$，优先排 $l$，然后开一个 $vis$ 用于记录在 $i$ 天结束的工作有几个

从第一天开始，看有几个在周期内的任务，当前到访时间的答案即为这个任务数

向下进行，要先减去前一天结束的任务数，再继续向下找符合条件的任务

时间复杂度是 $O(n+k)$

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;

struct Node {
    int l, r;
    bool operator<(const Node &a) const { return (l == a.l ? r < a.r : l < a.l); }
};

int n, d, k, mx, mn;
Node a[N];

void solve() {
    cin >> n >> d >> k;
    for (int i = 1; i <= k; i++) {
        cin >> a[i].l >> a[i].r;
    }
    int ans[N] = {0};
    int vis[N] = {0};
    int now = 1, tmp = 0;
    sort(a + 1, a + 1 + k);
    for (int i = 1; i <= n - d + 1; i++) {
        if (i > 1 && vis[i - 1]) tmp -= vis[i - 1];
        while (now <= k && i + d - 1 >= a[now].l && i <= a[now].r) {
            tmp++;
            vis[a[now].r]++;
            now++;
        }
        ans[i] = tmp;
    }
    mx = mn = 1;
    for (int i = 2; i <= n - d + 1; i++) {
        if (ans[mx] < ans[i]) mx = i;
        if (ans[mn] > ans[i]) mn = i;
    }
    cout << mx << " " << mn << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

E. Rendez-vous de Marian et Robin

最短路径问题，可以想到用 $dijkstra$ 解决

可以看出分为两种状态，骑马和步行

开两个 $dist$ 数组，分别记录从 $1,n$ 为起点的 $dijkstra$

$dist$ 要分别记录有马，没马状态下的值

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N=4e5+7, mod=1e9+7;

int n, m, h, dist1[N], dist2[N], inf=1e18;
bool vis[N], p[N];
vector<pair<int, int>> edge[N];

void dijkstra(int s, int dist[]) {
    for (int i = 1; i <= n * 2; i++) dist[i] = inf;
    for (int i = 1; i <= n * 2; i++) vis[i] = 0;
    dist[s] = 0;
    set<pair<int, int>> q;
    q.insert({0, s});
    if (p[s]) {
        dist[n + s] = 0;
        q.insert({0, n + s});
    }
    while (!q.empty()) {
        int u = q.begin()->second;
        q.erase(q.begin());
        if (vis[u]) continue;
        vis[u] = 1;
        int t = (u > n ? u - n : u);
        for (auto [v, w] : edge[t]) {
            if (u > n) {
                if (dist[v + n] > dist[u] + w / 2) {
                    dist[v + n] = dist[u] + w / 2;
                    if (!vis[v + n]) q.insert({dist[v + n], v + n});
                }
            } else {
                if (p[v]) {
                    if (dist[v + n] > dist[u] + w) {
                        dist[v + n] = dist[u] + w;
                        if (!vis[v + n]) q.insert({dist[v + n], v + n});
                    }
                } else {
                    if (dist[v] > dist[u] + w) {
                        dist[v] = dist[u] + w;
                        if (!vis[v]) q.insert({dist[v], v});
                    }
                }
            }
        }
    }
}

void solve() {
    cin >> n >> m >> h;
    for (int i = 1; i <= n; i++) p[i] = 0, edge[i].clear();
    for (int i = 1; i <= h; i++) {
        int x;
        cin >> x;
        p[x] = 1;
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    int ans = inf;
    dijkstra(1, dist1);
    dijkstra(n, dist2);
    for (int i = 1; i <= n; i++) {
        ans = min(ans, max(min(dist1[i], dist1[i + n]), min(dist2[i], dist2[i + n])));
    }
    if (ans == inf) cout << "-1\n";
    else cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

F. Sheriff’s Defense

树形 dp, 状态 $dp[i][j]$ 表示选不选 $i$ 号节点

类似没有上司的舞会

明天写篇树形 dp 的学习记录

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;

ll n,c,s,ans;
ll dp[N][2];
vector<int>edge[N];
bool vis[N];

void dfs(int now,int fa){
    for(auto i:edge[now]){
        if(i!=fa){
            dfs(i,now);
            dp[now][0]+=max(dp[i][0],dp[i][1]);
            dp[now][1]+=max(dp[i][0],dp[i][1]-(c<<1));
        }
    }
}

void solve(){
    ans=0;
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        edge[i].clear();
        cin>>dp[i][1];
        dp[i][0]=0;
        vis[i]=0;
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1,0);
    cout<<max(dp[1][0],dp[1][1])<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

后两题感觉有点可写，后面再补。。。

H. Robin Hood Archery

这题凭什么当 H

显然后手者不可能胜，因为每次都是取当前最大值，那么后手不输的唯一机会就是平局

奇数个数的时候，一定会输。
偶数个数的时候，如果出现的数都出现了偶数次，那么就能打成平局

直接异或的话，可能被某些数据 hack 掉，所以要加上哈希

随机数生成尽量不要用 time(0) 这些不够随机的数

使用 random_device 或 chrono::system_clock::now().time_since_epoch().count() 来生成高质量的随机数

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N=1e6+7, mod=1e9+7;

int n,q,x;
int a[N],s[N];
int l,r;
random_device rnd;

void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>x;
        s[i]=s[i-1]^a[x];
    }
    while(q--){
        cin>>l>>r;
        if((r-l+1)&1)cout<<"NO\n";
        else if(s[r]==s[l-1])cout<<"YES\n";
        else cout<<"NO\n";
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=1e6;i++){
        a[i]=rnd();
    }
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}