计软实验班小学期笔记(实时更新中)

实践学期

计软实验班小学期笔记(实时更新中)

前言：不到啊

求n种不同面额的纸币任选m张求总方案数

高中组合数学隔板法公式 C(n+m-1,n)

int C(int n,int m) {
    int ans=1;
    for(int i=1;i<=m;i++) {
        ans=ans*(n-m+i)/i;
    }
    return ans;
}

*热知识：杨辉三角 n行m列对应的数字就是 C(n,m) （0行开始)

21位的花朵数

任务描述

编写一个程序来寻找所有21位的十进制正整数，这些整数的每个位上的数字的21次方之和等于该整数本身。

定义

花朵数：一个N位的十进制正整数，如果它的每个位上的数字的N次方之和等于这个数本身，则称其为花朵数。
例子：
- 当N=3时，153是一个花朵数，因为 1^3 + 5^3 + 3^3 = 153。
- 当N=4时，1634是一个花朵数，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
- 当N=5时，92727是一个花朵数。

目标

求N=21时，所有满足条件的花朵数。输出所有符合条件的数字，每个数字占一行。

程序要求

输入：无
输出：所有21位的花朵数，每个数字占一行。
性能要求：程序应在1分钟内运行完毕。

示例输出

128468643043731391252
449177399146038697307

解题思路

由于直接枚举所有21位数所需时间非常大根据花朵数的性质我们可以dfs出0-9分别有几个

dfs所有可能隔板的位置

vector<vector<int>> ans;
void dfs(int n,int k,int st,vector<int>& path) {
    if (path.size()==k) {
        ans.push_back(path);
        return;
    }
    for (int i=st;i<=n;i++) {
        path.push_back(i);
        dfs(n,k,i+1,path);
        path.pop_back();
    }
}

反转数组

分苹果

题目描述：现有m个苹果，以及n个盘子，将苹果放在盘子里（盘子可以不全有苹果），问：有几种方案？

样例：6 3
输出：7

买票上车

题目描述：现有m个有0.5元的人，n个有1元的人需要上公交车，已知公交车费0.5元，司机可以找零，但司机目前没有零钱。问：有几种上车方案可以让司机为乘客找零？

输入样例：3 2
输出样例：5

高IQ过河

话说有一家六口人，包括爸爸、妈妈、两个女儿及两个儿子在旅行途中迷了路，还不幸遇上了一个逃狱的犯人，幸好犯人让一个也在旅行的警察逮捕，一家六口才得以保住性命。可是，在荒郊野外，手机接受不灵，他们都不能与外界联络，连警察也不能找到支援，他们只有通过一条河流方能回家，能帮帮他们么？

玩家的任务是，帮助这些人渡过河，交通工具只有一艘小船。只有爸爸、妈妈以及警察能控制小船，此外，不论成人或是小孩，小船每次最多只能搭乘二人。在渡河期间，玩家还要防止以下三种情况发生：
1、当警察与犯人分开时，犯人会伤害一家六口。
2、当爸爸看见妈妈离开女儿时，爸爸便会教训女儿。
3、当妈妈看见爸爸离开儿子时，妈妈便会教训儿子。

#include <bits/stdc++.h>
using namespace std;
#define M 100005
#define N 1005
#define MOD (1e9+7)
#define lowbit(x) (x & (-x))
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
enum {
    JC = 128,
    XT = 64,
    BB = 32,
    DR = 16,
    ER = 8,
    MM = 4,
    DY = 2,
    EY = 1
};
bool f1(int x, int y)
{
    return (x & y) == y;
}
bool f2(int x)
{
    if (x < 128 && x>64) return false;
    if(f1(x,BB)&&!f1(x,MM)&&(f1(x,DY)||f1(x,EY)))return false;
    if (!f1(x, BB) && f1(x, MM) && (f1(x, DR) || f1(x, ER)))return false;
    return true;
}
int kn[15] = {
    JC | XT,JC | BB,JC | DR,JC | ER,JC | MM,
    JC | DY,JC | EY,JC,BB | DR,BB | ER,BB | MM,BB,
    MM | DY,MM | EY,MM };
bool v[512];
using namespace std;
void f(int x, int a[], int step)
{
    if (x == 0)
    {
        int i;
        for (i = 0; i < step; i++)
            cout << a[i] << " ";
        cout << endl;
        return;
    }
    for ( int i = 0; i < 15; i++)
    {
        if (step % 2 == 0)
        {
            if (!f1(x, kn[i])) continue;
            if (!f2(x- kn[i])) continue;
            if (!f2(255-x + kn[i])) continue;
            if(v[x-kn[i]])continue;
            v[x - kn[i]] = true;
            a[step] = kn[i];
            f(x - kn[i], a, step + 1);
        } else {
            if (!f1(255 - x, kn[i])) continue;
            if (!f2(255 - x - kn[i])) continue;
            if (!f2(x + kn[i])) continue;
            if (v[256 + x + kn[i]])continue;
            v[256 + x + kn[i]] = true;
            a[step] = kn[i];
            f(x + kn[i], a, step + 1);
        }
    }
}
int main()
{
    int a[30];
    f(255,a,0);
}

张老师的生日

题目描述
小明和小强都是张老师的学生，张老师的生日是M月N日，2人都知道张老师的生日是下列10组中的一天：

3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
张老师将M值告诉了小明，将N值告诉了小强，张老师问他们知道他的生日是哪一天吗？
小明说：如果我不知道的话，小强肯定不知道
小强说：本来我也不知道，但是现在我知道了
小明说：哦，那我也知道了
据上面信息，推断出张老师的生日是哪一天？

猜数

有两个大于1小于100的自然数x,y，老师告诉小明两个数的和，告诉小强两个数的积。已知小明和小强足够聪明。

下面是两个人的对话：

小强：我不知道这两个数是多少,你肯定也不知道
小明：我本来不知道,但你这么我说,我就不知道了。
小强：那现在我知道了。

问这两个数是多少？

DFS与BFS

八皇后

最少砝码

题目描述

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
输入格式
输入包含一个正整数 N。
输出格式
输出一个整数代表答案。

样例输入

7

样例输出

3

样例说明
3 个砝码重量是 1、4、6 可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 – 4
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。
评测用例规模与约定
对于所有评测用例，1 \leqslant N \leqslant 1000000000
运行限制
最大运行时间：1s
最大运行内存: 512M

八数码拼图

题目描述

在 3\times 3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123456780），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

类似题目：P1379 八数码难题 - 洛谷

我的解法

使用BFS找到出最短的路径并用map记录上一个状态

#include <bits/stdc++.h>
using namespace std;
#define M 100005
#define N 1005
#define MOD (1e9+7)
#define lowbit(x) (x & (-x))
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
#define int long long
vector<int> random() { //随机生成一组测试样例 
    vector<int> mp;
    bool vis[11]={false};
    while (mp.size()<9) {
        std::random_device rd;
        std::mt19937 generator(rd());
        int r = generator();
        r%=9;
        if (vis[r]==0) {
            mp.push_back(r);
            vis[r]=true;
        }
    }
    return mp;
}
void out1(string &v) {
    // cout<<v<<"\n";
    for (int i=0;i<v.size();i++) {
        cout<<v[i]<<" ";
        if ((i+1) %3==0) {
            cout<<"\n";
        }
    }
    cout<<"\n";
}
void out2(vector<int> &v) {
    for (int i=0;i<v.size();i++) {
        cout<<v[i]<<" ";
        if ((i+1) %3==0) {
            cout<<"\n";
        }
    }
}
bool check(vector<int> &v) { //检查
    int sum=0;
    for (int i=0;i<v.size();i++) {
        for (int j=i+1;j<v.size();j++) {
            if (v[i]>v[j]) {
                sum++;
            }
        }
    }
    if (sum%2==1) return true;
    return false;
}
bool ok(vector<int>&v) {
    if (v.size()!=9) return false;
    for (int i=0;i<v.size()-1;i++) {
        if (v[i]!=i+1) return false;
    }
    if (v[v.size()-1]!=0) return false;
    return true;
}
unordered_map<string,string> str;
int bfs(string st) {
    string ed="123456780";//目标状态
    queue<string> q;
    unordered_map<string,int> mp;
    q.push(st);
    mp[st]=0;
    str.clear();
    while (!q.empty()) {
        auto t=q.front();
        auto be=t;
        q.pop();
        // cout<<t<<"\n";
        int d=mp[t];
        if (t==ed) {
            return d;
        }
        int z=t.find('0');
        int x=z/3,y=z%3;
        for (int i=0;i<4;i++) {
            int a=x+dx[i];
            int b=y+dy[i];
            if (a>=0&&a<3&&b>=0&&b<3) {
                // string next=t;
                swap(t[z],t[a*3+b]);

                if (!mp.count(t)) {
                    mp[t]=d+1;
                    q.push(t);
                    str[t]=be;
                }
                swap(t[z],t[a*3+b]);
            }
        }
    }
    return -1;
}
string tostring(vector<int> v) {
    string s;
    for (int i=0;i<v.size();i++) {
        s+=to_string(v[i]);
    }
    return s;
}
void solve() {
    vector<int> v=random();
    out2(v);
    cout<<endl;
    string s="123456780";
    int d = bfs(tostring(v));
    if (d==-1) {
        cout << "NO" << endl;
        return;
    }else {
        cout << "YES" << endl;
        // return;
    }
    stack<string> st;
    while (s!=tostring(v)) {//从原状态到目标状态 搜索路径并入栈
        st.push(s);
        s=str[s];
    }
    int n=st.size();
    while (!st.empty()) {  //输出路径  
        cout<<n-st.size()+1<<endl;
        out1(st.top());
        cout<< endl;
        st.pop();
    }
    cout << d << endl;

}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

随机用例

如果觉得文章对你有用，请随意赞赏

数据结构与算法 C++

计软实验班小学期笔记(实时更新中)

https://blog.lban.cc/archives/94o5YmNj

作者

LuBan

发布于

2025-07-02

更新于

2025-07-02

许可协议

CC BY 4.0

计软实验班小学期笔记(实时更新中)

计软实验班小学期笔记(实时更新中)

求n种不同面额的纸币 任选m张 求总方案数

21位的花朵数

任务描述

定义

目标

程序要求

示例输出

解题思路

dfs所有可能隔板的位置

反转数组

分苹果

买票上车

高IQ过河

张老师的生日

猜数

DFS与BFS

最少砝码

题目描述

八数码拼图

题目描述

我的解法

作者

发布于

更新于

许可协议

求n种不同面额的纸币任选m张求总方案数