有一说一，觉得视频讲解写的挺好，除了第一题我是用自己的思路所以没听。
报数
作为 NOIP 的第一题，需要一道签到题。
有 $n$ 个数 $a_1,a_2,…,a_n$，你需要找到一个集合 S，使得 S 中严格大于 S 的平均数的数字个数尽量多。输出最多的个数。
注意：这里的集合是可重集，数字可以重复。
解题思路
显然，如果我们在集合中放了一个数，那么将比这个数小的所有数都放进去肯定可以促使平均数变小从而使得数字大小平均数的个数尽量多。也就是说最优解就在将数据从大到小排序后所有前缀中的其中之一。那么，最多就只剩下了n种情况。由于后一种情况之比前一种情况多一个数字，所以平均数的大小一定是不严格单调增的，用队列即可快速求出最大的个数。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n;
int h,t;
int a[N];
int sum,res;
int ans;
bool cmp(int a,int b){
return a<b;
}
int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
return x;
}
signed main(){
// freopen("1.in","r",stdin);
// freopen("2.out","w",stdout);
// while((cin>>n)){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
cin>>n;
ans=0;
sum=0;
queue<int> q;
for(int i=1;i<=n;i++){
a[i]=read();
}
sort(a+1,a+1+n);
h=t=1;
for(int i=1;i<=n;i++){
q.push(a[i]);
t++;
sum+=a[i];
//cout<<q.front()<<'\n';
while((!q.empty())&&q.front()*i<=sum){
q.pop();
h++;
}
//cout<<h<<' '<<t<<'\n';
ans=max(ans,t-h);
}
cout<<ans<<'\n';
return 0;
// }
}数列
作为 NOIP 的第二题，需要一道简单的dp题。
你有个 n 个点 m 条边的无向图，每条边都有红蓝两种颜色中的一种，保证红色的边形成了这个图的一个生成树。
你希望给这些边赋上边权，保证边权是 1∼m 的排列，使得红色的边是最小生成树。
希望这些边权形成的序列字典序最小，也就是先比较第一条边的边权，再比较第二条边的边权，依次类推。
提示：注意内存限制。
解题思路
这题在考场上只打了暴力，这题需要用到最小生成树的一种性质。
在最小生成树上的任意不直接相连的两边之间连一条边，那么一定会组成一个环，而如果想要让最小生成树保持不变，则这一条新加的边的值一定大于环中任意一条树边。
这一题就是运用到了上面的思路，对于红边与蓝边组成的环，蓝边的权值一定比环中红边的权值要大。所以我们只需在遇到蓝边时，将这条边与红边组成的环取出来，将其中未附值的红边按编号大小赋值，最后再赋值这一条蓝边即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int f[N],n,m;
int e[N],ne[N],h[N],idx,id[N];
int u[N],v[N],c[N];
int dep[N],fa[N];
int ans[N];
int rnk[N];
int cnt;
void add(int x,int y,int z){
e[++idx]=y;
ne[idx]=h[x];
h[x]=idx;id[idx]=z;
}
int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
return x;
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void dfs(int ver){
f[ver]=ver;
for(int i=h[ver];i;i=ne[i]){
int j=e[i];
if(f[j]) continue;
fa[j]=ver,dep[j]=dep[ver]+1;
rnk[j]=id[i];
dfs(j);
}
}
void merge(int x,int y){
vector<int> v;
x=find(x);
y=find(y);
while(x!=y){
if(dep[x]<dep[y]) swap(x,y);
v.push_back(rnk[x]),f[x]=fa[x],x=find(x);
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
if(!ans[v[i]]) ans[v[i]]=++cnt;
}
}
int main(){
n=read();
m=read();
for(int i=1;i<=m;i++){
// int u,v,c;
u[i]=read(),v[i]=read(),c[i]=read();
if(c[i]){
add(u[i],v[i],i);
add(v[i],u[i],i);
}
}
dfs(1);
for(int i=1;i<=m;i++){
if(c[i]){
if(!ans[i]) ans[i]=++cnt;
}
else {merge(u[i],v[i]);if(!ans[i])ans[i]=++cnt;}
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<' ';
}
}方差
作为 NOIP 的第三题，需要一个模拟退火题。
现在有 n 个区间 $[l_i,r_i][l_i,r_i]$，每个区间有个权值 $w_i$。我们把这 $n$ 个区间当成 $n$ 个点，如果两个区间它们之间有交（包括端点），那么我们就在这两个区间之间连边，形成了一个区间图。
现在希望你删除一些区间，使得每个连通块大小不超过 $k$。输出删除区间最小的权值和。
解题思路
不是很会讲，建议去看视频讲解。
复制一下题解？
可以发现，最后肯定是删除经过某些位置的所有区间。 记$dp[i]$ ，表示当前切到$i$ 这个位置，然后枚举上⼀段切什么地⽅$j$ ，然后考虑$[i,j]$之间的区间只保留价值最⼤的$ k$个，把其他的都删了，这样直接做是 $O（n^3log \ n）$的。从后往前枚举$j$ ，依次加⼊区间，然后⽤堆维护⼀下前$k$ ⼤即可，时间复杂度 $O(n^2log \ n)$，但是实际很快。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2510;
const long long INF=1e18;
int n,k;
struct node{
int l,r,w;
}a[N];
int pre[N];
long long f[N];
bool cmp(node a,node b){
return a.r<b.r;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].w;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
pre[i]=lower_bound(a+1,a+i,node({0,a[i].l,0}),cmp)-a-1;
f[i]=INF;
}
for(int i=0;i<n;i++){
priority_queue<int,vector<int>,greater<int> >q;
long long now=f[i];
for(int j=i+1;j<=n;j++){
if(pre[j]>=i){
q.push(a[j].w);
if(q.size()>k){
now+=q.top();
q.pop();
}
}
else{
now+=a[j].w;
}
f[j]=min(f[j],now);
}
}
cout<<f[n]<<'\n';
}还有最后一题与线段树有关，线段树我只会写板子，写不来。
