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