1 条题解

  • 0
    @ 2025-5-12 21:29:01

    题目要求给丁一个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
    上传者