@Venous
2018-02-22T22:08:26.000000Z
字数 4129
阅读 1007
考试
本次考试排名:Rank23
本次考试题目推荐:数字游戏(细节巨多),麦乐鸡翅(可后悔堆)
板子:次小生成树(数据较弱)
今天没有心路历程(Angry),要加油了
对自己算作一次警告吧
认识到了游泳的巨大安全隐患之后,小朋友们都决定不去游泳了。于是,游泳馆冷清了下来。为了能因时制宜、因事制宜,游泳馆决定在游泳项目之外,还开设头脑风暴项目。头脑风暴当中有这样一道题目:给出一个LEN位的数字A,你可以删除数字A当中的N位,删除之后得到一个LEN-N位的数字B,你的目标就是使这个数字B最小。
对于 50%的数据,LEN<=100000.
对于 100%的数据,LEN<=5000000 , 0<=N<=LEN.
利用单调栈,从前往后尽力去维护递增,只要仍有删除次数就维护下去。说白了是贪心即可(每次删除左边第一个比右边大的)
好了,上代码
int Max=cnt-N;
for(int i=1;i<=cnt;i++)
{
while(a[i]<zhan[top]&&N&&top)
top--,N--;
zhan[++top]=a[i];
}
bool flag=0;
for(int i=1;i<=top&&i<=Max;i++)
{
if(!flag&&!zhan[i])continue;
flag=1;
printf("%d",zhan[i]);
}
if(!flag)puts("0");
在太行山路上,有一家麦乐鸡翅的生意火爆。因为好吃,所以卖的特别好。排队的人就特别多,经常有很多人买不到鸡翅。鸡翅会在每分钟烤出个,每分钟也只会卖给一个客人,第i个客人需要买个。因为生意火爆,老板可以选择在这分钟不卖给这个客人鸡翅,或者卖给这个顾客他需要的鸡翅,如果现在剩余的鸡翅不够,那就肯定不能卖给这个客人。无论这个客人能否买到鸡翅,他必须离开队伍。现在给定 N 分钟,且已经知道每分钟烤出的鸡翅个数,也知道每个客人需要鸡翅的个数,现在老板想知道,如何合理安排卖给与拒绝,最多可以满足多少人
50% 数据保证 N<=1000
100% 1<=N<=250000 Xi,Yi 都在[0,10^9]范围内
弄一个大根堆出来,然后后悔就OK了,
甚是简单(那你怎么不现切)
rg ll sum=0,now;
for(rg int i=1;i<=n;i++)
{
sum+=a[i];
if(!chi.empty())now=chi.top();
if(sum>=b[i])
{
sum-=b[i];
chi.push(b[i]);
}
else if(b[i]<now)
{
sum+=now-b[i];
chi.pop();
chi.push(b[i]);
}
}
rg int ans=chi.size();
cout<<ans<<endl;
小 C 最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。 正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:如果最小生成树选择的边集是EM,严格次小生成树选择的边集是 ES,那么需要满足:(value(e) 表示边 e 的权值)
数据中无向图无自环;
50% 的数据 N≤2 000 M≤3 000;
80% 的数据 N≤50 000 M≤100 000;
100% 的数据 N≤100 000 M≤300 000 ,边权值非负且不超过 10^9 。
最小生成树与次小生成树一定只有一条边的长度不同(
证明感性思考一下就好了),因而我们要先构出一棵最小生成树,然后再从边集中选入某条边以此来代替最小生成树上的边。由于我们新加入的边所连接的两点x,y必定是在同一个集合中的了,因而我们考虑将x->y路径上某条边断掉,那么为了使修改后的边权和尽可能接近最小生成树的边权和,我们查询x->y路径上的最大值,因而这个可以用倍增或树剖+线段树完成(笔者用的是倍增)
但是!!!(这个题目这么简单就太天真了!)会存在如下情况
有多组最小生成树满足条件
因而我们还需要维护一个次大值,在有多组最大满足下输出次大就好了!这样是不是可以解决问题了!好了,还有一些细节要处理,笔者放在代码里了,希望对大家有帮助(这个题目要思想有思想,要难度有难度,要细节有细节)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rg register
#define ll long long
#define inf 1e18
const int MAXN=3e5+5;
int N,M;
ll ans=inf,s;
inline int read()
{
rg char ch='!';rg int z=1,num=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')z=-1,ch=getchar();
while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
return z*num;
}
struct edge{int x,y,z,pd;}e[MAXN];
inline bool cmp(edge A,edge B)
{
if(A.z!=B.z)return A.z<B.z;
if(A.x!=B.x)return A.x<B.x;
return A.y<B.y;
}
int bcj[MAXN];
int find(int x)
{
if(bcj[x]!=x)bcj[x]=find(bcj[x]);
return bcj[x];
}
struct hand{int to,next,w;}a[MAXN<<1];
int head[MAXN],cnt,tot;
inline void link(int u,int v,int z)
{
a[++cnt]=(hand){v,head[u],z};
head[u]=cnt;
}
int dep[MAXN],f[MAXN][26];
ll g1[MAXN][26],g2[MAXN][26];
void dfs(int u,int fa)
{
for(rg int i=head[u];i;i=a[i].next)
{
rg int v=a[i].to;
if(v==fa)continue;
f[v][0]=u;
g1[v][0]=a[i].w;
g2[v][0]=-inf;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
inline void Kru()
{
rg int cao=0;
for(rg int i=1;i<=M;i++)
{
rg int x=e[i].x,y=e[i].y;
rg int dx=find(x),dy=find(y);
if(dx!=dy)
{
bcj[dy]=dx;
e[i].pd=1;
cao++;
s+=e[i].z;
link(y,x,e[i].z);
link(x,y,e[i].z);
}
if(cao==N-1)break;
}
}
inline void match(int &u,int j,ll &maxx,ll &semx)
{
if(maxx>g1[u][j])
{
semx=max(semx,g1[u][j]);
}
else if(maxx<g1[u][j])
{
semx=max(maxx,g2[u][j]);
maxx=g1[u][j];
}
else
{
semx=max(semx,g2[u][j]);
}
u=f[u][j];
}
inline ll Lca(int u,int v,int stand)
{
if(dep[u]<dep[v])swap(u,v);
rg int cha=dep[u]-dep[v];
rg ll maxx=-inf,semx=-inf;
for(rg int j=20;j>=0;j--)
{
if((1<<j)&cha)
match(u,j,maxx,semx);
}
if(u==v)
{
if(maxx==stand){return semx;}
return maxx;
}
for(rg int j=20;j>=0;j--)
{
if(f[u][j]!=f[v][j])
{
match(u,j,maxx,semx);
match(v,j,maxx,semx);
}
}
match(u,0,maxx,semx);match(v,0,maxx,semx);
if(semx==-inf)return -inf;
if(maxx==stand)return semx;
return maxx;
}
int main()
{
//freopen("pai.in","r",stdin);
//freopen("a.out","w",stdout);
N=read();M=read();
for(rg int i=1;i<=M;i++)e[i]=(edge){read(),read(),read()};
for(rg int i=1;i<=N;i++)bcj[i]=i;
sort(e+1,e+M+1,cmp);
for(rg int i=0;i<=20;i++)g1[1][i]=g2[1][i]=-inf;
Kru();dep[1]=1;dfs(1,0);
for(rg int j=1;j<=20;j++)
{
for(rg int i=1;i<=N;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
g1[i][j]=max(g1[i][j-1],g1[f[i][j-1]][j-1]);
if(g1[i][j-1]!=g1[f[i][j-1]][j-1])
{
g2[i][j]=min(g1[i][j-1],g1[f[i][j-1]][j-1]);
}
else
{
g2[i][j]=max(g2[i][j-1],g2[f[i][j-1]][j-1]);
}
}
}
rg int x,y;
for(rg int i=1;i<=M;i++)
{
if(e[i].pd)continue;
x=e[i].x,y=e[i].y;
ans=min(ans,s-Lca(x,y,e[i].z)+e[i].z);
}
cout<<ans<<endl;
return 0;
}