CF 490E 贪心,回溯法

Advertisement

题目链接:这里
题意:一个严格递增序列 某些数字的某些位被盖住了 求 恢复后的序列。
解法:贪心,让每个数在大于前一个的基础上尽量小,先考虑数字长度。if(len[i] < len[i+1])输出NO,当len[i] > len[i-1],如果第一位是?就改成1,其他的问号改成0,接下来是长度相等的时候DFS(回溯法)即可。

//CF 490E

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
char a[maxn][10];
int n, len[maxn];
bool dfs(int i, int j, bool flag){//r行c列是否满足>关系
    if(j == len[i]){
        return flag;
    }
    if(a[i][j] != '?'){
        if(!flag && a[i][j] < a[i-1][j]) return false;
        return dfs(i, j+1, flag|(a[i][j]>a[i-1][j]));
    }else{
        if(flag){
            a[i][j] = '0';
            if(dfs(i, j+1, 1)) return true;
            a[i][j] = '?';
            return false;
        }
        else{
            for(char k = a[i-1][j]; k <= '9'; k++){
                a[i][j] = k;
                if(dfs(i, j+1, k > a[i-1][j])) return true;
            }
            a[i][j] = '?';
            return false;
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%s", a[i]);
        len[i] = strlen(a[i]);
    }
    for(int i = 1; i <= n; i++){
        if(len[i] < len[i-1]){
            puts("NO");
            return 0;
        }
        else if(len[i] == len[i-1]){
            if(dfs(i, 0, 0) == false){
                puts("NO");
                return 0;
            }
        }
        else{
            if(a[i][0] == '?') a[i][0] = '1';
            for(int j = 1; j < len[i]; j++) if(a[i][j] == '?') a[i][j] = '0';
        }
    }
    puts("YES");
    for(int i = 1; i <= n; i++) puts(a[i]);
    return 0;
}

Similar Posts:

  • 0-1背包问题求解归纳(动态规划法,贪心算法,回溯法,分治法和分支界限法)__更新到完整

    0-1背包问题是一个经典的算法问题,问题定义如下: 有n个物品 重量分别为W={w1, w1, w3, ..., wn}, 价值分别为V={v1, v2, v3, ..., vn}. 现在要将这N个物品放入允许的最大重量为w的包中,问怎样选择物品能使包中的物品总价值最大. 下面分别用动态规划法,贪心算法,回溯法,分治法和分支界限法求解 1.动态规划法

  • 分支限界与回溯法对比

    分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法.但在一般情况下,分支限界法与回溯法的求解目标不同.回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解. 由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同.回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T.分支限界法的搜索

  • 回溯法与分支限界算法

    回溯法 1.概念 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就"回溯"返回,尝试别的路径. 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 许多复杂的,规模较大的问题都可以使用回溯法,有"通用解题方法"的美称. 2.基本思想

  • UVA - 524 Prime Ring Problem(dfs回溯法)

    UVA - 524 Prime Ring Problem Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Description A ring is composed of n (even number) circles as shown in diagram. Put natural numbers into each circle separately, and the sum of numbers in two

  • HDU 2553 n皇后问题(回溯法)

    DFS Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Description 在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上. 你的任务是,对于给定的N,求出有多少种合法的放置方法. Input 共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量:如果N=0,表示结束. Output 共有若干行,每行一个正整数,表

  • 回溯法求解N皇后问题(Java实现)

    回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并以此慢慢地扩大问题规模,迭代地逼近最终问题的解.这种迭代类似于穷举并且是试探性的,因为当目前的可能答案被测试出不可能可以获得最终解时,则撤销当前的这一步求解过程,回溯到上一步寻找其他求解路径. 为了能够撤销当前的求解过程,必须保存上一步以来的求解路径,这一点相当重要. 光说不做没意思,用学过的算法题来运用一下. N 皇后问题:在一个 N * N 的国际象棋棋盘中,怎样放置 N 个皇后才能使 N

  • 回溯法子集树与排列树

    当所给问题是从n个元素的集合S中找出满足某种性质的子集时,解空间为子集树. 当所给问题是从n个元素的集合S中找出满足某种性质的排列时,解空间为排列树. 回溯法搜索子集树算法描述为: void backtrack(int t) { if(t>n) output(x); else for(int i=0; i<=1; i++) { x[t] = i; if(constraint(t) && bound(t)) backtrack(t+1); } } 回溯法搜索排列树的描述为: vo

  • 回溯法求解n皇后和迷宫问题

    回溯法是一种搜索算法,从某一起点出发按一定规则探索,当试探不符合条件时则返回上一步重新探索,直到搜索出所求的路径. 回溯法所求的解可以看做解向量(n皇后坐标组成的向量,迷宫路径点组成的向量等),所有解向量的几何称为解空间.理论上说,回溯法可以遍历有限个解组成的解空间. 首先介绍回溯法中所需的几个要素: 起点 解向量中第一个元素,第一个可能取得的值. 如迷宫的起点或者假设第一个皇后在(1,1)的位置. 遍历解向量中下一个元素所有可能取值的方法 如迷宫中四个方向沿顺时针试探,n皇后中行优先遍历二维数

  • 回溯法(非递归实现)

    问题:给出一些数目,可以用加减乘除计算结果,求一些满足条件的结果.例如算24点. 简化:生成+-*/的所有可能计算方式.(貌似不是数学中的排列,也不是数学中的组合) 求解:(非递归)回溯法. #include <iostream> using namespace std; // 0=>+, 1=>-, 2=>*, 3=>/ int op[100]; int count = 0; void output(int n) { for(int i = 0; i <= n-

  • 回溯法小实例

    1.图的m着色问题: 1 /* 2 *问题描述:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各个顶点着色,每个顶点着一种颜色.是否有一种着色法使G中每条边的两个顶点着不同的颜色. 3 * 这个问题是图的m可着色判定问题.若一个图最少需要m中颜色才能使图中每条边连接的2个顶点着不同的颜色,则称这个数m为该图的色数. 4 *算法分析:给定图G=(V,E)和m中颜色,如果这个图不是m可着色,给出否定回答:如果这个图是m可着色的,找出所有不同的着色法. 5 * 回溯法+子集树 6 * 问题的解空

Tags: