ExileK1G的个人博客

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152# -*- coding:utf-8 -*-import jsonimport socketimport urllib.errorimport requestsimport urllib.requestimport urllib.parsefrom bs4 import BeautifulSoupimport reimport datetimeimport timeimport osimport xlwings as xwimport pandas as pdfrom pandas import Series, DataFramefrom icecream import icheaders = { 'cookie': 'SESSIONID=NbZdSDM9vxjCm49QloVUek1p4SESon111VN5lO28kIn; JOID=UFsVAkiK ...

IndexTree特点: 1)支持区间查询 2)没有线段树那么强,但是非常容易改成一维,二维,三维的结构 3)只指出单点更新(线段树可以实现范围更新) ps:线段树的作用:1.add(L,R,10),某个区间同时加上10 ​ 2.update(L,R,7)某个区间同时变成7 ​ 3.求区间(L,R)的累加和 ​ 三分函数的时间复杂度都为O(logN) 例如数组{1,2,3,4,5,6,7,8} index=1->管1 index=2->管1,2 index=3->管3 index=4->管1,2,3,4 index=5->管5 index=6->管5,6 index=7->管7 index=8->管1,2,3,4,5,6,7,8 规律一:当将index化为二进制表示的形式 如当index=8=01000 将最右边的1改为0并在末尾加上1后的二进制形式为index’=00001 则index ...

KMP算法简单介绍KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的经典算法，其目的是在一个文本串（主串）中查找一个模式串的出现位置。与朴素的字符串匹配算法相比，KMP算法具有更高的效率，特别是在处理大型文本时。 KMP算法的核心思想是利用已经匹配过的部分信息来避免不必要的比较。算法的关键在于构建一个部分匹配表（Partial Match Table，PMT），该表用于存储模式串中每个位置的最长前缀和最长后缀的匹配长度。 经典例题引入题目描述:给定文本串 T 和模式串 P，找到模式串在文本串中的第一次出现的位置。 一般的暴力算法(朴素字符串匹配算法): 1234567891011121314151617int search(char text[], char pattern[]) { int m = strlen(pattern); int n = strlen(text); for (int i = 0; i <= n - m; i++) { int j; for (j = 0; j < ...

dp数组的维数–>看可变参数的个数 模型:从左往右尝试模型,范围尝试模型,样本对应模型,业务限制模型 题目一 robotwalk题目描述: 假设有排成一行的N个位置，记为1～N，N一定大于或等于2开始时机器人在其中的M位置上（M一定是1～N中的一个）如果机器人来到1位置，那么下一步只能往右来到2位置； 如果机器人来到N位置，那么下一步只能往左来到N—1位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走； 规定机器人必须走K步，最终能来到P位置（P也是1～N中的一个）的方法有多少种给定四个参数N、M、K、P，返回方法数。 方法一(纯递归dfs)(有大量的重复计算): 123456789101112131415161718192021//方法一:纯暴力搜索(dfs，递归)//机器人当前来到的位置是cur//机器人还有rest步需要去走//最终的目标是aim//有哪些位置？1-N//返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数是多少int process1(int cur,int rest,int aim,int N){ if(rest ...

以经典的跳楼梯问题来解析递推(dfs),记忆化搜索与递推的区别递归(类似于深度优先搜索dfs)(dfs属于递归的一种)记忆化搜索 递推(ps.记忆化搜索和递推的时间复杂度都比递归小,但空间复杂度高,实现了空间换时间)(动态规划是递推的一个子集) 优化过程:最暴力的dfs–>记忆化搜索–>递推(dp ) 记忆化搜索=暴力dfs+记录答案 递推的公式=dfs向上递归的公式(递推公式通常更容易理解为自底向上的递归) 递推数组的初始值=递归的边界 例题:大盗阿福 题目描述阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 NN 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。 作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？ 【输入】输入的第一行是一个整数T(T≤50)T(T≤50) ，表示一共有T组数据。 接下来的每组数据，第一行是一个整数N(1≤N≤100 ...

DFS入门级模板看CSDN文章 DFS入门级（模板）_dfs模型-CSDN博客 题目一 烤鸡 题目描述猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。 现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 1010 种配料的所有搭配方案。 输入格式一个正整数 n，表示美味程度。 输出格式第一行，方案总数。 第二行至结束，1010 个数，表示每种配料所放的质量，按字典序排列。 如果没有符合要求的方法，就只要在第一行输出一个 0。 输入输出样例输入 #1 111 输出 #1 1234567891011101 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 ...

一： 123456789101112#include <iostream>// 计算最大公约数（Greatest Common Divisor）int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}// 计算最小公倍数（Least Common Multiple）int lcm(int a, int b) { return a / gcd(a, b) * b; // LCM = a * b / GCD(a, b)} 二（c++中的库函数）: 123#include <numeric> // 包含 gcd 和 lcm 函数int gcdResult = std::gcd(num1, num2);int lcmResult = std::lcm(num1, num2);

迷宫问题 问题描述:迷宫由m行n列的单元格组成,每个单元格要么是空地,要么是障碍物,请你找出一条从起点到终点的最小路径长度 DFS深搜解决迷宫问题 DFS深搜要点： 使用递归方式求解：先判断当前点是否为终点，非终点时递归调用DFS 调用DFS前当前点标记为已访问，DFS执行结束后当前点标记为未访问：前者防止递归调用时重复访问当前点走回头路，后者是为探索其他路径时能重复访问该点。 使用外部变量统计最小步数 代码: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<stdio.h>int min = 999999;int p, q,m,n;//p,q分别表示终点的行坐标和列坐标。 m，n表示该迷宫的函数和列数int dx[4] = { 0,1,0,-1 };int dy[4] = { 1,0,-1,0 };int a[100][100];//1表示空地，2表示障碍物in ...

贪心算法的基本思想是每次选择局部最优解,期望最终得到全局最优解,其解题思路无法证明,只能用对数器(另个用纯暴力解法)来证明其正确性(贪心就是没道理)(ps.证明贪心不对–>举反例) 题目一 题目描述:一个项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲，给你每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多，返回最多的宣讲场次 贪心算法思路:对于这个问题，我们可以按照项目的结束时间进行排序，然后依次选择结束时间最早的项目。在每一步选择时，我们==选择的项目应该是与当前会议室时间不冲突且结束时间最早的项目==。这样可以最大程度地释放会议室，使得能够安排更多的宣讲场次。 代码: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <stdio.h>#include <stdlib.h>// 结构体表示一个项目struct ...

并查集算法 典型题目 题解： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<cstdio>#include<cstdlib>using namespace std;#define MAXN 20001int fa[MAXN];void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i;}int find(int x){ if (x == fa[x]) return x; else { fa[x] = find(fa[x]);//父节点设为根节点 return fa[x];//返回父节点 }}void unionn(int i, int j) { int i_fa = find(i);//找到i的祖先 int j_fa = ...