Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

说一下这个题。。。

Posted by KatrineYang at 2016-07-09 10:38:44 on Problem 1090 and last updated at 2016-07-09 10:42:00
算法是这样的:先列出来所有为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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator