2_1

image.png

思路

對(duì)于我來說只能想到最笨的暴力方法，正解應(yīng)該是所謂的數(shù)位dp，有空要把這塊知識(shí)補(bǔ)一下，這里先欠一下數(shù)位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

思路

這題是看見了群里一個(gè)同學(xué)發(fā)的思路，然后順著這個(gè)思路，再加上一些優(yōu)化，就ac過了。具體是：首先找到一個(gè)距離當(dāng)前這個(gè)數(shù)字n最接近的兩個(gè)數(shù)，一個(gè)比n大(max)，一個(gè)比n小(min)，如果等于n直接返回所需要的1的個(gè)數(shù)。再遞歸處理n-min和n-max差值的絕對(duì)值，記錄本次min和max所使用的1的個(gè)數(shù)，返回使用個(gè)數(shù)較少的那個(gè)。剪枝主要就是加入|n-min|或者|n-max|大于原來的n，則無需在這個(gè)分支遞歸下去，它必然不會(huì)是最優(yōu)解了。

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;
}