A 斗牛
描述
给定五个 0~9 范围内的整数 a1, a2, a3, a4, a5。如果能从五个整数中选出三个并且这三个整数的和为
10 的倍数（包括 0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结
果，显然如果有多个三元组满⾜和是 10 的倍数，剩下两个数之和对 10 取余的结果都是相同的；如果
选不出这样三个整数，则这五个整数的权值为 -1。
现在给定 T 组数据，每组数据包含五个 0~9 范围内的整数，分别求这 T 组数据中五个整数的权值。
【输⼊格式】
第⼀ 行⼀个整数 T (1<=T<=1000)，表示数据组数。
接下来 T 行，每 行 5 个 0~9 的整数，表示⼀组数据。
【输出格式】
输出 T 行，每 行⼀个整数，表示每组数据中五个整数的权值。
【样例输⼊】
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
【样例输出】
2
-1
-1
0
【解释】
在第⼀组（1 0 0 1 0）中，三元组 0 0 0 的和为 0，是 10 的倍数，剩余的 1 1 之和为 2，对 10 取余为
2。
在第⼆组中，不存在任何⼀个三元祖只和为 10 的倍数。
在第四组中，三元组 5 7 8 的和为 20，是 10 的倍数，剩余的 4 6 只和为 10，对 10取余为 0。
在第五组中，三元组 0 3 7 和三元组 0 4 6 的和都是 10，是 10 的倍数，但是根据简单的数论可知，如
果存在多个三元组满⾜情况，那么剩余数字的结果之和对 10 取余是相等的，在本例中和为 10，对 10
取余为 0。
思路
总共5个数字嘛，组合方式有限
写个脚本算出所有的组合方法
然后依次排除即可
AC代码
用了邪道方法跑了组合数
a = [0, 1, 2, 3, 4]
import itertools
for obj in list(itertools.combinations(a, 3)):
a, b, c = obj
_a = [0, 1, 2, 3, 4]
_a.pop(_a.index(a))
_a.pop(_a.index(b))
_a.pop(_a.index(c))
# print(_a)
print(
"""
if ((a[{}] + a[{}] + a[{}]) % 10 == 0)
return (a[{}] + a[{}])%10;
""".format(a, b, c, _a[0], _a[1])
)
# break
int find_loc(const vector<int> &a) {
// 下面的东西有些冗余，时间够的话删掉点。
if ((a[0] + a[1] + a[2]) % 10 == 0)
return (a[3] + a[4]) % 10;
if ((a[0] + a[1] + a[3]) % 10 == 0)
return (a[2] + a[4]) % 10;
if ((a[0] + a[1] + a[4]) % 10 == 0)
return (a[2] + a[3]) % 10;
if ((a[0] + a[2] + a[3]) % 10 == 0)
return (a[1] + a[4]) % 10;
if ((a[0] + a[2] + a[4]) % 10 == 0)
return (a[1] + a[3]) % 10;
if ((a[0] + a[3] + a[4]) % 10 == 0)
return (a[1] + a[2]) % 10;
if ((a[1] + a[2] + a[3]) % 10 == 0)
return (a[0] + a[4]) % 10;
if ((a[1] + a[2] + a[4]) % 10 == 0)
return (a[0] + a[3]) % 10;
if ((a[1] + a[3] + a[4]) % 10 == 0)
return (a[0] + a[2]) % 10;
if ((a[2] + a[3] + a[4]) % 10 == 0)
return (a[0] + a[1]) % 10;
return -1;
}
int fd_solver() {
int n;
vector<int> input(5);
vector<int> res;
int _;
scanf("%d", &n);
// res.resize(n);
for (int i = 0; i < n; i++) {
scanf("%d%d%d%d%d", &input[0], &input[1], &input[2], &input[3], &input[4]);
res.push_back(find_loc(input));
}
for (auto i:res) {
printf("%d\n", i);
}
return 0;
}
B 打地鼠
题目描述
给定 n 个整数 a1, a2, ..., an 和⼀个 d，你需要选出若⼲个整数，使得将这些整数从⼩到⼤排好序之
后，任意两个相邻的数之差都不⼩于给定的 d，问最多能选多少个数出来。
【输⼊格式】
第⼀ 行两个整数 n,d (1<=n<=10^5, 0<=d<=10^9)，分别表示整数个数和相邻整数差的下界。
第⼆ 行 n 个整数 a1, a2, ..., an (1<=ai<=10^9, 1<=i<=n)，表示给定的 n 个整数。
【输出格式】
仅⼀ 行⼀个整数，表示答案。
【样例输⼊】
6 2
1 4 2 8 5 7
【样例输出】
3
【解释】
注意，选出的数在排序后，相邻两数之差不⼩于给定值。
⽐如，对于给定值 2，[1 4 7] 是⼀个满⾜条件的选择⽅案，但是[1 4 5] 却不是，因为 5 - 4 = 1 < 2。
在本样例中，[1 4 7]，[1 4 8]，[1 5 7]，[1 5 8]，[2 4 7]，[2 4 8] 都是满⾜要求的选择⽅案，但是⽆论
如何都没有办法得到⼀个选出 4 个数且满⾜条件的⽅案，所以本样例的答案为 3。
思路
双指针，将这该序列排序即可
注意一下特殊数据点
2 0
1 2
2
2 999
1 2
0
// 自己脑补的特殊情况
1个数字，选不出，输出0
2个数字，如果满足则输出2，不满足则输出0
AC代码
bool cmp1(const int &a, const int &b) {
return a < b;
}
int fd_solver() {
int n, _;
LL d;// d是0-10^9
vector<LL> input;
scanf("%d%lld", &n, &d);
if(n==1){
printf("%d", 0);
return 0;
}
input.resize(n, 0);
for (int i = 0; i < n; i++) {
scanf("%d", &_);
input[i] = _;
}
if(n==2){
printf("%d", (input[1] - input[0] >= d)?2:0);
return 0;
}
sort(input.begin(), input.end(), cmp1);
int low = 0, fast = 1, cnt = 1; // low fast 为下标
while (fast <= input.size()) {
if ((input[fast] - input[low]) >= d) {
cnt++;
low = fast;
fast++;
} else {
fast++;
}
}
printf("%d", cnt);
return 0;
}
C 排队打饭
题目描述
下课了，有 n 位同学陆续赶到⻝堂进 行排队打饭，其中第 i 位同学的到达时间为 ai，打饭耗时为 ti，
等待时间上限为 bi，即如果其在第 ai+bi 秒的时刻仍然没有轮到他开始打饭，那么他将离开打饭队列
另寻吃饭的地⽅。问每位同学的开始打饭时间，或者指出其提前离开了队伍（如果这样则输出 -1）。
【输⼊格式】
第⼀ 行⼀个整数 n (1<=n<=10^5)，表示来打饭的同学数量。
接下来 n 行，每 行三个整数 ai,ti,bi (1<=ai,ti,bi<=10^9, 1<=i<=n)，分别表示每位同学的到达时间、打
饭耗时、等待时间上限。
保证 a1<a2<...<an
【输出格式】
⼀ 行 n 个整数，表示每位同学的开始打饭时间或者 -1（如果该同学提前离开了队伍）。
【样例输⼊】
4
1 3 3
2 2 2
3 9 1
4 3 2
【样例输出】
1 4 -1 6
【解释】
第⼀个同学在 1 时刻到达队列，需要 3 个单位时间才能打好饭（也就是说如果在 1 时刻开始打饭，那
么将在 1 + 3 = 4 时刻打好饭离开），最⻓等待时间为 3 个单位时间（也就说如果在到达队列之后的 3
单位时间后还没开始给他打饭，他就忍耐不了离开了）。
在本样例中，
1 时刻：第⼀个同学在 1 时刻到达队列，同时开始了打饭操作（对应输出的第⼀个值为 1）。
2 时刻：在 2 时刻，第⼆个同学加⼊了队列，给第⼆个同学打饭需要 2 个单位时间，但是如果在等待
了 2 个单位时间没给第⼆个同学打饭的话，第⼆个同学将离开。
3 时刻：在 3 时刻，第三个同学加⼊了队列，给第三个同学打饭需要 9 个单位时间，但是如果在等待
了 1 个单位时间没给第三个同学打饭的话，第三个同学将离开，换句话说，如果在 3 （到达时刻） + 1
（可等待时间⻓度）= 4 时刻还没给第三个同学打饭，那么第三个同学将离开。
4 时刻：第⼀个同学在时刻 4 打完饭离开，同时队列⾥的第⼆个同学开始打饭（对应输出的第⼆个值
为 4），此时第三个同学没有达到饭，所以第三个同学就在时刻 4 离开了队伍（对应输出的第三个值
为 -1）。同时，在时刻 4，第四个同学也加⼊了队列，第四个同学最⻓等待到 4（到达时刻）+ 2 （可
等待时间⻓度）= 6 时刻。
5 时刻：5 时刻还在给第⼆个同学打饭，第四个同学还在队列⾥⾯排队。
6 时刻：6 时刻，第⼆个同学打饭完成，同时第四个同学开始打饭（对应输出的第四个值为 6）。
根据上⾯描述的过程，输出为 1 4 -1 6。
思路
PAT上银行模拟的简化版，用队列就行了，不用考虑太多东西
AC代码
struct student {
int id = 0;
int ai = 0;
int ti = 0;
int bi = 0;
student() = default;
student(int i, int a, int t, int b) : id(i), ai(a), ti(t), bi(b) {};
};
int n;
queue<student> stu_vec;
bool cmp1(const student &s1, const student &s2) {
// 这样排，先到的先考虑，后到的后考虑
if (s1.ai != s2.ai) {
return s1.ai < s2.ai;
} else {
return s1.bi < s2.bi;
}
}
int fd_solver() {
scanf("%intd", &n);
int _1, _2, _3;
for (int i = 0; i < n; i++) {
scanf("%intd%intd%intd", &_1, &_2, &_3);
stu_vec.push(student(i, _1, _2, _3));
}
// 保证了到达时间，不用sort
// sort(stu_vec.begin(), stu_vec.end(), cmp1);
int T = 0;
if (n == 1) {
printf("%intd", stu_vec.front().ai);
return 0;
}
bool flag = true;
// res.push_back(stu_vec[0].ai);
while (!stu_vec.empty()) {
student current = stu_vec.front();
if (T >= current.ai && T <= (current.ai + current.bi)) {
stu_vec.pop();
if (flag) {
printf("%d", T);
flag = false;
} else {
printf(" %d", T);
}
T += current.ti;
} else if (T < current.ai) {
T++;
} else {
if (flag) {
printf("%d", -1);
flag = false;
} else {
printf(" %d", -1);
}
stu_vec.pop();
}
}
return 0;
}
D 二叉搜索树
这里不是最好的方法
题目描述
给定⼀个 1~n 的排列 P，即⻓度为 n，且 1~n 中所有数字都恰好出现⼀次的序列。现在按顺序将排列
中的元素⼀⼀插⼊到初始为空的⼆叉搜索树中（左⼩右⼤），问最后每个节点的⽗亲节点的元素是什
么。特别地，根节点的⽗亲节点元素视为 0。
【输⼊格式】
第⼀ 行⼀个整数 n (1<=n<=10^5)，表示排列 P 中的元素个数。
第⼆ 行 n 个整数 p1, p2, ..., pn (1<=pi<=n, 1<=i<=n)，表示给定的排列。
【输出格式】
⼀ 行 n 个整数，其中第 i 个整数 ai 表示元素 i 对应节点的⽗亲节点的元素。特别地，根节点的⽗亲节
点元素视为 0。
D.⼆叉搜索树
【样例输⼊】
5
2 3 5 1 4
【样例输出】
2 0 2 5 3
【样例解释】
最后建出来的⼆叉搜索树如下：
2
/ \
1 3
\
5
/
4
1 的⽗亲为 2，2 为根结点，所以⽗亲为 0，3 的⽗亲为 2，4 的⽗亲为 5，5 的⽗亲为 3。
思路(后来听别人讲解了一下，然后想明白了）
按照BST的规则，如果一个序列的输入是从小到大的，那么每个节点的父亲节点，一定是这个点对应输入序列的前一个数或者后一个数所对应的节点。
所以，再进一步说，现在输入序列如果是不按序的，那么我们对于已经输入的序列进行排序（MAP），那么每一个点对应的父亲节点，一定是这个点对应输入序列的前一个数或者后一个数所对应的节点中，较晚输入的那个。
也许这么讲很抽象，在代码中的注释可以仔细看一下
AC 代码（后来做出来的）
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
using namespace std;
int res[100005];
int main(){
int N;
map<int,int> m;
scanf("%d",&N);
for(int i=0;i<N;i++){
int temp;
scanf("%d",&temp);
map<int,int>::iterator it=m.insert({temp,i}).first;
if (it == m.begin()&&next(it)==m.end()) {
// CASE 1 当前MAP为空的情况，直接插入，并且其父节点为0
res[temp]=0;
}
else if(it == m.begin()){
// CASE 2 当前插入节点为第一个节点的时候，根据MAP的性质，数值小的节点在前面
// 排在MAP最前面的，值最小，一定是最左节点
// 则其父节点一定是排在第二个的节点。
res[temp]=next(it)->first;
}
else if(next(it)==m.end()) {
// CASE 3 当前插入节点为最后一个节点的时候，根据MAP的性质，健值大的节点在后面
// 排在MAP最后面的，值最大，一定是最右节点
// 则其父节点一定是排在倒数第二个节点。
res[temp]=prev(it)->first;
}
else{
// CASE 4 当前插入节点为中间节点的时候，思路与刚才相同
map<int,int>::iterator t;
// 此时比较的不是值，而是其前一个或者后一个节点的位置
if(prev(it)->second>next(it)->second){
t=prev(it);
}
else{
// CASE 5
t=next(it);
}
res[temp]=t->first;
}
}
for(int i=1;i<=N;i++){
printf("%d",res[i]);
if(i!=N)
printf(" ");
}
}
AC 50% 的代码
struct node {
int data = 0;
node *lchild = nullptr;
node *rchild = nullptr;
// node *father = nullptr;
node() = default;
};
int res = 0;
map<int, int> resDict;
void BST_insert(node *&r, int data, int father) {
if (r == nullptr) {
r = new node;
r->data = data;
res = father;
} else {
if (data < r->data) BST_insert(r->lchild, data, r->data);
else BST_insert(r->rchild, data, r->data);
}
}
int fd_solver() {
int n, _;
scanf("%d", &n);
node *root = nullptr;
for (int i = 0; i < n; i++) {
scanf("%d", &_);
BST_insert(root, _, 0);
resDict[_] = res;
res = 0;
}
printf("%d", resDict[1]);
for (int i = 2; i <= n; i++) {
printf(" %d", resDict[i]);
}
return 0;
}
E 序列
题目描述
给定⼀个⻓为 n 的序列 A，其中序列中的元素都是 0~9 之间的整数，对于⼀个⻓度同样为 n 整数序列
B，定义其权值为 |A_i-B_i| (1<=i<=n) 之和加上 (B_j-B_j+1)^2 (1<=j<n) 之和。求所有⻓为 n 的整数序
列中，权值最⼩的序列的权值是多少。
【输⼊格式】
第⼀ 行⼀个整数 n (1<=n<=10^5)，表示序列 A 的⻓度。
第⼆ 行 n 个整数 a1, a2, ..., an (0<=ai<=9, 1<=i<=n)，表示序列 A 中的元素。
【输出格式】
E.序列
仅⼀ 行⼀个整数，表示答案。
【样例输⼊】
6
1 4 2 8 5 7
【样例输出】## 标题 ##
11
【解释】
A 数组是 [1 4 2 8 5 7]
B 数组可以是 [3 4 4 5 5 6]。
权值为 |A_i - B_i| (1<=i<=n) 之和加上 (B_j - B_j+1)^2 (1<= j <n) 之和。
权值第⼀部分|A_i - B_i| (1<=i<=n)之和为：
|1 - 3| + |4 - 4| + |2 - 4| + |8 - 5| + |5 - 5| + |7 - 6| = 2 + 0 + 2 + 3 + 0 + 1 = 8
权值第⼆部分(B_j - B_j+1)^2 (1<= j <n) 之和为：
(3 - 4)^2 + (4 - 4)^2 + (4 - 5)^2 + (5 - 5)^2 + (5 - 6)^2 = 1 + 0 + 1 + 0 + 1 = 3
所以总权值为 8 + 3 = 11。
思路
有难度的DP题目，大概是这么想的
给定⼀个⻓为 n 的序列 A，其中序列中的元素都是 0~9 之间的整数，对于⼀个⻓度同样为 n 整数序列 B，定义其权值为
dp[i][x]表示第B的第i个位置如果是x，那么B的总权值和为dp[i][x]，计上一轮次中的最佳权重为 best_x。则有
dp[i][x] = dp[i-1][best_x] + |Ai-x| + (x-best_x)^2
考虑一下边界问题，不难发现i=1的时候只有绝对值项无平房项
dp[1][x] = |A1-x|
感觉自己在找best_x的路上发生了挫折，后来索性就直接三层循环走起
AC代码
int fd_solver() {
// 这个DP好JB难写...
// 不管咋先骗点分
int n;
LL dp[maxSize][10];
scanf("%d", &n);
LL _;
vector<LL> A(n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &_);
A[i] = _;
}
if (n == 1) {
printf("0");
return 0;
}
for (int i = 0; i <= 9; i++) {
dp[1][i] = abs(i - A[1]);
}
for (int i = 1; i <= n; i++) {
for (int x = 0; x <= 9; x++) {
dp[i][x] = dp[i - 1][0] + (x) * (x) + abs(x - A[i]);
for (int y = 1; y <= 9; y++) {
dp[i][x] = min(dp[i][x], dp[i - 1][y] + (x - y) * (x - y) + abs(x - A[i]));
}
}
}
LL Min = dp[n][0];
for (int i = 1; i <= 9; i++) {
Min = min(Min, dp[n][i]);
}
printf("%lld", Min);
return 0;
}
