2_1

image.png

思路

对于我来说只能想到最笨的暴力方法，正解应该是所谓的数位dp，有空要把这块知识补一下，这里先欠一下数位dp解法的代码。先上一段暴力代码，不过有8分还是很香的。

code

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

int main(int argc, char *argv[]) {
    long long n, i, ans = 0, temp;
    int x, m, count[10];
    scanf("%lld", &n);
    for(i = 101; i <= n; i++) 
    {
        memset(count, 0, sizeof(count));
        temp = i;
        m = 0;
        while(temp > 0)
        {
            x = temp % 10;
            if(!count[x])
            {
                m++;
                count[x]++;
            }
            temp /= 10;
        }
        if(m <= 2)
            ans++;
    }
    printf("%lld\n", n >= 100? ans + 100 : n);
    return 0;
}

2_2

2_2.PNG

思路

这题是看见了群里一个同学发的思路，然后顺着这个思路，再加上一些优化，就ac过了。具体是：首先找到一个距离当前这个数字n最接近的两个数，一个比n大(max)，一个比n小(min)，如果等于n直接返回所需要的1的个数。再递归处理n-min和n-max差值的绝对值，记录本次min和max所使用的1的个数，返回使用个数较少的那个。剪枝主要就是加入|n-min|或者|n-max|大于原来的n，则无需在这个分支递归下去，它必然不会是最优解了。

code

#include <bits/stdc++.h>
using namespace std;

long long t[15] = {1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111};
int r[10] = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3};

int dfs(long long n)
{
    if ( n <= 10)
        return r[n - 1];
    int l_m, r_m, l = 1e9, r = 1e9;
    for (int i = 0; i < 13; i++)
    {
        if (t[i] == n) return i + 1;
        else if (t[i] > n)
        {
            r_m = i;
            break;
        }
        else l_m = i;
    }
    
    if(abs(n - t[l_m]) <= n) l = l_m + 1 + dfs(abs(n - t[l_m]));
    if(abs(n - t[r_m]) <= n) r = r_m + 1 + dfs(abs(n - t[r_m]));

    return min(l, r);
}

int main() {
    long long n;
    scanf("%lld", &n);
    printf("%d\n", dfs(n));
    system("pause");
    return 0;
}