服务器需求
我觉得我考场上也想不到
\(ans=max(a_i,ceil(sum/m))\)
模拟的话 每加一台服务器就是选择最大需求消1 总的就需要\(ceil(sum/m)\)
考虑有一天需求量贼大 其他所有的天数都做完了他还有剩的(因为一次操作只能消掉一天)
好叭还是感性理解一下
int n,m,q,a[N];
ll sum;
multiset<ll>s;
multiset<ll>::iterator its;
int main(){
#ifndef ONLINE_JUDGE
freopen("T1.txt","r",stdin);
#endif
rd(n),rd(m),rd(q);
for(int i=1;i<=n;++i) rd(a[i]),sum+=(ll)a[i],s.insert(-a[i]);
printf("%lld\n",max(-*s.begin(),(ll)(ceil((double)sum/m))));
for(int i=1,x,y;i<=q;++i){
rd(x),rd(y);
its=s.find(-a[x]),s.erase(its);
s.insert(-y),sum+=y-a[x],a[x]=y;
printf("%lld\n",max(-*s.begin(),((ll)ceil((double)sum/m))));
}
return 0;
}沙漠点列
只得了\(K=0\)和为\(0\)的情况的分
其实考场上想到的就是正解 但是我思维特别混乱 就gg了
其实我也并没有掌握搞环的那顿操作 算是查到了以前的惊天大洞
先删掉途中所有割边 每删一个割边就会多一个连通块 删完割边之后就得自己创造割边 贪心每次拆开一个当前最长的环
我居然才真正理解到\(tarjan\)，它无向图按有向图跑缩点最后的\(Bcnt\)减去连通块数得到割边数
不搞了QAQ搞不动了 90昏够了
int head[N],tot=0;
struct edge{int v,nxt;}e[M<<1];
void add(int u,int v){e[++tot]=(edge){v,head[u]},head[u]=tot;}
int Bcnt=0,idx=0,dfn[N],low[N],s[N];bool inst[N];
void tarjan(int u,int ff){
dfn[u]=low[u]=++idx,s[++s[0]]=u,inst[u]=1;
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=ff){
if(!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
else if(inst[v]&&dfn[v]<low[u]) low[u]=dfn[v];
}
if(low[u]==dfn[u]){
int v;++Bcnt;
do{v=s[s[0]--],inst[v]=0;}while(u!=v);
}
}
int dis[N],cir[N];
void dfs(int u,int ff){
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=ff){
if(!dis[v]) dis[v]=dis[u]+1,dfs(v,u);
else if(dis[v]<dis[u]+1) cir[++cir[0]]=dis[u]-dis[v]+1;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("T2.txt","r",stdin);
#endif
rd(n),rd(m),rd(K);
for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add(u,v),add(v,u);
for(int i=1;i<=n;++i) if(!dfn[i]) ++bcnt,tarjan(i,0);
if(Bcnt-bcnt>=K) return printf("%d",K+bcnt),0;
ans=Bcnt,K-=Bcnt-bcnt,cir[0]=0;
for(int i=1;i<=n;++i) if(!dis[i]) dfs(i,0);
sort(cir+1,cir+cir[0]+1);
for(int i=cir[0];i&&K>=0;--i){
--K;
ans+=min(K,cir[i]-1),K-=cir[i]-1;
}
printf("%d",ans);
return 0;
}维护序列
考试的时候写成了if(a[i]==x).... else if(a[i]==y) 当\(x=y\)时这样就错了....
然后这个代码50昏
void upd(int l,int r,int k){for(int i=l;i<=r;++i) a[i]=k;}
void query(int x,int y,int &las){
int pa=0,pb=0;las=inf;
for(int i=1;i<=n;++i){
if(a[i]==x) las=Min(las,pb?abs(i-pb):inf),pa=i;
if(a[i]==y) las=Min(las,pa?abs(i-pa):inf),pb=i;}
if(!pa||!pb){puts("-1");las=0;return;}
printf("%d\n",las);
}
void work(){
for(int i=1,opt,x,y,k,lasans=0;i<=m;++i){
rd(opt),rd(x),rd(y);
if(zx) x^=lasans,y^=lasans;
if(opt==1) rd(k),k^=(zx?lasans:0),upd(x,y,k);
else query(x,y,lasans);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("T3.txt","r",stdin);
#endif
rd(n),rd(m),rd(zx);
for(int i=1;i<=n;++i) rd(a[i]);
work();
return 0;
}