- 博客(30)
- 收藏
- 关注
RSS订阅原创 2022年河南大学软件学院新生寒假开学考核题解
本次是whr和zy出的题，题目质量也挺高，建议把能补的题都补了。比赛链接A题最短路问题：这一题时间是两秒，而且数据范围也不是很大。我直接爆搜过的，也没卡掉，我先提供一个爆搜的代码：思路：从起点开始依次遍历每一个能入队的点（可以被更新的点）将其入队，取队头的点更新其他的点，直到队列为空，f[][]数组记录答案，f [ i ] [ j ] 表示 从起点到 ( i , j ) 的最短距离。#include<bits/stdc++.h>#define int long longus
2022-02-28 23:28:44
565
原创 2022_1 _10_56_D
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;const int N=1e5+3;vector<int>v[N],dv[N],idx[N];//v[i]：储存i的所有因数 idx[i]:储存i在序列中出现的位置int f[N],g[N],n,a[N];int main(){ scanf("%d",&n);
2022-01-10 22:33:58
431
原创 第一次省赛总结（非题解）
2021年CCPC河南省省赛总结毕竟第一次打省赛先说一下感想吧省银，有点儿小高兴也有点儿小失望。高兴是因为拿了个奖，失望是因为如果自己暑假足够努力的话是可以冲冲金的。不过忏悔没什么用。毕竟未来还有很多路要走。最重要的还是查漏补缺。简要说一下比赛过程这次比赛的时候，我们采取的是单开，邢单开的A题，我单开B题，孟手速快码模板，看完题之后，邢说A题签到，可以过。结果敲了一半，发现A题细节挺多不好搞，这时候我们看已经有三个队过了K题，于是我们开K题，他们码K题我看L题，他们K题过了之后，我就顺便把L题过了
2021-10-31 21:03:15
146
原创 蓝桥杯训练赛第一周
AB题没必要会，但CD两题一定要会, EF我没看题，不做评论；cf rate 1700+的出题就是不一样，差了200分感觉距离差的挺远的。我只负责前三题题解，后面的不是我A题（求逆序对）：暴力肯定会T掉，所以要借助树状数组这个利器；题意：给一段序列，找出该序列中的逆序对个数。考察范围：（树状数组，离散化）思路：依次遍历数组中的每个元素，将元素的值为其插入的下标并在逐渐插入的过程中不断计算逆序对的数量即可；注意：由于本题中a[i]<=1e9数据过大，需要离散化；因此对于样例：
2021-10-17 12:17:36
145
原创 暑假集训之树状数组C题（C - Minimum Inversion Number）
一道经典的逆序对的题目：要求一个长度为n的序列的n种不同循环同构体的最小逆序对数；n<=5000,由于多组测试样例暴力肯定肯定不行，不过我还是试了三发，都tle了；先上暴力的错误代码：#include<iostream>#include<algorithm>#include<cstring>#define ll long long using namespace std;const int N=5010;int n;int t[N];i
2021-08-05 18:27:36
82
原创 C++课--单链表的基本操作
链表是一种重要的数据结构，能够动态地进行存储分配的一种结构链表，它与数组比较是不用事先确定存储空间，链表的实现方式有两种（其实是我只会这两种）第一种：是通过结构体指针实现。（课本上讲的就是这种方法）第二种：是通过数组模拟实现。即链式向前星（不需要掌握）这两种只是实现方式不同，本质是相同的；下面讲解单链表如何实现：首先链表的每个节点分为数据域和指针域；头指针Head指向第一个元素第一个元素存储第一个数据和指针域指向第二个元素的地址 （第二个元素不必要紧挨着第一个元素）第二个元素存储第二个数据
2021-06-09 15:59:14
1108
4
原创 计算表达式的值
不难，一点也不难真的简单，不信往下看：题目简单俺先说一下大致思路哈：就是用模拟个二叉树，内部节点存符号，叶节点存数字没啦，思路就这么简单开玩笑的哈首先 输入字符串，依次枚举每一个字符如果为数字就进行数字的处理直到处理到不是数字为止如果是字符则判断待入栈的优先级和已入栈的优先级谁的高如果已入栈的大于等于待入栈的优先级则进行计算处理如果遇到 '('直接入栈即可如果遇到 ‘)’ 从右向左依次计算直到计算到 ‘(’ 为止最后如果还存在内结点的话，就在进行eval()即可不废话了，上代码
2021-05-18 20:00:31
362
2
原创 Kruskal算法和染色法判定二分图
今天搞的挺简单的1.Kruskal算法求最小生成树 (结构体对权重排序)2.染色法判定二分图（深度优先遍历）1.kruskal#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=200010,M=100010; int p[M];int n,m;struct Edge{ int a,b,w;
2021-04-11 23:01:49
142
1
原创 最短路问题-基础篇
先写篇博客回复一下心情吧图论太难了，我不配总结一下这几天学的吧。朴素版dijkstra算法时间复杂是 O(n2+m), n 表示点数，m 表示边数主要用于解决边权为正，存在重边和自环；参考链接#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<algorithm>#includ
2021-04-09 14:19:25
127
原创 自然数拆分,搜索。
又是被搜索折磨的一天…洛谷自然数拆分#include<iostream>using namespace std;int n;int a[15];void dfs(int x,int y,int startx){//x代表递归的层数，y代表剩余数； if(y==0&&x!=2){ for(int i=1;i<x-1;i++){//startx指遍历开始的位置； cout<<a[i]<<"+"; }cout<<
2021-03-13 22:14:49
96
原创 朴素版的dijkstra算法
去你大爷的dijkstra算法没忍住，学了好久终于解决了朴素版的dijkstra算法水题链接 最短路径问题#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,m;const int N=510;int dis[N];//某点到n的距离；int g[N][N];int a,b,c;bool is[N];int ddd(int n){ me
2021-03-13 21:00:22
169
原创 最小k元素
卧槽，牛逼啊咳咳，好孩子不说脏话，今天发现一个强大的STL他就是 nth_elementnth_element(数组名,数组名+第k小元素,数组名+元素个数)；#include<bits/stdc++.h>using namespace std;long long n,k,a[5000010];int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&am
2021-03-13 15:42:53
97
1
原创 最长公共子序列（动态规划+二分）
最长公共子序列（动态规划+二分）用f[n]存储最长公共子序列，用a[i]来存储数组， cnt代表最长公共序列的长度，遍历时用a[i]遍历，每次遍历时用a[i]与f[cnt]比较大小，如果a[i]>f[cnt-1],则f[cnt++]=a[i];否则，用二分的方法将a[i]插入在f[n]这个数组中；代码如下：#include<iostream>using namespace std;typedef long long ll;const int N=1e7+10;int n
2021-03-12 12:19:20
259
2
原创 深搜之全排列
#include<bits/stdc++.h>using namespace std;int n;//n<=10;int b[120],flag[120],p;//flag为0表示未标记；flag为1表示已标记； void pr(){ for(int i=1;i<=n;i++){ cout<<setw(5)<<b[i];//setw(5)指场宽为五； }cout<<"\n"; }int dfs(int x){ if(x&
2021-03-06 22:49:04
221
原创 深搜之最短路径问题
从起点走到终点的迷宫；若求所走的步数，则先设定int min1=0x3f;需构造两个二维数组，一个用来储存地图，另一个用来是否已走过；注意入dfs前与出dfs前状态相同，即注意回溯；关键是上下左右四个方向移动，朴素写法为#include<bits/stdc++.h>using namespace std;int H,L,q[15][15];//1表示可走，0表示不可走； int startx,starty,endx,endy;int min1=0x3f;int cnt;i
2021-03-06 21:43:38
534
原创 完全背包问题
0/1背包是物体的数量是单一的；而完全背包问题物品的数量是无限的；#include<iostream>//完全背包问题 using namespace std;int M,N;//M代表容积，N代表物体的个数；int m[1000],n[1000];//n代表价值，m代表重量 int dp[1000]; int main(){ cin>>M>>N; for(int i=1;i<=N;i++)cin>>m[i]>>n[i];
2021-03-04 15:57:05
61
1
原创 0/1背包问题；
0/1背包最重要的是状态转移方程 ；#include<iostream>#include<cmath>using namespace std;int V,N;//N是物品的个数，V 是所容纳最大的体积 int v[1005],c[1005];int dp[1005][1005]; int main(){ cin>>N>>V; for(int i=1;i<=N;i++)cin>>v[i]>>c[i]; for(
2021-03-04 09:34:54
104
1
原创 优先队列＞＞priority_queque；
优先级队列定义:#include<bits/stdc++.h>using namespace std;//typedef less<int> Z;priority_queue <int,vector<int>,greater<int> > a;//递增的优先级队列 priority_queue <int,vector<int>,less<int> > a;//递减的优先级队列//***********
2021-01-30 09:07:10
87
原创 贪心之部分背包问题
#include<bits/stdc++.h>using namespace std;int n,t,s1;double s2;struct jb{//定义一个结构体； int m; int v; double dj;};jb a[101];bool cmp(jb a,jb b){ return a.dj >b.dj ;//用int和bool都一样；对结构体比大小；} int main(){cin>>n>>t;for(int i=0;.
2021-01-29 19:23:04
83
原创 欧式筛法；**注意是数组开的要够大**
欧式筛法；//#include<bits/stdc++.h>#include<iostream>////////运用欧式筛时数组一定要开的够大；；；；；； #include<cstdio>using namespace std;bool flag[5000000];//0为素数，1为非素数； int prime[5000000];//储存素数的地方； int s,n=1000000,t;int d[5000000],q;int main(){ cin&
2020-12-29 14:28:16
194
1
原创 分数大小的比较
#include<iostream>#include<cstring>#include<cmath>using namespace std;int main(){long long a,b,x,y,a1,b1;while(~scanf("%lld %lld %lld %lld",&x,&a,&y,&b)){ if(x/a>y/b){ printf(">\n"); }else if(x/a==y/b){ a.
2020-12-28 22:49:47
575
原创 大整数的加与乘；
大整数的加与乘；1.加#include<bits/stdc++.h>using namespace std;int a[10000],b[10000],c[10000];char a1[10000],b1[10000];int cnt,i,j;int main(){ cin>>a1>>b1; int lena=strlen(a1); int lenb=strlen(b1); int len=max(lena,lenb)+1; for(i=
2020-12-28 22:11:23
49
原创 无限循环判断方法；
无限循环判断方法；例题：2019新生狂欢赛B题```cpp#include<iostream>using namespace std;int w[110];int beichu(int n){ while(n%2==0){ n=n/2;//是否为无限小数，含除1，2，5，本身外的因子，就是无限小数； 同理不含就不是； }while(n%5==0){ n=n/5; }return n;}int sushu(int n){ if(n==1){ return
2020-12-25 12:22:08
1000
原创 2020-12-17
算法优化之最大公约数；#include<iostream>#include<string>using namespace std;int f(int a,int b){ int t; while(b!=0){ t=a%b; a=b; b=t; }return z;}int main(){int x,y;cin>>x>>y;int r=f(x,y);cout<<r; return 0;}思想a为除
2020-12-17 20:43:43
60
原创 字符串处理：
字符串处理：1.字符串的输入a.cin.getline(字符型数组名称，输入的位数，截止标志)；例```cpp#include<iostream>using namespace std;char q[11100];int main(){cin.getline(q,11100,'a');//对q进行输入到a截止且最多输入110位；for(int i=0;i<11100;i++){ cout<<q[i];}return 0;}结果：b.getli
2020-12-17 19:16:25
150
原创 2020-12-12
大整数相减；相比于大整数相加，大整数相减多了一个比大小和最后输出时再次将int型数组转化成字符串的形式进行输出；#include <bits/stdc++.h>using namespace std; const int maxn = 210;//固定数组的大小； string yunsuan(char *s1, char *s2){ int a[maxn], b[maxn]; memset(a, 0, sizeof(a));//a,b数组的初始化； memset(b, 0,
2020-12-12 00:16:49
105
原创 2020-12-06
简单的模拟题；当对数组进行移位时，注意数组越界问题；例(q==3)后面的a[x-1]=a[x+i]可能就会导致数组发生越界且后必须加上判定条件；
2020-12-06 23:13:06
67
原创 2020-12-06
1.对于字符型数组如何查找某一个字符的个数？可用头文件：#include<bits/stdc++.h>#include<bits/stdc++.h>using namespace std;int main(){char a[10010];char c=’.’;cin.getline(a,10010,’.’);int d=0;int q=strlen(a);a[q]=’.’;for(int i=0;a[i+1]!=’.’;i++){if(a[i]==‘a’)d+
2020-12-06 21:13:23
127
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人