2024.7.24份题解

发表于 更新于 阅读次数：
梦熊2024/7/24题解

T1 最短路

给定一个包含 $ n $ 个节点和 $ m $ 条边的图，每条边有一个权值。
你的任务是回答 $ k $ 个询问，每个询问包含两个正整数 $ s $ 和 $ t $ 表示起点和终点，要求寻找从 $ s $ 到 $ t $ 的一条路径，使得路径上权值最大的一条边权值最小。

  1. 最短路一定在最小生成树上
  2. 跑一遍 $ prim $ ，顺便更新 $ ans $
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
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define maxn 1020
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define love return
#define you 0
#define inf 0x3f3f3f3f
#define me 1

using namespace std;

int dist[maxn];
int n,m,k;
int cosent[maxn][maxn];
int ans[maxn][maxn];

int to[maxn];
bool f[maxn];

 
signed main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    cin >> n >> m >> k;

    memset(cosent, inf, sizeof(cosent));
    memset(ans,0, sizeof(ans));

    rep(i, 0, n)
    {
        to[i] = i;
        dist[i] = inf; 
        cosent[i][i] = 0;
    }
    
    rep(i, 1, m)
    {
        int u, v, w;
        cin >> u >> v >> w;

        if(cosent[u][v] > w)
        {
            cosent[u][v] = cosent[v][u] = w;
        }    
    }
  
    dist[1] = 0;
    
    rep(i, 1, n)
    {
        int mx = inf;
        int v = -1;

        rep(j, 1, n) 
        {
            if(!f[j] && dist[j] < mx)
            {
                v = j;
                mx = dist[j];
            }
        }

        if(v==-1) break;

        rep(j, 1, n) 
        {
            if(f[j])
            {
                ans[v][j] = ans[j][v] = max(ans[to[v]][j], mx);
            }
        }
        f[v] = 1;


        rep(j, 1, n) 
        {
            if(!f[j] && cosent[v][j] < dist[j])
            {
                dist[j] = cosent[v][j];
                to[j] = v;
            }
        }
    }

    rep(i, 1, k)
    {
        int u, v; cin >> u >> v; 
        cout << (ans[u][v] == 0 ? -1 : ans[u][v]) << endl;
    }
    
    love you;
}

T2 序列

有一个长度为 $ n $ 的数列 $ a_1,…,a_n $, 其中对任意 $ 1 \leq i \leq n $ :
• 若 $ i $ 为奇数, 那么 $ a_i = \frac{i+1}{2} $.
• 否则 $ z_i = n + 1 - \frac{i}{2} $.
你需要回答q次询问, 每次询问会给定一个特定的数 $ s $, 请你求出有多少对 $ (l, r) $ 满足 $ 1 \leq l \leq r \leq n $ 且 $ \sum_{i=l}^{r}a_i = s $.

显然当 $l, r$ 分别取奇偶, 偶奇, 奇奇, 偶偶时存在规律. 

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

signed main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);

    int n, q; cin >> n >> q;
    while(q --)
    {
        long long int s; cin >> s;
        long long int ans = 0;
        int a = s % (n + 1), b = s % (n + 2);
        if(a == 0)
        {
            ans += max(0ll, n / 2 - (s / (n + 1)) + 1);
        }
        else if(a * 2 - 1 <= n)
        {
            if((a * 2 - 1) - 2 * (s / (n + 1)) >= 1) ans ++;
        }
        if(b == 0)
        {
            ans += max(0ll, (n - 1) / 2 - (s / (n + 2)) + 1);
        }
        else if(b * 2 - 1 > n) 
        {
            if((n - b + 1) * 2 - 2 * (s / (n + 2)) >= 1) ans ++;
            
        }
        
        cout << ans << endl;
    }

    return 0;
}

T3 函数

数位dp，待更

T3 游戏

nim游戏，待更