A

Problem - A

题目要求的是连续获胜k轮，所以num在比较赢了之后应该置为1

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 <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N],b[N];
int main()
{
    int n, k;
    cin >> n >> k;
    int maxn = 0, maxi = -1;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        if(a[i] > maxn)
        {
            maxn = a[i];
            maxi = i; 
        }
    }
    int l = 1, r = 2, num = 0;
    while(r <= n)
    {
        if(a[r] <= a[l]) num++, r++;
        else
        {
            l = r;
            r ++;
            num = 1;
        }
        if(num == k) 
        {
            cout << l;
            return 0;
        }
    }
    cout << maxi;
    return 0;
}

C

Problem - C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
double R, a;
const int N = 1e5 + 10;
double r[N];
int main()
{
    cin >> n >> R >> a;
    for (int i = 1; i <= n; i++) cin >> r[i];
    double res = R * a;
    res = min(res, R * (2 * 3.1415926 - a));
    for (int i = 1; i <= n; i++)
    {
        res = min(res, r[i] * a + 2 * (R - r[i]));
        res = min(res, r[i] * (2 * 3.1415926 - a) + 2 * (R - r[i]));
    }
    printf("%.6lf", res);
}

E

Problem - E

  1. 数组备长，模拟一轮，如果过程中出现连续t秒都小于等于k了，就符合条件。不倍长的话如果最后刚好是等于k，但是在开头是先减小的，那么就会在队头和队尾连接的位置实现连续t秒
  2. 当模拟一轮后，清醒值降低了，那显然是 YES
  3. 如果模拟一轮后清醒度升高了，并且过程中没有出现连续t秒都小于等于k，那显然是 NO
  4. 如果t很大，那么只遍历两边数组很显然是不够的，所以需要取\(t=min(t, n)\)，保证在整个数组都是小于k且t很大的情况下输出YES
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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
void solve(){
    int x, t, k, n, d;
    cin >> x >> t >> k >> n >> d;
    t = min(t, n);
    vector<int>v(n, 1);
 
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int u; cin >> u;
        if (u <= d) v[i] = -1;
        sum += v[i];
    }
 
    if (sum < 0) {
        cout << "YES\n";
        return;
    }
 
    int cnt = 0;
    
    for (int i = 0; i < n; i++) {
        x += v[i];
        if (x <= k) cnt++;
        else cnt = 0;
        if (cnt >= t) {
            cout << "YES\n";
            return;
        }
    }
    for (int i = 0; i < n; i++) {
        x += v[i];
        if (x <= k) cnt++;
        else cnt = 0;
        if (cnt >= t) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

G

Problem - G

  1. 因为中间有间隔的t，所以每一次应该先减去间隔t进去的人
  2. 因为在他醒来时队列的人数可能是0，所以要取0和当前人数的max
  3. 排队时间最少 != 人数最少 ：人数不同排队时间可能相同，所以要比较的是时间不是人数
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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 5e5 + 10;
typedef pair<int, int> PII;
vector<PII> h;
void solve()
{
    int t, n, m, k;
    cin >> t >> n >> m >> k;
    h.push_back({ 0, 0 });
    for(int i = 1; i <= m; i++)
    {
        int ti, x;
        cin >> ti >> x;
        h.push_back({ ti, x });
    }
    sort(h.begin(), h.end());
    int q = 0, minn = 1e18 + 5, mint = -1;
    for (int i = 1; i <= m; i++)
    {
        if (q >= k * (h[i].first - h[i - 1].first - 1)) q -= k * (h[i].first - h[i - 1].first - 1);
        else q = 0;
     
        q += h[i].second;
        if (h[i].first < t && h[i + 1].first > t)
        {         
            if (max(0ll, q - (t - h[i].first) * k) != n)
            {
                cout << "Wrong Record";
                return;
            }
        }
 
        if (h[i].first > t && (q + k) / k <= minn)
        {
            minn = (q + k) / k;
            mint = h[i].first;
        } // 排队时间最少 != 人数最少 ：人数不同排队时间可能相同
 
        if (q >= k) q -= k;
        else q = 0;
    }
    cout << mint << " " << minn;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

H

Problem - H

预处理，走过\(1\sim n-1\)个节点时的最短路

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 <iostream>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
int n, m;
vector<PII> e[N];
int dist[N][N];//第一维 记录路过多少个节点 第二维 节点i
 
void Deal()
{
    for (int i = 0; i <= n; i++) 
    {
        for (int j = 0; j <= n; j++) 
        {
            dist[i][j] = 3e18;
        }
    }
    dist[0][1] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (auto t : e[j])
            {
                dist[i][j] = min(dist[i][j], dist[i - 1][t.first] + t.second);
            }
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, t;
        cin >> u >> v >> t;
        e[u].push_back({ v, t });
        e[v].push_back({ u, t });
    }
    Deal();
    int q; cin >> q;
    while (q--)
    {
        int t; cin >> t;
        int sum = 0, res = 3e18;
        for (int i = 1; i <= n - 1; i++)
        {
            int x;
            cin >> x, sum += x;
            res = min(res, dist[i][t] + sum);
        }
        cout << res << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}