Codeforces Round #312 (Div. 2) ABC题解

  1. 云栖社区>
  2. 博客>
  3. 正文

Codeforces Round #312 (Div. 2) ABC题解

技术mix呢 2017-10-19 18:04:00 浏览615
展开阅读全文

【比赛链接】click here~~

A. Lala Land and Apple Trees:

【题意】:

AMR住在拉拉土地。

拉拉土地是一个很漂亮的国家,位于坐标线。拉拉土地是与著名的苹果树越来越随处可见。

拉拉土地恰好n苹果树。树数i位于位置xi和具有人工智能的苹果就能够了增长。阿姆鲁希望从苹果树收集苹果。 AMR眼下维持在X =0的位置。在開始的时候,他能够选择是否去左边或右边。他会在他的方向继续下去。直到他遇见一棵苹果树,他之前没有參观。他会採取全部的苹果。然后扭转他的方向。继续走这个方向,直到他遇到了还有一个苹果树,他之前没有參观等。

在换句话说,阿姆鲁訪问每个新的苹果树反转时他的方向。 AMR将停止收集苹果时,有没有很多其它的树木。他也没有在他所面对的方向參观。
求他能够收集的最大数量?

代码:

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=1e6+10;
int  i,j,n,m,t,ans,res,cnt,tmp;

char str[N];
bool vis[N];
int nx[N],ny[N];

int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

struct node
{
    int x,y;
};

vector< pair<int,int> >ll,rr;

bool cmp1(pair<int ,int >a,pair <int ,int >b)
{
    return a.first>b.first;
}
bool cmp2(pair<int ,int >a,pair <int ,int >b)
{
    return a.first<b.first;
}
int main()
{
    while(cin>>n)
    {
        int x,a;
        rep(i,0,n)
        {
            cin>>x>>a;
            if(x<0) ll.push_back(make_pair(x,a));
            else rr.push_back(make_pair(x,a));
        }
        sort(ll.begin(),ll.end(),cmp1);
        sort(rr.begin(),rr.end(),cmp2);
        int res=0;
        int lenl=ll.size(),lenr=rr.size();
        if(lenl==lenr)
        {
            rep(i,0,lenl)
            {
                res+=ll[i].second;
                res+=rr[i].second;
            }
        }
        else if(lenl<lenr)
        {
            for(int i=0; i<lenl; ++i) res+=ll[i].second;
            for(int i=0; i<=lenl; ++i)  res+=rr[i].second;
        }
        else
        {
            for(int i=0; i<=lenr; ++i) res+=ll[i].second;
            for(int i=0; i<lenr; ++i)  res+=rr[i].second;
        }
        cout<<res<<endl;
    }
    return 0;
}

B. Amr and The Large Array

【题意】:

阿姆鲁得到了一个大阵大小为n的。AMR不喜欢大型阵列,所以他打算把它缩小。



AMR并不关心。除非它的漂亮阵列中的不论什么东西。阵列的美被定义为次一些数发生在此数组的最大数目。他想选择这个阵列。使得它的漂亮将是一样的原始数组中最小的子段。

帮助阿姆鲁通过选择最小的子段。

代码:

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?

a:b #define Min(a,b) a>b?b:a #define mem(a,b) memset(a,b,sizeof(a)) typedef long long LL; typedef unsigned long long LLU; typedef double db; const int N=1e6+10; int i,j,n,m,t,ans,res,cnt,tmp; char str[N]; bool vis[N]; int nx[N],ny[N]; int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; struct node { int x,y; }; bool cmp1(node a,node b) { return a.x<b.x; } pair<int,int> num [N]; int c[N]; int pre[N]; int last[N]; int maxxa=-1; int maxxb=-1; int main() { cin>>n; rep(i,0,n) { cin>>j; ++c[j]; maxxa=max(maxxa,c[j]);///找出那个数出现次数最多 maxxb=max(maxxb,j);///那个数最大 if(c[j]==1) { pre[j]=last[j]=i;/// pre[1]=last[1]=1 } else { pre[j]=min(pre[j],i); last[j]=max(last[j],i); } // cout<<"pre[j]="<<j<<" "<<pre[j]<<endl; // cout<<"last[j]="<<j<<" "<<last[j]<<endl; } //cout<<maxxa<<endl;///3 //cout<<maxxb<<endl;///2 int fx=-1,fy=N; for(int i=0; i<=maxxb; ++i) { if(c[i]==maxxa) { if(last[i]-pre[i]<fy) { fx=pre[i]; fy=last[i]-pre[i]; } } } cout<<fx+1<<" "<<fx+fy+1; return 0; }


C. Amr and Chemistry

【题意】

 AMR热爱化学,以及专门做实验。他正在准备一个新的有趣的实验。



AMR有n个不同类型的化学品。每一化学i具有艾升的起始体积。对于该实验,阿姆鲁具有混合全部的化学品一起。但全部的化学品卷必须等于第一位。所以,他的任务就是使全部的化学品数量相等。

要做到这一点。阿姆鲁能够做两种不同的操作。



选择一些化学i和一倍当前音量。使新卷将2AI
选择一些化学i和除以2(整数除法)的体积。使新卷会
如果每一个化学包括在无限量的容器。如今阿姆鲁想知道是什么操作,使全部化学品卷等于所需的最低人数?

代码:

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?

b:a #define mem(a,b) memset(a,b,sizeof(a)) #define debug(x) cerr<<#x<<"="<<x<<endl; #define FF first #define SS second #define PB push_back #define MP make_pair typedef long long ll; const ll INF=1<<28; const ll LINF=1ll<<61; //My own input/output stream #define geti(x) x=getnum() #define getii(x,y) geti(x),geti(y) #define getiii(x,y,z) getii(x,y),geti(z) #define puti(x) putnum(x),putsp() #define putii(x,y) puti(x),putnum(y),putsp() #define putiii(x,y,z) putii(x,y),putnum(z),putsp() #define putsi(x) putnum(x),putendl() #define putsii(x,y) puti(x),putnum(y),putendl() #define putsiii(x,y,z) putii(x,y),putnum(z),putendl() inline ll getnum() { register ll r=0; register bool ng=0; register char c; c=getchar(); while(c!='-'&&(c<'0'||c>'9'))c=getchar(); if(c=='-')ng=1,c=getchar(); while(c!=' '&&c!='\n')r=r*10+c-'0',c=getchar(); if(ng)r=-r; return r; } template <class T> inline void putnum(T x) { if(x<0)putchar('-'),x=-x; register short a[20]= {},sz=0; while(x>0)a[sz++]=x%10,x/=10; if(sz==0)putchar('0'); for(int i=sz-1; i>=0; i--)putchar('0'+a[i]); } inline void putsp() { putchar(' '); } inline void putendl() { putchar('\n'); } inline char mygetchar() { register char c=getchar(); while(c==' '||c=='\n')c=getchar(); return c; } typedef long long LL; typedef unsigned long long LLU; typedef double db; const int N=1e6+10; int i,j,n,m,t,ans,res,cnt,tmp; char str[N]; bool vis[N]; int nx[N],ny[N]; int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; struct node { int x,y; }; bool cmp1(node a,node b) { return a.x<b.x; } pair<int,int> num [N]; int c[N]; int pre[N]; int last[N]; int maxxa=-1; int maxxb=-1; int a[N],b[N]; vector <bool>v[N],vans; int main() { scanf("%d",&n); int kk=20; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); int j; for(j=1; j<20; j++) { if((a[i]>>(j-1))>0&&(a[i]>>j)==0) { break; } } for(int k=j-1; k>=0; k--) { v[i].PB((a[i]>>k)&1); } kk=min(kk,int(v[i].size())); } for(int i=0; i<kk; i++) { bool ok=1; for(int j=1; j<n; j++) { if(v[j][i]!=v[j+1][i]) { ok=0; break; } } if(ok)vans.PB(v[1][i]); else break; } for(int i=1; i<=n; i++) { int j=vans.size(); while(j<v[i].size()&&v[i][j]==0) { b[i]++; j++; } } int ans=99999999999; for(int i=0; i<30-int(vans.size()); i++) { int tans=0; for(int j=1; j<=n; j++) { tans+=int(v[j].size())-int(vans.size()+min(i,b[j]))+max(0,i-b[j]); } ans=min(ans,tans); } printf("%d\n",ans); return 0; }








本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5222818.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
技术mix呢
+ 关注