头像

GHOSTANDBREAD




离线:19小时前


最近来访(78)
用户头像
an_87
用户头像
qiao
用户头像
Mångata_9
用户头像
AmazingMing
用户头像
贾淏文
用户头像
QiiLin
用户头像
Gunnvor5
用户头像
白执事ღ
用户头像
qwwjh
用户头像
yyl__
用户头像
Depojhy
用户头像
爱吃干煸鱼的大布丁
用户头像
小轩喵灬
用户头像
坚持就行
用户头像
混个国奖就行
用户头像
AI小海
用户头像
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ
用户头像
_魂淡_
用户头像
五柳先生
用户头像
萌妹

活动打卡代码 AcWing 905. 区间选点

证明

定义:ans是题目应该的答案, cnt是通过贪心算法得出的解

证明 ans<=cnt: cnt 是一种可行方案, ans是可行方案的最优解,也就是最小值,所以自然ans <= cnt

证明 ans>=cnt: cnt可行方案是一个区间集合,区间从小到大排序,两两之间不相交, 所以要覆盖这些区间,至少需要cnt个点,所以答案应该 >= cnt,所以ans >= cnt

则ans = cnt,证明了这个贪心算法是正确的

y 总 版 (更快)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (range[i].l > ed)
        {
            res ++ ;
            ed = range[i].r;
        }

    printf("%d\n", res);

    return 0;
}

pair 版

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
vector<PII> rig;

bool cmp(PII a, PII b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int t;
    cin >> t;

    while(t --) {
        int l, r;
        cin >> l >> r;
        rig.push_back({l, r});
    }

    sort(rig.begin(), rig.end(), cmp);

    int tmp = -0x3f3f3f3f, cnt = 0;
    for(auto x : rig) {
        if(tmp < x.first) {
            cnt ++;
            tmp = x.second;
        } 
    }

    cout << cnt;

    return 0;
}



分享 抽象工厂

1.jpg


①增加产品族,是符合开闭原则的
②增加产品等级结构,需要修改每个产品族的代码,不符合开闭原则


package Abstract_Factory;

public interface Creator {
    public ProductA factoryA();
    public ProductB factoryB();
}


package Abstract_Factory;

public class Creator1 implements Creator{   // 产品族 1
    public ProductA factoryA() {
        return new ProductA1();
    }

    public ProductB factoryB() {
        return new ProductB1();
    }
}


package Abstract_Factory;

public class Creator2 implements Creator{   // 产品族 2
    public ProductA factoryA() {
        return new ProductA2();
    }

    public ProductB factoryB() {
        return new ProductB2();
    }
}


package Abstract_Factory;

public interface ProductA {    // 产品等级结构 A
    public void show();
}


package Abstract_Factory;

public class ProductA1 implements ProductA{
    public void show() {
        System.out.println("这是A1");
    }
}


package Abstract_Factory;

public class ProductA2 implements ProductA{
    public void show() {
        System.out.println("这是A2");
    }
}


package Abstract_Factory;

public interface ProductB {      // 产品等级结构 B
    public void show();
}


package Abstract_Factory;

public class ProductB1 implements ProductB{
    public void show() {
        System.out.println("这是B1");
    }
}


package Abstract_Factory;

public class ProductB2 implements ProductB{
    public void show() {
        System.out.println("这是B2");
    }
}


package Abstract_Factory;

public class Client {
    public static void main(String[] args) {
        Creator c1 = new Creator1();    // 产品族 1 的工厂
        ProductA pa1 = c1.factoryA();   // 生产 A1
        ProductB pb1 = c1.factoryB();   // 生产 B1
        pa1.show();
        pb1.show();

        System.out.println();

        Creator c2 = new Creator2();    // 产品族 2 的工厂
        ProductA pa2 = c2.factoryA();   // 生产 A2
        ProductB pb2 = c2.factoryB();   // 生产 B2
        pa2.show();
        pb2.show();
    }
}

例题

1.jpg 2.jpg 3.jpg 4.jpg



package Homework_Abstract_Factory;

public abstract class EnemyFactory {    // 工厂
   public abstract Fighter getFighter();   // 抽象类中只定义函数而不实现只能是抽象函数
   public abstract Monster getMonster();   // 需要加上 abstract 前缀

    public static EnemyFactory getAFactory(String choice) {
        EnemyFactory ef = null;
        if(choice.equals("初级")) ef = new SlowEnemyFactory();
        else if(choice.equals("中级")) ef = new MedEnemyFactory();
        else ef = new SupEnemyFactory();
        return ef;
        }
}



package Homework_Abstract_Factory;

public class SlowEnemyFactory extends EnemyFactory{  // 初级工厂
    public Fighter getFighter() {
        return new SlowFighter();
    }
    public Monster getMonster() {
        return new SlowMonster();
    }
}


package Homework_Abstract_Factory;

public class MedEnemyFactory extends EnemyFactory{   // 中级工厂
    public Fighter getFighter() {
        return new MedFighter();
    }
    public Monster getMonster() {
        return new MedMonster();
    }
}


package Homework_Abstract_Factory;

public class SupEnemyFactory extends EnemyFactory{   // 高级工厂
    public Fighter getFighter() {
        return new SupFighter();
    }
    public Monster getMonster() {
        return new SupMonster();
    }
}



package Homework_Abstract_Factory;

public interface Fighter {          // 士兵接口
    public void getSpeed();
    public void getWeapon();
}


package Homework_Abstract_Factory;

public class SlowFighter implements Fighter{   // 初级士兵
    int SlowSpeed = 10;
    String SlowWeapon = "初级武器";

    public void getSpeed() {
        System.out.println("初级士兵的移速:" + SlowSpeed);
    }
    public void getWeapon() {
        System.out.println("初级士兵的武器:" + SlowWeapon);
    }
}


package Homework_Abstract_Factory;

public class MedFighter implements Fighter{   // 中级士兵
    int MedSpeed = 100;
    String MedWeapon = "中级武器";

    public void getSpeed() {
        System.out.println("中级士兵的移速:" + MedSpeed);
    }
    public void getWeapon() {
        System.out.println("中级士兵的武器:" + MedWeapon);
    }
}


package Homework_Abstract_Factory;

public class SupFighter implements Fighter{     // 高级士兵
    int SupSpeed = 1000;
    String SupWeapon = "高级武器";

    public void getSpeed() {
        System.out.println("高级士兵的移速:" + SupSpeed);
    }
    public void getWeapon() {
        System.out.println("高级士兵的武器:" + SupWeapon);
    }
}


package Homework_Abstract_Factory;

public interface Monster {          // 怪兽接口
    public void getVitality();
    public void getIntelligence();
}


package Homework_Abstract_Factory;

public class SlowMonster implements Monster{    // 初级怪兽
    int SlowVitality = 10;
    String SlowIntelligence = "反应迟钝";

    public void getVitality() {
        System.out.println("初级怪兽的生命值:" + SlowVitality);
    }
    public void getIntelligence() {
        System.out.println("初级怪兽的智力情况:" + SlowIntelligence);
    }
}


package Homework_Abstract_Factory;

public class MedMonster implements Monster{     // 中级怪兽
    int MedVitality = 100;
    String MedIntelligence = "反应适度";

    public void getVitality() {
        System.out.println("中级怪兽的生命值:" + MedVitality);
    }
    public void getIntelligence() {
        System.out.println("中级怪兽的智力情况:" + MedIntelligence);
    }
}


package Homework_Abstract_Factory;

public class SupMonster implements Monster{     // 高级怪兽
    int SupVitality = 1000;
    String SupIntelligence = "反应敏捷";

    public void getVitality() {
        System.out.println("高级怪兽的生命值:" + SupVitality);
    }
    public void getIntelligence() {
        System.out.println("高级怪兽的智力情况:" + SupIntelligence);
    }
}


package Homework_Abstract_Factory;
import java.util.Scanner;

public class Client {    
    public static void main(String[] args) {      // 主函数

        Scanner reader = new Scanner(System.in);

        String s = "";

        while(!s.equals("0")) {

            System.out.println("请输入选择难度:1 为初级,2 为中级,3 为高级. 0 为退出 :");
            s = reader.nextLine();

            EnemyFactory ef = null;

            if(s.equals("0")) {
                System.out.println("退出成功!");
                break;
            }
            else if(s.equals("1")) ef = EnemyFactory.getAFactory("初级");

            else if(s.equals("2")) ef = EnemyFactory.getAFactory("中级");

            else ef = EnemyFactory.getAFactory("高级");

            Fighter f = ef.getFighter();
            Monster m = ef.getMonster();
            f.getSpeed();
            f.getWeapon();
            m.getVitality();
            m.getIntelligence();

            System.out.println();
        }
    }
}






分享 工厂方法

1.png


①解决了增加新产品的问题(创建一个工厂和一个新产品即可)
②符合开闭原则
③一个工厂创建一个产品


代码模板:

public interface Creator{
    public Product factory();  // 工厂返回值为产品超类的类型
}


public class CreatorA implements Creator{
    public Product factory(){
        return new ProductA();
    }
}


public class CreatorB implements Creator{
    public Product factory(){
        return new ProductB();
    }
}


public interface Product{
    public void show();
}


public class ProductA implements Product{
    public void show(){
        System.out.println("正在生产A产品");
    }
}


public class ProductB implements Product{
    public void show(){
        System.out.println("正在生产B产品");
    }
}


public class Client{
    public static void main(String[] args){
        Creator c = new CreatorA();
        Product p = c.factory();
        p.show();
    }
}




例题:

2.png


public interface Creator {
    public Fruit factory();
}


public class CreatorApple implements Creator{
    public Fruit factory() {
        return new Apple();
    }
}


public class CreatorGrape implements Creator{
    public Fruit factory() {
        return new Grape();
    }
}


public class CreatorStrawberry implements Creator{
    public Fruit factory() {
        return new Strawberry();
    }
}


public interface Fruit {
    public void show();
}


public class Apple implements Fruit {
    public void show() {
        System.out.println("正在生产苹果");
    }
}


public class Grape implements Fruit {
    public void show() {
        System.out.println("正在生产葡萄");
    }
}


public class Strawberry implements Fruit{
    public void show() {
        System.out.println("正在生产草莓");
    }
}


import java.util.Scanner;

public class Client {
    public static void main(String[] args) {

        Scanner reader = new Scanner(System.in);

        String s;
        s = "";

        while(!s.equals("0")) {
            System.out.println("请输入要生产的水果,苹果输入 1,葡萄输入 2,草莓输入 3, 退出输入 0 !");
            s = reader.nextLine();

            Creator c = null;

            if(s.equals("0")) {
                System.out.println("退出成功!");
                break;
            }
            else if(s.equals("1")) c = new CreatorApple();

            else if(s.equals("2")) c = new CreatorGrape();

            else c = new CreatorStrawberry();

            Fruit f = c.factory();
            f.show();
        }
    }
}




大佬题解


朴素版

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 12, M = 1 << N;  // N多开了一个,因为枚举列数时要多枚举一列
ll f[N][M];   //  范围超int
bool st[M];   // 状态的合法性

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int n, m;

    while(cin >> n >> m, n || m) {

        // 预处理,判断合并列的状态 i 是否合法
        // 合并列的某行是 1 表示横放,是 0 表示竖放
        // 如果合并列不存在连续的奇数个 0,则为合法的

        for(int i = 0; i < 1 << n; i ++) {  // 枚举所有可能的列状态
            int cnt = 0; st[i] = true;      // cnt记录连续出现的 0 的个数
            for(int j = 0; j < n; j ++) {   // 枚举这个列状态的每一位
                if(i >> j & 1) {      // 当碰到 1 时
                //看这个1前面连续的0是奇数还是偶数,是奇数就不合法
                    if(cnt & 1) st[i] = false;   
                //每碰到一个1,cnt就重置为0,记录后面连续的 0 的个数
                    cnt = 0;                
                } else cnt ++;   // 碰到 0,记录 0 的个数
            }
            // 最后一段可能是连续的 0 ,没有被 1 截止,需要进行特判
            if(cnt & 1) st[i] = false;  
        }

        memset(f, 0, sizeof f);

        f[0][0] = 1;    // 第 0 列不横放是一种合法的方案

        // 棋盘的列是 0 ~ m - 1

        for(int i = 1; i <= m; i ++) {  
// 枚举每一列,从 1 开始,去找从第 0 列伸出的,枚举到m列,比棋盘多一列,因为m - //1列不能伸出方块了
            for(int j = 0; j < 1 << n; j ++) {   // 枚举第 i 列的状态
                for(int k = 0; k < 1 << n; k ++) {  // 枚举第i - 1 列的状态
                    // 两列不出现重叠的 1 && 没有连续的奇数个 0 
                    if((j & k) == 0 && st[j | k]) {  
                        f[i][j] += f[i - 1][k];      // 前一列兼容状态的方案数之和
                    }
                }
            }
        }

        cout << f[m][0] << endl;   // 从m - 1列伸出 0 个的方案数
    }

    return 0;
}

去除无效状态的优化写法

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 12, M = 1 << N;
ll f[N][M];
bool st[M];
vector<int> state[M];

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int n, m;

    while(cin >> n >> m, n || m) {
        for(int i = 0; i < 1 << n; i ++) {
            int cnt = 0; st[i] = true;
            for(int j = 0; j < n; j ++) {
                if(i >> j & 1) {
                    if(cnt & 1) {
                        st[i] = false;
                        break;
                    } 
                    cnt = 0;
                } else cnt ++;
            }
            if(cnt & 1) st[i] = false;
        }

        // 预处理, 每一列把它前面合法的列存起来

        for(int i = 0; i < 1 << n; i ++) {
            state[i].clear();
            // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
            // 解释一下st[j | k] 
            // 已经知道st[]数组表示的是这一列没有连续奇数个0的情况,
            // 我们要考虑的是第i-1列(第i-1列是这里的主体)中从第i-2列横插过来的,
            // 还要考虑自己这一列(i-1列)横插到第i列的
            // 比如 第i-2列插过来的是k=10101,第i-1列插出去到第i列的是 j =01000,
            // 那么合在第i-1列,到底有多少个1呢?
            // 自然想到的就是这两个操作共同的结果:两个状态或。 j | k = 01000 | 10101 = // 11101
            // 这个 j|k 就是当前 第i-1列的到底有几个1,即哪几行是横着放格子的


            for(int j = 0; j < 1 << n; j ++) {
                if((i & j) == 0 && st[i | j]) 
                    state[i].push_back(j);
            }
            //二维数组state[j]表示第j行, 
            //j表示 第i列“真正”可行的状态,
            //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
            //“真正”可行是指:既没有前后两列伸进伸出的冲突;又没有连续奇数个0。
        }

        memset(f, 0, sizeof f);

        f[0][0] = 1;

        //按定义这里是:前第-1列都摆好,且从-1列到第0列伸出来的状态为0的方案数。
        //首先,这里没有-1列,最少也是0列。
        //其次,没有伸出来,即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for(int i = 1; i <= m; i ++) {
            for(int j = 0; j < 1 << n; j ++) {  //遍历当前列(第i列)所有状态j
                for(auto k : state[j]) {    //遍历第i-1列的状态k,如果“真正”可行,就转移
                    f[i][j] += f[i - 1][k];     
                    // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
                }
            }
        }

        cout << f[m][0] << endl;

        //f[m][0]表示 前m-1列都处理完,并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数
    }

    return 0;
}


活动打卡代码 AcWing 4613. 方格跳跃

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 2e5 + 10;

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int n;
    cin >> n;

    string s;
    cin >> s;

    int cnt = 0;
    for(int i = 0; i < n; i ++) 
        if(s[i] == '<') cnt ++;
        else break;

    for(int i = n - 1; i >= 0; i --) 
        if(s[i] == '>') cnt ++;
        else break;

    cout << cnt;

    return 0;
}


活动打卡代码 AcWing 4612. 去掉0

思维题角度

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int t;
    cin >> t;

    while(t --) {
        string a;
        cin >> a;

        int l = a.size() - 1, r = 0, cnt = 0;
        for(int i = 0; i < a.size(); i ++) {
            if(a[i] == '1') l = min(l, i), r = max(r, i), cnt ++; 
        }
        if(!cnt) cout << 0 << endl;
        else cout << r - l + 1 - cnt << endl;
    }

    return 0;
}

双指针模拟

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int t;
    cin >> t;

    while(t --) {
        string a;
        cin >> a;

        int res = 0;
        for(int i = 0; i < a.size() - 1; ) {
            if(a[i] == '1' && a[i + 1] == '0') {
                int j = i + 1, cnt = 0;
                while(a[j] == '0' && j < a.size()) cnt ++, j ++;
                if(j == a.size() && a[j - 1] != '1') break;
                else res += cnt, i = j;
            } else i ++;
        }
        cout << res << endl;
    }

    return 0;
}


分享 简单工厂

未命名图片.png

package Homework2;

public interface Fruit {
    public void show();
}

package Homework2;

public class Apple implements Fruit{
    public void show() {
        System.out.println("这是苹果的生长过程");
    }
}

package Homework2;

public class Grape implements Fruit{
    public void show() {
        System.out.println("这是葡萄的生长过程");
    }
}


package Homework2;

public class StrawBerry implements Fruit{
    public void show() {
        System.out.println("这是草莓的生长过程");
    }
}


package Homework2;

public class FruitFactory {
    public static Fruit getFruit(String choice) {
        if(choice.equals("1")) return new Apple();
        else if(choice.equals("2")) return new Grape();
        else return new StrawBerry();
    }
}

package Homework2;
import java.util.Scanner;

public class Client {
    public static void main(String[] args) {
        String choice;
        Scanner reader = new Scanner(System.in);

        choice = "";

        while(!choice.equals("0")) {
            System.out.println("请输入 1, 2, 3,退出请输入 0 :");
            choice = reader.nextLine();
            if(choice.equals("0")) {
                System.out.println("退出成功!");
                break;
            }
            Fruit f = FruitFactory.getFruit(choice);
            f.show();
        }
    }
}



活动打卡代码 AcWing 900. 整数划分

大佬题解


1.完全背包方法

f[i][j] 表示1 ~ i 中取数和正好是 j 的 方案数量
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ... f[i - 1][j - s * i]
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + ... + f[i - 1][j - s * i]
f[i][j] = f[i - 1][j] + f[i][j - i];
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1010, mod = 1e9 + 7;
int f[N][N];

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int n;
    cin >> n;

    for(int i = 0; i <= n; i ++) f[i][0] = 1;

    for(int i = 1; i <= n; i ++) {
        for(int j = 0; j <= n; j ++) {
            f[i][j] = f[i - 1][j];
            if(j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }
    }

    cout << f[n][n];

    return 0;
}
完全背包方法优化
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1010, mod = 1e9 + 7;
int f[N];

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int n;
    cin >> n;

// f[i][j] = f[i - 1][j] + f[i][j - i]   
// 用类似完全背包的优化方法进行降维优化
    for(int i = 0; i <= n; i ++) f[0] = 1;

    for(int i = 1; i <= n; i ++) {
        for(int j = i; j <= n; j ++) {
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }

    cout << f[n];

    return 0;
}

2.计数类dp

f[i][j] 表示总和为 i, 总个数为 j 的方案数
f[i][j] = f[i - 1][j - 1] + f[i - j][j]
把所有方案分成组成数字最小为1的和最小数字大于1的
最小数字为1的方案,把最小的数字1删去也就是f[i-1][j-1]与这个方案是一一对应的
最小数字大于1的方案,把所有数字都减去1,也就是f[i-j][j]与这个方案是一一对应的
两个方案相加
最后求f[n][i],i∈[1,n]
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1010, mod = 1e9 + 7;
int f[N][N];

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    int n;
    cin >> n;

    // f[i][j] = f[i - 1][j - 1] + f[i - j][j];

    f[0][0] = 1;  //总和为0,0个数的选择方案为1

    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= i; j ++) {
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i ++) res = (res + f[n][i]) % mod;

    cout << res;

    return 0;
}



类图:

微信图片_20220907180518.jpg

代码:

package homework;

public interface IBOOK {

    public void printTitle();
}

package homework;

public class PDFBook implements IBOOK{
    public void printTitle() {
        System.out.println("正在阅读PDF类型的书\n");
    }
}

package homework;

public class WordBook implements IBOOK{
    public void printTitle() {
        System.out.println("正在阅读Word类型的书\n");
    }
}

package homework;

public class TXTBook implements IBOOK{
    public void printTitle() {
        System.out.println("正在阅读Txt类型的书\n");
    }
}

package homework;

public class EBookReader {

    public void read(IBOOK ibook) {
        ibook.printTitle();
    }

}

package homework;
import java.util.Scanner;

public class User {
    public static void main(String[] args) {

        EBookReader er = new EBookReader();

        String s;
        Scanner reader = new Scanner(System.in);

        s = "";

        while(!s.equals("0")) {
            System.out.println("请输入要阅读的书的类型:  (PDF输入 1,Word输入 2,Txt输入 3)输入 0 退出! ");

            s = reader.nextLine();
            if(s.equals("0")) {
                System.out.println("退出成功");
                break;
            }

            if(s.equals("1")) {
                er.read(new PDFBook());
            } 
            else if(s.equals("2")) { 
                er.read(new WordBook());
            }
            else if(s.equals("3")) {
                er.read(new TXTBook());
            } 
            else System.out.println("输入错误,请正确输入!!\n");
        }
    }
}


活动打卡代码 AcWing 899. 编辑距离

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 15, M = 1010;
char a[M][N];
char target[N];
int f[N][N];

int solve(char a[], char b[]) {  // 返回两个数组的最小编辑次数
    int la = strlen(a + 1), lb = strlen(b + 1);
    for(int i = 0; i <= la; i ++) f[i][0] = i;
    for(int i = 0; i <= lb; i ++) f[0][i] = i;

    for(int i = 1; i <= la; i ++) {
        for(int j = 1; j <= lb; j ++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j]) 
            f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else 
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    return f[la][lb];
}

int main() {

    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++) scanf("%s", a[i] + 1); // 二维字符数组的逐行输入

    int limit;
    while(m --) {

        scanf("%s%d", target + 1, &limit);

        int cnt = 0; 
        for(int k = 1; k <= n; k ++) 
            if(solve(a[k], target) <= limit) cnt ++; // 遍历n个数组看有几个小于限制次数

        cout << cnt << endl;

    }

    return 0;
}

y 总 优 雅 版

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 15, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
    for (int i = 0; i <= la; i ++ ) f[i][0] = i;

    for (int i = 1; i <= la; i ++ )
        for (int j = 1; j <= lb; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    return f[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1);

    while (m -- )
    {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i ++ )
            if (edit_distance(str[i], s) <= limit)
                res ++ ;

        printf("%d\n", res);
    }

    return 0;
}