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

2248K 1032MS 1A 还是比较水的,暴力就是线性复杂度

Posted by KatrineYang at 2016-08-25 03:07:20 on Problem 1174 and last updated at 2016-08-25 03:09:55
另外要注意一点,输出前N个的时猴,是前N个不同的次数,而不是前N个不同的string
比如样例如果只输出
23 00
15 10 01
12 100
11 001 000 11
10 010
8 0100
7 1001
那就WA了
#include <iostream>
#include <stdio.h>
using namespace std;

int gs[13][4097] = {0};

bool s[2000002] = {0};
bool used[13][4097] = {0};

inline int mn(int a, int b){
	return a<b ? a : b;
}

int main() {
	int N, A, B;
	scanf("%d%d%d\n", &A, &B, &N);
	int offset = 0;
	while(1){
		char c = getchar();
		if(c == '2') break;
		s[offset] = c - '0';
		offset++;
		//printf("%c", c);
	}
	B = mn(B, offset);
	if(B < A) return 0;
	for(int i = A; i <= B; i++){
		int start = 0;
		int N2 = (1 << (i-1));
		for(int j = 0; j < i; j++){
			start *= 2;
			start += s[j];
		}
		gs[i][start]++;
		for(int j = i; j < offset; j++){
			start -= s[j-i] * N2;
			start *= 2;
			start += s[j];
			gs[i][start]++;
		}
	}
	for(int k = 0; k < N; k++){
		int thGs = 0;
		for(int i = B; i >= A; i--){
			int NB = (1 << i) - 1;
			for(int j = NB; j >= 0; j--){
				if(used[i][j]) continue;
				if(gs[i][j] > thGs){
					thGs = gs[i][j];
				}
			}
		}
		if(thGs == 0) break;
		printf("%d", thGs);
		for(int i = B; i >= A; i--){
			int NB = (1 << i) - 1;
			for(int j = NB; j >= 0; j--){
				if(gs[i][j] == thGs){
					used[i][j] = 1;
					printf(" ");
					for(int t = i-1; t >= 0; t--){
						if((j>>t)%2 == 0) printf("0");
						else printf("1");
					}
				}
			}
		}
		printf("\n");
	}
	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