abc437

题面

A - 英尺

分值：100 分

题目描述

1 英尺等于 12 英寸。
请问 A 英尺 B 英寸换算成英寸是多少英寸？

约束条件

1. $1 \leq A \leq 8$
2. $0 \leq B \leq 11$
3. 所有输入值均为整数

输入格式

输入通过标准输入按以下格式给出：

A B

输出格式

将答案输出在一行中。省略单位（英寸）进行输出。

输入样例 1

6 7

输出样例 1

79

6 英尺 7 英寸换算成英寸为 $6 \times 12 + 7 = 79$ 英寸。

输入样例 2

4 11

输出样例 2

59

4 英尺 11 英寸换算成英寸为 $4 \times 12 + 11 = 59$ 英寸。

输入样例 3

8 0

输出样例 3

96

8 英尺 0 英寸换算成英寸为 $8 \times 12 + 0 = 96$ 英寸。

B - 幸运抽奖

题目描述

有一个 $H$ 行 $W$ 列的网格。每个格子中写着一个整数，所有整数互不相同。从上到下第 $i$ 行、从左到右第 $j$ 列的格子中写有整数 $A_{i,j}$。

现在，主持人喊出了 $N$ 个互不相同的整数 $B_1, \dots, B_N$。

对于每一行，计算出主持人喊出的整数中，有多少个出现在该行中。这些数量的最大值是多少？

约束条件

$1 \leq H \leq 3$
$1 \leq W \leq 5$
$1 \leq N \leq 90$
$1 \leq A_{i,j} \leq 90$
$A_{i,j}$ 互不相同
$1 \leq B_i \leq 90$
$B_i$ 互不相同
所有输入值均为整数

输入格式

输入通过标准输入给出，格式如下：

H W N
A_{1,1} ... A_{1,W}
...
A_{H,1} ... A_{H,W}
B_1
...
B_N

输出格式

输出一行，包含答案。

输入样例 1

3 4 5
12 3 5 7
6 10 11 9
1 2 4 8
2
4
9
6
11

输出样例 1

3

输入样例 2

3 5 2
81 63 31 16 15
30 3 6 54 24
26 41 48 64 66
44
79

输出样例 2

0

输入样例 3

3 5 12
78 19 70 58 83
12 30 80 20 27
48 71 8 43 82
82
30
43
8
80
70
20
78
12
71
19
48

输出样例 3

5

C - 驯鹿与雪橇 2

题目描述

有 $N$ 头驯鹿和 1 架雪橇。第 $i$ 头驯鹿的体重为 $W_i$，力量为 $P_i$。

对于每头驯鹿，需要选择是让它“拉雪橇”还是“乘坐雪橇”。
但是，拉雪橇的驯鹿的力量总和必须大于等于乘坐雪橇的驯鹿的体重总和。
最多可以让多少头驯鹿乘坐雪橇？

给定 $T$ 个测试用例。请分别回答每个用例。

约束条件

$1 \leq T \leq 10^5$
$1 \leq N \leq 3 \times 10^5$
$1 \leq W_i, P_i \leq 10^9$
所有输入值均为整数。
单个输入文件中所有 $N$ 的总和不超过 $3 \times 10^5$。

输入格式

输入通过标准输入给出，格式如下：

T
case_1
case_2
⋮
case_T

每个测试用例的格式如下：

N
W_1 P_1
W_2 P_2
⋮
W_N P_N

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

输入样例 1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

输出样例 1

2
0
6

D - 差之和

题目描述

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个长度为 $M$ 的正整数序列 $B = (B_1, B_2, \dots, B_M)$。

求 $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|$ 的值，并对 $998244353$ 取模。

约束条件

$1 \leq N, M \leq 3 \times 10^5$
$1 \leq A_i, B_j < 998244353$
所有输入值均为整数。

输入格式

输入通过标准输入给出，格式如下：

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M

输出格式

输出一行，包含答案。

输入样例 1

4 2
1 6 9 2
3 1

输出样例 1

26

输入样例 2

8 8
185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631
455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528

输出样例 2

529117255

E - 对数组排序

题目描述

有 $N+1$ 个序列 $A_0, A_1, \dots, A_N$。$A_i$ 定义如下：
. $A_0$ 是一个空序列。
. $A_i$ $(1 \le i \le N)$ 是在序列 $A_{x_i}$ $(0 \le x_i < i)$ 的末尾添加整数 $y_i$ 后得到的序列。

找出满足以下条件的排列 $P = (P_1, P_2, \dots, P_N)$（即 $(1, 2, \dots, N)$ 的一个排列）：
. 对于 $i = 1, 2, \dots, N-1$，满足以下条件之一：
. $A_{P_i}$ 在字典序上小于 $A_{P_{i+1}}$。
. $A_{P_i} = A_{P_{i+1}}$ 且 $P_i < P_{i+1}$。
换句话说，当将 $A_1, A_2, \dots, A_N$ 按字典序排列（当有多个相同的序列时，索引较小的在前）时，$P$ 就是该排列中出现的索引序列。

约束条件

$1 \leq N \leq 3 \times 10^5$
$0 \leq x_i < i$
$1 \leq y_i \leq 10^9$
所有输入值均为整数。

输入格式

输入通过标准输入给出，格式如下：

N
x_1 y_1
x_2 y_2
⋮
x_N y_N

输出格式

在一行中输出 $P_1, P_2, \dots, P_N$，用空格分隔。

输入样例 1

4
0 2
0 1
2 2
0 1

输出样例 1

2 4 3 1

解释：
$A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1)$，所以 $P = (2, 4, 3, 1)$。

输入样例 2

5
0 1
0 1
0 1
0 1
0 1

输出样例 2

1 2 3 4 5

输入样例 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

输出样例 3

3 8 10 5 9 6 7 1 4 2

F - 曼哈顿圣诞树 2

题目描述

在二维平面上有 $N$ 棵圣诞树。第 $i$ 棵（$1 \leq i \leq N$）圣诞树位于坐标 $(X_i, Y_i)$。

给你 $Q$ 个查询。请按顺序处理这些查询。每个查询是以下两种类型之一：

类型 1：以 1 i x y 的形式给出。将第 $i$ 棵圣诞树的坐标改为 $(x, y)$。
类型 2：以 2 L R x y 的形式给出。输出从坐标 $(x, y)$ 到第 $L, L+1, \dots, R$ 棵圣诞树中最远的圣诞树的曼哈顿距离。

这里，坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

约束条件

$1 \leq N, Q \leq 2 \times 10^5$
$-10^9 \leq X_i, Y_i \leq 10^9$
$1 \leq i \leq N$
$1 \leq L \leq R \leq N$
$-10^9 \leq x, y \leq 10^9$
所有输入值均为整数。

输入格式

输入通过标准输入给出，格式如下：

N Q
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N
query_1
query_2
⋮
query_Q

其中，第 $i$ 个查询 query_i 以下列两种格式之一给出：

1 i x y
2 L R x y

输出格式

根据问题描述中的说明，输出查询的答案，每个答案占一行。

输入样例 1

3 4
-1 -1
1 2
-2 1
2 1 2 0 0
2 1 3 -1 2
1 1 0 1
2 1 3 -1 2

输出样例 1

3
3
2

解释：
最初，第 1、2、3 棵圣诞树分别位于坐标 $(-1, -1)$、$(1, 2)$、$(-2, 1)$。
处理每个查询：

1. 从第 1、2 棵圣诞树到坐标 $(0, 0)$ 的曼哈顿距离分别为 $2$ 和 $3$。因此输出 $3$，即 $2, 3$ 中的最大值。
2. 从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $3$、$2$、$2$。因此输出 $3$，即 $3, 2, 2$ 中的最大值。
3. 将第 1 棵圣诞树的坐标改为 $(0, 1)$。第 1、2、3 棵圣诞树的坐标变为 $(0, 1)$、$(1, 2)$、$(-2, 1)$。
4. 从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $2$、$2$、$2$。因此输出 $2$，即 $2, 2, 2$ 中的最大值。

输入样例 2

5 7
-9 5
-2 -9
10 -6
9 8
2 9
1 3 -9 -6
2 3 4 2 7
1 4 -2 -10
2 1 2 0 -10
2 3 4 10 -9
2 3 4 8 7
2 5 5 0 2

输出样例 2

24
24
22
30
9

G - 彩色圣诞树

题目描述

今年的圣诞节季节已经结束，终于到了新年的时刻。高桥正在忙着进行大扫除，要收起圣诞树。

有一棵用三种颜色（红色、蓝色、绿色）装饰的灯泡装饰的圣诞树。圣诞树上有 $N$ 个灯泡，它们由 $N-1$ 条丝带连接。将灯泡视为顶点，丝带视为边，这个图是一棵树。

灯泡编号从 $1$ 到 $N$，丝带编号从 $1$ 到 $N-1$。丝带 $i$ 连接灯泡 $u_i$ 和 $v_i$。灯泡 $i$ 初始亮着红色（如果 $c_i$ 是 R），绿色（如果 $c_i$ 是 G），或蓝色（如果 $c_i$ 是 B）。

高桥正在考虑执行以下操作 $N-1$ 次来移除所有丝带：

1. 从尚未移除的丝带中选择一条，其两端的灯泡颜色不同，然后移除该丝带。

2. 设 $u$ 和 $v$ 是被移除丝带两端的灯泡。对于每个灯泡 $u$ 和 $v$，根据以下规则改变它们亮的颜色：

   • 如果之前亮红色，则改为亮绿色。
   • 如果之前亮绿色，则改为亮蓝色。
   • 如果之前亮蓝色，则改为亮红色。

确定高桥是否可以通过重复此操作来移除所有丝带。如果可能，输出一种方法。

给定 $T$ 个测试用例。请解决每个测试用例。

约束条件

$1 \leq T \leq 20000$
$2 \leq N \leq 2000$
$c_i$ 是 R、G 或 B。
$1 \leq u_i, v_i \leq N$
将灯泡视为顶点，丝带视为边，给定的图是一棵树。
$T, N, u_i, v_i$ 是整数。
单个输入文件中所有 $N^2$ 的总和不超过 $2000^2$。

输入格式

输入通过标准输入给出，格式如下：

T
case_1
case_2
⋮
case_T

每个测试用例的格式如下：

N
c_1 c_2 ... c_N
u_1 v_1
u_2 v_2
⋮
u_{N-1} v_{N-1}

输出格式

按顺序输出 case_1, case_2, ..., case_T 的答案，格式如下：

如果无法移除所有丝带，输出 No。

如果可能，设 $e_i$ 为第 $i$ 次操作移除的丝带编号，输出：

Yes
e_1 e_2 ... e_{N-1}

其中 $(e_1, e_2, \dots, e_{N-1})$ 必须是 $(1, 2, \dots, N-1)$ 的一个排列。

如果有多个解，任意一个都将被视为正确。

输入样例 1

3
4
GBBR
1 2
1 3
1 4
3
RRR
1 2
2 3
5
RGBRG
1 2
2 3
3 4
3 5

输出样例 1

Yes
1 3 2
No
Yes
1 4 2 3

解释：
对于第一个测试用例，例如，可以通过以下操作移除所有丝带：

1. 初始时，灯泡颜色依次（从灯泡 1 开始）为绿色、蓝色、蓝色、红色。
2. 移除丝带 1。移除后，灯泡颜色依次为蓝色、红色、蓝色、红色。
3. 移除丝带 3。移除后，灯泡颜色依次为红色、红色、蓝色、绿色。
4. 移除丝带 2。移除后，灯泡颜色依次为绿色、红色、红色、绿色。
   满足条件的 $(e_1, e_2, e_3)$ 是 $(1, 3, 2)$ 和 $(2, 3, 1)$，任意一个都将被视为正确。

对于第二个测试用例，无论你如何操作，都无法移除所有丝带。

反思

A

本题是一道签到题
根据题意可知：

$$ \text{总英寸数} = A \times 12 + B $$

由于题目的数据范围过小，可直接使用顺序结构求解
以下是我赛场时的代码

#include <bits/stdc++.h>
using namespace std;
int a,b;
int main(){
    cin>>a>>b;
    cout<<a*12+b;
}

B

题目的意思就是：题目要求计算每一行中主持人喊出的整数出现的个数，并输出这些个数的最大值
由于数据范围过小，可直接使用数组存储，不需要使用任何数据优化方案
思路：

1. 读入 $H,W,N$
2. 用二维数组 $A$ 存储矩阵
3. 用一个大小为 $91$ （∵ $1 \leq B_i \leq 90$）的布尔数组 isB 标记 $B$ 中的数
4. 对每一行遍历，统计这一行中有多少个数在 isB 中被标记为 true
5. 记录这些统计数的最大值并输出
   以下是我赛时的代码：

#include <bits/stdc++.h>
using namespace std;
int H,W,N,i,j,b,cnt,ma,a[5][6],fl[91];
int main(){
    cin>>H>>W>>N;
    for(i=0;i<H;i++) for(j=0;j<W;j++) cin>>a[i][j];
    for(i=0;i<N;i++){
        cin>>b;fl[b]=1;
    }
    for(i=0;i<H;i++){
        cnt=0;
        for(j=0;j<W;j++) if(fl[a[i][j]]) cnt++;
        if(cnt>ma) ma=cnt;
    }
    cout<<ma;
}

根据题目思路就可以得出代码，非常 Easy

C

这题我在赛时并没有得出正确程序
赛后，我邀请 deepseek 完成此题，我将对 deepseek 的内容进行阐述

算法：贪心
题目阐述：有 (N) 头驯鹿，每头驯鹿有体重 (W_i) 和力量 (P_i)。选择一部分驯鹿“乘坐雪橇”，剩下的“拉雪橇”。要求“拉雪橇”的驯鹿的力量总和 ≥ “乘坐雪橇”的驯鹿的体重总和。问最多可以让多少头驯鹿乘坐雪橇
问题转化为：在不超过总力量 (S) 的前提下，最多能选择多少头驯鹿，使得它们的 (W_i + P_i) 之和不超过 (S)。这是一个典型的贪心问题：按 (W_i + P_i) 从小到大选择，直到总和超过 (S)
对每个测试用例：

1. 读入 (N) 和每头驯鹿的 (W_i, P_i)
2. 计算总力量 (S = \sum P_i)
3. 计算每头驯鹿的 (a_i = W_i + P_i)，并排序
4. 从小到大累加 (a_i)，直到总和超过 (S)，累加的个数即为答案
   时间复杂度：$O(N \operatorname{log} N)$

这是 deepseek 给出的代码：

#include<iostream>
#include<algorithm>
using namespace std;
int T,N,i,cnt;
long long totalP,sum,W,P;
long long a[100005];

int main(){
    cin>>T;
    while(T--){
        cin>>N;
        totalP=0;
        for(i=0;i<N;i++){
            cin>>W>>P;
            a[i]=W+P;
            totalP+=P;
        }
        sort(a,a+N);
        sum=0;
        cnt=0;
        for(i=0;i<N;i++){
            if(sum+a[i]<=totalP){
                sum+=a[i];
                cnt++;
            }else{
                break;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

【知识要点】栈、队列、堆、优先队列

1. 栈(Stack)和队列(Queue)基础

1.1 基本概念对比

1.2 队列的详细定义

• 队列是C++标准库中的重要数据结构
• 允许删除的一端称为队头(Front)
• 允许插入的一端称为队尾(Rear)
• 空队列：队列中没有元素的状态
• 操作原则：先进先出(FIFO)

1.3 C++队列基本操作示例

#include<bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q; // 定义一个空队列
  
    for(int i=0; i<5; i++) {
        q.push(i); // 将i插入到队尾
    }
  
    q.emplace(32); // 将32放置到队尾，作用和push一样
  
    cout << q.size() << endl; // 输出队列中元素的个数
  
    while(!q.empty()) { // 当队列不为空时，继续循环
        cout << q.front() << endl; // 输出队列中的首元素
        q.pop(); // 将元素从队头删除
    }
  
    return 0;
}

1.4 队列queue的完整函数列表

• q.pop() - 删除queue的队头元素
• q.front() - 返回队列的队头元素，但不删除
• q.back() - 返回队列的队尾元素，但不删除
• q.push(arg) - 将元素arg插入到队列的队尾
• q.emplace(arg) - 将元素arg放置到队列的尾部(效果同push)
• q.size() - 返回队列中元素的个数
• q.empty() - 队列为空时返回true，否则false
• q.swap(q1) - 交换q和q1中的元素(交换底层数据结构)
• swap(q,q1) - 非成员函数，效果同成员函数swap

1.5 队列的应用场景

• BFS(广度优先搜索)算法
• 单调队列
• 缓冲区管理
• 任务调度

2. 堆(Heap)与优先队列(Priority Queue)

2.1 堆的基本概念

• 堆是一类特殊的数据结构，常用的是二叉堆
• 形式上是一个数组，本质上是一棵完全二叉树

• 分为大根堆和小根堆：

  • 大根堆：除根节点外，每个节点的值都大于等于其子节点的值

    • 公式表示：A[parent(i)] >= A[i]

  • 小根堆：除根节点外，每个节点的值都小于等于其子节点的值

    • 公式表示：A[parent(i)] <= A[i]
• 堆中的任一子树也还是堆

2.2 堆的基本操作

• push操作(插入)：往堆尾加入元素，并通过从下往上调整保持堆性质
• get操作(删除)：取出堆顶元素，用堆尾元素覆盖堆顶，再从上往下调整

2.3 优先队列的实现

C++中用 priority_queue实现堆的功能：

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 默认大根堆
    priority_queue<int> max_heap;
  
    // 小根堆定义方式
    priority_queue<int, vector<int>, greater<int>> min_heap;
  
    // 自定义结构体的优先队列
    struct Node {
        int u, len;
        bool operator < (const Node &x) const {
            return x.len < len; // 注意这里是反向定义，实现小根堆效果
        }
    };
  
    priority_queue<Node> custom_heap;
  
    return 0;
}

2.4 优先队列的操作函数

• push(Elem e) - 插入元素，时间复杂度O(log n)
• pop() - 删除顶部元素，O(log n)
• top() - 返回顶部元素，O(1)
• size() - 返回元素数量
• empty() - 判断是否为空

2.5 优先队列的特殊注意事项

1. 不支持除顶部外其他元素的访问和操作
2. 没有内置的clear()操作，需要手动实现：

void clear(priority_queue<int> &q) {
    while (!q.empty()) q.pop();
}

3. 访问top()前必须检查队列是否为空

3. 经典问题与解决方案

3.1 合并果子问题

问题描述：有n堆果子，每次合并两堆消耗体力值为两堆果子数之和，求最小总消耗。

解决方案：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
  
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        q.push(x);
    }
  
    while(q.size() > 1) {
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        ans += x + y;
        q.push(x + y);
    }
  
    cout << ans;
    return 0;
}

时间复杂度分析：O(n log n)

3.2 互数问题

问题描述：给定素数集合S，生成由S中素数乘积构成的"互数集合"，求第n小的互数。

解决方案：

typedef long long ll;

int main() {
    ll k, n;
    cin >> k >> n;
    vector<ll> primes(k);
    priority_queue<ll, vector<ll>, greater<ll>> heap;
    set<ll> seen;
  
    for(int i = 0; i < k; i++) {
        cin >> primes[i];
        heap.push(primes[i]);
        seen.insert(primes[i]);
    }
  
    ll humble = 1;
    for(int i = 0; i < n; i++) {
        humble = heap.top(); heap.pop();
        for(auto p : primes) {
            ll num = humble * p;
            if(seen.find(num) == seen.end()) {
                seen.insert(num);
                heap.push(num);
            }
        }
    }
  
    cout << humble;
    return 0;
}

时间复杂度分析：O(nk log n)

3.3 两个序列的最小N个和

问题描述：有两个长度为N的有序序列A和B，求A和B中各取一个数相加得到的N²个和中最小的N个。

解决方案：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

struct HeapNode {
    int x, val;
    bool operator < (const HeapNode &other) const {
        return val > other.val; // 小根堆
    }
};

int main() {
    int n, a[maxn], b[maxn], pos[maxn] = {0};
    priority_queue<HeapNode> q;
  
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
  
    // 初始时每个a[i]配b[0]
    for(int i = 0; i < n; i++) {
        q.push({i, a[i] + b[0]});
    }
  
    for(int i = 0; i < n; i++) {
        HeapNode tmp = q.top(); q.pop();
        cout << tmp.val << " ";
        int x = tmp.x;
        if(++pos[x] < n) {
            q.push({x, a[x] + b[pos[x]]});
        }
    }
  
    return 0;
}

时间复杂度分析：O(n log n)

4. 高级应用提示

1. Dijkstra算法优化：堆/优先队列可用于优化Dijkstra最短路径算法，将时间复杂度从O(V²)降低到O(E + V log V)
2. 单调队列：一种特殊的队列，可以高效解决滑动窗口最值问题
3. 多路归并：优先队列可以高效解决多路归并问题，如上面的最小N个和问题
4. Huffman编码：优先队列可用于构建最优前缀编码树

5. 总结

掌握这些基础数据结构及其应用场景，对于算法学习和编程竞赛至关重要。优先队列作为堆的高级抽象，在实际应用中更为方便，但理解其底层堆的原理同样重要。

【熟能生巧】

P9588 「MXOI Round 2」队列

题目描述

小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：

$1\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$；

$2\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素；

$3\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素；

$4$：这是第四种操作，表示查询队列中所有元素的最大值。

你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。

输入格式

第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【题目描述】。

输出格式

对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。

输入输出样例 #1

输入 #1

0 9
1 5
1 3
2 2
1 4
3 6
3 8
2 4
4
3 3

输出 #1

3
2
4
1

说明/提示

【样例解释 #1】

在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。

在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。

【数据范围】

设 $\sum x$ 表示单个测试点内 $x$ 之和。

对于 $100\%$ 的数据，$1 \le q \le 2\times 10^5$，$1 \le x,y,z \le 10^9$，$0 \le \sum x \le 2\times10^{14}$，保证在进行第二种操作前队列内元素个数不小于 $y$，在进行第三种操作前队列内元素个数不小于 $z$，在进行第四种操作前队列内元素个数大于 $0$。

特殊性质 A：没有第二种操作。

特殊性质 B：没有第三种操作。

特殊性质 C：没有第四种操作。

P2723 [USACO3.1] 丑数 Humble Numbers

题目描述

对于一给定的素数集合 $S = \{ p_1, p_2, ..., p_k \}$, 考虑一个正整数集合，该集合中任一元素的质因数全部属于 $S$。这个正整数集合包括，$p_1$、$p_1 \times p_2$、$p_1 \times p_1$、$p_1 \times p_2 \times p_3$ ...(还有其它)。该集合被称为 $S$ 集合的“丑数集合”。注意：我们认为 $1$不是一个丑数。

你的工作是对于输入的集合 $S$ 去寻找“丑数集合”中的第 $n$ 个“丑数”。保证答案可以用 32 位有符号整数表示。

补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第 $n$ 个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第 $n$ 小的数。

输入格式

输入的第一行是两个的整数，分别代表集合 $S$ 的大小 $k$ 和给定的参数 $n$。

输入的第二行有 $k$ 互不相同的整数，第 $i$ 个整数代表 $p_i$。

输出格式

输出一行一个整数，代表答案。

输入输出样例 #1

输入 #1

4 19
2 3 5 7

输出 #1

27

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1 \leq k \leq 100$。
• $1 \leq n \leq 10^5$。
• $2 \leq p_i < 2^{31}$，且 $p_i$ 一定为质数。

说明

题目翻译来自 NOCOW。

USACO Training Section 3.1

P1323 删数问题

题目描述

一个集合有如下元素：$1$ 是集合元素；若 $P$ 是集合的元素，则 $2\times P+1$，$4\times P+5$ 也是集合的元素。

取出此集合中最小的 $k$ 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 $m$ 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。

注：不存在所有数被删除的情况。

输入格式

只有一行两个整数，分别代表 $k$ 和 $m$。

输出格式

输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。

输入输出样例 #1

输入 #1

5  4

输出 #1

137915
95

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $1\le k,m\le300$。
• 对于 $100\%$ 的数据，保证 $1\le k,m\le3\times10^4$。

P2085 最小函数值

题目描述

有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

输出格式

输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

输入输出样例 #1

输入 #1

3 10
4 5 3
3 4 5
1 7 1

输出 #1

9 12 12 19 25 29 31 44 45 54

说明/提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10$,
$0 \leq B_i\le100$,
$0 \leq C_i\le10^4$。

【答案校对】

队列

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=800010;
int c,T,t,i,cnt,op,x,del,qwq,f[N],l[N],r[N],a[N*2],h=1,n=400005;
int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ 
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void update(int x,int l,int r,int ql,int qr,int k){
    int mid=(l+r)>>1;
    if(ql<=l&&r<=qr){
        a[x]=k;return;
    }
    if(ql<=mid) update(x*2,l,mid,ql,qr,k);
    if(qr>mid) update(x*2+1,mid+1,r,ql,qr,k);
    a[x]=max(a[x*2],a[x*2+1]);
}
int query(int x,int l,int r,int ql,int qr){
    int mid=(l+r)>>1,sum=0;
    if(ql<=l&&r<=qr){
        return a[x];
    }
    if(ql<=mid) sum=max(sum,query(x*2,l,mid,ql,qr));
    if(qr>mid) sum=max(sum,query(x*2+1,mid+1,r,ql,qr));
    return sum;
}
signed main(){
    cin>>c>>T;
    while(T--){
        op=read();
        if(op==1)
            x=read(),l[++t]=1,r[t]=x,update(1,1,n,t,t,x),f[t]=f[t-1]+x;
        else if(op==2){
            x=read();cnt=0;
            for(i=h;i<=t;++i){
                cnt+=r[i]-l[i]+1;
                if(cnt>=x){
                    cnt-=r[i]-l[i]+1;
                    l[i]+=x-cnt;del+=x-cnt;
                    if(l[i]>r[i])update(1,1,n,i,i,0),++h;
                    break;
                }
                del+=r[i]-l[i]+1;r[i]=l[i]=0;++h;
                update(1,1,n,i,i,0);
            }
        }
        else if(op==3){
            x=read();
            qwq=lower_bound(f+h,f+t+1,del+x)-f;
            printf("%lld\n",del+x-f[qwq-1]);
        }
        else printf("%lld\n",query(1,1,n,h,t));
    }
}

丑数

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,i,j,a[105],b[105],s[100005],zx;
signed main(){
    cin>>n>>m;
    for(i=1;i<=n;i++)
        cin>>a[i];
    s[0]=1;
    for(i=1;i<=m;i++){
        zx=pow(2,31)-1;
        for(j=1;j<=n;j++){
            while(a[j]*s[b[j]]<=s[i-1])
                b[j]++;
            if(a[j]*s[b[j]]<zx)
                zx=a[j]*s[b[j]];
        }
        s[i]=zx;
    }
    cout<<s[m];
}

删数问题

#include <bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
string p;
int k,m,s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>k>>m;
    q.push(1);
    while(k){
        int s=q.top();
        p=p+to_string(s);
        q.pop();
        q.push(s*2+1);
        q.push(s*4+5);
        k--;
    }
    cout<<p<<"\n";
    while(true){
        for(int i=0;i<p.size();i++){
            if(p[i+1]>p[i]){
                s++;
                p.erase(i,1);
                if(s>=m){
                    cout<<p;
                    exit(0);
                }
                break;
            }
        }
    }
}

最小函数值

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[10001],b[10001],c[10001],n,m,s[10000001],i,j,t;
signed main(){
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
    for(i=1;i<=n;i++) for(j=1;j<=100;j++) s[++t]=a[i]*j*j+b[i]*j+c[i];
    sort(s+1,s+1+t);
    for(i=1;i<=m;i++) cout<<s[i]<<" ";
}