Educational Codeforces Round 8

A - Tennis Tournament

简单模拟

*B - New Skateboard

一条挺有意思的题目。

题意：给一个很长的十进制数字字符串（可以允许前导零）。求这个字符串有多少个子串（可以允许前导零），其表示的数字是4的倍数。

题解：考虑到 10 mod 4 = 2 ，而 100,1000,10000 等都是4的倍数，所以一个数是否是4的倍数，和百位及其以前无关，只和最后两位有关。所以对于每一个可能的4的倍数的个位（也就是每一个偶数），检测其是否搭配了正确的十位，若正确，那么前面的百位及其以前的位都可以作为开头。

char s[300005];

void TestCase() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 1; i <= n; ++i)
        s[i] = (s[i] - '0') % 4;
    ll sum = 0;
    for(int i = 1; i <= n; ++i) {
        if(s[i] == 1 || s[i] == 3)
            continue;
        if(s[i] == 0) {
            if(s[i - 1] == 0 || s[i - 1] == 2)
                sum += i;
            else
                sum += 1;
            continue;
        }
        if(s[i] == 2) {
            if(s[i - 1] == 1 || s[i - 1] == 3)
                sum += i - 1;
            continue;
        }
    }
    printf("%lld
", sum);
}

C - Bear and String Distance

随便贪心

*D - Magic Numbers

一个超恶心的数位dp。

题意：给两个不超过2000位的十进制数a和b，保证他们的位数相同。另外给两个数m([1,2000])和d([0,9])。定义一个数是“魔数”，当且仅当：

1、其是m的倍数
2、其所有的偶数位都是d，且所有的奇数位都不是d，这里是从把最高位看作第1位的。

求[a,b]之间有多少个“魔数”。

题解：由于m比较小，让人想起了这种某个比较小的数的倍数这种数位dp的套路，开一个余数位r来记录之。这个r的转移也是非常常见的。需要注意的是，这个位数d怎么判断。其实另开一个位k，来记录这是奇数位还是偶数位，那么在奇数位的时候跳过d，在偶数位的时候从d转移。**觉得自己很厉害，注意到了这里需要判断前导零对“最高位是第1位”的影响，当某个位是奇数位，且 lead&&i==0 的时候，下一位继续会是奇数位。不过当某个位是偶数位，就说明已经没有前导零了。

然后，因为不想计算a-1的值，所以直接判断a是否满足的，若a是满足的就把这个补上就可以了。求出(a,b]的合法值，然后补上a。

注意：
1、不要溢出。
2、不要到处取模。
3、按照我的数位dp模板的含义，只有在没有lead也没有limit的时候才会记录状态，这样的状态是和a,b无关的，可以一起使用。
4、在补上a的时候，不要忘记检测奇数位。

const int MOD = 1e9 + 7;

int m, d;

char a[2005], b[2005];
int di[2005];
int dp[2005][2005][2];

int dfs(int pos, int r, int k, bool lead, bool limit) {
    if(pos == 0)
        //递归到最后，奇偶位填d的限制已经在途中满足了，只需要余数也是0就可以了
        return (r == 0);
    if(!lead && !limit && dp[pos][r][k] != -1)
        return dp[pos][r][k];
    int up = limit ? di[pos] : 9;
    ll ans = 0;
    if(k == 0) {
        //偶数位，必须填d
        if(d > up) {
            if(!lead && !limit)
                dp[pos][r][k] = ans;
            return ans;
        }
        ans = dfs(pos - 1, (r * 10 + d) % m, 1, lead && d == 0, limit && d == di[pos]);
        if(!lead && !limit)
            dp[pos][r][k] = ans;
        return ans;
    } else {
        //奇数位，必须不填d
        for(int i = 0; i <= up; i++) {
            if(i == d)
                continue;
            //若这一位是0，并且还是前导0，那么下一位依然是奇数位
            ans += dfs(pos - 1, (r * 10 + i) % m, lead && i == 0 ? 1 : 0, lead && i == 0, limit && i == di[pos]);
        }
        ans %= MOD;
        if(!lead && !limit)
            dp[pos][r][k] = ans;
        return ans;
    }
}

int solve(int pos) {
    //一开始余数为0，且为奇数位
    return dfs(pos, 0, 1, true, true);
}

void TestCase() {
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &m, &d);
    scanf("%s", a + 1);
    int n = strlen(a + 1);
    for(int i = 1; i <= n; ++i)
        di[i] = a[n + 1 - i] - '0';
    ll tmp1 = solve(n);
    int r = 0;
    for(int i = 1; i <= n; ++i) {
        r = r * 10 + a[i] - '0';
        if(r >= m)
            r %= m;
    }
    if(r == 0) {
        int suc = 1;
        for(int i = 2; i <= n; i += 2) {
            if(a[i] - '0' != d) {
                suc = 0;
                break;
            }
        }
        if(suc) {
            for(int i = 1; i <= n; i += 2) {
                if(a[i] - '0' == d) {
                    suc = 0;
                    break;
                }
            }
        }
        if(suc)
            tmp1 -= 1;
    }
    scanf("%s", b + 1);
    int n2 = strlen(b + 1);
    for(int i = 1; i <= n2; ++i)
        di[i] = b[n2 + 1 - i] - '0';
    ll tmp2 = solve(n2);
    printf("%lld
", ((tmp2 - tmp1) % MOD + MOD) % MOD);
}