LANSGANBS

With a determined mindset, no obstacle is insurmountable.

统计加载中...

公告

如需添加友链，可以在任意文章下评论，并留下网站名称,链接,介绍和头像链接。

关于本站

2915 字

15 分钟

20251026测验题解与STD

2025-08-30

算法竞赛

算法与数据结构

/

项目与题解

统计加载中...

20251026测验题解与STD#

赛时公告#

全场首杀：

2504020207 网络25-2 - 阳灿 E题 00:05:01

顽强拼搏奖:

2504010606 计算机25-6 - 刘誉聪 02:59:43

最快解题奖：

A: 2504010610 计算机25-6 - 何俊杰 00:31:57

B: 2504090208 计算机双学士25-2 - 闫迪 00:29:08

C: 2504020207 网络25-2 - 阳灿 02:35:07

D: 2504020207 网络25-2 - 阳灿 00:45:43

E: 2504020207 网络25-2 - 阳灿 00:05:01

F: 2504010317 计算机25-3 - 刘亭瑞 00:20:53

G: 2504090208 计算机双学士25-2 - 闫迪 01:05:51

H: 2504090208 计算机双学士25-2 - 闫迪 00:59:41

A BLG回来了 #

Problem tags: 贪心排序

Prediction Difficulty：Medium

Actual Difficulty：Medium

Problem Statement#

16个队伍每轮自行排列进行1对1比赛，按照战力评胜负。赛制其实就是瑞士轮赛制，相同比分的队伍在同一组别比赛，3胜晋级，3败出局。目的让第二个队伍“T1”能够淘汰。

Solution#

考虑贪心，最差情况就是：

0-0组别最强的队伍打T1，第二强的队伍和第三强的队伍打，可以让T1和第三强的队伍掉到0-1组别。
0-1组别安排T1和第三强的队伍比赛，让T1进入0-2组别，第三强的队伍进入1-1组别；与此同时1-0组别让最强的队伍和第二强的队伍比赛，让第二强的队伍进入1-1组别。
1-1组别让第三强的队伍和第二强的队伍比赛，让第三强的队伍进入1-2组别。0-2组别让T1跟任意比他弱的队伍打，进入1-2组别。
最后在1-2组别，让T1和第三强的队伍打，即可让T1达成3败淘汰。

时间复杂度： $\mathcal{O}(T)$ 。

Std#

1
void solve() {
2
  vector<int> a(16);
3
  for (int i = 0; i < 16; i++) {
4
    cin >> a[i];
5
  }
6
  int t1 = a[1], S = 0;
7
  for (int i = 0; i < 16; ++i) {
8
    if (a[i] > t1) {
9
      S++;
10
    }
11
  }
12
  cout << (S >= 3 ? "We are the champions." : "Faker is forever.") << endl;
13
}

B 求数 #

Problem tags: 递推预处理

Prediction Difficulty：Medium-Hard

Actual Difficulty：Medium

Problem Statement#

略。

Solution#

如果每次询问时处理 $f(n)$ ，时间复杂度为 $\mathcal{O}(tn)$ 。考虑预处理 $1$ 到 $n$ 的 $f(n)$ 值，每次 $\mathcal{O}(1)$ 询问答案。预处理时，每算出一个 $f(i)$ ，就更新 $max$ 和 $min$ 的值。总时间复杂度 $\mathcal{O}(1e6+t)$ 。注意要开 long long。

Std#

1
const int N=1e6+7;
2
int f[N];
3
void init()
4
{
5
  f[1]=1;
6
  int maxn=f[1],minn=f[1];
7
  int sign=1;
8
  for(int i=2;i<N;i++)
9
  {
10
    f[i]=f[i-1]+sign*(maxn-minn)+i;
11
    sign=-sign; // 正负互换
12
    maxn=max(maxn,f[i]);
13
    minn=min(minn,f[i]);
14
  }
15
}
16
int n;
17
void solve()
18
{
19
  cin>>n;
20
  cout<<f[n]<<endl;
21
}
22
signed main()
23
{
24
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
25
  init();
26
  int T=1; cin>>T;
27
  while(T--){solve();}
28
  return 0;
29
}

C 刀剑神域：艾恩葛朗特的评分机关 #

Problem tags: 二分双指针贪心

Prediction Difficulty：Hard

Actual Difficulty：Hard

Problem Statement#

给定一个非降序整数序列 $[a_1,a_2,\ldots,a_n]$ 。定义子序列的评分为 $\frac{s_1 \cdot s_2 \cdot \ldots \cdot s_d}{d!}$ ，空序列评分为 1。序列的配置长度 = 在所有评分最大的子序列中，长度的最大值。

求：对每个前缀 $[a_1,a_2,\ldots,a_k]$ ，输出它的配置长度。

Solution1#

我们先来看如何求一个非降序序列 $s_1, s_2, \ldots, s_\ell$ 的配置长度。

如果我们选择一个长度为 $k$ 的子序列，为了获得最大评分，最优的选择就是取序列中最大的 $k$ 个元素。由于序列是非降序的，最大的 $k$ 个元素就是最后的 $k$ 个元素。因此，所有可能成为答案的候选子序列都是序列的后缀。

现在我们把从右往左数的第 $i$ 个元素除以 $i$ 。于是这个序列变成了：

\frac{s_1}{\ell}, \; \frac{s_2}{\ell-1}, \; \ldots, \; \frac{s_{\ell-1}}{2}, \; \frac{s_\ell}{1}.

注意到，原序列某个后缀的评分，等于在这个新序列中对应后缀的乘积。

原序列满足

s_1 \leq s_2 \leq \ldots \leq s_{\ell-1} \leq s_\ell.

而分母部分满足

\frac{1}{\ell} \leq \frac{1}{\ell-1} \leq \ldots \leq \frac{1}{2} \leq \frac{1}{1}.

把这两个条件结合起来，可以得到：

\frac{s_1}{\ell} \leq \frac{s_2}{\ell-1} \leq \ldots \leq \frac{s_{\ell-1}}{2} \leq \frac{s_\ell}{1},

因此，新序列依然是非降序的。

为了使新序列后缀的乘积最大，我们会选择新序列中所有 $\geq 1$ 的元素（这些元素必然形成一个后缀，因为新序列是非降序的）。如果新序列中有元素恰好等于 1，那么我们必须把它们也选进去，这样才能保证在最大评分的所有子序列中长度最大。

因此，序列 $s_1, s_2, \ldots, s_\ell$ 的配置长度，就是新序列

\frac{s_1}{\ell}, \; \frac{s_2}{\ell-1}, \; \ldots, \; \frac{s_{\ell-1}}{2}, \; \frac{s_\ell}{1}

的最长后缀长度，并且这个后缀中的每个元素都不小于 1。

接下来，我们要计算给定序列 $[a_1,a_2,\ldots,a_n]$ 的所有前缀的配置长度。

对某个前缀 $[a_1,a_2,\ldots,a_k]$ ，它的配置长度就是新序列

\frac{a_1}{k}, \; \frac{a_2}{k-1}, \; \ldots, \; \frac{a_{k-1}}{2}, \; \frac{a_k}{1}

的最长后缀长度，其中的每个元素都不小于 1。

我们可以用二分查找来求这个长度。注意不能显式构造每个前缀对应的“变换序列”，那样会太慢。相反，在二分的每一步，我们可以直接计算该位置对应的值，判断它是否 $\geq 1$ 。这样就能在 $\mathcal{O}(\log n)$ 的时间内求出每个前缀的配置长度。

时间复杂度：每个测试用例的时间复杂度为 $\mathcal{O}(n \log n)$ 。

Std1#

1
void slu() {
2
  int n;
3
  cin >> n;
4
  vector<int> a(n);
5
  for (int i = 0; i < n; i++) {
6
    cin >> a[i];
7
  }
8
  vector<int> res;
9
  for (int i = 0; i < n; i++) {
10
    int l = 1, r = i + 1;
11
    while (l <= r) {
12
      int m = (l + r) / 2;
13
      if (a[i - m + 1] >= m) {
14
        l = m + 1;
15
      } else {
16
        r = m - 1;
17
      }
18
    }
19
    res.push_back(r);
20
  }
21
  for (auto &x : res) {
22
    cout << x << ' ';
23
  }
24
  cout << endl;
25
}

Solution2#

对前缀 $A[1..k]$ 构造的「变换序列」

\frac{A_1}{k},\;\frac{A_2}{k-1},\;\ldots,\;\frac{A_k}{1}

是非降序的（证明见 Solution 1）。我们要找的是最长后缀满足其中所有元素 $\geq 1$ 。设该后缀长度为 $d_k$ ，则

\frac{A_{k-d_k+1}}{d_k}\geq 1,\; \frac{A_{k-d_k+2}}{d_k-1}\geq 1,\;\ldots,\; \frac{A_k}{1}\geq 1.

由于序列非降，最左边的限制最强，因此只需

A_{k-d_k+1}\geq d_k. \tag{*}

我们按 $k=1..n$ 顺序处理，维护当前最优长度 $d$ （即 $d_k$ ）。当 $k$ 增加 1 时，先令 $d$ 不变，然后尝试向前扩展一位：

只要 $d<k$ 且新的「最左元素」满足

A_{k-d}\geq d+1

就说明能把第 $k-d$ 个元素也拉进来，于是 $d\leftarrow d+1$ 。因为序列非降，每次扩展后仍保证 $(*)$ 对新的 $d$ 成立；否则停止扩展。

时间复杂度： $\mathcal{O}(n)$ 。

Std2#

略。

D 吃馒头 #

Problem tags: 二分

Prediction Difficulty：Medium-Hard

Actual Difficulty：Hard

Problem Statement#

有 $n$ 个人要一起吃掉 $k$ 个馒头。第 $i$ 个人吃一个馒头要 $t_i$ 秒，一次最多能连续吃 $a_i$ 个，然后必须休息 $b_i$ 秒，再重复吃。所有人同时开始吃时，吃完全部 $k$ 个馒头所需的最短时间。

Solution#

看到最大值最小或者最小值最大，我们就要考虑二分答案。假设当前答案时间为 $p$ 秒，对于第 $i$ 个人，设 $T = (t_i * a_i + b_i)$ ，在每 $T$ 秒可以吃掉 $a_i$ 个馒头，则在 $(p / T) * T$ 秒内可以吃掉 $(p / T) * a_i$ 个馒头，还剩下 $p \% T$ 秒可以吃馒头，设 $res = p \% T$ ，在最后的 $res$ 秒可以吃掉 $max(res / t_i, a_i)$ ，加到当前吃馒头的数量，以此可以推出 $n$ 个人在 $p$ 秒内吃掉的馒头的总和，与 $k$ 比较大小写一个 check 函数即可。

Std#

1
#include <bits/stdc++.h>
2
#define ll long long
3
#define int ll
4
using namespace std;
5

6
const int N = 2e5 + 7;
7

8
int n, k;
9
int t[N], a[N], b[N];
10

11
bool check(int x)
12
{
13
    int ans = 0;
14
    for (int i = 1; i <= n; i++)
15
    {
16
        int T = (a[i] * t[i] + b[i]);
17
        ans += (x / T) * a[i];
18
        int y = x % T;
19
        if (a[i] * t[i] >= y)
20
        {
21
            ans += y / t[i];
22
        }
23
        else
24
            ans += a[i];
25
        if (ans >= k)
26
            return 1;
27
    }
28
    return 0;
29
}
30

31
signed main()
32
{
33
    ios ::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
34
    int TT = 1;
35
    cin >> TT;
36
    while (TT--)
37
    {
38
        cin >> n >> k;
39
        for (int i = 1; i <= n; i++)
40
        {
41
            cin >> t[i];
42
        }
43
        for (int i = 1; i <= n; i++)
44
        {
45
            cin >> a[i];
46
        }
47
        for (int i = 1; i <= n; i++)
48
        {
49
            cin >> b[i];
50
        }
51
        int l = 0, r = 1e18 + 7;
52
        while (l < r)
53
        {
54
            int mid = (l + r) / 2;
55
            if (check(mid))
56
                r = mid;
57
            else
58
                l = mid + 1;
59
        }
60
        cout << l << '\n';
61
    }
62
    return 0;
63
}

E 计算器 #

Problem tags: 分支结构

Prediction Difficulty：Easy

Actual Difficulty：Easy

Problem Statement#

模拟两个数字的五种运算。

Solution#

模拟即可。注意乘法会爆 int，需要 long long 来进行存储。

Std#

1
int main()
2
{
3
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
4
  int TT;
5
  cin >> TT;
6
  while (TT--)
7
  {
8
    long long a, b;
9
    char op;
10
    cin >> a >> b >> op;
11
    if ((op == '%' || op == '/') && (b == 0))
12
    {
13
      cout << "No" << '\n';
14
      continue;
15
    }
16
    if (op == '+')
17
    {
18
      cout << a + b << '\n';
19
    }
20
    else if (op == '-')
21
    {
22
      cout << a - b << '\n';
23
    }
24
    else if (op == '*')
25
    {
26
      cout << a * b << '\n';
27
    }
28
    else if (op == '/')
29
    {
30
      cout << a / b << '\n';
31
    }
32
    else
33
    {
34
      cout << a % b << '\n';
35
    }
36
  }
37
}

F 边狱巴士是一款大概率发生小概率事件的游戏 #

Problem tags: 顺序结构数学贪心

Prediction Difficulty：Easy-Medium

Actual Difficulty：Easy-Medium

Problem Statement#

给定 $atk,add,n,a,b(a+b=n)$ ，第 $i$ 次发生攻击时的伤害为 $atk+i\cdot add$ 。普通硬币反面不攻击；不可摧毁硬币无论正反都攻击。求此技能总伤害的最小值与最大值。

Solution1#

记 $D_i=atk+i\cdot add$ 。最大值：令所有 $n$ 次都发生攻击（把普通硬币全为正面），有：

\text{max}=n\cdot atk+add\cdot\frac{n(n+1)}{2}

最小值：仅让 $b$ 次不可摧毁硬币发生攻击并占据最小序号 $1\ldots b$ ，有 $\text{min}=b\cdot atk$ ，即输出： $\text{max}=n\cdot atk+add\cdot\frac{n(n+1)}{2}$ 、 $\text{min}=b\cdot atk$

时间复杂度： $\mathcal{O}(1)$ 。

Std1#

1
void slu() {
2
  int atk, add, n, a, b;
3
  cin >> atk >> add >> n >> a >> b;
4
  int mn = b * atk;
5
  int mx = n * atk + add * (n * (n + 1) / 2);
6
  cout << mn << " " << mx << endl;
7
}

Solution2#

按攻击发生的序号从 $i=1$ 递增累加 $atk+i\cdot add$ ：最大值累加 $i=1\ldots n$ ，最小值累加 $i=1\ldots b$ 。

由输出量级：

\text{max}=n\cdot atk+add\cdot\frac{n(n+1)}{2}、\text{min}=b\cdot atk

可知，数据会爆int，但不会爆long long，所以需要使用64位long long进行存储。

时间复杂度： $\mathcal{O}(n)$ 。

Std2#

1
void slu() {
2
  int atk, add, n, a, b;
3
  cin >> atk >> add >> n >> a >> b;
4

5
  {
6
    int w = atk, ans = 0;
7
    for (int i = 0; i < b; i++) {
8
      ans += w;
9
    }
10
    cout << ans << ' ';
11
  }
12

13
  {
14
    int w = atk, ans = 0;
15
    for (int i = 0; i < n; i++) {
16
      w += add;
17
      ans += w;
18
    }
19
    cout << ans << endl;
20
  }
21
}

G hc_orz #

Problem tags: 后缀和

Prediction Difficulty：Medium

Actual Difficulty：Medium-Hard

Problem Statement#

找出每个 $hc$ 右边有多少 $orz$ 出现的总和。

Solution#

若考虑暴力求每个 $hc$ 能匹配的个数，时间复杂度为 $\mathcal{O}(n^2)$ ，会超时。

我们可以从后往前用一个 $cnt$ 计算 $orz$ 的数量，每次碰到 $hc$ 就加一次 $cnt$ ，也就是此位置 $hc$ 能匹配的 $orz$ 数量。时间复杂度 $\mathcal{O}(n)$ 。

Std#

1
const int N=1e6+7;
2
int n;
3
string s;
4
int a[N],m; // 用于记录 hc和 orz的位置
5
int suf; // 记录后缀的 orz数量
6
void solve()
7
{
8
    cin>>n;
9
    cin>>s;
10
    s=' '+s; // 保证字符串从 1开始遍历
11
    suf=m=0;
12
    for(int i=1;i<=n;i++)
13
    {
14
        if(i+1<=n&&s[i]=='h'&&s[i+1]=='c') a[++m]=i;
15
        if(i+2<=n&&s[i]=='o'&&s[i+1]=='r'&&s[i+2]=='z') a[++m]=i;
16
    }
17

18
    int ans=0;
19
    for(int i=m;i>=1;i--)
20
    {
21
        if(s[a[i]]=='o') suf++;
22
        else ans+=suf;
23
    }
24
    cout<<ans<<endl;
25
}
26
signed main()
27
{
28
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
29
    int T=1; cin>>T;
30
    while(T--){solve();}
31
    return 0;
32
}

H pre and suf #

Problem tags: 暴力枚举

Prediction Difficulty：Easy-Medium

Actual Difficulty：Medium-Hard

Problem Statement#

给定一个数组 $a$ ，与询问的 $b$ 数组拼接在一起，找出拼接后的最大公共前后缀。

Solution#

设拼接后的数组为 $c$ ，不管是长度为多少的最大公共前后缀，我们都要从前往后遍历 $c$ 数组，找出最大的 $l$ 满足 $c[l] = c[2n-l+1]$ ，此时 $l$ 则为答案。因此遍历一遍 $c$ 数组即可，时间复杂度 $\mathcal{O}(n)$ 。

Std#

1
const int N=1e6+7;
2
int n,q;
3
int a[N];
4
void solve()
5
{
6
  cin>>n>>q;
7
  for(int i=1;i<=n;i++) cin>>a[i];
8

9
  while(q--)
10
  {
11
    for(int i=n+1;i<=2*n;i++) cin>>a[i];
12

13
    int l=0;
14
    while(a[l+1]==a[2*n-l]&&l+1<=2*n) l++;
15
    cout<<l<<endl;
16
  }
17
}
18
signed main()
19
{
20
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
21
  int T=1; cin>>T;
22
  while(T--){solve();}
23
  return 0;
24
}