E::::::::::::::::：小明的衣服（哈曼夫树）
题目描述
小明买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的所有衣服寄去染色厂，第 ii 件衣服的邮费为 ai 元，染色厂会按照小明的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小明， 请问小明要将 nn 件衣服染成不同颜色的最小代价是多少？
输入描述
第一行为一个整数 n ，表示衣服的数量。
第二行包括 n 个整数 a1,a2...an 表示第 i 件衣服的邮费为 ai 元。
（1≤n≤105,1≤ai≤109 ）
输出描述
输出一个整数表示小明所要花费的最小代价。
输入输出样例
示例 1
输入
5 5 1 3 2 1
输出
25
运行限制
最大运行时间：1s
最大运行内存: 256M
#include <iostream> #include <queue> using namespace std; long long ans; priority_queue<long long,vector<long long>,greater<long long> > q; int n; int main(){ cin>>n; for(int i=0;i<n;i++){ long long ai; cin>>ai; q.push(ai); } while(q.size()!=1){ long long a=q.top(); q.pop(); long long b=q.top(); q.pop(); ans+=a+b; q.push(a+b); } cout<<ans; return 0; }
F::::::::::::::::：蓝桥骑士（LIS求最长递增序列）
题目描述
小明是蓝桥王国的骑士，他喜欢不断突破自我。
这天蓝桥国王给他安排了 NN 个对手，他们的战力值分别为 a1,a2,...,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。
身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 N，表示对手的个数。
第二行包含 N 个整数 a1,a2,...,an，分别表示对手的战力值。
1≤N≤3×105，1≤ai≤109。
输出描述
输出一行整数表示答案。
输入输出样例
示例 1
输入
6 1 4 2 2 5 6
输出
4
#include <iostream> #include <algorithm> using namespace std; int n; long long a[300005]; long long dp[300005]; long long LIS(int n){ dp[1]=a[1]; int ans=2; for(int i=2;i<=n;i++){ if(dp[ans-1]<a[i]){ dp[ans]=a[i]; ans++; }else{ dp[lower_bound(dp+1,dp+ans,a[i])-dp]=a[i]; } } return ans-1; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cout<<LIS(n); return 0; }
G::::::::::::::::：蓝桥幼儿园（并查集）
题目描述
蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。
小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：
小明会用红绳连接两名学生，被连中的两个学生将成为朋友。
小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。
输入描述
第 1 行包含两个正整数 N,M，其中 N 表示蓝桥幼儿园的学生数量，学生的编号分别为 1∼N。
之后的第 2∼M+1 行每行输入三个整数，op,x,y：
如果 op=1，表示小明用红绳连接了学生 x 和学生 y 。
如op=2，请你回答小明学生 x 和 学生 y 是否为朋友。
1≤N,M≤2×105，1≤x,y≤N。
输出描述
对于每个 op=2 的输入，如果 x 和 y 是朋友，则输出一行 YES，否则输出一行 NO。
输入输出样例
示例 1
输入
5 5 2 1 2 1 1 3 2 1 3 1 2 3 2 1 2
输出
NO YES YES
#include <iostream> using namespace std; int n,m; int rel[200005]; int find(int x){ if(rel[x]==x) return x; return rel[x]=find(rel[x]); } void jiaru(int x,int y){ int x1=find(x); int y1=find(y); if(x1!=y1){ rel[x1]=y1; } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ rel[i]=i; } for(int i=1;i<=m;i++){ int op,x,y; cin>>op>>x>>y; if(op==1){ jiaru(x,y); }else{ if(find(x)==find(y)){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } } return 0; }
H::::::::::::::::：蓝桥幼儿园（并查集）
题目描述
小明在练习绝世武功， n 个练功桩排成一排，一开始每个桩的损伤为 0。
接下来小明会练习 m 种绝世武功，每种武功都会对 [l,r] 区间分别造成 [s,e] 的伤害。
这个伤害是一个等差序列。例如 l=1,r=4,s=2,e=8 ,则会对 1−4 号练功桩造成2，4，6，8 点损伤。
小明想让你统计一下所有练功桩的损伤的和。
输入描述
第一行输入 n,m，代表练功桩的数量和绝世武功的种类数。
接下来 m 行输入 4 个整数 l,r,s,e 。
1≤n≤107,1≤m≤3×105,1≤l,r≤n
输出描述
输出一个整数代表所有练功桩的损伤和， 题目保证所有输入输出都在 [[0,9×1018]
输入输出样例
示例 1
输入
6 2 1 5 2 10 2 4 1 1
输出
33
运行限制
最大运行时间：1s
最大运行内存: 512M
#include<iostream> using namespace std; //绝世武功(二阶差分数组) typedef long long ll; ll n,m,d,ans;//d：[s,e]公差 ll a[10000005],d1[10000005],d2[10000005]; //一阶差分数组d1，二阶差分数组d2 int main() { cin>>n>>m; for(int i=1;i<=m;i++){ ll l,r,s,e; cin>>l>>r>>s>>e; d=(e-s)/(r-l);//求出公差 d2[l]= d2[l]+s; d2[l+1]=d2[l+1]+d-s; d2[r+1]=d2[r+1]-d-e; d2[r+2]=d2[r+2]+e; } for(int i=1;i<=n;i++){ d1[i]=d1[i-1]+d2[i]; a[i]=a[i-1]+d1[i]; ans+=a[i]; } cout<<ans<<endl; return 0; }
