- 博客(83)
- 收藏
- 关注
RSS订阅原创 求C（n，m）
1、组合数与杨辉三角有对应关系：#include <iostream>#include <math.h>using namespace std;const int maxn=1e6+20;const int mod=1e9+7;typedef long long ll;ll C[1005][1005];void getC(int n){ for(int i=0;i<=n;i++) { for(int j=0;j<=i;
2020-11-28 23:30:22
757
原创 最近公共祖先（LCA）
题目链接题意：求树中两个节点的最近公共祖先。一、先深搜记录每个结点的父亲节点。先将两个节点中的一个节点往上遍历（寻找父亲节点）直到源节点，并标记遍历过的节点，再遍历另一个节点，若遇到的节点已经遍历过，说明该节点为最近公共祖先。#include <iostream>#include <vector>#include <cstring>using namespace std;const int maxn=1e5+10;int n,m,s;int p[m
2020-11-09 21:49:58
218
原创 数列区间最大值（st表、倍增）
题目链接题意：求区间最大值。log(n)/log(k):表示k的多少次方为n。st [ i ][ j ]:表示从i开始往后2^j以内最大的数。st [ i ][ 0 ]:表示从i开始往后2^0=1以内最大的数，只有一个数即为a[i];f（l，r）：k=log(r-l+1)/log(2);st [ l ][ k ]：从l开始往后2^k以内最大的数。st[r-(1<<k)+1][k]：从r开始往前2^k以内最大的数。#include <iostream>#include
2020-11-09 21:37:20
494
原创 约瑟夫环问题
题目链接约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？模拟整个过程，复杂度为O(NM)。用数学方法来求解：例如：15 66, 12, 3, 10, 2, 11, 5, 15, 13, 9, 14, 4, 1, 8, 7.当只有一个人的时候，数组中只有一个人，所以下次一定是下标为0的人出列，即F(1)=0。当有2个人的时候（N=2），因为要报到M的人自杀，所以应该从上一次的下标开始的第M个的人自杀，即F(2)=F(1)+M递推公式：F(i)=F
2020-11-01 13:23:44
95
原创 将一个字符串转换为另一个字符串
题目链接题意：交换一个字符串中的两个字符，使之成为另一个字符串，求最少的步骤。#include <iostream>#include <cstring>#include <algorithm>#include <string>#include <map>using namespace std;typedef long long ll; const int maxn=1e6+10;map<char,int> g;i
2020-10-31 11:21:19
2751
原创 求n的所有因子个数
题目链接反函数y=n/x面积求和来求解。t=n\sqrt{n}n这个函数按照(t,t)对称，所以结果为t前的所有∑n/i乘以2，再减去t*t。#include <iostream>#include <cstring>#include <algorithm>#include <math.h>using namespace std;typedef long long ll;ll f(ll d){ ll ans=1; ll t=sqrt
2020-10-30 13:46:25
1313
原创 畅通工程续（spfa）+求最短路径
题目链接题意：求两点之间最短距离（迪杰斯特拉）Dijkstra算法：以起始点为中心向外层层扩展(bfs)，直到扩展到终点为止。#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <queue>using namespace std;const int maxn=205;vector<pair<int,
2020-10-15 18:26:55
100
原创 vector注意事项
使用 vector<int> v; 声明一个容器v时，即没有预定存储空间；则使用v.push_back(x);插入变量x，那么插入的第一个元素可以用v[0]访问到。使用vector<int> v(n);声明一个容器v时，即预定了存储空间；不能用v.push_back(1)，因为此时的v.push_back(1)是把1插入到v[n]位置，但是v[n]越界了，实际上是无法插入的;圆括号vector<int> v(n)：圆括号是构造函数，表示1个容量为n的vector方
2020-10-05 19:50:17
189
原创 D. Non-zero Segments
题目链接通过插入数使任意子段不为零。通过前缀和，如果两个前缀和相同，说明夹着的部分字段和为零，用map记录，但是每次要清空，因为前面的会影响。相当于在这个数之前加一个特别的数使之往后字段不可能为0；并把这个数放入map；#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <math.h>#include <map
2020-10-05 17:56:07
211
原创 KMP算法
串的模式匹配算法：#include <iostream>#include <cstring>#include <algorithm>#include <string>using namespace std;int Next[1100];void getNext(string t){ Next[0]=-1; Next[1]=0; int len=0,i=1; while(i<t.length())
2020-10-04 14:51:10
73
原创 走方格
题目链接题意：从（1，1）走到（n，m），不能走行数和列数都是偶数的，求有多少种方案。思路：深搜+记忆搜索#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n,m;int d[2][2]= {{1,0},{0,1}};int g[50][50];int dfs(int x,int y){ if(x&1||y&1)
2020-09-28 19:14:48
167
原创 生命之树
题目链接题意：从树中求一个最大连通子块，保证这个连通子块的权值和最大。思路：邻接矩阵+dfs#include <iostream>#include <vector>#define inf -0x3f3f3f3fusing namespace std;const int maxn=1e5+10;typedef int ll;int n;ll w[maxn],dw[maxn];ll ans;vector<ll> g[maxn];void dfs(in
2020-09-27 20:52:50
69
原创 垒骰子
题目链接题意：把 n个骰子垒成一个柱子，但是有 m对面不能贴在一起，问有几种方式。思路一：递归。将所有的情况遍历一遍。#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const ll mod=1e9+7;int n,m;int op[7],dl[7][7];void init(){ op
2020-09-25 19:58:13
239
原创 大臣的旅费
题目链接题意：求一个树中两点之间的最大距离。思路：等于求树的直径。先从根开始找离根最远的那个点，树的直径一定是从这个点出发到另一个点的距离。然后再从这个点找离这个点最远的点，这两个点的距离就是树的直径。只需要两次深搜遍历。#include <iostream>#include <vector>#include <algorithm>#include <cstring>using namespace std;typedef long lo
2020-09-22 18:30:01
75
原创 小朋友排队
题目链接题意：将无序的数列按从小到大排排序，只能和相邻的数交换，求每个数交换的次数。思路：每个数交换的次数 = 左边比它大的数 + 右边比它小的数。因为只能和相邻的数交换，左边比它大的数一定会到这个数的右边，所以左边比它大的数一定会和这个数发生一次交换；同理右边也一样。首先是暴力解法，复杂度为O(n^2)，只能通过30%。#include <iostream>#include <cstring>using namespace std;const int maxn=1
2020-09-21 19:08:08
103
原创 树状数组模板
求数组区间和：#include <iostream>#include <cstring>using namespace std;int lowbit(int n){ return n-(n&(n-1));}void updata(int n,int i,int v,int c[]){ for(int k=i; k<=n; k+=lowbit(k)) c[k]+=v;}int getsum(int c[],int i)
2020-09-20 20:58:21
55
原创 波动数列
题目链接题意：求长度为 n 、和为 s， 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种。1、n*x+n*(n-1)/2*a=s ---> x=(s-n*(n-1)/2*a)/n 首项最小的时候。n*x-n*(n-1)/2*b=s ---> x=(s+n*(n-1)/2*b)/n 首项最大的时候。通过枚举首项，通过深搜找出符合的数组。2、通过 a的数量可以得出 b的数量。因为有的 a，b的数量无论如何都不可能成立，所以可以进行剪枝。3、
2020-09-15 18:16:36
223
原创 矩阵快速幂与斐波那契
题目链接视频讲解好像没有可以完全通过的代码。。。斐波那契和矩阵的关系：#include <bits/stdc++.h>using namespace std;typedef long long ll;vector<vector<ll> > mat_mul(vector<vector<ll> > a,vector<vector<ll> > b){ int ra = a.size(), ca =
2020-09-09 18:10:40
130
原创 数学考试、最大子矩阵
题目链接题意：给 n 个数，求两个长度为 k 的不相交的区间的和。思路：sum数组表示前 i 个数的和，sum [ j ] - sum [ i ]可以表示数组 i 到 j 的和leftmax数组表示 i 左边区间为 k 的最大和。rightmax数组表示 i 右边区间为 k 的最大和。#include <iostream>#include <cstring>#include <algorithm>#include <cstring>using
2020-08-05 17:18:17
115
原创 合并回文子串
查看题目题意：将两个字符串按照原先顺序合并，求最长回文串。code：#include <iostream>#include <cstring>using namespace std;const int maxn=110;char a[maxn],b[maxn];bool f[maxn][maxn][maxn][maxn];int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
2020-07-29 21:50:34
195
原创 运算符：^，~，-
一、^按位异或运算符“^”是双目运算符。当两对应的二进位相异时，结果为1。2(10) 1(01) => 2^1=3(11);3(11) 1(01) => 3^1=2(10);Number^1：（0，1），（2，3），（4，5），（6，7），（8，9）……（n-1，n）；当知道每组的其中一个数，可求另一个数。二、~步骤：~B：B二进制 =>取反 => 减1 => 再取反 => 转化为 10 进制的负数计算~60：60的8位二进制数是 0011 1100
2020-07-29 20:21:31
3597
原创 网络最大流
题目code#include <iostream>#include <queue>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N=1e4+5;const int M=2e5+5;struct node{ ll y,w,nxt;};node Edge[M<<1];ll head[N]
2020-07-29 11:19:38
683
原创 小A与小B
题目code：#include <iostream>#include <queue>#include <algorithm>#include <cstring>using namespace std;const int maxn=1010;char M[maxn][maxn];int dw[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};int visit[maxn][maxn];int n,m;struct no
2020-07-28 19:53:18
160
原创 Manacher(马拉车)：字符串中最长回文子串长度
一、模板#include <iostream>#include <cstring>#include <algorithm>#define M 10000010using namespace std;char str[M],StrNew[2*M];int p[2*M],len;void init(){ int i; len=strlen(str); StrNew[0]='@'; StrNew[1]='#'; for(
2020-07-24 18:11:50
150
原创 Fake Maxpooling、碗的叠放、着色方案
一、Fake Maxpooling题目链接输入n,m,k;在n行m列的矩阵中找出每一个k*k的矩阵中最大的数相加。A{i,j} = lcm(i, j)：矩阵的元素为行和列的最小公倍数。思路：滑动窗口。代码：#include <iostream>#include <cstring>#include <algorithm>#include <deque>using namespace std;const int maxn=5010;int
2020-07-17 20:55:59
206
原创 第八届蓝桥杯大赛省赛-C语言B组
等差素数列2,3,5,7,11,13,…是素数序列。类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。上边的数列公差为30，长度为6。2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。这是数论领域一项惊人的成果！有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：长度为10的等差素数列，其公差最小值是多少？注意：需要提交...
2020-04-28 21:12:01
509
1
原创 Zut_round 8(多维dp1)
A - 编辑距离题目题意：替换、插入、删除。问需要变换多少次可将字符串转换为目的串。思路：遍历两个字符串；相同：在a删除一个字符去匹配b、a添加一个字符去匹配b、a不变的时候去匹配b中选择一个最小的。不同：在a删除一个字符去匹配b、a添加一个字符去匹配b、a替换一个字符去匹配b中选择一个最小的。#include <iostream>#include <cstring...
2020-04-27 21:49:03
119
原创 Codeforces Round #629
A. Divisibility Problem题目题意：a每次加1，问a加多少次就可以整除以b思路：若a可以整除以b，输出0；否则输出(a/b+1)*b-a;#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ...
2020-04-09 22:10:37
86
原创 格子刷油漆
题目描述解题视频#include <iostream>using namespace std;const int M=1000000007;typedef long long ll;int main(){ int i,n; cin>>n; ll a[1010],b[1010]; b[1]=1; for(i=2;i<...
2020-04-09 21:32:13
106
原创 第七届蓝桥杯大赛省赛-C语言B组
煤球数目有一堆煤球，堆成三角棱锥形。具体：第一层放1个，第二层3个（排列成三角形），第三层6个（排列成三角形），第四层10个（排列成三角形），…如果一共有100层，共有多少个煤球？请填表示煤球总数目的数字。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。CODE:#include <iostream>using namespace std;/...
2020-03-18 14:14:34
428
原创 Codeforces Round #626
A. Even Subset Sum Problem题目描述题意：找n个数中找最少的数，是他们的和为偶数。只有一个奇数，输出-1；如果偶数，就输出一个偶数的下标；如果没有偶数，就输出两个奇数的下标。CODE:#include <iostream>#include <cstring>#include <algorithm>using names...
2020-03-10 21:44:13
120
原创 Codeforces Round #625
A. Contest for Robots题目描述题意：有两个机器人对于n个问题有会和不会（1、0）两种情况，让你设置题目的分数使得机器a的分数比b的分数大，求设置的分数的最大值的最小值。若机器a不能赢就输出-1。a、b都能解决或都不能解决的就不用管了。算出a能解决的b不能解决的；算出b能解决的a不能解决的；让第二种情况除以第一种情况再加一。CODE:#include <io...
2020-03-10 19:09:25
88
原创 小 C 的数论习题
题目样例输入：6 6 61 24 24样例输出：624CODE:#include <iostream>using namespace std;typedef long long ll;int main(){ int a,b,c; cin>>a>>b>>c; int A=23,B=233,C=23...
2020-01-31 15:20:26
176
原创 背包问题
0-1背包有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。输出格式输出一个...
2019-12-23 21:53:29
594
原创 查找和排序的应用
[问题描述] 学生信息管理系统[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1.试选择一种方式存储：基于数组、链表或文件方式2．总成绩要求自动计算；3．查询：分别给定学生学号、姓名，能够查找到学生的基本信息（要求至少用两种查找算法实现）；排序：分别按学生的学号、总成绩进行排序（要求至少用两种排序算法实现）。...
2019-12-12 23:48:47
578
原创 进制转换
十六进制转八进制问题描述 给定n个十六进制正整数，输出它们对应的八进制数。输入格式 输入的第一行为一个正整数n （1<=n<=10）。 接下来n行，每行一个由0-9、大写字母A-F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。输出格式 输出n行，每行为输入对应的八进制正整数。【注意】输入的十六进制数不会有前导0，比如012A。...
2019-12-05 21:50:46
188
原创 vector函数用法
一维基本用法：(1)头文件#include <vector>(2)创建vector对象，vector<int> vec;(3)尾部插入数字：vec.push_back(a);(4)使用下标访问元素，cout<<vec[0]<<endl;记住下标是从0开始的。(5)使用迭代器访问元素.vector<int>::iterator...
2019-11-27 21:18:34
2520
1
原创 图的基本操作及应用
题目一： 图的遍历[问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求] 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】 由学生依据软件工程的测试技术自己确定。输入样例：4 40 1 2 30 10 20 32 3输出样例：输出邻接表:0:3 2 11:...
2019-11-21 17:37:36
2072
原创 数位DP：Bomb、不要62
Bombhttp://acm.hdu.edu.cn/showproblem.php?pid=3555Problem DescriptionThe counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence...
2019-11-05 21:24:32
129
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人