| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
说一下这个题。。。算法是这样的:先列出来所有为1的点。如果个数为奇数,那么在这个序列的前面增加一个洞。之后亮亮配对,构成前闭后开区间。所有这些区间内面的数取2的幂相加就是结果。
比如如果是1 3 6 7 10,就是先变成0 1 3 6 7 10,然后区间是(0),(3 4 5),(7 8 9),结果就是2^0+2^3+2^4+2^5+2^7+2^8+2^9。
如果是2 4,就直接是区间(2 3),结果2^2+2^3。
如果高精度预处理计算2^0到2^1000会超时。然后我就把这些东西先算出来然后硬编码进去。竟然告诉我代妈长度太长交不了什么鬼啊!!!第一次遇到这种恶心的限制。。。
放弃高精度直接二进制转十进制可以成功,但是要注意全部为洞的时候要输出一个洞。。。
附代妈
//============================================================================
// Name : main1090.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
using namespace std;
void c2(int *res){
for(int i = 0; i < 303; i++){
res[i] *= 2;
}
for(int i = 0; i < 303; i++){
res[i+1] += res[i]/10;
res[i] %= 10;
}
}
void j1(int *res){
res[0]++;
for(int i = 0; i < 303; i++){
if(res[i]/10 == 0) break;
res[i+1] += res[i]/10;
res[i] %= 10;
}
}
void print(int *res){
bool nonzero = false;
for(int i = 303; i >= 0; i--){
if(nonzero || res[i] != 0){
nonzero = true;
cout << res[i];
}
}
}
int main() {
int len;
cin >> len;
int state[1001];
int gui[1001];
int cnt = 1;
for(int i = 1; i <= len; i++){
cin >> state[i];
if(state[i] == 1){
gui[cnt] = i;
cnt++;
}
}
cnt--;
if(cnt == 0) {
cout << 0 << endl;
return 0;
}
int offset;
if(cnt%2 == 1){
gui[0] = 0;
offset = -1;
}
else{
offset = 0;
}
int a[1001] = {0};
for(int i = 1 + offset; i <= cnt; i += 2){
for(int j = gui[i]; j < gui[i+1]; j++){
a[j] = 1;
}
}
int res[1000] = {0};
for(int i = len-1; i >= 0; i--){
c2(res);
if(a[i]) j1(res);
}
print(res);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator