25福建省赛

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

G. 炒股高手

已知 \(n\) 个交易日中股票的股价（所有价格均以自然对数的形式给出）。可以购买非整数份的股票。共有 \(m\) 个时间区间，本金均为 \(e^k\)。求每个时间区间进行买入卖出后得到的总资产。\(n\le 10^5,m\le 10^5\)。

点击查看题解

数学 贪心 价格 \(e^a\) 时买入，\(e^b\) 时卖出，本金与获利为 \(e^k/e^a·e^b=e^{k-a+b}\)。所有买入卖出操作都可以用每天选择昨天买入今天卖出或不进行操作来表示。只有昨天股票价格低于今天才选择买入卖出操作，即 \(b_i=\max(a_i-a_{i-1},0)\)，本质上为对 \(b_i\) 区间求和。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

void solve() {
    ll n, m, k;
    cin >> n >> m;
    ll a[n + 10] = {}, b[n + 10] = {}, S[n + 10] = {};
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = max(0ll, a[i] - a[i - 1]);
        S[i] = S[i - 1] + b[i];
    }
    cin >> k;
    for (ll i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        cout << k + S[r] - S[l] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

J. 构造大师CFJ

给定一个正整数 \(n\)，请在 \(100\) 次操作以内，将其变为一个完全平方数。每次操作的内容为如下：

  • 选择一个当前数字 \(n\) 的正约数 \(x\)；
  • 每次选择的 \(x\) 需跟之前任何一次选择的都不同；
  • 随后让 \(n\) 加上 \(x\)。

在整个操作过程中，\(n\) 不允许超过 \(10^{18}\)。\(T\le 10^3,n\le 10^{12}\)。

点击查看题解

数学 考虑把 \(n\) 变为 \(2^{2k}\) 形式。设 \(n\) 的 lowbit 为第 \(a\) 位，加上 lowbit 之后，第 \(a\) 位及更低位都不会出现 \(1\)。所以每次加上 \(n\) 的 lowbit 即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

ll lb(ll x) { return x & -x; }

void solve() {
    ll n;
    vector<ll> ans;
    cin >> n;
    while (n != lb(n)) {
        ans.push_back(lb(n));
        n += lb(n);
    }
    ll jud = 0;
    for (ll i = 1; i <= n; i *= 2) {
        jud++;
    }
    if (jud % 2 == 0) {
        ans.push_back(n);
    }
    cout << ans.size() << endl;
    for (auto i: ans) {
        cout << i << " ";
    }
    cout << endl;
}

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

K. VERTeX

给定一棵有 \(n\le 2\times10^5\) 个结点的树，结点依次以 \(1,2,...,n\) 标号。第 \(i\)（\(1\le i\le n\)）个结点有正整数权值 \(b_i > 0\)。对于连接结点 \(u\) 与 \(v\) 的树边，其边权为 \(w_{uv}=b_u+b_v\)。 现在给定树的形态与每条树边的边权，你需要判断是否存在满足条件的一组结点权值。若存在，则求出任意一组结点权值。

点击查看题解

如果根节点权值确定，整棵树就确定了。设根节点权值为 \(x\)，\(x\) 升高时，奇数层权值升高，偶数层权值降低。开始时令 \(x=1\)，升高 \(x\) 使得奇数层、偶数层权值最小值均大于零即可。

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

const ll N = 2e5 + 10, inf = 1e17;

ll n, a[N], d[N], mino = inf, minj = inf, add = 0;
vector<PII> e[N];

void dfs(ll root, ll dad) {
    d[root] = d[dad] + 1;
    if (d[root] % 2 == 0) {
        mino = min(mino, a[root]);
    } else {
        minj = min(minj, a[root]);
    }
    for (auto [son, w]: e[root]) {
        if (son == dad) {
            continue;
        }
        a[son] = w - a[root];
        dfs(son, root);
    }
}

void solve() {
    cin >> n;
    for (ll i = 1, u, v, w; i <= n - 1; i++) {
        cin >> u >> v >> w;
        e[u].push_back((PII) {v, w});
        e[v].push_back((PII) {u, w});
    }
    a[1] = 1, d[1] = 0;
    dfs(1, 1);
    while (mino >= 1) {
        if (minj >= 1) {
            cout << "YES" << endl;
            for (ll i = 1; i <= n; i++) {
                cout << a[i] + add * (-1 + 2 * (d[i] % 2)) << " ";
            }
            cout << endl;
            return;
        }
        mino--, minj++, add++;
    }
    cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

L. 众数

有 \(n\) 个整数构成的序列 \(a_i\)，对于序列的每个前缀，考虑选择其中一个非空下标集合 \(S\)，定义 \(f(S)=\min\{a_i\mid i\in S\}+\max\{a_i\mid i\in S\}\)。求对于序列 \(a\) 的每个前缀，在其对应的 \(2^k−1\) 种情况下，\(f(S)\) 的值的众数（出现最多的数），如果有多种数出现次数一样均为最多，则输出其中最大的数。

要求线性做法。

点击查看题解

思维题 结论：

  • 集合只有一种数 \(x\)：众数为 \(2x\)。
  • 集合有两种数 \(x<y\)：如果 \(x\) 只有一个，则众数为 \(2y\)，否则是 \(x+y\)。
  • 其余情况，答案为 \(x+y\)。

证明看大佬题解：https://www.luogu.com.cn/article/uc6e4npb

H. 难以控制的滑板火箭

\(n\times m\) 的 01 地图，\(0\) 为障碍。从 \((1,1)\) 走到 \((n,m)\)，可走八连通。每分钟必须走 \([l,r]\) 步，求最短几分钟到达。要求线性做法。

点击查看题解

最短路 类似于这种到达终点后需要来回踱步的要求，可以考虑到奇偶最短路。之后分类讨论：

  • 如果 \(L=R=x\)，需要看 \(x\) 奇偶性。
    • 如果为奇数，说明如果多走一分钟可以改变奇偶性。先考虑偶最短路 \(sum0\)，那么第一次走到终点的时间为 \(\lceil sum0/x \rceil\)（不一定是最终时间）。如果走的步数 \(x\times \lceil sum0/x \rceil\) 为偶数，说明可以来回踱步保证最后停在终点；否则必须额外花一分钟。对于奇最短路 \(sum1\)，情况完全相同。
    • 如果为偶数，说明走的步数一定为偶数步，必须要求偶最短路存在，答案为 \(\lceil sum0/x \rceil\)。
  • 如果 \(L<R\)，说明我们可以调整某一分钟走的步数，使得任意改变步数的奇偶性。答案为 \(\lceil \min(sum0,sum1)/x \rceil\)。
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
#include <bits/stdc++.h>

#define ll long long
using namespace std;
#define int long long
#define PII pair<int, int>

struct node {
    int x;
    int y;
    int t;
};

const ll N = 4e18;

void solve() {
    int n, m, l, r;
    cin >> n >> m >> l >> r;

    string a[n + 2];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
    }
    int nex[8][2] = {0, 1, 1, 0, -1, 0, 0, -1, 1, 1, -1, -1, 1, -1, -1, 1};
    int dis[n + 2][m + 2][2];
    int b[n + 2][m + 2][2] = {};
    dis[1][1][0] = 0;
    dis[n][m][0] = -1;
    dis[n][m][1] = -1;
    queue<node> q;
    q.push({1, 1, 0});

    while (!q.empty()) {
        auto [x, y, t] = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + nex[i][0];
            int ny = y + nex[i][1];
            if (nx <= 0 || ny <= 0 || nx > n || ny > m || a[nx][ny] == '0') {
                continue;
            }
            int nt = t ^ 1;
            if (b[nx][ny][nt] == 1) {
                continue;
            }
            dis[nx][ny][nt] = dis[x][y][t] + 1;
            b[nx][ny][nt] = 1;
            q.push({nx, ny, nt});
        }
    }
    int sum1 = dis[n][m][1];
    int sum2 = dis[n][m][0];
    if (sum1 == -1 && sum2 == -1) {
        cout << -1;
        return;
    }
    if (sum1 == -1)
        sum1 = N;
    if (sum2 == -1)
        sum2 = N;
    int ans;
    if (l < r) {
        ans = (min(sum1, sum2) - 1) / r + 1;
    } else {
        if (r % 2 == 1) {
            int ans1, ans2;
            if (sum1 == N)
                ans1 = N;
            else
                ans1 = (((sum1 - 1) / r + 1) * r - sum1) % 2 + (sum1 - 1) / r + 1;

            if (sum2 == N)
                ans2 = N;
            else
                ans2 = (((sum2 - 1) / r + 1) * r - sum2) % 2 + (sum2 - 1) / r + 1;

            ans = min(ans1, ans2);
        } else {
            if (sum2 == N) {
                cout << -1;
                return;
            }
            ans = (sum2 - 1) / r + 1;
        }
    }
    cout << ans;
}

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

I. 割点

给定一个正整数 \(n\le2000\) 和一个长度为 \(n-2\) 的 01 序列 \(a_{2}, a_{3}, \dots, a_{n-1}\)，要求你构造一个 \(n\) 个点的无向简单连通图 \(G\)，使得：

  • 点 \(1\) 是割点，点 \(n\) 不是割点。
  • 对于每个 \(1 < i < n\)，若 \(a_{i} = 1\)，则点 \(i\) 在图 \(G\) 中是割点；若 \(a_{i} = 0\)，则点 \(i\) 在图 \(G\) 中不是割点。
  • 图 \(G\) 中各顶点的度数满足：\(\rm{deg}_1\geq \rm{deg}_2\geq\dots\geq \rm{deg}_n\)。

如果存在多种可行的图，输出任意一种；如果不存在满足条件的图，则输出 \(-1\)。

点击查看题解

如果排除 \(1,n\) 号点：

  • 都是割点：无解。
  • 只有一个非割点：这个点必须是 \(n-1\)，否则无解。构造方法是一条链，\(n-1,1,2,...,n\)。
  • 两个以上非割点：构造方法是令非割点与 \(1\) 号点连成环，然后 \(1\) 号点后面连接所有割点成一条链，最后连接 \(n\) 号点。

E. 卡牌游戏

小 A 和小 B 正在玩卡牌游戏。

有 \(2n\) 张卡牌垒成一摞牌堆，自上而下的第 \(i\)（\(1\leq i\leq 2n\)）张牌上标注了数字 \(a_i\)。发牌时，牌堆中的卡牌自上而下以 \(1, 2, \dots, 2n\) 编号，编号为奇数的卡牌将分给一位玩家，编号为偶数的卡牌将分给另一位玩家。这意味着，小 A 将会获得编号同为奇数或同为偶数的 \(n\) 张卡牌。

对于玩家而言，所得到的卡牌上的数字之和越大，游戏局面对他越有利。因此小 A 想最大化最坏情况下他所得到的卡牌数字之和。为了达到这个目的，小 A 可以对当前牌堆执行恰好一次以下操作：

  • 从当前牌堆中抽出一张卡牌，并插回牌堆中的任意位置。注意发牌时的编号可能会发生变化。

例如，初始时牌堆中卡牌标注的数字自上而下依次是 \(1, 2, 3, 4\)，发牌时一位玩家将得到 \(1, 3\)，另一位玩家将得到 \(2, 4\)。小 A 可以选择抽出第二张卡牌，并将其插回最后一张卡牌后面，此时牌堆为 \(1, 3, 4, 2\)，发牌时一位玩家将得到 \(1, 4\)，另一位玩家将得到 \(3, 2\)。

你需要求出小 A 在执行恰好一次操作后，最坏情况下所得到的卡牌数字之和的最大值。要求 \(O(n\log n)\) 做法。

点击查看题解

思维题 经过分析后得知题意为通过切牌操作使得奇偶牌数字和尽量平均，而切牌操作等价于选择一个长度为偶数的区间，反转内部的奇偶牌（奇偶交换）。

可以令奇数位权值为 \(1\)，偶数位权值为 \(-1\)，问题转化为求一段偶数长度的区间，其区间和尽量接近总和的一半。用 set 插入数列的各个前缀，使用二分查找即可。

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>
typedef long long ll;
using namespace std;
const ll N = 2e5 + 100;
const ll INF = 1e18;
ll a[N], s[N];
void __() {
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
        a[i] *= 2;
        if (i % 2) {
            s[i] = s[i - 1] + a[i];
        } else {
            s[i] = s[i - 1] - a[i];
        }
        sum += a[i];
    }
    set<ll> val1, val2;
    ll ans = abs(s[2 * n]) / 2, tar = s[2 * n];
    val1.insert(INF);
    val1.insert(-INF);
    val2.insert(INF);
    val2.insert(-INF);
    for (int i = 1; i <= n; i++) {
        ll R = s[i * 2 - 1];
        ans = min(ans, abs(R - *val1.lower_bound(R - tar / 2) - tar / 2));
        ans = min(ans, abs(R - *prev(val1.upper_bound(R - tar / 2)) - tar / 2));
        val1.insert(R);
        R = s[i * 2];
        ans = min(ans, abs(R - *val2.lower_bound(R - tar / 2) - tar / 2));
        ans = min(ans, abs(R - *prev(val2.upper_bound(R - tar / 2)) - tar / 2));
        val2.insert(R);
    }
    cout << (sum / 2 - ans) / 2 << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        __();
    }
    return 0;
}