题目传送门

Description

小睿睿在游戏开始时有n根火柴棒,他想知道能摆成形如“A+B=n”的等式且使用的火柴棒数也恰好等于n/k的等式有多少种(B+A=n与A+B=n看作一种)
注:
“=”与“+”分别需要使用2根火柴棒

Solution

思维DP题。

设 $f[i]$ 表示 $i$ 这个数需要用多少火柴棒摆出来,易得 $f[i]=f[i/10]+a[i%10]$

然后直接计算,若 $f[i]+2+f[n-i]+2+f[n]==n/k$ , 则 $ans++$ 。

复杂度 $O(n)$

Code

/*
 * @Name: 371A.cpp
 * @Author: Lovely_XianShen
 * @Date: 2019-11-06 20:58:11
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

const int N = 5e7 + 5;

int dp[N], a[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int n, k;

int main() {
    n = read();
    k = read();

    for (int i = 1; i <= n; i++)
        dp[i] = dp[i / 10] + a[i % 10];
    dp[0] = 6;
    int ans = 0;
    for (int i = 0; i <= n / 2; i++)
        if (dp[i] + 2 + dp[n - i] + 2 + dp[n] == n / k)
            ans++;
    cout << ans << endl;
    return 0;
}