文章目录
A.斗牛B.打地鼠C.排队打饭D、二叉搜索树E、序列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 ⾏，每⾏⼀个整数，表⽰每组数据中五个整数的权值。
【样例输⼊】41 0 0 1 01 0 0 8 63 4 5 6 74 5 6 7 8【样例输出】2-1-10
【解释】
在第⼀组（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个，我们完全可以使用暴力开三层for循环判断所有情况，具体看代码。时间复杂度为O(n3)O(n^3)O(n3)。
AC代码：
/**邮箱：unique_powerhouse@*blog:/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h>//POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 1e5;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//int t,nums[5];int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>t){while(t--){int ans=0,flag=0;rep(i,0,4){cin>>nums[i];ans+=nums[i];}rep(i,0,4){rep(j,i+1,4){rep(k,j+1,4){if((nums[i]+nums[j]+nums[k])%10==0){ans=ans-nums[i]-nums[j]-nums[k];flag=true;break;}}if(flag)break;}if(flag)break;}if(flag)cout<<ans%10<<endl;else cout<<"-1"<<endl;}}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 21 4 2 8 5 7【样例输出】3
解题思路：这是一道简单的贪心题，我们先排序构造一个递增序列。再从中贪心选择最好的结果统计即可。具体看代码。时间复杂度为O(n)O(n)O(n)。
AC代码：
/**邮箱：unique_powerhouse@*blog:/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h>//POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 1e5+2;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//int n,d,a[maxn];int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n>>d){rep(i,0,n-1)cin>>a[i];sort(a,a+n);//排序//开始遍历，统计最大值。int ans=1,temp=a[0];rep(i,1,n-1){if(a[i]-temp>=d){temp=a[i];ans++;}}cout<<ans<<endl;}return 0;}
C.排队打饭
原题：下课了，有 n 位同学陆续赶到⻝堂进⾏排队打饭，其中第 i 位同学的到达时间为 aia_iai，打饭耗时为 tit_iti，等待时间上限为 bib_ibi，即如果其在第 (ai+bi)(a_i+b_i)(ai+bi) 秒的时刻仍然没有轮到他开始打饭，那么他将离开打饭队列，另寻吃饭的地⽅。问每位同学的开始打饭时间，或者指出其提前离开了队伍（如果这样则输出 -1）。
【输⼊格式】 第⼀⾏⼀个整数 n (1<=n<=10^5)，表⽰来打饭的同学数量。 接下来 n ⾏，每⾏三个整数 ai,ti,bia_i,t_i,b_iai,ti,bi(1≤ai,ti,bi≤1091 \leq a_i,t_i,b_i\leq 10^91≤ai,ti,bi≤109 1≤i≤n1\leq i \leq n1≤i≤n)，分别表⽰每位同学的到达时间、打 饭耗时、等待时间上限。 保证 a1a_1a1<a2a_2a2<…<ana_nan
【输出格式】 ⼀⾏ n 个整数，表⽰每位同学的开始打饭时间或者 -1（如果该同学提前离开了队伍）。
【样例输⼊】41 3 32 2 23 9 14 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。
解题思路：这道题是一道模拟题，我们开一个三个数组用来存放每个同学对应的属性，设初始时间为第一个同学的到达时间，遍历这个数组模拟即可，要注意存放每个同学的打饭时间，若打不了饭则存-1，同时打饭成功后要更新时间。
AC代码：
/**邮箱：unique_powerhouse@*blog:/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h>//POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 1e5;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//int n;//打饭学生的数量。int a[maxn],t[maxn],b[maxn],result[maxn];//每个学生对应的到达时间，打饭耗时和等待时间。int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n){rep(i,0,n-1)cin>>a[i]>>t[i]>>b[i];int temp=a[0]+t[0];//对于第一个人我们直接是用来记录时间的初始值。result[0]=a[0];rep(i,1,n-1){if(a[i]+b[i]<temp){result[i]=-1;}else{if(a[i]>=temp){temp=a[i]+t[i];result[i]=a[i];}else{if(b[i]>=temp-a[i]){result[i]=temp;temp+=t[i];}elseresult[i]=-1;}}}rep(i,0,n-1){cout<<result[i]<<" ";}cout<<endl;}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。
【样例输⼊】52 3 5 1 4【样例输出】2 0 2 5 3
【样例解释】
最后建出来的⼆叉搜索树如下：
1 的⽗亲为 2，2 为根结点，所以⽗亲为 0，3 的⽗亲为 2，4 的⽗亲为 5，5 的⽗亲为 3。
解题思路：题目考察的就是关于二叉搜索树的建立，我们按要求建树即可，注意我们在建的过程中就要保存每个所建结点父结点的值，利用father数组存储。建完之后按顺序输出即可。时间复杂度为O(n2)O(n^2)O(n2)。
AC代码：
/**邮箱：unique_powerhouse@*blog:/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h>//POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 1e5+2;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//struct node{int val;//结点值node *left;//左子树node *right;//右子树。};int a[maxn],father[maxn];//a数组存储输入数据，result数组存储父节点的值。int n;//排列数。int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n){node *T=new node;//建树。T->val=0;T->left=T->right=NULL;rep(i,1,n)cin>>a[i];rep(i,1,n){node *p=T;while(1){//左小右大，根据这个规则进行建树。if(a[i]>p->val){if(p->right)p=p->right;else{//说明为空，我们在此建立。node *q=new node;q->val=a[i];q->left=q->right=NULL;p->right=q;break;}}else{if(p->left)p=p->left;else{node *q=new node;q->val=a[i];q->left=q->right=NULL;p->left=q;break;}}}//这里我们需要记录父结点的值，也就是p。father[a[i]]=p->val;}rep(i,1,n)cout<<father[i]<<" ";cout<<endl;}return 0;}
E、序列
给定⼀个⻓为 n 的序列 A，其中序列中的元素都是 0~9 之间的整数，对于⼀个⻓度同样为 n 整数序列B，定义其权值为 ∣Ai−Bi∣(1≤i≤n)|A_i-B_i| (1\leq i \leq n)∣Ai−Bi∣(1≤i≤n) 之和加上 (Bj−Bj+1)2(1≤j<n)(B_j-B_{j+1})^2 (1\leq j <n)(Bj−Bj+1)2(1≤j<n) 之和。求所有长为 n 的整数序列中，权值最小的序列的权值是多少。
【输⼊格式】 第⼀⾏⼀个整数 n (1≤n≤1051\leq n \leq 10^51≤n≤105)，表⽰序列 A 的⻓度。 第⼆⾏ n 个整数 a1a_1a1, a2a_2a2, …, ana_nan (0≤ai≤90 \leq a_i \leq 90≤ai≤9, 1≤i≤n1 \leq i \leq n1≤i≤n)，表⽰序列 A 中的元素。
【输出格式】仅⼀⾏⼀个整数，表⽰答案。
【样例输⼊】61 4 2 8 5 7【样例输出】11
【解释】
A 数组是 [1 4 2 8 5 7]
B 数组可以是 [3 4 4 5 5 6]。
权值为 ∣Ai−Bi∣(1≤i≤n)|A_i-B_i| (1\leq i \leq n)∣Ai−Bi∣(1≤i≤n) 之和加上 (Bj−Bj+1)2(1≤j≤n)(B_j-B_j+1)^2 (1\leq j \leq n)(Bj−Bj+1)2(1≤j≤n) 之和。
权值第⼀部分 ∣Ai−Bi∣(1≤i≤n)|A_i-B_i| (1\leq i \leq n)∣Ai−Bi∣(1≤i≤n) 之和为：
∣1−3∣+∣4−4∣+∣2−4∣+∣8−5∣+∣5−5∣+∣7−6∣=2+0+2+3+0+1=8|1 - 3| + |4 - 4| + |2 - 4| + |8 - 5| + |5 - 5| + |7 - 6| = 2 + 0 + 2 + 3 + 0 + 1 = 8∣1−3∣+∣4−4∣+∣2−4∣+∣8−5∣+∣5−5∣+∣7−6∣=2+0+2+3+0+1=8
权值第⼆部分 (Bj−Bj+1)2(1≤j<n)(B_j-B_{j+1})^2 (1\leq j < n)(Bj−Bj+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(3 - 4)^2 + (4 - 4)^2 + (4 - 5)^2 + (5 - 5)^2 + (5 - 6)^2 = 1 + 0 + 1 + 0 + 1 = 3(3−4)2+(4−4)2+(4−5)2+(5−5)2+(5−6)2=1+0+1+0+1=3
所以总权值为8+3=118 + 3 = 118+3=11。
解题思路：这道题是一道暴力枚举型dp题。因为对于B序列我们只知道它是一个长为n的序列。且对于给出的计算权值公式我们也暂时没有发现构建什么序列能使其最小。但由于给出的数据范围只有0~9，我们是完全可以枚举的。又因为计算总权值之和的问题我们可以通过组合子问题的解来求解，这同样符合dp的思想。所以我们关键就是找状态点。对于初始状态，即长度为1的时候，我们最小权值之和自然只要第一部分的权值之和，即abs(j−a[1])。对于接下来的状态：abs(j-a[1])。对于接下来的状态：abs(j−a[1])。对于接下来的状态：我们可以设dp[i][j]dp[i][j]dp[i][j]为长度为iii且第iii位jjj的状态，即最小权值之和。我们不断增加iii的长度直至nnn，同时也不断枚举每个位置上的数值不断比对得出最小权值之和，对于最终状态dp[n][j]dp[n][j]dp[n][j]，我们还需要在遍历一次，因为最后一次填的最后一个所对应的最小权值之和都不一样，我们要找其中最小的那个，这就是答案了。
AC代码：
/**邮箱：unique_powerhouse@*blog:/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h>//POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 1e5+2;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//int n,a[maxn],dp[maxn][10];int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n){rep(i,1,n)cin>>a[i];memset(dp,inf,sizeof(dp));rep(i,0,9)dp[1][i]=abs(i-a[1]);//对于长度为1的自然只是绝对值。.rep(i,2,n){rep(j,0,9){rep(k,0,9){dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(a[i]-j)+(k-j)*(k-j));}}}int ans=inf;rep(i,0,9){ans=min(ans,dp[n][i]);}cout<<ans<<endl;}return 0;}
