编程之美复赛A题小数据解法-白红宇

编程之美复赛A题小数据解法

阅读量：5368 次

发布时间：2019-06-15

本文共 3385 字，大约阅读时间需要 11 分钟。

题目列表 > 无尽的编号

时间限制: 1000ms 内存限制: 256MB

描述

在一条公路上，将要依次建造N座建筑。在每个建筑建成之后，都会用一个01串来给它编号。整条公路从起点到终点，所有建筑的编号都严格按照字典序递增的顺序来排列，而每在一个新的地方建起一个建筑时，它的编号会按以下规则确定：

1) 编号要比前一个建筑（起点方向）的字典序大，比后一个建筑（终点方向）的字典序小

3) 编号一定以1结尾

2) 编号要尽可能短，满足该条件时，字典序尽可能小

最开始时，公路的起点和终点上各有一个建筑，编号分别是0和1。接下来依次给出N个坐标 a₁, a₂, ..., a_N，依次表示下一个建筑将要建造的位置，最后要问，当所有建筑建成时，这些建筑的编号总长度是多少，其中又出现了多少个字符1。所有建筑都在公路起点和终点之间，并且没有两个建筑建在同一个位置。

输入

输入文件包含多组测试数据。

第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。

每组数据中第一行为一个整数 N，表示将要建造的建筑数量，第二行是用单个空格隔开的N个互不相同的整数 a₁, a₂, ..., a_N，表示依次将要建造的建筑所在的坐标。

输出

对于每组测试数据，输出一行"Case #X: Y Z"，其中X表示测试数据编号，Y表示所有建筑编号总长，Z表示所有编号中字符1的数量。所有建筑包括起点和终点的这两个建筑。所有数据按读入顺序从1开始编号。

数据范围

小数据：T ≤ 100, 0 < N ≤ 100, 0 ≤ a_i ≤ 1000

大数据：T ≤ 10, 0 < N ≤ 50000, 0 ≤ a_i ≤ 500000

样例输入

151 2 3 4 5

样例输出

Case #1: 22 16

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          using namespace std;//typedef long long LL;//typedef __int64 LL;//typedef long double DB;//typedef unisigned __int64 LL;//typedef unsigned long long ULL;#define EPS 1e-8#define MAXN 10005#define MAXE 300000#define INF 0x3f3f3f3f#define PI acos(-1.0)#define MOD 99991//#define MOD 99990001//#define MOD 1000000007#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define max3(a,b,c) (max(max(a,b),c))#define min3(a,b,c) (min(min(a,b),c))#define mabs(a) ((a<0)?(-a):a)//#define L(t) (t << 1) //Left son t*2//#define R(t) (t << 1 | 1) //Right son t*2+1//#define Mid(a,b) ((a+b)>>1) //Get Mid//#define lowbit(a) (a&-a) //Get Lowbit//int gcd(int a,int b){return b?gcd(b,a%b):a;}//int lcm(int a,int b){return a*b/gcd(a,b);}//std::ios::sync_with_stdio(false);struct node{ int loc; int now;}x[50005];string line[50005];int cmp(node a, node b){ return a.loc < b.loc;}int cmp2(node a,node b ){ return a.now < b.now;}string getstr(string t,string v){ string a = t; string b = v; int lena = a.size(); int lenb = b.size(); int len = max(lena,lenb); string c; bool flag = false; for(int i = 0 ; i < len ; i++) { if(a[i] != '0' && a[i] != '1') a += "0"; if(b[i] != '1' && b[i] != '0') b += "0"; } for(int i = 0 ; i < len ; i++) { if(a[i] == b[i]) c = c + a[i]; else { if( (c + "1") != v) { c = c +"1"; return c; }else if( (c + "1") == v) { c = c + "0"; while(c + "1" <= t) c = c + "1"; c = c + "1"; return c; } } }}int main(){ int T; cin>>T; for(int t = 1 ; t <= T ;t++) { int n; cin>>n; line[0] = "0"; line[n+1] = "1"; for(int i = 1 ; i <= n ; i++) line[i] = "2"; for(int i = 0 ; i < n ; i++) { scanf("%d",&x[i].loc); x[i].now = i+1; } sort(x,x+n,cmp); for(int i = 0 ; i < n ; i++) x[i].loc = i+1; sort(x,x+n,cmp2); for(int i = 0 ; i < n ; i++) { string t1,t2; int p = x[i].loc; for(int j = p+1 ; j <= n+1 ; j++) { if(line[j] != "2") { t2 = line[j]; break; } } for(int j = p-1 ; j >= 0 ; j--) { if(line[j] != "2") { t1 = line[j]; break; } } line[p] = getstr(t1,t2); } int sum = 0,sum1 = 0; for(int i = 0 ; i <= n+1 ; i++) { int size = line[i].size(); sum += size; for(int j = 0 ; j < size; j++) { if(line[i][j] == '1') sum1++; } } cout<<"Case #"<
                          
                           <<": "<
                           
                            <<" "<
                            
                             <

题目意思我就不说了...getstr函数就是求满足要求的字符串...保证编号最短就行了...然后序号可能很大所以用了离散化处理

大数据的解法应该是加线段树优化,我这里只用了离散化所以自然会TLE....由于没地方提交了所以也无法验证

转载于:https://www.cnblogs.com/Felix-F/archive/2013/04/23/3223625.html

你可能感兴趣的文章