描述
在一條公路上，將要依次建造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 <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
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 #"<<t<<": "<<sum<<" "<<sum1<<endl;
}
return 0;
}
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
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 #"<<t<<": "<<sum<<" "<<sum1<<endl;
}
return 0;
}
題目意思我就不說了...getstr函數就是求滿足要求的字符串...保證編號最短就行了...然後序號可能很大所以用了離散化處理
大數據的解法應該是加線段樹優化,我這裡只用了離散化所以自然會TLE....由於沒地方提交了所以也無法驗證
