A. 日历游戏

\(sg\) 函数板子题，就是需要多处理一个日期

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

using namespace std;

int T;
int y, m, d;
int bg, ed;
map<int, int> f;
int mon[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int y)
{
    return (y % 4 == 0 && y % 100) || y % 400 == 0;
}

int get_day(int y, int m, int d)
{
    int res = d;
    for (int i = 1; i < y; i++)
    {
        res += 365;
        if (check(i)) res++;
    }
    
    mon[2] = check(y)? 29 : 28;
    for (int i = 1; i < m; i++) res += mon[i];
    
    return res;
}

int dp(int x)
{	
    if (f.count(x)) return f[x];
    
    int t = x, y, m, d;
    for (int i = 1; i <= 2024; i++)
    {
    	if (t > 365 + check(i)) t -= 365 + check(i);
    	else
    	{
            y = i;
    	    break;
    	}
    }
   	
   	mon[2] = check(y)? 29 : 28;
    for (int i = 1; i <= 12; i++)
    {
    	if (t > mon[i]) t -= mon[i];
    	else
    	{
    	    m = i, d = t;
    	    break;
    	}
    }
    
    map<int, int> p;
    if (x + 1 <= ed) p[dp(x + 1)] = 1;
    if (x + mon[m] <= ed && mon[m % 12 + 1] >= d) 
    {
    	mon[2] = check(y)? 29 : 28;
    	p[dp(x + mon[m])] = 1;
    }
    
    int sg = 0;
    while (p.count(sg)) sg++;
    return f[x] = sg;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> y >> m >> d;
        bg = get_day(y, m, d), ed = get_day(2024, 8, 1);
        
        if (dp(bg)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    
    return 0;
}

B. 学生分组

当序列元素和sum满足 \(\lfloor\frac{sum}{n}\rfloor >= L\) 并且 \(\lceil\frac{sum}{n}\rceil <= R\) 时，可以使该序列变成好序列 分别算出小于 \(L\) 的数加到 \(L\) 需要的次数和与大于R的数减到R需要的次数和，取 \(max\) 即为答案

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>

#define int long long

using namespace std;

const int N = 1000010;

int n, l, r;
int a[N];

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> l >> r;
    
    int c1 = 0, c2 = 0, sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
        if (a[i] < l) c1 += l - a[i], a[i] = l;
        else if (a[i] > r) c2 += a[i] - r, a[i] = r;
    }
    
    if (sum / n < l || (sum + n - 1) / n > r) cout << -1 << endl;
    else cout << max(c1, c2) << endl;
    
    return 0;
}

C. 小美想收集

首先对所有冲突按照冲突值进行排序 接下来有两种做法： 1. 并查集 按照冲突值从大到小遍历，判断当前冲突值的两点是否已经是共同祖先，如果是，那么该冲突值则无法避免，答案就是当前冲突值，否则，把两点的祖先和对方冲突点的祖先合并，不断进行以上操作即为答案 2. 二分+染色法判断二分图 二分最小冲突值，\(check\)函数里把冲突值大于答案的两点都进行连边，用染色法判断是否是二分图即可，如果是则返回 \(true\)，否则返回 \(false\)

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

#define x first
#define y second

using namespace std;

const int N = 100010;

struct Node
{
    int a, b, x;
};
int n, m;
Node w[N];
int p[N];
vector<int> h[N];
int enemy[N];

bool cmp(Node A, Node B)
{
    return A.x > B.x;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, a, b;
        cin >> a >> b >> x;
        w[i] = {a, b, x};
    }
    
    sort(w, w + m, cmp);
    
    for (int i = 1; i <= n; i++) p[i] = i;
    
    int res = 0;
    for (int i = 0; i < m; i++)
    {
    	int a = w[i].a, b = w[i].b;
    	int fa = find(a), fb = find(b);
    	if (fa == fb)
    	{
    	    res = w[i].x;
    	    break;
    	}
    	if (!enemy[a]) enemy[a] = b;
    	else p[find(enemy[a])] = fb;
    	if (!enemy[b]) enemy[b] = a;
    	else p[find(enemy[b])] = fa;
    }
    
    cout << res << endl;
    
    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
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
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

const int N = 100010;

struct Node
{
    int a, b, x;
};
int n, m;
Node w[N];
vector<int> h[N];
int color[N];

bool cmp(Node A, Node B)
{
    return A.x < B.x;
}

bool dfs(int u, int c)
{
	color[u] = c;
	for (int i = 0; i < h[u].size(); i++)
	{
	    int j = h[u][i];
	    if (color[j] == c) return false;
	    else if (!color[j])
	        if (!dfs(j, 3 - c))
		    return false;
	}
	return true;
}

bool check(int x)
{
    for (int i = 1; i <= n; i++)
    {
        h[i].clear();
        color[i] = 0;
    }
    
    map<pair<int, int>, int> p;
    for (int i = x + 1; i < m; i++)
    {
    	int a = w[i].a, b = w[i].b;
    	p[{a, b}] = p[{b, a}] = 1;
    }
    
    for (auto it: p)
    {
        int a = it.x.x, b = it.x.y;
        h[a].push_back(b);
    }
    
    bool flag = true;
    for (int i = 1; i <= n; i++)
    	if (!color[i] && !dfs(i, 1))
    	{
            flag = false;
    	    break;
    	}
    
    return flag;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, a, b;
        cin >> a >> b >> x;
        w[i] = {a, b, x};
    }
    
    sort(w, w + m, cmp);
    
    int l = -1, r = m - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (!check(mid)) l = mid + 1;
        else r = mid;
    }
    
    if (~l) cout << w[l].x << endl;
    else cout << 0 << endl;
    
    return 0;
}

D. 区间问题1

线段树模板题

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

using namespace std;

typedef long long ll;

const int N = 100010;

struct Node
{
	int l, r;
	ll sum, add;
}tr[N * 4];
int n, m;
int w[N];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    if (!tr[u].add) return;
    tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;
    tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
    tr[u << 1].add += tr[u].add;
    tr[u << 1 | 1].add += tr[u].add;
    tr[u].add = 0;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, w[l]};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int x)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
	    tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
	    tr[u].add += x; 
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, x);
        if (r > mid) modify(u << 1 | 1, l, r, x);
        pushup(u);
    }
}

ll query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    else
    {
    	pushdown(u);
    	int mid = tr[u].l + tr[u].r >> 1;
    	ll res = 0;
    	if (l <= mid) res += query(u << 1, l, r);
    	if (r > mid) res += query(u << 1 | 1, l, r);
    	return res;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
	
    build(1, 1, n);
	
    cin >> m;
    while (m--)
    {
        int st;
        cin >> st;
        if (st == 1)
        {
            int l, r, d;
            cin >> l >> r >> d;
            modify(1, l, r, d);
        }
        else
        {
            int x;
            cin >> x;
            cout << query(1, x, x) << endl;
        }
    }
	
    return 0;
}

E. 哥德巴赫猜想

预处理质数，对于每个质数，用 \(f\) 数组记录该数能分为两个质数中的最小质数，用记忆化搜索维护

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

#define x first
#define y second

using namespace std;

const int N = 50010;

int T;
int n;
int f[N];
int p[N], cnt;
bool st[N];

void init()
{
    st[0] = st[1] = true;
    for (int i = 2; i <= 50000; i++)
    {
        if (!st[i]) p[cnt++] = i;
        for (int j = 0; p[j] <= 50000 / i; j++)
        {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}

int dp(int x)
{
    if (f[x]) return f[x];
    for (int i = 0; i < cnt; i++)
    {
        if (p[i] >= x) break;
        if (!st[x - p[i]]) return f[x] = p[i];
    }
    return f[x] = -1;
}

int main()
{
    init();
    
    cin >> T;
    while (T--)
    {
        cin >> n;
        
        int r1 = 0, r2 = 0, r3 = 0;
        for (int i = 0; i < cnt; i++)
        {
            if (p[i] >= n) break;
            int x = dp(n - p[i]);
            if (~x)
            {
                r1 = p[i], r2 = x, r3 = n - r1 - r2;
                break;
            }
        }
        
        if (r1) cout << r1 << ' ' << r2 << ' ' << r3 << endl;
        else cout << -1 << endl;
    }
    
    return 0;
}

F. 小美想跑步

开两个图，分别连正向边和反向边，做一遍最短路，处理出 \(1\) 到每个点的距离，最后全部相加即可

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
#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 = 1000010;

int n, m;
vector<PII> h1[N], h2[N];
int d1[N], d2[N];
bool st[N];

void dijkstra(int d[], vector<PII> h[])
{
	memset(st, false, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (int i = 2; i <= n; i++) d[i] = 1e18;
    heap.push({0, 1});
    
    
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.y;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = 0; i < h[ver].size(); i++)
        {
            int j = h[ver][i].x, dist = h[ver][i].y;
            if (d[j] > d[ver] + dist)
            {
                d[j] = d[ver] + dist;
                heap.push({d[j], j});
            }
        }
    }
}

signed main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        h1[a].push_back({b, c});
        h2[b].push_back({a, c});
    }
    
    dijkstra(d1, h1);
    dijkstra(d2, h2);
    
    int res = 0;
    for (int i = 2; i <= n; i++) res += d1[i] + d2[i];
    
    cout << res << endl;
    
    return 0;
}

G. 爬楼梯

简单 \(dp\)，假设 \(f[i]\) 为爬到第 \(i\) 层的方案数，则可以从 \(f[i - 3]\)、\(f[i - 1]\)、\(f[i - 1]\) 转移过来

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

#define int long long

using namespace std;

const int N = 1000010, mod = 1e9 + 7;

int n;
int f[N];

signed main()
{
    cin >> n;
    
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 3; j++)
            if (i - j >= 0)
                f[i] = (f[i] + f[i - j]) % mod;
    
    cout << f[n] << endl;
    
    return 0;
}

H. 区间问题2

线段树模板题，但是数据有问题线段树会 \(tle\)

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

#define ls u << 1
#define rs u << 1 | 1

using namespace std;

const int N = 1000010;

struct Node
{
    int l, r;
    int maxv;
}tr[N * 4];
int n, q;
int a[N];

void read(int &n)
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < '0'|| ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    n = x * f;
}

void print(int n)
{
    if(n < 0)
    {
        putchar('-');
        n *= -1;
    }
    if(n > 9) print(n / 10);
    putchar(n % 10 + '0');
}

void pushup(int u)
{
    tr[u].maxv = max(tr[ls].maxv, tr[rs].maxv);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, a[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
    else
    {
        int res = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) res = max(res, query(ls, l, r));
        if (r > mid) res = max(res, query(rs, l, r));
        return res;
    }
    return 0;
}

int main()
{
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
        
    build(1, 1, n);
    
    read(q);
    while (q--)
    {
        int l, r;
        read(l), read(r);
        print(query(1, l, r));
        printf("\n");
    }
    
    return 0;
}

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

#define int long long

using namespace std;

const int N = 1000010;

int n;
int a[N];

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    sort(a, a + n);
    
    int res = 1;
    for (int i = 0; i < n; i++) res += abs(a[i] - a[(n + 1) / 2 - 1]);
    
    cout << res << endl;
    
    return 0;
}

J. 平方根

二分答案

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
#include <iostream>

#define int unsigned long long

using namespace std;

int T;
int n;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        int l = 0, r = 1e10;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (mid * mid <= n) l = mid;
            else r = mid - 1;
        }
        
        cout << l << endl;
    }
    
    return 0;
}

K. 小美想游泳

\(bfs\) 更新 \(s\) 岛到 \(t\) 岛的最厉害波浪值

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
#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 = 10010;

int n, m;
vector<PII> h[N];
int st, ed;
int d[N];

int bfs()
{
    for (int i = 1; i <= n; i++) d[i] = 1e18;
    d[st] = 0;
    queue<int> q;
    q.push(st);
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < h[t].size(); i++)
        {
            int j = h[t][i].x, dist = max(d[t], h[t][i].y);
            if (d[j] > dist)
            {
                d[j] = dist;
                q.push(j);
            }
        }
    }
    
    return d[ed];
}

signed main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        h[a].push_back({b, c}), h[b].push_back({a, c});
    }
    cin >> st >> ed;
    
    cout << bfs() << endl;
    
    return 0;
}