363045841 的博客

致谢

写了我整整三天，三个晚上和一个下午，真的是魔鬼周末，还只是勉强整理出来本周末学习的一半内容hhhh。感谢刘岩，贾天宇，金朱仪昊，季圣熙，沈嘉勇同学的深度探讨，以及文心一言的各种细节性解答，还有朱强和汪前进老师的授课。

深搜水仙花数

[[搜索题单]]

cpp

#include <iostream>
#define L 0
#define H 9
#define N 3
using namespace std;

int a[N];

bool cut(int i,int j){
	if(i == 0 && j == 0){
		return false;
	}
	return true;
}

void dfs(int i){
	if(i == N){
		if(a[0]*a[0]*a[0]+a[1]*a[1]*a[1]+a[2]*a[2]*a[2] == a[0]*100+a[1]*10+a[2]){
			cout << a[0] << a[1] << a[2] << '\n';
		}
		return;
	}
	for(int j = L;j<H;j++){
		if(cut(i,j)){
			a[i] = j;
			dfs(i+1);
		}
	}
}

int main(int argc, char const *argv[])
{
	dfs(0);
	return 0;
}

唯一需要注意的就是这里的剪枝条件i == 0 && j == 0，目的是排除掉形如0XX的数，因为第一位为0的数一定不是一个三位数。即把第一层分支为0的所有子节点剪掉。

背包问题

0-1背包问题

有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。因为每个物体只有取与不取的两种状态，对应二进制中的0和1，故称为0-1背包问题。更为一般的情况则称为完全背包问题。

深搜背包

cpp

#include <iostream>
#define L 0
#define H 1
#define N 6 //物品个数
#define C 20//背包容量
using namespace std;

int a[N];
int w[] = {5,3,2,10,4,2};
int v[] = {11,8,15,18,12,6};
int tw,tv,max_value;

inline bool cut(int i,int j){
	return true;
}

void dfs(int i){
	if(i == N){
		tw = 0,tv = 0;
		for(int j = 0;j<N;j++){
			tw += w[j]*a[j];
			tv += v[j]*a[j];
		}
		if(tw <= C){
			cout << "value = " << tv << '\n';
			if(tv > max_value) max_value = tv;
		}
		return;
	}

	for(int j = L;j<=H;j++){
		if(cut(i,j)){
			a[i] = j;
			dfs(i+1);
		}
	}
}

int main(int argc, char const *argv[])
{
	dfs(0);
	cout << "max_value = " << max_value << '\n';
	return 0;
}

本质上是计算一个 $A_{6}^{6}$ 的 0-1 全排列，根据这个全排列计算对应的

\begin{aligned} t v & = v_{i} a_{i} \\ t w & = w_{i} a_{i} \end{aligned}

其中a对应的是第 $i$ 个物品所对应的状态，0即未放入，1即放入。当递归到最深时，计算当前排列结果的总价值，同时检查是否超重，更新max值即可。

突然发现的小问题

因为标准库函数中存在max，所以如果定义一个变量叫max会造成冲突。

cpp

#include <iostream>
using namespace std;
int max;//声明为全局变量
int main(int argc, char const *argv[])
{
    cout << max;
    int a = max(5,10);
    return 0;
}

这时候编译器会报错，提示reference to 'max' is ambiguous，即对max的引用不明确，因为在全局命名空间下存在一个max变量，而我们使用了using namespace std导致std作用域全局可见，这时候在全局作用域中就存在了两种max，于是乎导致了不明确的引用。这时候只要使用作用域解析运算符::声明各自作用域就行了。

cpp

cout << ::max;//全局作用域下的max变量
int a = std::max(5,10);//std标准库作用域下的max函数

再深究一下，这时候如果max是个局部变量，那么cout这里不会报错，因为编译器会优先尝试一个可以输出的值，而不是一个函数（况且也没填参数）。这不是函数重载实现的，变量和函数之间无法重载。 C 中不存在命名空间，但是如果存在max变量再调用max函数依然会出现called object 'max' is not a function or function pointer，即编译器不能把max识别为函数或函数指针。因为编译器总是会在当前作用域中搜索max实体，所以它会优先将max解析成变量而不是函数。反之，如果我们在调用max函数之后定义max变量，就不会出现这个问题。

cpp

#include <stdio.h>
int main(int argc, char const *argv[])
{
    int a = max(5,10);
    int max;//不会产生冲突
    return 0;
}

旅行商问题(TSP)

要求： 给定n个点，m条无向边，每条边有一个权值代表两个点之间的距离，现在要求把每一个点都走一遍并回到原点，求路径的最短值。

基本概念

图(Graph)

由顶点集合 $V (G)$ 和顶点之间边的集合 $E (G)$ 构成的数据结构，表示为 $G = (V, E)$ 可以用 $| V |$ 表示图G中顶点的个数，称为图G的阶， $| E |$ 则为图G中边的条数

无向图

E为无向边的集合，则为无向图。两个顶点 $v, w$ 之间的边为无序对 $(v, w)$ ，称边 $(v, w)$ 依附于顶点 $v, w$ 。

权、网： 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

邻接矩阵

稠密图：边 $E$ 接近于顶点 $V$ 邻接矩阵通常用于稠密图及快速判断两个节点之间是否有边相连的情况。对于上面的带权图，可以用邻接矩阵表示为

[\begin{matrix} M & 6 & 1 & 5 & M & M \\ 6 & M & 5 & M & 3 & M \\ 1 & 5 & M & 5 & 6 & 4 \\ 5 & M & 5 & M & M & 2 \\ M & 3 & 6 & M & M & 6 \\ M & M & 4 & 2 & 6 & M \end{matrix}]

矩阵每一行描述一个节点与周围的联通关系及对应边的权重，如果不联通或者是它本身用M表示。在例题中令 $M = 32768$ ，或者是另外一个很大的数，反正只要保证带M路径全被剪枝函数剪掉就行了。

^eae0c0

哈密顿回路、哈密顿图

哈密顿回路： 除起点外每个点只通过一次的路径存在哈密顿回路的图称为哈密度图。

深搜哈密顿回路

[[搜索题单]]

剪枝条件

存在重复节点
边不连通(含M)
最后的节点与开始节点不连通(递归到最深再判断)

cpp

#include <iostream>
#define N 6//节点数
#define M 32768
using namespace std;

int a[N];
int cnt;
int min = M;
int g[N][N]={{M,6,1,5,M,M,},
            { 6,M,5,M,3,M,},
            { 1,5,M,5,6,4,},
            { 5,M,5,M,M,2,},
            { M,3,6,M,M,6,},
            { M,M,4,2,6,M,}};

bool ok(int i,int j){//添加的节点
    for(int k = 0;k<i;k++){
        if(a[k] == j) return false;//检查每次添加的节点是否已经走过
    }
    if(i > 0 && g[a[i-1]][j] == M) return false;//检查上一个节点是否联通j节点
    return true;
}

bool ok2(){//检查最后的节点与开始的节点是否联通
    if(g[a[N-1]][a[0]] == M) return false;
    else return true;
}

void dfs(int i){
    int k;
    if(i == N){
        if(ok2()){
            int s = 0,f = a[0];//f为上一个节点
            for(int j = 0;j<N;j++){
                cout << a[j];
                if(j > 0){
                    s += g[f][a[j]];//增加上一个节点到当前节点的距离
                }
                f = a[j];
            }
            s += g[a[N-1]][a[0]];//增加终点到起点的距离
            cnt++;
            cout << "  s=" << s << '\n';
            if(::min > s) ::min = s;
        }
        return;
    }

    for(int j = 0;j<N;j++){
        if(ok(i,j)){
            a[i] = j;
            dfs(i + 1);
        }
    }
}

int main(int argc, char const *argv[])
{
    dfs(0);
    cout << endl << cnt << " min_s:" << ::min;
    return 0;
}

Problem D

这题是P1028 [NOIP2001 普及组] 数的计算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)的变式，主要是加强了数据。

题面

概括： 给出 $P, L, K$ 使用 $1 \sim P$ 生成一个长度为 $L$ 的序列，要求不出现大于等于 $K$ 个连续的1。 $(1 \leq P < 10, 1 < L < 31, 1 < K < L + 1)$ 深搜枚举法原理和上面一样，包括之前C题也是一个道理，写不出来应该回顾前面的，这里不再细讲。（因为太晚了，太累了hhhh）

最小规模

根据题目范围，先考虑最小规模的 $(1, 2, 2)$ 情况，显然一个符合条件的数都没有。因为 $P = 1$ 的时候，无论 $K$ 等于几都会使得序列违反题意。稍微扩大一点规模，考虑 $(3, 2, 3)$ 情况，思考一下它是怎么构成的。与C题类似， $(3, 2, 3)$ 与 $(3, 1, 3)$ 存在联系，分为三种情况：

在 $(3, 1, 3)$ 的所有结果基础上加上一个非1的数，必然成立；
在 $(3, 1, 3)$ 的加非1结果基础上加上一个1，这个时候因为只加了一个1，结果合法；
在 $(3, 1, 3)$ 的非1加1加过基础上加上一个1，之前加了一个1，现在再加上一个1，结果依旧合法。按照上述方法一直推到 $(3, 3, 3)$ ，结果分别为：

[\begin{matrix} 2 & 1 & 0 \\ 6 & 2 & 1 \\ 18 & 6 & 2 \end{matrix}]

总结一下，每次加1操作会使进行这个操作合法的数向右下方移动，位于第 $n$ 列的数就表示当前条件下末尾序列为 $n - 1$ 个连续的 $1$ 的序列个数，按此规推出状态转移方程即可。

最大规模

考虑 $(1, 30, 30)$ 情况

动态规划

\begin{aligned} N u m [L] [0] & = (P - 1) \sum_{0}^{k} N u m [L - 1] [i] \\ N u m [L] [i + 1] & = N u m [L - 1] [i], 0 \leq i \leq k - 1 \end{aligned}

快速实现一下：

cpp

#include <iostream>
#include <cstring>
using namespace std;

int p=2,l=5,k=6;
int a[35][35];

int main(int argc, char const *argv[])
{
    memset(a,0,sizeof(a));
    a[0][0] = p-1,a[0][1] = 1;
    for(int i = 1;i<l;i++){
        int sum = 0;
        for(int j = 0;j<k;j++){
            sum += a[i-1][j];
        }
        a[i][0] = (p-1)*sum;
        for(int j = 1;j<k;j++){
            a[i][j] = a[i-1][j-1];
        }
    }
    int s = 0;
    for(int i = 0;i<k;i++){
        s += a[l-1][i];
    }
    cout << s;
    return 0;
}

不过，因为数据较大，极限情况 $(9, 30, 30)$ 会溢出（试过了，开int64也溢出），所以加法还需要使用高精度实现。顺带在这里讲运算符重载。

运算符重载

运算符重载，顾名思义，就是赋予一个运算符在某个类中另外一个含义，这样当我们使用这个类的实例化对象进行该运算符的操作的时候就可以进行我们自定义的操作了。

cpp

struct math{
    string a1;

    math(string a){
        a1 = a;
    }
    math operator+(const math &b1) const{
        string a = this->a1;
        string b = b1.a1;
        if(a.length() > b.length()){
            b = string(a.length()-b.length(),'0') + b;
        }else{
            a = string(b.length()-a.length(),'0') + a;
        }
        string c = "";
        int len = a.length();
        int add = 0;
        for(int i = len - 1;i>=0;i--){
            int t = (a[i] - '0') + (b[i] - '0') + add;//计算加上进位后的结果
            add = 0;
            if(t >= 10) add = t / 10;
            c = to_string(t % 10) + c;
        }
        if(add > 0) c = to_string(add) + c;
        return math(c);
    }
};

我们来看一下它到底在干什么，为了避免深入讨论类的相关概念，这里使用结构体，当然，在C++中，结构体可以看作一个弱化的类。首先，这个高精度加法类math下有一个成员变量a1，用于接收传值。接下来是一个与类同名的构造函数math，用于实例化对象时的初始化。接下来，我们在math类中对该类中+运算符进行了重载，让它完成一个高精度加法运算。运算符重载的格式为

返回值： 这里返回一个math对象，在最后使用math(c)隐式进行了对象的实例化； 参数： 这里用的是一个常值引用，指向一个math类对象，引用和指针类似，主要区别就是引用一旦指向某个对象便不可更改。const修饰时防止这个对象成员被乱改。用引用时为了直接操作内存避免多余的对象复制操作导致性能降低； 末尾const： 声明该函数为常量成员函数，避免修改类的非静态成员变量。 ^f3b4b7

重载的+运算符作用于两个math对象，比如

cpp

math a2("1");
math a3("2");
a2 = a2 + a3;//重载的是+而不是+=，所以不能写a2+=a3
cout << a2.a1 << endl;

在第三行这里，可以想象成a2调用了一个方法，这个方法就是+，虽然它与运算符同名，这个方法的参数就是对a3的常值引用。

cpp

string a = this->a1;
string b = b1.a1;

在重载运算符第一行我们搜集了进行高精度加法的两个字符串参数，this代表指向当前对象的成员变量a1，当前对象也就是这个调用运算符重载的对象的成员变量a1，因为我们又传了一个math类对象a3作为参数，所以我们可以通过形参的b1.a1找到传入对象的成员变量a1，进而对这两个数进行高精度运算，最后把结果作为一个匿名对象返回给主调函数，让a2等于这个匿名对象，就能把a2的值更新了。所以，在接下来的高精度实现中，每次都要这样通过对象进行加的操作，由于乘法没有重载，所以用循环模拟实现（因为我懒）。

高精度解极限情况

因为是高精度，所以参与运算的都是字符串对象，而不是常整型对象了，需要修改。

cpp

#include <iostream>
#include <cstring>
using namespace std;

int p=9,l=30,k=30;
string a[35][35];

struct math{
    string a1;

    math(string a){
        a1 = a;
    }
    math operator+(const math &b1) const{
        string a = this->a1;
        string b = b1.a1;
        if(a.length() > b.length()){
            b = string(a.length()-b.length(),'0') + b;
        }else{
            a = string(b.length()-a.length(),'0') + a;
        }
        string c = "";
        int len = a.length();
        int add = 0;
        for(int i = len - 1;i>=0;i--){
            int t = (a[i] - '0') + (b[i] - '0') + add;
            add = 0;
            if(t >= 10) add = t / 10;
            c = to_string(t % 10) + c;
        }
        if(add > 0) c = to_string(add) + c;
        return math(c);
    }
};

signed main(int argc, char const *argv[])
{
    for(int i = 0;i<=34;i++){
        for(int j = 0;j<=34;j++){
            a[i][j] = "0";
        }
    }
    a[0][0] = to_string(p-1),a[0][1] = "1";
    
    math sum = math("0");
    for(int i = 1;i<l;i++){
        sum.a1 = "0";
        for(int j = 0;j<k;j++){
            math aa(a[i-1][j]);
            sum = sum + aa;
        }
        math aa(sum);
        for(int i = 1;i<=p-2;i++){
            sum = sum + aa;
        }
        a[i][0] = sum.a1;
        for(int j = 1;j<k;j++){
            a[i][j] = a[i-1][j-1];
        }
    }
    math s = math("0");
    for(int i = 0;i<k;i++){
        math t(a[l-1][i]);
        s = s + t;
    }
    cout << s.a1;
    return 0;
}

正确答案为42391158275216203514294433200。

二分查找

题目链接：D-小红的数组操作_牛客周赛 Round 24

小红拿到了一个长度为 $n$ 的数组，她每次可以进行如下操作：选择一个数，使其减去 $x$ ，小红希望次操作之后，该数组的最大值尽可能小。请你求出这个尽可能小的最大值。其中， $1 \leq n \leq 10^{5}, 1 \leq a_{i}, k, x \leq 10^{9}$ 。

二分思想

暴力方法的目标是通过模拟，每次减去数列中最大的那个数，得到最后的最大的 $a_{i}$ 显然时间复杂度会很高，所以这时候可以使用二分查找的方式缩短时间。而二分查找的思路就是在一个给定的区间里查找一个符合条件的值 $n$ ，避免每次模拟的时候的排序操作和减少判断次数，进而优化时间复杂度到对数阶(前提是查找一个有序数列)。特别注意这道题的二分条件，要查找的不是范围内第一个满足条件的值，而是满足 $o p s = k$ 的最小值（即满足 $o p s = k$ 条件的二分查找区间的左端点值）。

二分模板

选择一个正确的二分模板可以保证二分区间内的所有数都可以被搜索到，这样只要考虑二分搜索返回的值符合题意就可以了。以下这个模板就是套返回 min 即可。

cpp

while (min < max) {
    ...
    if (xxx)
        max = mid; // 这俩是重点
    else
        min = mid + 1;
}
return min;

范围确定

上界： 由于是减法操作，上界显然是 $x = 0, a_{1} = 10^{5}$ 的情况，此时要搜索的结果为 $10^{5}$ 下界： $x, k = 10^{9}, a_{1} = 1$ ，显然 $1 - 10^{9} \times 10^{9} > 10^{- 18} = I N T 64_M I N$ ，使用int64并不会溢出综上所述，二分查找范围应该为 $[I N T 64_M I N, 10^{5}]$

缩小区间条件

每次二分都要取当前二分区间下的中点（即 $⌊ \frac{l + r}{2} ⌋$ , $l$ 为左区间端点， $r$ 为右区间端点），每次取中点值作为假定的结果，计算给定数列每次减去 $x$ 需要 $o p s$ 次操作使得这个中点数成为当前数列中的最大项。

$o p s <= k$ ，说明中点值取大了，因为数列中的数只要进行很少的减法操作就能让取的数最大，这时候中点值应当取小，即把区间中点作为下次查找区间的右端点；
$o p s > k$ ，就是上面情况的相反情况。

避免溢出情况

1.判断条件溢出： 对[[#范围确定]]区间作分析，最初的中值的绝对值为 $⌊ \frac{10^{18} + 10^{5}}{2} ⌋ \to ⌊ \frac{10^{18}}{2} ⌋$ ,考虑最极端的情况，在靠近 $10^{5}$ 的地方取数列，只要有两个数计算 $o p s$ ，就会导致 $o p s >= 10^{18}$ ,导致溢出。不过，对于 $o p s$ 的单次计算，则不会超过 $⌊ \frac{10^{18}}{2} ⌋$ ，所以单次计算是安全的，因为上面为了计算方便取中点趋于 $⌊ \frac{10^{18}}{2} ⌋$ 了，实际上这个区间还会更小，也就是说两次 $o p s$ 计算也能够保证安全。当然这是在区间取得很极端的情况下。 为什么不存在ops溢出导致 $o p s > k$ 失效的情况： 不难发现，计算上一次必然有 $o p s \leq 10^{9}$ ，上文已经推出ops每次自增量不超过 $⌊ \frac{10^{18}}{2} ⌋$ ，显然不会溢出，且可以保证在符合 $o p s > k$ 条件后立即退出循环，（虽然看上去简单其实想起来还是挺绕的）。

cpp

for (int i = 0; i < n; i++) {
	ops += (max(a[i] - m, i64(0)) + x - 1) / x;
	if(temp > k && ops < k && i <= n-5){
		while(1);
	}
	temp = ops;
	if(ops>k) return false;
}//通过卡评测机确定存在溢出情况，存在溢出就执行while(1)把评测机卡超时，效果类似于assert

2.除法溢出： x / k的等价写法如下

cpp

int p = x / k + (x % k ? 1 : 0);
int p = (x + k - 1) / k;
int p = (x - 1) / k + 1;

问题解决

用时48ms(因为之前范围算的精确相比课上已经优化了20ms左右)

cpp

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
int n, k, x;//数组长度、操作次数，每次操作减的数
vector<int> a;
bool check(i64 m) {//m:mid
	i64 ops = 0;//操作次数
	for (int i = 0; i < n; i++) {
		ops += (max(a[i] - m, i64(0)) + x - 1) / x;
		if(ops>k) return false;
	}
	/* cout << ops << endl; */
	return ops <= k;
}
int main() {
	cin >> n >> k >> x;
	
	a.resize(n);
	for (auto &ai: a) cin >> ai;
	
	i64 l = -1e18, r = 1e9;
	while (l < r) {
		i64 mid = (l + r) >> 1;//等价除以2并下取整
		if (check(mid)) r = mid;//<=op,mid取的太大，把mid取小
		else l = mid+1;//>=op，mid取的太小，把mid取大
	}//binary search
	
	cout << r;
	return 0;
}

性能优化

1.[[移位操作符]] 都知道了hhh 2.[[读入]] 优化到28ms

cpp

cin.tie(nullptr);//断开cin/cout的绑定，减少IO次数
ios::sync_with_stdio(false);//断开cin/cout流和scanf/printf的同步

实际做了下面的T1240后发现，这两行不是必然可以大幅优化性能的，有时候反而会导致时间增长，还是要视具体情况使用。有的环境使用这两行会导致printf,scanf输出为空，注意自测输出免得罚时。 3.使用引用而非对象[[#^f3b4b7]]4.使用'\n'换行而非endl 避免重复刷新输出缓冲区导致的时间开销

T1240

本节整理一下做这道题时候遇到的稀奇古怪问题。 0(条件处理错误)-80-90(边界处理错误)-100

边界处理、哨兵(guard)

二分查找原理简单，但是细节问题上容易出岔子。上面给的模板虽然不会出现返回左右指针超范围的问题，但是你如果沿用处理中间边界的处理方法，返回边界的左/右侧的值，在边界上会越界，进而出现奇奇怪怪的问题，处理方式大致有以下两种。 1.特判边界： 因为给的有序数列，直接特判搜索数是否在数列以外，从而避免二分搜索搜索到左右端点位置。 2.增加哨兵： 直接在数列两端增加一个很小的值和一个很大的值，从而把原数列端点保护起来，避免出现左右指针为负或者大于区间的情况。

实现

cpp

#include <iostream>
#include <vector>
#include <cstdint>
#include <cmath>
using namespace std;

int n,des,delta,m;
vector<int> a;

int main(int argc, char const *argv[])
{	
	cin >> n;
	a.resize(n);
	for(int &x : a) cin >> x;
	/* a.insert(a.begin(),-2e9);
	a.push_back(2e9); */
	cin >> m;

	for(int i = 0;i<m;i++){
		cin >> des;
		int l = 0, r = n - 1;
		while(l < r){
			int mid = l + (r - l) / 2;
			if(a[mid] >= des) r = mid;
			else l = mid + 1;
		}
		int maax = l > r ? l : r;
		int d1 = abs(a[maax] - des);
		int d2 = abs(a[maax-1] - des);
		if(des >= a[n-1]) cout << a[n-1] << '\n';
		else if(des <= a[0]) cout << a[0] << '\n';
		else if(d1 == d2) cout << (a[maax] > a[maax-1] ? a[maax-1] : a[maax]) << '\n';
		else cout << (d1 < d2 ? a[maax] : a[maax-1]) << '\n';
	}
	return 0;
}

哨兵二分搜索优化，AC本题后可看。

基础

逻辑复用

源码解析

组件

实验

MOOC题解

致谢 ​

深搜水仙花数 ​

背包问题 ​

深搜背包 ​

突然发现的小问题 ​

旅行商问题(TSP) ​

基本概念 ​

深搜哈密顿回路 ​

剪枝条件 ​

Problem D ​

题面 ​

最小规模 ​

最大规模 ​

动态规划 ​

运算符重载 ​

高精度解极限情况 ​

二分查找 ​

二分思想 ​

二分模板 ​

范围确定 ​

缩小区间条件 ​

避免溢出情况 ​

问题解决 ​

性能优化 ​

T1240 ​

边界处理、哨兵(guard) ​

实现 ​

致谢