首页 > 代码库 > Codeforces Round #398 (Div. 2)[]

Codeforces Round #398 (Div. 2)[]

Codeforces Round #398 (Div. 2)

 

A.

我和官方题解的命名神相似...

技术分享
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,has[N];int main(){    //freopen("in","r",stdin);    n=read();    int now=n;    for(int i=1;i<=n;i++){        has[read()]=1;        while(has[now]) printf("%d ",now),now--;        puts("");    }}
View Code

B.

比赛时花了1h然后弃疗

C.

比B简单多了,发现就是$\frac{1}{3}$,分类讨论选的子树是否互相包含,最后$5min$通过了...

技术分享
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e6+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,d[N],fa,w[N],root;struct edge{    int v,ne;}e[N<<1];int h[N],cnt=0;inline void ins(int u,int v){    cnt++;    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;}void dp(int u){    d[u]=w[u];    for(int i=h[u];i;i=e[i].ne)        dp(e[i].v),d[u]+=d[e[i].v];}int f[N],val;void dp2(int u){    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        dp2(v);        if(f[v]==0) f[u]+=d[v]==val;        else f[u]+=f[v];    }}int a[N],p;int main(){    //freopen("in","r",stdin);    n=read();    for(int i=1;i<=n;i++){        fa=read();w[i]=read();        if(fa==0) root=i;        else ins(fa,i);    }    dp(root);    if(d[root]%3!=0) puts("-1");    else{        val=d[root]/3;        dp2(root);        //for(int i=1;i<=n;i++) printf("%d %d %d\n",i,d[i],f[i]);        if(f[root]==0) puts("-1");        else if(f[root]>=2){            for(int i=1;i<=n;i++) if(i!=root&&d[i]==val&&f[i]==0) a[++p]=i;            printf("%d %d",a[1],a[2]);        }else{            int flag=0,a,b;            for(int i=1;i<=n;i++) if(i!=root&&d[root]-d[i]==val&&f[i]==1){                flag=1;a=i;break;            }            for(int i=1;i<=n;i++) if(i!=root&&d[i]==val&&f[i]==0) {b=i;break;}            if(flag) printf("%d %d",a,b);            else puts("-1");        }    }}
View Code

D.

赛后补题.....

一开始贪心乱搞失败,然后发现直接二分答案就好了.....然而是$O(n log^{2}n)$

看了一个别人的代码发现贪心也能做并且很快,明天再说

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=2e6+5;inline int read(){    char c=getchar();int x=0;    while(c<0||c>9){c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x;}int n,m,k,a[N];struct data{    int id,b;    bool operator <(const data &r) const{        return b>r.b;    }}b[N];int p,c[N];bool check(int x){//printf("check %x\n",x);    ll now=0;    p=0;    for(int i=1;i<=n;i++) c[++p]=a[i];    for(int i=1;i<=x;i++) c[++p]=b[i].b;    sort(c+1,c+1+p);    //for(int i=1;i<=p;i++) printf("%d ",c[i]);puts("");    for(int i=1;i<=p;i++){        now++;//printf("now %d %d %d\n",i,c[i],now);        if(now>(ll)k*c[i]) return false;    }    return true;}int main(){    //freopen("in","r",stdin);    n=read();m=read();k=read();    for(int i=1;i<=n;i++) a[i]=read()+1;    for(int i=1;i<=m;i++) b[i].b=read()+1,b[i].id=i;    sort(a+1,a+1+n);    sort(b+1,b+1+m);    int l=0,r=m,ans=-1;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid)) ans=mid,l=mid+1;        else r=mid-1;    }    printf("%d\n",ans);    if(ans!=-1){        memset(c,0,sizeof(c));        for(int i=1;i<=ans;i++) c[b[i].id]=1;        for(int i=1;i<=m;i++) if(c[i]) printf("%d ",i);    }}

 

Codeforces Round #398 (Div. 2)[]