Codeforces Round #398 (Div. 2) A-E

分数史上新低

开场5分钟过了A题，想着这次赌一把手速，先去切C吧

看完C题觉得这应该是道水题，码了十分钟提交，WA

想着这明明是道水题，估计少考虑了情况，添了几行再交，WA

不可能啊，这题都A不掉，和SB有什么区别

（开始半小时后）A不掉啊，要不去做别的题吧，啊不行，不能对不起我写了这么久的代码，继续debug

（开始一小时后）心态崩了，辣鸡比赛我不玩了。关了CF跑去写了半道主席树

（倒数半小时）反正要掉分，今天和这C题死磕吧

（结束看题解）结论：我和SB有什么区别

（第二天写BDE题）卧槽这么简单我为什么看都没看，我和SB有什么区别*3

A. Snacktower

要搭一座数字下面大上面小的树塔，但数字出现的顺序不定。

每个时刻拿到一个数字，不能堆到塔上就扔到堆里，能就建塔

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 priority_queue<int>q;

 bool f[mxn];

 int main(){

     int i,j,x;

     int n=read();

     f[n+]=;

     for(i=;i<=n;i++){

         x=read();

         q.push(x);

         while(!q.empty() && f[q.top()+]){

             f[q.top()]=;

             printf("%d ",q.top());

             q.pop();

         }

         printf("\n");

     }

     return ;

 }

B.The Queue

模拟，贪心找到一个适合的插入点。

如果所有人都处理完了，营业还没结束，那主角可以等到最后再过去

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define LL long long

 using namespace std;

 const int mxn=;

 LL read(){

     LL x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 LL ts,tf,t;

 LL w[mxn];

 int main(){

     int i,j;

     ts=read();tf=read();

     t=read();

     int n=read();

     for(i=;i<=n;i++){w[i]=read();}

     if(w[]>ts){printf("%I64d\n",ts);return ;}

     LL ans=1e15,pos=-;

     LL smm=ts,last=;

     for(i=;i<=n;i++){

         last=smm-w[i]+;

         if(last<=){

             printf("%I64d\n",w[i]-);

             return ;

         }

         if(smm+t>tf)break;

         if(last<ans){

             ans=last;pos=w[i]-;

         }

         smm+=t;

     }

     if(smm+t<=tf)pos=smm;

     printf("%I64d\n",pos);

     return ;

 }

C. Garland

把一棵树分成权值和相等的三部分

明明只是一个DFS？

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 struct edge{

     int v,nxt;

 }e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v){

     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;

 }

 int w[mxn];

 int sz[mxn];

 int n,smm=,rt;

 int ans[],cnt=;

 int f[mxn];

 void DFS(int u){

     f[u]=;

     sz[u]+=w[u];

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         DFS(v);

         sz[u]+=sz[v];

 //        if(sz[v]==smm){f[v]=v;}

         if(f[u] && f[v]){

             ans[]=f[u];

             ans[]=f[v];

         }

         if(f[v])f[u]=f[v];

     }

 /*

     cnt=0;

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         if(f[v]){

             f[u]=f[v];

             if(f[v]!=ans[1])ans[++cnt]=f[v];

             if(cnt==2){

                 printf("%d %d\n",ans[1],ans[2]);

                 exit(0);

             }

         }

     }

     if(u!=rt && u!=ans[1] && smm*2==sz[u] && cnt){

         printf("%d %d\n",u,ans[1]);exit(0);

     }

     if(sz[u]==smm)f[u]=u;

 */

     if(u!=rt && sz[u]==smm* && f[u]){

         ans[]=u;

         ans[]=f[u];

     }

     if(sz[u]==smm)f[u]=u;

     return;

 }

 int main(){

     int i,j,u,v;

     n=read();

     for(i=;i<=n;i++){

         u=read();v=read();

         if(!u)rt=i;

         else add_edge(u,i);

         w[i]=v;smm+=v;

     }

     if(smm%){printf("-1\n");return ;}

     smm/=;

     DFS(rt);

     if(ans[])printf("%d %d\n",ans[],ans[]);

     else printf("-1\n");

     return ;

 }

D. Cartons of milk

排序+二分答案

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 struct node{

     int w,id;

 }a[mxn],b[mxn];

 int cmp(const node a,const node b){

     return a.w<b.w;

 }

 int n,m,k;

 bool check(int lim){

     int i,j;

     int day=,now=;

     for(i=,j=m-lim+;i<=n || j<=m; ){

         if(i<=n && (j>m || a[i].w<=b[j].w)){

             now++;

             if(now>k){now-=k;day++;}

             if(a[i].w<day)return ;

             i++;

         }

         else{

             now++;

             if(now>k){now-=k;day++;}

             if(b[j].w<day)return ;

             j++;

         }

     }

     return ;

 }

 int main(){

     int i,j;

     n=read();m=read();k=read();

     for(i=;i<=n;i++){a[i].w=read();}

     for(i=;i<=m;i++){b[i].w=read();b[i].id=i;}

     sort(a+,a+n+,cmp);

     sort(b+,b+m+,cmp);

     int l=,r=m,ans=;

     while(l<=r){

         int mid=(l+r)>>;

         if(check(mid)){

             ans=mid;

             l=mid+;

         }

         else r=mid-;

     }

     if(!ans)if(!check())ans=-;

     printf("%d\n",ans);

     for(i=m-ans+;i<=m;i++){

         printf("%d ",b[i].id);

     }

     return ;

 }

E. Change-free

起初有个脑洞，先每次都付纸币，然后贪心找不满度最大的日子“退流”。对正确性没有自信，悄悄看了看dalao们的代码，发现写法都是每次付硬币，然后贪心找不满度最小的日子改付纸币。

后一种好写，就写后一种咯

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 struct cmp{

     int w,id;

     friend bool operator < (const cmp a,const cmp b){

         return a.w>b.w;

     }

 };

 priority_queue<cmp> q;

 bool note[mxn];

 int n,m;

 int c[mxn],w[mxn];

 long long ans=;

 void solve(){

     int i,j;

     for(i=;i<=n;i++){

         int cost=c[i]%;if(!cost)continue;

         int res=-cost;

 //        printf("res:%d\n",res*w[i]);

         q.push((cmp){res*w[i],i});

         m-=cost;

         while(m<){

             cmp tmp=q.top();q.pop();

             ans+=tmp.w;

             note[tmp.id]^=;

             m+=;

         }

     }

     return;

 }

 int main(){

     int i,j;

     n=read();m=read();

     for(i=;i<=n;i++)c[i]=read();

     for(j=;j<=n;j++)w[j]=read();

     solve();

     printf("%I64d\n",ans);

     for(i=;i<=n;i++){

         if(note[i])printf("%d %d\n",(c[i]+)/,);

         else printf("%d %d\n",c[i]/,c[i]%);

     }

     return ;

 }

巴特西

Codeforces Round #398 (Div. 2) A-E

最新文章

热门文章