- 博客(40)
- 收藏
- 关注
RSS订阅原创 MySQL事务+@Transactional注解
为什么需要事务？事务四大特性、事务的概念、MySQL中事务的常用语句和@Transactional注解的使用。
2023-03-03 14:48:43
1054
原创 指针为参数的时候，不带引用和带引用的区别
指针为参数的时候，不带引用和带引用的区别1.问题场景描述案例1#include<bits/stdc++.h>using namespace std;//指针参数不带引用void test1(int* a){ a=new int; (*a) = 2;}//指针参数带引用void test2(int* &a){ a=new int; (*a) = 3;}int main(){ int* a=new int;
2022-04-22 21:15:39
762
原创 HTML导出为word：jquery.exportWord.js
通过使用jquery.exportWord.js，将HTML导出为word，手动控制分页。
2022-04-21 19:04:17
3353
原创 HTML基础
一 .HTML基础网页上有各种各样的元素，比如文字、图片、链接等，他们都是通过HTML语言进行表达的，接下来对使用HTML语言编写简单的静态网页进行讲解。1.1 静态网页制作1.1.1 HTML简介HTML超文本标记语言，是构成网页文档的主要语言。一般情况下用于在网页上看到的图片、链接、动画、文字等元素都是通过HTML语言表达的。1.1.2 HTML文档的基本结构基本结构如下<!--这是一行注释--><html> <head> 头部信息 &
2021-11-19 13:40:28
1461
原创 Hdu 4738 Caocao‘s Bridges 割边(桥）
题意给定n个兵营和m座桥，每座桥上有若干个敌人，要求炸掉最多一座桥使得n个兵营和m座桥连成的无向图被分为至少两个连通块。炸一座桥至少出动一名士兵并且出动的士兵个数不能小于桥上的敌人个数，桥上可能没有敌人。思路炸掉一座桥使得无向图变成2个以上的连通图。也就是从图中删除一条边e之后，图分裂为两个不相连的子图，那么e称为桥 或者 割边 。就是这题就是求割边的模板题了。具体算法链接跳转Tarjan算法与无向图连通性。具体思路是求割边中权值最小的边，如果图本来就是2个以上的连通图输出答案0，如果不是那么输出割
2021-11-16 21:55:47
109
原创 Tarjan算法与无向图连通性
无向图的割点与桥在看Tarjan算法之前先看以下概念：给定无向图连通图G=(V,E)。若对于 x∈V ，从图中删除节点x以及与x关联的所有边之后，G 分裂为两个或者以上的连通块，则称节点 x 为无向连通图 G 的割点。若对于 e∈E ，删除边 e 之后，G 分裂为两个不相连的子图，则称 e 为 G 的桥或割边。Tarjan算法能够在线性的时间内求出无向图的割点和桥。时间戳在图的dfs过程中，按照每个节点被第一次访问的时间顺序，一次给 N 个节点 1~N 的整数标记，这个标记就是时间戳，节点 x
2021-11-16 21:31:26
389
原创 C++内存管理机制
内存五大分区1.栈区程序运行时分配内存。c++程序运行时分配内存，主要存储函数的参数以及局部变量。局部变量分配内存时在栈区从高地址到低地址查找空的内存区域进行分配。函数运行结束时回收内存。2.堆区程序运行时分配内存堆区又称动态内存分配区，主要存储new或者malloc出来的内存，分配内存时在内存的堆区中从低地址到高地址寻找空的内存区域进行分配。delete或者free后回收内存，如果没有delete或者free操作则在程序运行结束后由操作系统回收内存。3.全局区程序编译时分配内存全
2021-11-09 19:55:26
3627
1
原创 C++字符串输入缓冲区机制
一、缓冲定义1.缓冲定义缓冲是在两种不同速度设备之间传输信息时平滑传输过程的常用手段。2.为什么引入缓冲区操作系统这门课有明确的说明缓冲的作用，是为了解决高速设备和低速设备之间速度不匹配的问题，直接举个书上的CPU和打印机的例子：首先我们要用打印机打印一篇文章肯定要经过CPU处理然后给到打印机打印文章，但是CPU处理1000个字节的文字一眨眼的事情，但是打印机可能需要若干秒，总不可能让CPU一直处理一个数据给打印机一个数据这样子等着运行，这就引入了缓冲区，CPU处理完数据存入缓冲区，打印机直接从缓
2021-10-27 21:06:58
1242
原创 D. Frog Traveler Codeforces Round #751 (Div. 2) DP
题意给定一口深度为n的井，和两个个长度为n的数组a和b（下标从1~n），a[i]表示你可以再高度i的位置往上跳a[i]高度，b[i]表示如果你跳到i这个位置会往下滑b[i]的高度，求从井底跳到深度0的位置最少需要多少步，并且输出跳的方案。思路看思路之前首先看数据范围，1≤n≤300000，0≤a[i]≤i，0≤b[i]≤n-i。比较容易能想到一种dp的思路，设dp[i]为从井底跳到高度i所需的最少步数，设你当前位置为x，x高度所有可以跳到的地方yi（跳到一个高度之后滑下来的地方），都可以有一个转移
2021-10-26 19:55:16
124
原创 CF F1. Korney Korneevich and XOR (easy version) Codeforces Round #750 (Div. 2) DP
题意给定一个长度为n的数组a，要求选择a的一个上升子序列，这个上升子序列所有元素异或值为x，要求求所有的x并从小到大输出，这个子序列可以为空，为空的时候异或值为0.思路首先看一下数据范围：n (1≤n≤105).a1,a2,…,an (0≤ai≤500)。ai小于等于500,那么异或值一定不会超过512-1，所以说异或的情况最多就只有512种，也就是0~511，那么我们可以用一个ans数组存储当前已经求得的异或的情况，然后选取一个ans[j]和当前这个数字a[i]异或，当然需要满足上升子序列这个条件，
2021-10-25 15:59:21
297
原创 CF D. Vupsen, Pupsen and 0 Codeforces Round #750 (Div. 2)
题意给定一个长度为n(n>=2)且不包含0的数组a，要求求一个数组b使得∑ai⋅bi=0（其中bi不等于0）也就是每个ai和bi的乘积的和等于0。要求∑abs(bi)<=1de9思路这种构造题思路一般不唯一，我只讲下我的构造方式，并不代表只有我这种是正解=3=。首先假设n为2，也就是a中的元素有a1和a2，对于两个数字我们有一种显而易见的构造方式，a1*(-a2)+a2*a1=0，也就是b1=-a2,b2=a1.那么我们的思路就清晰了，对于n长度>2的情况每次找两个没被用过数字构造成
2021-10-25 13:55:01
82
原创 CF E. Moment of Bloom Codeforces Round #749
题意给定n个节点m条边的无向连通图以及q个查询，一开始所有边的权值为0，每个查询给定两个点u和v，要求选择从u到v的一条简单路径（路径上每个点不经过超过1次），使得这条路径上的权值都+1，最后得到的图中所有边的权值都为偶数，问是否能有q条路径满足条件，满足的话输出路径，不满足则输出需要添加的查询数。思路首先证明以下两点：1.某个点在q次查询中如果出现奇数次，那么这张图一定无解。2.所有点在q次查询中出现次数都为偶数次，那么这张图一定有解。首先证明1，如果某个点u在查询中出现奇数次，因为对于每个查
2021-10-19 18:20:29
124
原创 CF D2. Half of Same Codeforces Round #748 (Div. 3)
题意简单版本题意：给定n(偶数)个数字，可以进行如下操作，选定一个数字k，对每个数字减去若干个k最终所有数字相等，求最大的k是多少，如果k可以任意大输出-1。复杂版本题意：给定n(偶数)个数字，可以进行如下操作，选定一个数字k，对其中n/2个数字每个数字减去若干个k使得这n/2个数字相同，求最大的k,如果k可以任意大输出-1。思路在求解困难版本之前我们先看简单版本，所有数字要减去若干个k变成同一个数字。首先看两个数字的情况，假设有两个数字a,b(其中b>a),如果b-a不是0而且也不是k的整数
2021-10-14 19:41:39
121
原创 矩阵连乘问题 动态规划
问题描述给定n个矩阵，保证可以按顺序从第一个矩阵乘到第n个矩阵，你不可以改变矩阵的顺序，但是你可以在任意位置加入合法的括号，比如1234表示矩阵1×矩阵2×矩阵3×矩阵4，你可以加入括号1(23)4,1(234),来使得乘的顺序发生一定改变，要求求给定n个矩阵连乘其中乘法运算次数最少是多少。两个3×3的矩阵相乘需要27次乘法运算。思路首先看两个矩阵的乘法A×B,假设A的行数为r1列数为l1，B的行数为r2列数为l2，前提条件是l1必须等于r2,也就是第一个矩阵的列数必须等于第二个矩阵的行数，而且A×B
2021-10-13 21:48:06
778
原创 1598D Training Session Educational Codeforces Round 115 (Rated for Div. 2) 组合数学+暴力
题意有n个题目组成的题目集，每个题目有一个topic和一个diffcult，同一个topic中的题目不会有相同的diffcult，要求取3个题目出来对应的topic都不同或者difficulty都不同有多少种取法。思路题目要求选3个题目出来对应的topic都不同或者对应的difficulty都不同，我们反向考虑，选3个题目出来，题目对应的topic和difficulty都有相同，然后用方案总数-topic和diffculty都有相同的方案数。因为同一个topic中的difficulty都不同，所以3个
2021-10-12 21:11:17
133
原创 2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛（重赛）1011 Jumping Monkey
1011 Jumping Monkey思路：首先看当前图中剩下的权值最大的点u，要使得答案最优从任何一个节点开始跳，跳到最后肯定会跳到u。那么考虑把v从图中去掉，图会变成若干个连通块，这些连通块自己内部求最优解再加上跳到权值最大的点u就是正解。按照这个思路，每趟将所有连通块中权值最大的点拿出来，对于节点v,如果该节点再第k趟被拿出来，那么节点v的解为k。这里我们反向进行如上过程，对于最后一趟拿出来的点一定是每个连通块中最小的节点，我们按照权值从小到大遍历每个节点v，并将已经遍历过的并且和v联通的节点标
2021-10-10 21:13:51
1113
原创 1579E2 Array Optimization by Deque
思路题意就不赘述了，对于一个数字插入deque前面的话对答案的贡献就是当前deque中比该数字小的个数，一个数字插入到deque的后面的话对答案的贡献就是当前deque中比该数字大的个数，和上一个数字插到前面和后面无关。所以这里比较容易得出思路，对于a数组中第i位上的数字，计算它对答案的贡献需要算出：1.前面的数字比他小的个数2.他前面的数字比他大的个数，然后取小的那个个数就是第i位对答案的贡献。对每一位都求一次然后加起来就行了。代码示例TT 先看一下蠢比做法（错误做法）distance函数对于随机
2021-09-29 21:42:32
332
原创 ST表 解决RMQ区间最值查询问题
概念ST表(Sparse Table,稀疏表)，用于解决求区间最大值最小值问题，预处理复杂度O(NlogN)，查询区间最小值O(1).算法思想假设你当前需要解决的问题是求区间最大值。朴素的思想去遍历每次需要O(N)查询区间最大值，如果查询次数为M，时间复杂度需要O(NM),在M比较大的情况下非常浪费时间。接下来我们提出ST表。对于上述问题我们建立一个二维数组mx [N] [log2(N)+1] ,mx [i] [j] 表示第i位开始到i+2j-1这段区间的最大值，假设我们出来出来所有mx [i] [
2021-09-22 21:00:44
96
原创 1574D The Strongest Build （Educational Codeforces Round 114 (Rated for Div. 2)）
题意给定n个从小到大的数组，从每个数组中选出一个构成一个序列，但是有m种序列被ban了，要求选出的序列没有被ban且和最大。思路因为有m个序列被ban了，那么最坏的情况可以假设为最大的m个序列被ban了，那么要求的序列就是第m+1大的序列，优先队列+bfs求前m+1大的序列就好了，在求的中途碰到没有被ban的序列直接退出输出即可。查询一个序列是否被ban用hash的思想,用map+vector的方式查询一个序列是否被ban。还是不好懂的看代码比较清晰=3=.代码#include<bits/s
2021-09-21 14:15:04
229
原创 Codeforces Round #743 (Div. 2) D. Xor of 3
题意给你一个长度为n的数组，只由0和1构成，你可以进行如下操作，从1~n-2中选择一个下标i，使得a[i],a[i+1],a[i+2]同时变为a[i] xor a[i+1] xor a[i+2]，要求将数组中的数字全部变为0。思路首先数字不能全部为1，全部为1无论怎么操作都不可能将任何数字变为0.不能有奇数个1，观察我们的操作，a[i],a[i+1],a[i+2]同时变为a[i] xor a[i+1] xor a[i+2]，如果三个数字中有0个1，则不变，增加了0个1，减少了0个1；如果三个数字中有
2021-09-20 19:30:02
145
原创 Codeforces Round #743 (Div. 2) C. Book(拓扑排序，dp，优先队列)
题意一本书有n个章节，每个章节都有可能有前置章节，对于某个章节i只有理解完他的全部前置章节才能理解章节i，每次看书从第一章看到最后一章，求最少要多少次能理解全部章节，没办法理解所有章节则输出-1。思路看题意就能比较容易看出来是有向图的拓扑排序，对于章节i由di个前置章节那么他的入度就是di，理解了章节i的其中一个前置章节那么di–,只有当di=0的时候才能理解章节i。如果有向图存在环，那么就无解以下给出两种解法：1.dp对于某个章节x，如果他的前置章节y的编号小于x，那么章节x和y可能同时理解，
2021-09-20 15:33:34
180
原创 Codeforces Global Round 16 E. Buds Re-hanging
题意给定一颗n个节点，n-1条边，以1号节点为根节点的树。引入一个bud节点，bud节点不是根节点，也不是叶子节点，但是他的子节点都是叶子节点。你可以进行无限次以下操作：将bud节点和他的所有叶子节点移到任意节点的下方，也就是将bud节点从原来的地方断开变成别的节点的子节点。如下图图1到图2的过程。图1中2号节点为bud节点，将其与1号根节点连接的边断开，链接到3号节点下方得到图2.要求对图进行操作后得到最少的叶子节点数量是多少。思路先将所有bud节点操作后都变为与根节点直接相连，那么图中就只剩
2021-09-14 21:52:16
133
原创 Codeforces Global Round 16 D2. Seating Arrangements (hard version)
题目大意给定n行m列的座位，每个座位按编号从1~nm，一共有nm个观众观众编号1 ~ n*m，对于第i个观众有一个视力a[i],对于不同视力的两个观众i和j，如果a[i]<a[j]，如果他们分到的座位使si和sj，那么必须有si<sj(si和sj为座位编号)。给每个人分配好座位之后，每个观众按照编号先后入场，如果一个人走到自己座位时，有k个人给他让路让他进去，那么针对这个人的不方便值为k。比如一行5列的座位，按照如下方式分给观众：1 2 3 4 5，也就是第i个位子坐观众i，因为按观众顺序就坐
2021-09-14 20:07:46
253
原创 POJ2442
题意给定M个长度为N的序列，要求从每个序列中任取1个数字，可以构成NM个和，求其中最小的N个和。思路首先考虑只有两个序列的情况，分别为序列A和序列B，先将序列A和序列B从小到大排序。最小的和一定是A[1]+B[1]，第二小的是min(A[1]+B[2],A[2]+B[1])，假设第二小的是A[1]+B[2]，那么第三小的就是min(A[2]+B[1],A[2]+B[2],A[1]+B[3])。这里我们可以看出一些规律了，最小的一定是A[1]+B[1]，因为对序列进行过从小到达排序的操作，下一次最小的一
2021-09-11 19:40:34
135
原创 POJ1456 二叉堆
题目大意给定n个商品，第i个商品有一个利润vi，和保质期di，每天只能卖一个商品，要求最大化利润。思路以前写这题的时候思路是对商品按照利润排序，然后优先出售利润大的商品。假设商品A的利润大于商品B，如果他们保质期都只有1天，那么肯定出售利润高的商品。如果有商品A,B,C,利润A>B>C,且保质期都是2天，那么肯定卖A和B，往下继续同理，对于前t天，尽量卖出前t大的商品。卖一个商品尽量在迟的时间卖，这样子就尽量不会占用保质期比他小的商品了。如果那天被占了就往前面找一天卖，在一个商品利润比另一
2021-09-11 15:30:31
153
原创 CF1569D Inconvenient Pairs
题目大意在一个1e6*1e6的网格中，有个n条垂直街道和m条水平街道，k个居民，其中居民只能在街道上。要求求出有多少对村民(a,b)的最短路径大于他们的|Xa-Xb|+|Ya-Yb|，称为不方便路径。其中(a,b)和(b,a)为同一种答案，在计算中不应该算作两种。思路两个村民的最短路径大于他们的横坐标差的绝对值+纵坐标差的绝对值。如果其中一个村民在一个垂直路径上，另一个村民在水平路径上，那么他们之间的最短路一定不是不方便路径，首先这两个路径一定有一个交点，一个村民从开始位置走到交点，再从交点走到另一个
2021-09-09 21:04:10
5102
原创 CF1569C Jury Meeting 组合排列 乘法逆元
题目大意给定一个长度为n的数组，第i位表示第i个人有a[i]个问题需要提出，会议中每个人按照一个特定的顺序依次提出一个问题，没有问题则被跳过，直到所有人都没有问题。比如a数组为 1 2 3 4 5，这个顺序为 5 4 3 2 1，提出问题的顺序就是先5号提出一个问题，然后4号，然后3号，然后2号，然后1号，再回到开始先5号，然后4号，然后3号，然后2号，1号因为没有问题被跳过，直到所有人都没有问题。有多少个这样的顺序使得所有人都不会连着提出两个及以上的问题，也就是不会一个人提出问题后下一个立马又是他提出问
2021-09-09 16:42:01
250
原创 最小表示法
定义：给定一个字符串S，长度为n，将字符串末尾不断提到最前面构成字符串，总共得到n个字符串，称这n个字符串是循环同构的，其中字典序最小的字符串成为字符串S的最小表示。解决方法：令b[i]表示S的循环同构中以第i个字符为开头的字符串，循环比较每个b[i]的字典序，找到最小的那个。在S后面再添加一个S构成一个字符串SS，b[i]就等价于SS[i,i+n-1]。当b[i]和b[j]比较时，从SS[i]与SS[j],SS[i+1]与SS[j+1],SS[i+2]与SS[j+2],比到SS[i+k]与SS[j+
2021-09-07 21:17:34
111
原创 POJ1961 KMP模板
用KMP处理出字符串自己的Next数组之后，对于一个位置i，如果i%(i-Next[i])==0&&i/(i-Next[i])>1,则说明以i为末尾的前缀存在长度为Next[i]循环元，且循环次数为i/(i-Next[i])。#include<iostream>#include<cstdio>using namespace std;int n;char a[1000005];int Next[1000005];void cal_next(){
2021-09-01 21:48:51
55
原创 POJ3974 Manacher模板
二分+字符串HASH#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;string a;int n;typedef unsigned long long ll;ll p[1000005];//p[i]表示27^ill f[1000005];//f[i]表示str[0~i]的hash函数值ll rf[1000005]
2021-08-31 14:59:38
58
原创 CF1561D1 Up the Strip (simplified version)
题意：给你一个长度为n的数组，对于数组的每个位置x，你可以执行两种操作：①.从1~x-1(包括1和x-1)中选一个数字y从x转移到y。②.从2 ~ x（包括2和x）选一个数字y从x转移到x/y（向下取整）这个位置。要求从位置n到达位置1的方案数有多少种。这里特别需要注意方案数的算法：假设当前在4号位置，通过操作①直接选择1号位置是一种方案，通过操作②选则4/4的位置进行转移也算一种方案，这两种情况算两种方案。tle思路：用dp的思想，首先设dp[n]=1，然后从n~2进行循环，设当前位置为i，首先把能
2021-08-25 12:38:29
109
2
原创 CF1559D1.Mocha and Diana (Easy Version)
题意：Mocha和Diana各有一个无向图，他们的无向图都是森林，森林由一个或者多个树构成，所以森林里一定不存在环。要求向Mocha和Diana的森林中同时加入某条边使得他们的图依旧没有环，最多可以加入多少条这样的边。思路：首先对于一棵有m个节点的树来说，这棵树一定有n-1条边，并且每两个点之间都有一条路径，而且树中的任意节点父亲节点个数不会超过一个。为什么树中一定没有环呢，假设树中有环x->y->x，这个环在无向图中其实可以看为x->y的路径有两条甚至以上，那么y这个节点就有两个父
2021-08-16 11:46:55
208
原创 POJ3417 树上差分
题意：给定一个无向图，共有n-1+m条边，其中n-1条为主要边，其他边为非主要边，图中任意两点都存在一条只有主要边构成的路径，要求按顺序删除一条主要边和一条非主要边使得图中所有点至少被分为两个连通块，求这种方案数有多少种。思路：假设这个无向图只有n-1条主要边，那么该无向图很显然是一棵树，添加任意一条非主要边(a,b)都会使得从a到b这条主要边构成的路径加上这非主要边条边构成一个环，只要删除a到b这条主要边构成的路径中的其中一条边，再删除(a,b)这条非主要边就可以使得无向图被分为两个连通块。为了方便
2021-08-15 22:07:19
149
原创 CF1557C Moamen and XOR
C. Moamen and XORMoamen and Ezzat are playing a game. They create an array a of n non-negative integers where every element is less than 2k.Moamen wins if a1&a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an.Here & denotes the bitwise AND operation, and ⊕ de
2021-08-10 16:17:13
191
2
原创 poj1639
题意每个人都从家里开车出来去公园，去公园的路上可能经过别人的家里，这样子可以蹭别人的车，自己的车就不用费油了，假设一辆车子可以无限坐人，每个人家里可以停无限量车，但是公园只能最多停k辆车，求所有人都到达公园且所有车子走过的路程之和最小为多少。输入第一行一个整数n接下来n行每行两个字符串name1,name2和一个数字z，表示name1家到name2家又一条路径权值为z的路最后一行一个整数k表示公园能够停车的数量输出Total miles driven: xx为所有车子走过的路程总和解题思路
2021-08-08 23:32:27
65
原创 算法日记：最小生成树
最小生成树文章目录最小生成树一、什么是最小生成树？二、最小生成树求解方法1.Kruskal算法2.Prim算法三、例题一、什么是最小生成树？给定一个带权无向图G(V,E)，n=|V|,m=|E|。由V中全部n个顶点还有E中n-1条边构成的无向连通子图称为G的一颗生成树。边的权值之和最小的生成树被称为无向图G的最小生成树二、最小生成树求解方法1.Kruskal算法定理任意一颗最小生成树一定包含这个无向图中权值最小的边证明：假设无向图G存在一颗最小生成树不包含无线图中权值最小的边。设e(
2021-08-08 16:50:29
348
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人