Keven_11的博客

原创 C++题解：友好城市

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。仅一行，输出一个整数，表示政府所能批准的最多申请数。LIS（最长上升子序列）

原创 C++基础：二维费用的背包问题

一种思路保存原有的状态(dp[i][j])、方程，选取一个费用优先满足条件，并求出此时的价值，再看另一个费用是否满足条件。首先考虑01背包转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])，这只有一个费用。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。我们设dp[i][j][k]表示在前i个物品中选取、满足费用1的限制且满足费用2的限制的最大价值。体积是 vi，重量是 mi，价值是 wi。

原创 某不可靠消息

我于 2023.6.13 考完中考，感觉良好（应该能进全市前10）沉寂了那么久，我要开始重新更新了博客了。美好生活开始了(￣▽￣)"

原创 (娱乐)自贡市解中初三七班现状

解放路中学

原创 C++基础：KMP

SPPSPS输入格式NPPMSS输出格式0数据范围1≤N≤1051≤M≤106这就是著名的KMP问题。

原创 关于乘法逆元的一笔记

存在x使ax≡1(mod b) 则x为逆元。充要条件：gcd(a,b)=1。

原创 C++基础：扩展欧几里得算法

裴蜀定理内容：有一对正整数a、b，那么一定存在非0整数x、y，使得 ax+by=(a,b)扩展欧几里得算法用于求ax+by=(a,b)中的一个特解x,y

原创 C++基础：运算符优先级

记忆顺序1、单目运算符2、双目运算符，先乘除，后加减，再位移。3、关系运算符，先大于小于，后等于不等于。4、位运算符，位与，异或在中间，位或5、逻辑运算符，先与后或6、三目运算符一个。7、等于运算符一排

原创 C++基础：计数原理 例题

计数原理 例题

原创 C++题解：矩阵快速幂 求 斐波那契数列

一般先构造最后表示答案的矩阵，比如这里我们构造一个 1×2 的矩阵里边填上最开始的两项[a1​,a2​] ，接下来我们考虑把它往后推到 [a2​,a3​] ，那么我们需要构造一个矩阵，让 [a1​,a2​] 乘这个矩阵得到 [a2​,a3​]。依次看后边矩阵的每一项，看它可以由前边矩阵里边的每一项怎么凑出来，会发现 a2​=a2​,a3​=a1​+a2​，所以构造一个 2×2 的矩阵 A=[0,1，1,1​] ，这样就可以按照矩阵乘法递推，然后用矩阵快速幂解决问题了。这里n的范围极大，只能用矩阵快速幂。..

转载 C++基础：CSP & NOIP 烤前注意

应我们慈祥亲爱面容和蔼的老大哥要求，给各位dark♂佬做一下烤前指导qwq。那么，烤CSP前有啥注意事项呢？(我就不说啥算法，程序的事项)FIRST AND THE MOST IMPORTANT：1.freopen（NOTICE THE CSTDIO），保灵，教辅工具与人生路劈叉捆绑安装，且一旦安装无法卸载。2.注意你的文件格式，大文件夹（命名为你的准考证号）里面夹着四个小文件夹（每一个文件夹分别命名为每一道题的题目），...

原创 C++基础：数据结构 代码模板

#include#includeusing namespace std;const int N=1e5+10;int head,e[N],ne[N],idx;void init(){ head=-1; idx=0;}void add_to_head(int x){//头节点插入 e[idx]=x; ne[idx]=head; head=idx++;}void remove(int k){//删除 ne[k]=ne[ne[k]];}vo

原创 C++题解：二叉树（见证成长）

给定一个二叉树的中序遍历序列和前序遍历序列，先将树左右翻转（对于每个非叶结点，左右子树互换），然后输出翻转后树的层序遍历。二叉树每个结点的值不同。输出一行，包含 N 个整数，表示翻转后二叉树的层序遍历序列。第一行一个整数 N(1≤N≤30) ，表示二叉树结点个数。要求使用「文件输入、输出」的方式解题，输入文件为。二叉树每个结点的值为不超过 10^9 的正整数。第二行 N 个整数，表示二叉树的中序遍历序列。第三行 N 个整数，表示二叉树的前序遍历序列。输出时每行末尾的多余空格，不影响答案正确性。......

原创 宫崎骏著名电影 [娱乐]

起风了：https://v.pptv.com/show/BWPHREvo0Q9y8Fg.html风之谷：https://www.iqiyi.com/v_19rutelo44.html天空之城：https://www.iqiyi.com/v_19rt225s8k.html幽灵公主：https://www.iqiyi.com/v_19rwg9rfd8.htmlhttps://www.iqiyi.com/v_19rwg9rfd8.html千与千寻：https://www.asp400.com/dada..

原创 C++基础知识：挂分小技巧

​常见的挂分小技巧#max(a,b)或者min(a,b)写成(a,b)，这样会取后面的数，即b。在结构体里开数组开的太大。这种情况下即使没爆空间也会出现许多奇怪的错误。数组的下标减出负数导致RE。...

原创 C++基础：差分约束系统

基本思路：利用最短路中di≤dj+c（j指向i，边权为c，此指算法结束后）将求解三角不等式组转换为（单源）最短路问题三角不等式（组）： xi≤xj+ck 其中xi、xj是自变量，ck是常量差分约束系统有如下功能：求不等式组的可行解源点需要满足条件：从原点出发，一定可以走到所有的边。故可设“超级源点”超级源点：与每一个点相连的虚拟源点步骤：先将每个不等式xi≤xj+ck转化成一条从xj走向xi，长度为ck的一条边 找一个超级源点，使得该院点一定可以遍历到所有边 从源点求一边单..

原创 C++题解：苹果树

题目1500ms 131072K蒜头君的庄园里有一棵苹果树，树上有N个节点被N−1个树枝相连，蒜头君分别将它们标号为1到N，其中根为1号节点，每个节点开始的时候都有苹果，不过树上的苹果也是在变化的，有时某个节点会长出一个苹果，有时某个节点的苹果会被摘掉，蒜头君想知道某时刻某节点及其子树上一共有多少苹果，请你帮帮他。输入格式输入第一行两个整数 N,M，表示一共有N个节点，M次操作（节点状态更改或询问）(1≤N,M≤106)。接下来N - 1行，每...

原创 C++题解：棋子等级

目录题目输入格式输出格式题解：知识点：分析：代码：题目坐标系平面上有好多棋子，每个整点上至多有一个棋子。假定棋子的等级是左下方的棋子个数，现在给出若干棋子的位置，求不同等级的棋子各有多少个。左下方包含正下和正左。说明（0， 0) 坐标的位置在左下角。输入格式第一行一个整数N(1≤N≤100000)接下来N行，一行两个整数X,Y(0≤X,Y<100000)，表示坐标。数据保证坐标先按Y排序，再按X排序。输出格式...

原创 C++题解：公告板

目录题目输入格式输出格式题解：知识点：分析：代码：题目1000ms 131072K蒜厂有一个 h×w的矩形公告板，其中h是高度，w是宽度。现在有若干张 1×Wi​的公告， Wi​是宽度，公告只能横着放，即高度为1的边垂直于水平面，且不能互相有重叠，每张公告都要求尽可能的放在最上面的合法的位置上。若可以放置，输出每块可放置的位置的行号；若不存在，输出−1。行号由上至下分别为1,2,...,h。输入格式第一行三个整数h，w，n...

原创 C++基础：线段树（基础）

目录声明正文区间问题和线段树线段树的建立线段树的单点更新线段树的查询单点查询区间查询声明线段树理解起来不难，但是题灵活多变，难，建议学之后多刷题正文区间问题和线段树有一类区间问题可以抽象成如下模型。给定包含 n 个数的数组 a1​,a2​,⋯an​。有两种操作 查询区间[l,r]最小的数。 修改第ai​为x。 这里，为了解决这个问题，我们介绍一种灵活的数据结构——线段树。我们用一棵二叉树来表示线段树，线段树...

原创 C++基础：2-SAT问题

概述现有一个由 N 个布尔值组成的序列 A ，给出一些限制关系，比如 A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0⋯N−1]的值，使得其满足所有限制关系。这个称为SAT问题（已确定非2-SAT的SAT问题为NP完全问题），特别的，若每种限制关系中最多只对两个元素进行限制，则称为 2-SAT 问题。算法我们可以把每个点拆成两个点，一个代表取值为 true ，另一个代表取值为 false ，对点对进行遍历，如果两个点都没被选，则先假设选 false ，

原创 C++基础：二分图（染色法判定）

目录概述判断二分图算法实例C++ 示例代码概述对于一个无向图 G=(V,E) ，它的顶点集 V 可以恰好分为两个不相交的子集，并且在这个无向图中，任意一条边所连接的两个顶点都分别属于这两个不同的子集，那么我们将这个无向图称作 二分图（如果你愿意也称 二部图）。图例：（A中的点没有边直接相连，B同理）判断二分图我们可以使用 DFS 的方法对图进行染色，遍历所有点，如果当前点未被染色，则从此点开始进行 DFS 并进行染色，对路径上的点交替染色，如果发现在某个点时.

原创 C++基础：差分约束系统

基本思路：利用最短路中di≤dj+c（j指向i，边权为c，此指算法结束后）将求解三角不等式组转换为（单源）最短路问题三角不等式（组）： xi≤xj+ck 其中xi、xj是自变量，ck是常量差分约束系统有如下功能：求不等式组的可行解源点需要满足条件：从原点出发，一定可以走到所有的边。故可设“超级源点”超级源点：与每一个点相连的虚拟源点步骤：先将每个不等式xi≤xj+ck转化成一条从xj走向xi，长度为ck的一条边 找一个超级源点，使得该院点一定可以遍历到所有边 从源点求一边单..

翻译 C++基础：tarjan算法

一.割点和点双连通分量1.割点在一个 无向连通图 中，如果删除这个点和这个点关联的所有边，剩下图的连通分量大于 1，也即剩下的图不再连通，那么我们称这个点是 割点。比如对于下面这个图，割点有两个，分别是 1 和 3。这说明一个图可以有多个割点。2.点双连通图（点双）一个点双连通图的定义如下：一个 无向连通图 ，对于任意一个点，如果删除这个点和这个点关联的所有边，剩下的图还是连通的，那么称这个图是一个 点双连通图，也就是点双连通图中不会有割点出现。下图是一个点双连通图。3.

原创 C++题解：慈善晚会

经典题目注：As the time goes by,I have turned middle school student.So I'm shortof time.From now on, I will not write comments in the code. It may not be satisfaction with you.Sorry.目录题目输入格式输出格式题解：题目1000ms 131072K 蒜头君热心公益，他想要在近期举办一场慈善晚宴...

原创 C++题解：公路

目录题目输入格式输出格式题解：题目1000ms 131072K蒜头君有一些蒜园子，这些园子是由公路相互连通，其中一些形成回路的参观路线。如果有一条公路被多条参观路线公用，那么就可能会发生冲突；如果一条公路没有在任何一个回路内，那么就不会发生冲突。简单来说，就是在一个无向图中。如果至少有两个环共用了一些边，那么这些边被认为是“冲突边”。如果一些边不在任何一个环中，这些边被认为是“多余边”。请问有多少条公路有冲突，多少条公路没有冲突，另外这图不一定是连通的。输入格式..

原创 C++题解：网络大战

目录题目题解：题目1000ms 131072K一场无硝烟的战争即将爆发，蒜头君和花椰妹接到上级任务——破坏敌方通信网络。破坏敌方通信网络并不是一件简单任务，蒜头君和花椰妹只能各自破坏敌方通信网络中的一个节点。破坏两个节点后，如果敌方至少有两个节点无法通信（除了已被破坏的两个节点），就认为蒜头君和花椰妹破坏成功。为了简化问题，请你计算蒜头君和花椰妹有多少种方法可以成功破坏敌方通信网络。输入格式第一行输入两个整数 n(3≤n≤1000)和 m(0≤m≤10000)...

原创 C++基础：连通图与连通分量的区别

连通图：连通分量（极大连通子图）：

原创 C++题解：[CSP-J2020]表达式

目录题目题解：题目小C热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为0或1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：与运算：????&????。当且仅当????和????的值都为1时，该表达式的值为1。其余情况该表达式的值为00。 或运算：????|????。当且仅当????和????的值都为0时，该表...

原创 C++题解：火星人

如图所示，玛德洲，位于月球东南部距离地心-200m处，形似一个没有炮管和机枪管的坦克如图所示，玛德洲分为东北部的猥琐不达米亚平原、中部的倭利玛高原和南部的珠窝丘陵，南高北低，地势起伏不大...

原创 C++题解：[NOIP2008pj]立体图

目录题目题解题目小渊是个聪明的孩子，他经常会给周围的小朋友们将写自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。小渊有一块面积为m×n 的矩形区域，上面有 m×n个边长为1的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是1），小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：每个顶点用11个加号+表示，长用33个−表示，宽用11个...

原创 C++基础：string使用详解

string使用详解0.目录1.准备2.初始化3.赋值4.访问5.连接6.比较7.子串8.交换9.查找10.修改11.插入12.删除13.特性描述14.字符串流处理1.准备首先，需要做这样的事情#include <iostream>#include <string>using namespace std;//之后就可以体验string内置的各种强大功能了—string相关迭代器//返回string的起始位置const_iterator

原创 C++基础：运算符优先级

转载 基础概率与期望

一.对数的定义若有，

原创 C++题解：[NOIP2013] 货车运输

目录题目题解题目A 国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入格式输入文件第一行有两个用一个空格隔开的整数n，m，表示 A 国有n座城市和m条道路。接下来m行每行3个整数x、y、z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。注意：x不等...

翻译 C++基础：STL合集

vector, 变长数组，倍增的思想 vector<int> a;//定义了一个int类型的vector（int类型，名称为a，下同） vector<int> b(10);//定义了一个长度为10的vector vector<int> c(10,3);//定义了一个长度为10、里面每一个元素都为3的vector vector<int> d[10];//定义了10个vector size() 返回元素个数 em...

转载 C++基础：二叉树性质

原创 C++基础：关于结构体重载运算符的重要细节

我们来观察下面的结构体重载运算符代码：给set重载<： #include <iostream>#include <set>using namespace std;struct Point{ int x,y; bool operator<(const Point &rhs)const{ if(x==rhs.x){ return y<rhs.y; }else{

转载 主定理

先介绍几个符号的含义。符号Θ，读音西塔，既是上界也是下界，等于，严格贴紧。符号O，读音殴，表示上界，小于等于，贴紧未知。符号o，读音也是殴，小于，不贴紧。符号Ω，读音偶眯嘎，表示下界，大于等于，贴紧未知。符号ω，读音也是偶眯嘎，表示下界，大于，不贴紧。上面的“贴紧”是我根据tight翻译过来的(不是很准确啊)，大概就是是否严格等于的意思吧。意思就是Θ是平均时间复杂度，O是最坏情况下的复杂度，Ω是最好情况下的复杂度。假设我们有递推关系式：T(n)=aT(nb)+f(n)其

原创 C++题解：位运算

目录题目题解题目1000ms 131072K蒜头君有一个包含n个数的数组，他想把这个数组分成m段，然后在每一段里求出所有数异或的结果，然后再把这m个数求按位或以后的结果。蒜头君想知道他想要的结果最小可以是多少。输入格式输入第一行包含两个整数n,m(1≤m≤n≤5×105)，分别表示数组的大小和段数。第二行包含n个整数ai​(0≤ai​≤1018)，表示数组中的每个数。输出格式表示最小的结果。输出时每行末尾的多余空格...