contact

给一个很长很长的主串（0 和 1）， 需要求出长度从 A 到 B 的所有模式串各自出现的频数，最后输出频数由大到小的 N 个，频数相等的串还得按长度顺序、二进制顺序每行 6 个输出。

刚开始就想到，找长度为 x 的模式串只要从 0 ~ 2^x - 1 二进制就可以了。

然后就是这些 “模式串 + 频率” 怎么存，很容易想到用结构，那么是“频率，一组模式串”，还是直接每个模式串都存一个变量，“频率，一个模式串 ”存一大堆呢。我选择了后者，对每个模式串都存一下，模式串当然不想开 char*，不想管动态内存。于是我用了“长度 + 二进制值”表示模式串，在输出的时候再用个函数转换成字符串就好了。

长度最长为 12 的模式串是 4096 个，再加上长度从1 到 11 的，总共不超过 8192 个，我就开了这么大一个数组，反正内存不要钱。输出前用快排，定义排序按照频数降序，长度升序，二进制值升序。

匹配？

然后就是字符串匹配。原来我用了 kmp，自以为很快，结果很快就崩了，一个 Test 运行了 7s。我以为是后面的快排慢了，结果发现问题就在一句 kmp 上，注释掉就不到 1s 了。

就算 kmp 算法是 O(n)，那么对于主串 200000，模式串长度为 12 的，共有 4096 个模式串，做 4096 次 kmp，这也有点长了。还有，这个字符串分明是 01 组成的。所以又想到一种办法，就取 12 个连续字符， 看它们是哪一个模式串。进一步，这里还可以直接看作二进制转换成 int，然后给那个模式串 ++ 就可以了。这样对于某一长度的模式串，从前往后一遍，O(n) 的时间，每个模式串多少次就全出来了。完美！

struct Pattern{
    int ptn; //二进制的模式串
    int len; //模式串的长度
    int count; //出现的次数
};

int value(const char* T, int start, int len){
    int val = 0;
    for(int i = 0; i < len; i ++){
        val = val * 2 + (T[start + i] - '0');
    }
    return val;
}

//从整数里得到二进制的模式串
void getPattern(char *P, int n, int len){ 
    for(int i = len - 1; i >= 0; i --){
        P[i] = '0' + n % 2;
        n /= 2;
    }
    P[len] = '\0';
}

//count 降序， len 升序， ptn 升序；
int compar(const void* pattern1, const void* pattern2){ 
    int diffCount = ((Pattern*)pattern2)->count - ((Pattern*)pattern1)->count;
    if(diffCount != 0) return diffCount;
    int diffLen = ((Pattern*)pattern1)->len - ((Pattern*)pattern2)->len;
    if(diffLen != 0) return diffLen;
    return ((Pattern*)pattern1)->ptn - ((Pattern*)pattern2)->ptn;
}

int main(){
    FILE *fin = fopen("contact.in", "r");
    FILE *fout = fopen("contact.out", "w");
    int A, B, N, Tlen;
    char T[200010] = "", temp[81], P[13];
    fscanf(fin, "%d %d %d", &A, &B, &N);
    while(fscanf(fin, "%s", temp) != EOF){
        strcat(T, temp);
    }
    Tlen = strlen(T);

    Pattern patterns[4096];
    int Patlen = 0;
    int *count[12 + 1]; //count[len][value], 长度为len, 二进制值为 value 的计数
    for(int len = A; len <= B; len ++){
        count[len] = new int[1 << len];
        for(int val = 0; val < (1 << len); val ++){
            count[len][val] = 0;
        }
        for(int i = 0; i <= Tlen - len; i ++){
            count[len][value(T, i, len)] ++;
        }
        for(int val = 0; val < (1 << len); val ++){
            if(count[len][val] != 0){
                patterns[Patlen].ptn = val;
                patterns[Patlen].len = len;
                patterns[Patlen].count = count[len][val];
                Patlen ++;
            }
        }
        delete[] count[len];
    }

    qsort(patterns, Patlen, sizeof(Pattern), compar);

    int lastCount = 0, countPattern = 0, countFreq = 0, i;
    for(i = 0; i < Patlen; i ++){
        getPattern(P, patterns[i].ptn, patterns[i].len);
        if(lastCount == patterns[i].count){
            if(countPattern == 6) {
                fprintf(fout, "\n%s", P); countPattern = 0;
            }else{                
                fprintf(fout, " %s", P);
            }
            countPattern ++;
        }else{
            countPattern = 0;
            if(countFreq == N) break; //在这里break才能使最后一个频率的数据完整输出
            if(i == 0){
                fprintf(fout, "%d\n%s", patterns[i].count, P);
            }else{
                fprintf(fout, "\n%d\n%s", patterns[i].count, P);
            }
            countPattern ++;            
            lastCount = patterns[i].count;
            countFreq ++;
        }
        // fprintf(fout, "%s %d\n", P, patterns[i].count);
    }
    fprintf(fout, "\n");
    // fprintf(fout, "%s\n", T);

    return 0;
}

输出写得非常丑。运行时间正好没有太慢。

Executing...
   Test 1: TEST OK [0.000 secs, 4292 KB]
   Test 2: TEST OK [0.000 secs, 4296 KB]
   Test 3: TEST OK [0.000 secs, 4300 KB]
   Test 4: TEST OK [0.000 secs, 4292 KB]
   Test 5: TEST OK [0.182 secs, 4296 KB]
   Test 6: TEST OK [0.448 secs, 4300 KB]
   Test 7: TEST OK [0.448 secs, 4292 KB]

All tests OK.
Your program ('contact') produced all correct answers!  This is your
submission #6 for this problem.  Congratulations!

stamp：和背包问题相似的 DP

题目给了 N 种不同面值的邮票，而且最多只能贴 K 张，问所有能贴出来的总面值里面，做多能从 1 到多少。

感觉前面见过很相似的问题了。很可能就是开个二维数组，行表示各种值，列表示新增加一种面值，存一下还能贴几张。先在草稿纸上画一画：

嗯果然，没问题了。而且果然，只要从左到右算，就能缩减到一维数组里面，其实一维数组就够了。代码：

#include <cstdio>
#include <cstdlib>
#define max(a, b) ((a) > (b)? (a): (b))
#define min(a, b) ((a) < (b)? (a): (b))

int compar(const void* a, const void* b){
    return *(int*)a - *(int*)b;
}

int main(){
    FILE *fin = fopen("stamps.in", "r");
    FILE *fout = fopen("stamps.out", "w");

    const int maxK = 200, maxN = 50, Len = 2000000; //能贴K个邮票，邮票有N种
    int K, N;
    int dp[Len]; //内存应该不够
    int S[maxN];

    fscanf(fin, "%d %d", &K, &N);
    for(int i = 0; i < N; i ++){
        fscanf(fin, "%d", S + i);
    }
    qsort(S, N, sizeof(int), compar);

    dp[0] = K;
    for(int i = 1; i < Len; i ++) dp[i] = -1;
    for(int i = 0; i < N; i ++){ //又有一种邮票S[i]能用
        for(int j = 0; j < min(Len - S[i], S[i] * K); j ++){
            dp[j + S[i]] = max(dp[j + S[i]], dp[j] - 1);
        }
    }

    int continuous;
    for(continuous = 1; continuous < Len; continuous ++){
        if(dp[continuous] < 0) break;
    }

    fprintf(fout, "%d\n", continuous - 1);

    return 0;
}

核心代码只有几行，初始化，两层循环。

我以为题目给的内存还是 4000 + kB，而且我这里可能是因为设置的原因，数组达到 1000000 main 函数就崩了，段错误。强行开了最大值的数组，结果扔到上面，通过了……给我了这么大的内存，谢天谢地。

Executing...
   Test 1: TEST OK [0.000 secs, 11864 KB]
   Test 2: TEST OK [0.000 secs, 11864 KB]
   Test 3: TEST OK [0.000 secs, 11868 KB]
   Test 4: TEST OK [0.000 secs, 11868 KB]
   Test 5: TEST OK [0.000 secs, 11864 KB]
   Test 6: TEST OK [0.000 secs, 11868 KB]
   Test 7: TEST OK [0.000 secs, 11860 KB]
   Test 8: TEST OK [0.000 secs, 11868 KB]
   Test 9: TEST OK [0.000 secs, 11860 KB]
   Test 10: TEST OK [0.014 secs, 11864 KB]
   Test 11: TEST OK [0.084 secs, 11864 KB]
   Test 12: TEST OK [0.014 secs, 11868 KB]
   Test 13: TEST OK [0.000 secs, 11868 KB]

All tests OK.
Your program ('stamps') produced all correct answers!  This is your
submission #4 for this problem.  Congratulations!

DP 想出来真开心，代码简直瞬间就写完了……