最长公共子串、旋转骰子题解

最长公共子串

题目描述
给定两个字符串 a、b，现有k次机会对字符串中的字符进行修改，使修改后两个字符串的最长公共子串最长。
每一次修改，可以选择a、b字符串中某一个串的任意位置修改成任意字符。

输入格式:
第一行包括一个正整数 k。
第二行和第三行分别输入字符串 a、b。（每个串的长度不超过500）

输出格式:
输出为一个整数，表示修改后的两个串的最长公共子串长度。

解题思路
采用二重循环，在 a、b 字符串中选定不同起始位置，枚举所有可能，找最长子串的长度。

完整代码

#include<stdio.h>
#include<string.h>

int main()
{
    int k, n1, n2, ans = 0, count, i, j, p, q;
    char a[505], b[505];
    scanf("%d", &k);
    getchar();
    gets(a);
    gets(b);
    n1 = strlen(a);
    n2 = strlen(b);

    for (i = 0; i < n1; i++) {
        for (j = 0; j < n2; j++) {
            p = i;
            q = j;
            count = 0;
            while (count != k && p != n1 && q != n2) {
                if (a[p] != b[q]) {
                    count++;
                }
                p++;
                q++;
            }
            if (p - i > ans) {
                ans = p - i;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

旋转骰子

题目描述
玛莎有 n 个骰子，每个骰子的 6 个面上都恰好有一个 0 到 9 之间的数字。
现在玛莎将利用这 n 个骰子来制作新数字。她把 n 个骰子摆成一排，然后从左到右查看骰子的上表面并读取，即可得到一个新数字。随后她不断的旋转每个骰子的面就可以得到不同的新数字。旋转骰子需要满足以下规则：

1. 制作的数字不能包含前导零；
2. 制作新数字时不需要使用所有的骰子；
3. 使用骰子旋转，无法将数字 9 转换为数字 6 ，反之亦然。

给定 n 个骰子，玛莎可以用它们构成从 1 到 x 的所有整数。玛莎想知道，对于给定的 n 个骰子，这个 x 的最大取值是多少呢？

输入格式:
第一行仅一个整数 n ，表示骰子的数量（1≤n≤3）。
接下来 n 行，每行包含6个整数 a[i][j]（0≤ a[i][j] ≤9），表示第 i 个骰子的第 j 个面上的数字。

输出格式:
输出一个整数，即最大数 x ，玛莎可以使用她的骰子构成数字从 1 到 x。如果无法构成 1，则输出0。

解题思路

1.最多 3 个骰子的条件下，x 的最大值为 98。
2.任意一个骰子组成个位数，任意两个骰子组成十位数。1-100 分别对应 visit[1]-visit[100]，若组成数字 i，则 visit[i]=1。四重循环枚举任意两个骰子构成的十位数。
3.找出最大 x。

完整代码

#include<stdio.h>

int main()
{
    int n, i, j, p, q;
    int a[3][6], visit[100] = { 0 };
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < 6; j++) {
            scanf("%d", &a[i][j]);
            visit[a[i][j]] = 1;
        }
    }
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            for (p = 0; p < 6; p++) {
                for (q = 0; q < 6; q++) {
                    visit[a[i][p] * 10 + a[j][q]] = 1;
                    visit[a[j][q] * 10 + a[i][p]] = 1;
                }
            }
        }
    }
    for (i = 1; i < 100; i++) {
        if (visit[i] == 0) {
            break;
        }
    }
    printf("%d", i - 1);
    return 0;
}