暑期热身赛

BAPC 2014

The 2014 Benelux Algorithm Programming Contest

题目网址:https://odzkskevi.qnssl.com/365547ace19a71fae35ca0cfb5a843b3?v=1534772800

B Button Bashing

 #include<stdio.h>

 #include<bits/stdc++.h>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 const int inf=;

 int a[];

 int vis[];

 int tim,step,n,m;

 struct Node

 {

     int step,time;

 };

 void bfs()

 {

     queue <Node> q;

     Node s;

     s.step=s.time=;

     vis[]=;

     q.push(s);

     while(!q.empty())

     {

         Node now=q.front();

         q.pop();

         if(now.time>=m)

         {

             int temp=now.time-m;

             if(temp==tim)

             {

                 step=min(now.step,step);

             }

             if(temp<tim)

             {

                 tim=temp;

                 step=now.step;

             }

         }

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

         {

             Node next;

             next.step=now.step+;

             next.time=now.time+a[i];

             if(next.time>)

             {

                 next.time=;

             }

             if(next.time> && !vis[next.time])

             {

                 vis[next.time]=;

                 q.push(next);

             }

         }

     }

 }

 int main()

 {

     int t;

     cin>>t;

     while(t--)

     {

         cin>>n>>m;

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

             vis[i]=;

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

         {

             cin>>a[i];

         }

         tim=step=inf;

         if(m==)

         {

             printf("0 0\n");

             //continue;

         }

         else

         {

             bfs();

             printf("%d %d\n",step,tim);

         }

     }

     return ;

 }

E - Excellent Engineers

Gym - 101512E

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<stdio.h>

 #include<string.h>

 #define MAX 0x7f7f7f7f

 #define N 100004

 using namespace std;

 typedef long long LL;

 int cas,cass;

 int n,m,lll,ans;

 struct xxx

 {

     int x,y,z;

 } a[N];

 int t[N<<];

 bool cmp(xxx aa,xxx bb)

 {

     return aa.x<bb.x;

 }

 void change(int l,int r,int x,int c,int k)

 {

     if(l>r || x<l || x>r)return;

     if(l==r)

     {

         t[k]=c;

         return;

     }

     change(l,(l+r)>>,x,c,k+k);

     change((l+r)/+,r,x,c,k+k+);

     t[k]=min(t[k+k],t[k+k+]);

 }

 int query(int l,int r,int a,int b,int k)

 {

     if(l>r || l>b || r<a)return MAX;

     if(a<=l && r<=b)return t[k];

     int x1=query(l,(l+r)>>,a,b,k+k),x2=query((l+r)/+,r,a,b,k+k+);

     return t[k]=min(x1,x2);

 }

 int main()

 {

     int i,j,k;

     for(scanf("%d",&cas); cas; cas--)

     {

         ans=;

         memset(t,0x7f,sizeof t);

         scanf("%d",&n);

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

             scanf("%d%d%d",&a[i].y,&a[i].z,&a[i].x);

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

         change(,n,a[].y,a[].z,);

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

         {

             j=query(,n,,a[i].y,);

             if(j>a[i].z)ans++;

             change(,n,a[i].y,a[i].z,);

         }

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

     }

     return ;

 }

G - Growling Gears

Gym - 101512G

 #include<stdio.h>

 #include<bits/stdc++.h>

 #include<math.h>

 #include<algorithm>

 #include<string.h>

 using namespace std;

 int main()

 {

     int t,n;

     double a,b,c;

     cin>>t;

     while(t--)

     {

         cin>>n;

         int ans,shuchu;

         ans=;

         double maxn=;

         while(n--)

         {

             cin>>a>>b>>c;

             double q=(double)(c+(b*b)/(*a));

             //cout<<q<<" ";

             ans++;

             if(q>maxn)

             {

                  shuchu=ans;

             }

             maxn=max(q,maxn);

         }

         cout<<shuchu<<endl;

     }

     return ;

 }

I - Interesting Integers

Gym - 101512I

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 int main()

 {

     int t,n,x,y;

     int f[];

     f[]=;

     f[]=;

     int i=;

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

     {

         f[i]=f[i-]+f[i-];

     }

     cin>>t;

     while(t--)

     {

         cin>>n;

         bool bb=;

         for(i=; i>&&bb; i--)

         {

             for(int ty=; ty<=; ty++)

             {

                 if(ty*f[i]+f[i-]>n)

                 {

                     break;

                 }

                 else if((n-ty*f[i])%f[i-]== &&(n-ty*f[i])/f[i-]<=ty)

                 {

                     y=ty;

                     x=(n-ty*f[i])/f[i-];

                    bb=;

                     break;

                 }

             }

        }

        cout<<x<<" "<<y<<endl;

     }

     return ;

 }

J - Jury Jeopardy

Gym - 101512J

 #include<stdio.h>

 #include<algorithm>

 #include<math.h>

 #include<queue>

 #include<string.h>

 #define Max(a,b) (a>b?a:b)

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e6;

 struct node

 {

     int x,y,p;

     node(int x=,int y=,int p=):x(x),y(y),p(p) {}

 };

 char s[maxn],mp[][];

 int main()

 {

     int t,r,c;

     cin>>t;

     cout<<t<<endl;

     while(t--)

     {

         cin>>s;

         memset(mp,'#',sizeof mp);

         mp[][]='.';

         int minx=,maxx=,miny=,maxy=;

         node pi=node(,,);

         for(int i=; i<strlen(s); i++)

         {

             if(s[i]=='F')

             {

                 if(pi.p==)

                     pi.y+=;

                 if(pi.p==)

                     pi.x-=;

                 if(pi.p==)

                     pi.y-=;

                 if(pi.p==)

                     pi.x+=;

                 mp[pi.x][pi.y]='.';

             }

             else if(s[i]=='B')

             {

                 if(pi.p==)

                     pi.y-=;

                 if(pi.p==)

                     pi.x+=;

                 if(pi.p==)

                     pi.y+=;

                 if(pi.p==)

                     pi.x-=;

                 mp[pi.x][pi.y]='.';

                 pi.p=(pi.p+)%;

             }

             else if(s[i]=='L')

             {

                 if(pi.p==)

                     pi.x-=;

                 if(pi.p==)

                     pi.y-=;

                 if(pi.p==)

                     pi.x+=;

                 if(pi.p==)

                     pi.y+=;

                 mp[pi.x][pi.y]='.';

                 pi.p=(pi.p+)%;

             }

             else if(s[i]=='R')

             {

                 if(pi.p==)

                     pi.x+=;

                 if(pi.p==)

                     pi.y+=;

                 if(pi.p==)

                     pi.x-=;

                 if(pi.p==)

                     pi.y-=;

                 mp[pi.x][pi.y]='.';

                 pi.p=(pi.p+)%;

             }

             minx=min(minx,pi.x);

             maxx=max(maxx,pi.x);

             miny=min(miny,pi.y);

             maxy=max(maxy,pi.y);

         }

         cout<<(maxx-minx+)<<' '<<(maxy-miny+)<<endl;

         //cout<<maxy<<miny;

         for(int i=minx-; i<=maxx+; i++)

         {

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

             {

                 printf("%c",mp[i][j]);

             }

             printf("\n");

         }

     }

     return ;

 }

巴特西

ACM 第十七天

暑期热身赛

E - Excellent Engineers

G - Growling Gears

I - Interesting Integers

J - Jury Jeopardy

最新文章

热门文章