Educational Codeforces Round 5

时间：2024-01-21 16:36:45

616A - Comparing Two Long Integers    20171121

直接暴力莽就好了...没什么好说的

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

string a,b;int sa,sb;

char cmp()

{

    if(sa==- && sb==-)return '=';

    if(sa==-)return '<';if(sb==-)return '>';

    if(a.size()-sa>b.size()-sb)return '>';

    if(a.size()-sa<b.size()-sb)return '<';

    for(int i=sa,j=sb;i<a.size();i++,j++)

      if(a[i]!=b[j])return (a[i]<b[j])?'<':'>';

    return '=';

}

int main()

{

    cin>>a;cin>>b;sa=sb=-;

    for(int i=;i<a.size();i++)if(a[i]!=''){sa=i;break;}

    for(int i=;i<b.size();i++)if(b[i]!=''){sb=i;break;}

    return printf("%c\n",cmp()),;

}

616B - Dinner with Emma    20171121

在每行的最小值中取一个最大值输出就好了

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,x,mi,ans;

int main()

{

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

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

      {

      mi=;

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

        scanf("%d",&x),mi=min(mi,x);

      ans=max(ans,mi);

      }

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

}

616C - The Labyrinth    20171121

简单并查集

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#define N 1150

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

struct rua

{

    int x,y;

}fa[N][N];

int n,m,si[N][N];

bool s[N][N];

char ch;

bool read()

{

    ch=getchar();

    while(ch!='.' && ch!='*')

      ch=getchar();

    return ch=='.';

}

rua Find(int x,int y)

{

    if(fa[x][y].x==x && fa[x][y].y==y)return fa[x][y];

    else return fa[x][y]=Find(fa[x][y].x,fa[x][y].y);

}

void Union(int xx,int xy,int yx,int yy)

{

    fa[Find(xx,xy).x][Find(xx,xy).y]=Find(yx,yy);

}

bool equal(int xx,int xy,int yx,int yy)

{

    return fa[xx][xy].x==fa[yx][yy].x && fa[xx][xy].y==fa[yx][yy].y;

}

int main()

{

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

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

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

        fa[i][j].x=i,fa[i][j].y=j;

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

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

        {

        s[i][j]=read();

        if(s[i][j] && s[i-][j])

          Union(i,j,i-,j);

        if(s[i][j] && s[i][j-])

          Union(i,j,i,j-);

        }

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

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

        {

        fa[i][j].x=Find(i,j).x;

        fa[i][j].y=Find(i,j).y;

        si[Find(i,j).x][Find(i,j).y]++;

        }

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

      {

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

        if(s[i][j])

          printf(".");

        else

          {

          int ans=;

          if(s[i-][j])

            ans+=si[Find(i-,j).x][Find(i-,j).y];

          if(s[i+][j])

            if(!equal(i+,j,i-,j))

              ans+=si[Find(i+,j).x][Find(i+,j).y];

          if(s[i][j-])

            if(!equal(i,j-,i-,j))

              if(!equal(i,j-,i+,j))

                ans+=si[Find(i,j-).x][Find(i,j-).y];

          if(s[i][j+])

            if(!equal(i,j+,i-,j))

              if(!equal(i,j+,i+,j))

                if(!equal(i,j+,i,j-))

                  ans+=si[Find(i,j+).x][Find(i,j+).y];

          printf("%d",ans%);

          }

      printf("\n");

      }

    return ;

}

616D - Longest k-Good Segment    20171121

先找出当\(l=1\)时\(r\)的最大值，然后O(n)扫一遍。即先增大\(l\)的值到刚好不同元素个数\(<k\)，之后再增大\(r\)的值，这种做法在CF中好像叫做\(two \ pointers\)，在Educational Codeforces Round 50的D题里也有此算法的一个应用

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#define N 1000001

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int ansl,ansr,n,k,l,r,s,a[N],b[N];

int main()

{

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

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

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

    for(r=;s<=k && r<=n;r++)

      s+=(!b[a[r]]),b[a[r]]++;

    r--;if(s>k)s--,b[a[r--]]--;

    l=ansl=,ansr=r;

    while(r<n)

      {

      for(l;s==k;l++)

        b[a[l]]--,s-=(!b[a[l]]);

      for(r=r+;s<=k && r<=n;r++)

        s+=(!b[a[r]]),b[a[r]]++;

      r--;if(s>k)s--,b[a[r--]]--;

      if(s==k && ansr-ansl<r-l)

        ansr=r,ansl=l;

      }

    printf("%d %d\n",ansl,ansr);

}

616E - Sum of Remainders    20171121

直接分块做就好了

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define LL long long

#define MOD 1000000007

LL n,m,nexti,ans,an;

LL get_ans(LL a,LL b,LL n)

{

    if(n&)an=((n+)/)%MOD*(n%MOD)%MOD;

    else an=(n/)%MOD*((n+)%MOD)%MOD;

    an*=a%MOD,an%=MOD,an+=(n+)%MOD*(b%MOD)%MOD;

    return an%MOD;

}

int main()

{

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

    for(LL i=;i<=min(m,n);i=nexti+)

      {

      nexti=min(m,n/(n/i));

      ans+=get_ans(n/i,n%nexti,((n%i)-(n%nexti))/(n/i));

      ans%=MOD;

      }

    if(n<m)ans+=(m-n)%MOD*(n%MOD)%MOD;

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

    return ;

}

616F - Expensive Strings    20180917

[Educational Round 5][Codeforces 616F. Expensive Strings]

相关文章