【GYM102091】2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest

A-Evolution Game

题目大意：有$n$个不同的野兽，定义第$i$ 个野兽有 $i$ 个眼睛和 $h[i]$ 个角，你可以任意从中选择一个野兽进行进化，每次进化角数量必须增加，而且进化后要满足眼镜的变化量 $\triangle i \leq w$，求最多的进化次数。

题解：以$h$的值从大到小排序，$f[i]$表示从第i个野兽开始进化的最多次数。对于$1 \leq i \leq j$若满足条件则$f[j]=max \{ f[i]+1 \}$。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,w,ans;

 int f[];

 struct hh

 {

     int eye,horn;

 }a[];

 bool cmp(hh a,hh b)

 {

     return a.horn>b.horn;

 }

 int main()

 {

     int i,j;;

     scanf("%d%d",&n,&w);

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

         scanf("%d",&a[i].horn);

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

         a[i].eye=i;

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

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

         for(j=i+;j<=n;j++)//h[i]>h[j]

             if(a[i].horn>a[j].horn&&abs(a[i].eye-a[j].eye)<=w)

                 f[j]=max(f[j],f[i]+);

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

         ans=max(f[i],ans);

     printf("%d",ans);

     return ;

 }

D-Bus Stop

题目大意：给出$n$个房子的坐标，要建立公交车站使得每个房子离最近的车站不过10公里，求最少的车站数。

题解：从左往右贪心即可。

#include <bits/stdc++.h>

using namespace std;

const int N=3e6;

int m,n;

int a[N];

int ans,lstop;

int main()

{

    scanf("%d",&m);

    while(m--)

    {

        scanf("%d",&n);

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

            scanf("%d",&a[i]);

        }

        lstop=a[]+;

        ans=;

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

            if(abs(a[i]-lstop)<=){

                ;

            }

            else{

                lstop=a[i]+;

                ans++;

            }

        }

        if(n==)ans=;

        if(n==)ans=;

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

    }

}

G-Communication

题目大意：求有向图强连通分量数。

题解：Floyed+并查集或者Tarjan。

#include <bits/stdc++.h>

using namespace std;

const int N=1e3;

int m,n,c,ans,a,b;

int f[N];

int edge[N][N];

int fnd(int x)

{

    if(f[x]==x)return x;

    return f[x]=fnd(f[x]);

}

int main()

{

    scanf("%d",&m);

    while(m--)

    {

        scanf("%d%d",&n,&c);

        memset(edge,,sizeof(edge));

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

            f[i]=i;

        for(int i=;i<=c;i++){

            scanf("%d%d",&a,&b);

            edge[a][b]=;

        }

        for(int k=;k<n;k++)

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

                for(int j=;j<n;j++){

                    if(edge[i][k]&&edge[k][j])edge[i][j]=;

                }

        ans=;

        for(int i=;i<n-;i++)

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

                if(edge[i][j]+edge[j][i]==){

                    f[j]=fnd(i);

                }

            }

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

            if(f[i]==i)ans++;

        }

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

    }

}

H-As rich as Crassus

题目大意：$x^3 \equiv A_i \ \ (mod \ \ N_i) (i=3)$，求$x$。

题解：中国剩余定理

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int n,t;

long long ans;

long long b[],m[];

long long exgcd(long long a,long long b,long long &x,long long &y){

    if(b==){x=,y=;return a;}

    long long d=exgcd(b,a%b,x,y);

    long long z=x;x=y,y=z-a/b*y;

    return d;

}

void print(long long x){

    if(!x) return;

    if(x) print(x/);

    putchar(x%+'');

}

int main()

{

    int i;

    long long x,y,M,aa,bb,cc,d,tmp;

    bool flag;n=;

    scanf("%d",&t);

    while(t--)

    {

        ans=flag=;

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

            scanf("%I64d",&m[i]);

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

            scanf("%I64d",&b[i]);

        M=m[],ans=b[];

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

        {

            aa=M,bb=m[i],cc=(b[i]-ans%bb+bb)%bb;

            x=,y=;

            d=exgcd(aa,bb,x,y);

            bb=bb/d;

            if(cc%d){flag=;break;}

            x=((x*cc/d)%bb+bb)%bb;

            ans+=M*x;M*=bb;

            ans=(ans%M+M)%M;

        }

        if(flag)puts("-1");

        else {

            if(!ans)puts("");

            else

            {

                tmp=pow(ans,1.0/3.0);

                if(tmp*tmp*tmp<ans) printf("%I64d\n",tmp+);

                else printf("%I64d",tmp);

            }

        }

    }

    return ;

}

close

J-Floating-Point Hazard

题目大意：给出L,R，求$\sum_{i=L}^{R}(\sqrt[3]{i+10^{-15}}-\sqrt[3]{i})$。

题解：微分

#include <iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

int main()

{

    #ifdef LOCAL

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    #endif // LOCAL

    int a,b;

    while(~scanf("%d%d",&a,&b)){

        if(!a||!b) break;

        double ans=;

        for(ll i=a;i<=b;i++){

            ans+=pow(i*i,-/3.0);

        }

        ans*=1.0/*(1e-);

        printf("%.5E\n",ans);

    }

}

K-The Stream of Corning 2

题目大意：给出若干个数和存在的时间点，问某一时刻存在的数中的第k大。

题解：将一个操作的起始点和终止点拆开标记，按时间排序后，用树状数组+二分求动态第k大数。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int t,n,totp,totq,lim;

struct hh

{

    int opt,t,v,k,id;

}p[],q[];

int c[];

int lowbit(int x)

{

    return x&(-x);

}

void add(int pos,int v)

{

    for(;pos<=lim;pos+=lowbit(pos))

        c[pos]+=v;

}

int query(int pos)

{

    int ret=;

    for(;pos;pos-=lowbit(pos))

        ret+=c[pos];

    return ret;

}

bool cmp(hh a,hh b)

{

    return a.t<b.t;

}

bool cmp2(hh a,hh b)

{

    return a.id<b.id;

}

int solve(int k)

{

    int l,r,mid,ret,n;

    l=;r=lim;

    ret=lim;

    if(query(lim)<k) return -;

    while(l<=r)

    {

        mid=l+r>>;

        if(query(mid)>=k)

        {

            r=mid-;

            ret=min(ret,mid);

        }

        else l=mid+;

    }

    return ret;

}

int main()

{

    int T,i,j,a,b,z,prep,opt;

    scanf("%d",&t);

    for(T=;T<=t;T++)

    {

        scanf("%d",&n);

        totp=totq=;

        memset(p,,sizeof(p));

        memset(q,,sizeof(q));

        memset(c,,sizeof(c));

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

        {

            scanf("%d%d%d",&opt,&a,&b);

            lim=max(lim,b);

            if(opt==)

            {

                scanf("%d",&z);

                p[++totp].opt=;

                p[totp].v=b;

                p[totp].t=a;

                p[++totp].opt=-;

                p[totp].v=b;

                p[totp].t=z;

            }

            else

            {

                q[++totq].t=a;

                q[totq].k=b;

                q[totq].id=i;

            }

        }

        sort(p+,p++totp,cmp);

        sort(q+,q++totq,cmp);

        prep=;

        for(i=;i<=totq;i++)

        {

            while(p[prep].t<q[i].t&&prep<=totp)

            {

                add(p[prep].v,p[prep].opt);

                prep++;

            }

            q[i].v=solve(q[i].k);

        }

        sort(q+,q++totq,cmp2);

        printf("Case %d:\n",T);

        for(i=;i<=totq;i++)

            printf("%d\n",q[i].v);

    }

    return ;

}

L-Largest Allowed Area

题目大意：求一个最大的子矩阵，要求子矩阵的和为0或1。

题解：单调队列。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int t,n,m,ans;

int s[][],a[][];

char c;

int main()

{

    int i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        memset(s,,sizeof(s));

        memset(a,,sizeof(a));

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

            for(j=;j<=m;j++)

            {

                do{c=getchar();}while(c!=''&&c!='');

                s[i][j]=c-''+s[i-][j]+s[i][j-]-s[i-][j-];

            }

        for(i=,ans=;i<=n;i++)

            for(j=;j<=m;j++)

            {

                a[i][j]=a[i-][j-]-(a[i-][j-]>=);

                while(i+a[i][j]<=n&&j+a[i][j]<=m&&s[i+a[i][j]][j+a[i][j]]-s[i-][j+a[i][j]]-s[i+a[i][j]][j-]+s[i-][j-]<=)

                    a[i][j]++;

                ans=max(ans,a[i][j]);

            }

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

    }

    return ;

}

巴特西

【GYM102091】2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest

最新文章

热门文章