24暑排位2

发表于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

Dashboard - SDU 2024暑假排位 Round 2 - Codeforces

Problem A

一个圆形走廊由两个区域组成。内区域被均匀地分为 \(n\) 个扇区，外区域被均匀地分为 \(m\) 个扇区。每对相同区域（内或外）的扇区之间都有墙壁，但内区域和外区域之间没有墙壁。12 点钟位置总是有一堵墙。

内区域的扇区顺时针方向标记为 \((1,1),(1,2),⋯,(1,n)\)。外区域的扇区同样标记为 \((2,1),(2,2),⋯,(2,m)\)。

有 \(q\) 个询问，是否可以从一个扇区移动到另一个扇区。

\(1≤n,m≤10^{18},1≤q≤10^4\)。

点击查看题解

取 \(n\) 和 \(m\) 的最大公约数 \(g\)。则恰好有 \(g\) 个连通块。一个连通块中，\(n\) 有 \(n/g\) 个扇区，\(m\) 同理。对于每次询问计算两个扇区是否位于同一个连通块即可。

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;
typedef long long ll;
#define PII pair<int,int>

ll n, m, q;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll sx, sy, ex, ey, g;
    cin >> n >> m >> q;
    g = gcd(n, m);
    for (ll i = 1; i <= q; i++) {
        ll sty = -1, ety = -1;
        cin >> sx >> sy >> ex >> ey;
        if (sx == 1) {
            sty = (sy - 1) / (n / g);
        } else {
            sty = (sy - 1) / (m / g);
        }
        if (ex == 1) {
            ety = (ey - 1) / (n / g);
        } else {
            ety = (ey - 1) / (m / g);
        }
        if (sty == ety)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

Problem B

一天有 \(h\) 个小时。从第 \(0\) 时（刚好醒来）开始，睡觉 \(n\) 次。第 \(i\) 次睡觉将会在醒来后 \(a_i\) 小时之后准确地再次入睡，睡觉用时正好一天（\(h\) 小时）。

在每天的第 \(l\) 到 \(r\) 小时之间入睡是很棒的。若第 \(i\) 次入睡很棒，称此次睡眠是好的。

为了获取更多好的睡眠，在每次睡觉之前都可以选择：在 \(a_i\) 小时后入睡，或在 \(a_i−1\) 小时后入睡。

求可以获得的好的睡眠次数的最大值。

\(1\le n\le 2000,3\le h\le 2000,0\le l \le r<h,1≤a_i<h\)。

点击查看题解

解法一

可以发现，经过 \(i\) 次睡眠后，只需要知道提前睡了几次就可以算出当前的时间，从而判断睡眠是否很棒。

设 \(f(i,j)\) 代表前 \(i\) 次睡眠提前睡了 \(j\) 次的好的睡眠次数的最大值。限制：\(1\le i\le n, 0\le j\le i\)。

状态转移方程：

  • \(f(i,j)=\max\{f(i-1,j-1),f(i-1,j)\}+\text{isgood}(i,j)\) 。

  • \(\text{isgood}(i,j)=[l\le p_i-j\le r\pmod h]\)。

  • \(p_i\) 表示 \(a_i\) 的前缀和。

时间复杂度 \(O(n^2)\)，适用于 \(n\) 比较小而 \(h\) 比较大的情况。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>

const ll N = 2005;
const ll M = N * N;
ll n, h, l, r, a[N], p[N], f[N][N], ans = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> h >> l >> r;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    f[0][0] = 0;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= i; j++) {
            ll cur = ((p[i] - j) % h + h) % h;
            ll flag = 0;
            if (l <= cur && cur <= r)
                flag = 1;

            if (i > j)
                f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + flag;
            else
                f[i][j] = f[i - 1][j - 1] + flag;
        }
    }
    for (ll i = 0; i <= n; i++)
        ans = max(ans, f[n][i]);
    cout << ans << endl;
    return 0;
}

解法二

可以发现，只用记录睡觉的时间和好的次数，就可以判断睡眠是否很棒。

设 \(f(i,j)\) 代表前 \(i\) 次睡眠后在j小时醒来时，好的睡眠次数的最大值。限制：\(1\le i\le n, 0\le j<h\)。

状态转移方程：

  • \(f(i,j+a_i) = \max(f(i,j+a_i), f(i-1,j) +\text{isgood}(i,j))\)。
  • \(f(i,j+a_i-1) = \max(f(i,j+a_i-1), f(i-1,j) +\text{isgood}(i,j))\)。
  • \(\text{isgood}(i,j)=[l\le p_i-j\le r\pmod h]\)。
  • \(p_i\) 表示 \(a_i\) 的前缀和。

时间复杂度 \(O(nh)\)。

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 int long long


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, h, l, r;
    cin >> n >> h >> l >> r;
    int a[n + 1];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int dp[2005] = {};
    int temp[2005] = {};
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < h; j++) temp[j] = 0;
        for (int j = 0; j < h; j++) {
            if (dp[j] >= 1) {
                int delta = 0, t1 = (j + a[i]) % h, t2 = (j + a[i] - 1) % h;
                if (t1 >= l && t1 <= r)delta = 1;
                temp[t1] = max(temp[t1], dp[j] + delta);
                delta = 0;
                if (t2 >= l && t2 <= r)delta = 1;
                temp[t2] = max(temp[t2], dp[j] + delta);
            }
        }
        swap(dp, temp);
    }
    int ans = 0;
    for (int j = 0; j < h; j++) {
        ans = max(ans, dp[j]);
    }
    cout << ans - 1;
    return 0;
}

Problem C

给定 \(n\) 个点 \(m\) 条边的有向图，边权为 \(1\)。从 \(s\) 出发到达 \(t\)，按照以下路径：\(p_1, p_2, ..., p_k\)，其中 \(p_1=s, p_k=t,p_i\) 两两不同，且保证 \(\forall i\in[1,k-1]\)，边 \((p_i,p_{i+1})\) 存在。

在 \(p_1\)，导航事先生成一条对于此路径的每个点 \(p_i\)，