1 条题解
-
0
题目要求给丁一个01字符串,并且给丁A,B,N要求找出长度A<=Len<=B 的出现频率最高的N中字符串。
如果出现频率相同按照字符串长度排序,如果长度也相同,按照字典序排序。我用类似tire 树的方法解这到
题目,当然速度比较慢。1032ms -.-b 。由于串只有01,那么我们可以建立如下的树:
这个类似字典树的树,由于只有两个儿子,那么可以用类似堆的结构来保存,我们对字符串进行插入操作,就像对字典树进行插入操作一样,统计次数,最后进行排序输出即可:
#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; }
- 1
信息
- ID
- 175
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者