数独挑战

很简单但是给我启发很大的题目。对于怎么确定要填的数字所在小方块位置使用打表的方法，这一点一开始没能想到。

#include <bits/stdc++.h>
using namespace std;
int cnt;
int col[10][10],line[10][10],squr[10][10];
int arr[10][10];
int num[10][10] = {
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9}
};
struct Node{
    int x,y;
}a[100];
bool check(int x,int y,int z){
    return line[x][z] || col[y][z] || squr[num[x][y]][z];
}
void dfs(int pos){
    if (pos>cnt){
        for (int i=1;i<=9;i++){
            for (int j=1;j<=9;j++)
                printf("%d ",arr[i][j]);
            printf("\n");
        }
        return;
    }
    for (int i=1;i<=9;i++){
        int xx = a[pos].x,yy = a[pos].y;
        if (check(xx,yy,i)) continue;
        arr[xx][yy] = i;
        line[xx][i] = 1;
        col[yy][i] = 1;
        squr[num[xx][yy]][i] = 1;
        dfs(pos+1);
        arr[xx][yy] = 0;
        line[xx][i] = 0;
        col[yy][i] = 0;
        squr[num[xx][yy]][i] = 0;
    }
}
signed main(){
    for (int i=1;i<=9;i++){
        for (int j=1;j<=9;j++){
            scanf("%d",&arr[i][j]);
            if (arr[i][j]==0){
                cnt++;
                a[cnt].x = i;
                a[cnt].y = j;
            }
            else {
                line[i][arr[i][j]] = 1;
                col[j][arr[i][j]] = 1;
                squr[num[i][j]][arr[i][j]] = 1;
            }
        }
    }
    dfs(1);
}

幸运数字Ⅱ

思路很快就想到，就是枚举幸运数字然后一个个计数。

但是在某个点上调了很久，

//错误代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int l,r,ans;
int mini = 1e18;
void dfs(int num,bool ok){
    if (num>=r){
        mini = min(num,mini);
        return;
    }
    if (num>=l&&ok){
        ans += (num-l+1ll) * num;
        l = num + 1ll;//错误点在这里
    }
    dfs(num*10ll+4ll,1);
    dfs(num*10ll+7ll,1);
}
signed main(){
    scanf("%lld%lld",&l,&r);
    dfs(0,0);
    //cout<<l<<endl;
    ans += (r-l+1ll) * mini;
    printf("%lld",ans);
}

说一下错误原因：枚举的时候，是按前序遍历枚举的，即先枚举到的数不是最小数，但我默认了先枚举到的就是最小数，根据这个数调整左指针。

正确思路：依旧是全部枚举，但要将这些数都放在容器里，排序后逐一二分搜索。

//正确思路
#include <bits/stdc++.h>
#define int long long
using namespace std;
int l,r,ans;
int maxi = 5e9;
vector<int>v;
void dfs(int num,bool ok){
    if (num>=maxi){
        return;
    }
    if (ok){
        v.push_back(num);
    }
    dfs(num*10ll+4ll,1);
    dfs(num*10ll+7ll,1);
}
signed main(){
    scanf("%lld%lld",&l,&r);
    dfs(0,0);
    sort(v.begin(),v.end());
    for (auto it:v){
        if (l>r) break;
        int pos = upper_bound(v.begin(),v.end(),l) - v.begin();
        if (pos>0&&v[pos-1]>=l) pos--;
        ans += (min(v[pos],r)-l+1) * v[pos];//这边需要注意
        l = v[pos] + 1;//调整左指针
    }
    printf("%lld",ans);
}