编程之美复赛A题小数据解法 - c++编程基础

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

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

3) 编号一定以1结尾

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

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

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

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

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

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

数据范围
小数据：T ≤ 100, 0 < N ≤ 100, 0 ≤ ai ≤ 1000

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

样例输入
1
5
1 2 3 4 5样例输出
Case #1: 22 16

[cpp]
#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--)
{

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