- 博客(72)
- 收藏
- 关注
RSS订阅原创 二分查找易错分析总结
前言：二分分为两种：1.小数二分2.整数二分小数二分一般比较无脑，因为不用考虑边界问题，但是整数的二分涉及到边界问题就比较容易出错，以下是个人对整数二分的一个总结。AcWing 789. 数的范围#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;int main(){ int n,q; cin>>n>>q; int a[N]; for(int i=
2021-11-16 17:01:43
590
原创 java多线程学习
一、基本语法知识1.Thread的join方法指的是当前线程结束才能执行后面代码。2.start方法调用run方法二、体会理解1.new Thread(new Implements_Runnable()).start()这样的线程创建方式，可以反映出Thread类的实现方式：内置了一个Runnable对象，当传入一个实现了runnable接口的对象时，相当于重写了runnable方法，相当于实现runable方法的传递，实现方法可重复 利用。...
2021-11-09 11:31:11
301
原创 Stream学习总结
1.获取字符串组成的列表中最长的字符串 List<String> list = Arrays.asList("adnm", "admmt", "pot", "xbangd", "weoujgsd"); String s = list.stream().max(Comparator.comparing(String::length)).get(); System.out.println(s);2.获取数字列表中最大的数的两种方法 /*方法一：自定义比较函
2021-11-03 22:29:12
216
原创 大模拟技巧
在打acm的过程中，个人总是有这样一个现象，写思路不好想但是码量少的题，能够很快写出来。但是呢，思维难度小，但是码量大的题，总是写很久很久。这是什么原因呢？首先我们要分析一下大模拟，也就是码量大的题的特点：情况多，细节多码量大解决这个问题的纵向长度较长写这种类型的题目时，没有先树立一个大体思路，没有打好一个框架，只把这个思路放在脑子里，当处理细节的时候，处理着就忘了别的细节或者是大体思路，重新回想非常浪费时间，甚至导致忘记一些细节，导致崩盘。所以，为了解决以上问题，应该采取如下措施应对：
2021-09-28 15:27:43
1152
原创 线段树练习题
poj-3667–hotel整体来说思路不难想，就是细节比较多，处理复杂，容易出错题意：给出长为n的空间大小，支持两种操作1.给定长度len,尽可能填补靠左边的空间，并输出填补的起始位置2.给定起始位置pos，以及长度len，将以pos为起始长度为len的空间清空思路：变量记录：维护三颗线段树，seg_left[root]表示结点root对应的区间[l,r]上，从左端点l起始的空闲空间长度，seg_right[root]表示结点root对应的区间[l,r]上，从右端点r起始的空闲空间长度,
2021-09-24 12:35:25
127
原创 状态压缩dp
题面特征状态压缩dp这类 题目一般比较明显，通常是暴力的思路很好想但是很明显暴力的思路会远远超时，这是特征之一，然后观察到N或者M特别小例如N<10这样的，这是特征之二，这类题通常用状态压缩dp做。解题思路我们用状态压缩dp主要是将某个状态转换成二进制，遍历每一个状态，然后通过一系列预处理，达成降低时间复杂度的目的。例题acwing291. 蒙德里安的梦想#include <bits/stdc++.h>using namespace std;typedef long lon
2021-08-05 22:30:42
76
原创 背包dp
求 k 整除最大元素和细节比较多，好题#include <bits/stdc++.h>using namespace std;typedef long long ll;ll dp[105] ;ll w[100005];int main(){ int n,k; ll tmp[105]; memset(tmp,0xcf,sizeof(tmp));//注意初始化，表示初始不可被转移的位置 //cout<<dp[1][1]<<end
2021-05-24 20:47:09
68
原创 字典树（trie树）
1472：【例题2】The XOR Largest Pair板子题#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+10;/*第一维的大小是绝对位置，绝对位置的话是数的个数乘以位数，第一位的大小等于树的结点个数，结点个数跟数的个数以及这个数的长度有关*/int tree[32*N][2];int sum[32*N];int cnt=0;void Insert
2021-05-17 12:21:24
172
原创 蓝桥杯练习
1.深搜回溯1320: [蓝桥杯2017初赛]方格分割简单的深搜回溯题#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e6+10;const ll mod = 31536000;int vis[15][15];int ans;int tx[4]={1,0,-1,0},ty[4]={0,1,0,-1};void dfs(int x,int y){ if(x&
2021-03-24 22:33:40
196
原创 寒假cf补题
Codeforces Round #695 (Div. 2)B. Hills And Valleys*1700，这题直接暴力，不需要dp，判断的时候注意下标#include <bits/stdc++.h>using namespace std;const int N = 3e5+10,M=2e5+10;typedef long long ll;int a[N];bool judge(int left,int right,int now){ if(now>left&
2021-01-23 16:01:20
92
原创 拓扑排序c++（板子题）
HDU1285#include <bits/stdc++.h>using namespace std;vector<int>G[505];queue<int>q2;priority_queue<int,vector<int>,greater<int> >q;//优先队列在从小到大的情况下，没有条件队列即可int in[505];//顶点入度int topo(int n){ for(int i=1;i<
2020-12-21 15:37:39
254
原创 icpc上海站2020部分题解
第一次icpc比赛，最后是以3题300多名的成绩直接打铁，很可惜，D题赛后才知道是精度的问题，不然估计可以拿铜。从比赛中也能得到很多经验与教训。经验：1.选好赛区，少打两年。这次站除去打星队都有600多队，只有210个牌，听说济南站只有500队牌子数跟上海站一样，枯了。2.这次思维题有足足5题，全做了可以到银牌，以后要加强手速和思维题的锻炼，可以多打cf。3.数学题偏多。前5题：G B M D I 中，有G D I 都是数学题，注重公式推导，数学运算，这方面以后要加强锻炼。反思个人反思：1.
2020-12-14 21:17:42
1741
3
原创 根据前序序列（或后序序列）和中序序列构造二叉树
前序加中序void Create(BiTree &T,int *pre,int *in,int n){ if(n<=0||!pre||!in){T=NULL;return ;} T=new BiTNode; T->data=*pre; int *p; for(p=in;p<in+n;p++) if(*p==*pre)break; int k = p-in; //下面两句话比较关键 //左子树前序向
2020-11-24 21:27:32
392
原创 线索二叉树
下面代码为中序线索二叉树#include <iostream>using namespace std;#include <stdio.h>#include <stdlib.h>typedef char TElemType;typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild; int LTag,RTag;}BiThrNode,*BiTh
2020-11-17 16:58:53
81
原创 层序遍历二叉树
用队列实现的层序遍历二叉树，就是宽搜bfs#include <bits/stdc++.h>using namespace std;typedef char TElemType;typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;void CreatTree(BiTree &T){ char ch; scanf("
2020-11-17 16:52:58
74
原创 非递归中序遍历二叉树
用栈实现#include <bits/stdc++.h>using namespace std;typedef char ElemType;typedef struct node{ ElemType data; struct node *lchild,*rchild;}BiTNode,*BiTree;stack<BiTree>s;void Create(BiTree &T){ char ch; cin>>ch;
2020-11-17 16:49:19
218
原创 数位dp
不要62方法一：记忆化搜索/*数位dp分析1.把每位数字抠出来2.分情况：画树状分析图3.预处理数组4.注意处理最后一种情况5.注意位数的问题，预处理的数组表示的含义弄清*/#include <bits/stdc++.h>using namespace std;const int N = 12;typedef long long ll;const int mod = 1e9+7;int dp[10][2];int digit[20];int dfs(int
2020-11-12 21:11:18
87
原创 栈与队列（数据结构）
1.顺序栈#include <iostream>using namespace std;#define MaxSize 50typedef int ElemType;typedef struct{ ElemType data[MaxSize]; int top;}SqStack;void InitStack(SqStack &S)//要改变栈内的元素或者，top指针{ S.top=-1;}bool Empty(SqStack S){
2020-10-27 09:17:48
108
原创 东北四省赛2019 H - Skyscraper（树状数组）
看了下题解思路才做出来的，一开始根本没有思路，还以为是线段树维护。要掌握分析题目的方法：先在样例上尝试，各种方法，并且结合题目，看上去不是线段树就是树状数组，并且也不是简单的维护前缀和，并且有区间修改的操作，想到维护差分数组的树状数组。最后要思路清晰得得出结论，便可找到合适的算法或数据结构解决，此题结论便是：构造差分数组，维护两个树状数组，一个是普通差分数组，另外一个是只维护大于0值的差分数组。在这里总结一下个人对树状数组与线段树区别的理解：树状数组（1）复杂度稳定O(logn)，常数小，比线段树快
2020-09-24 20:15:14
262
原创 线段树segment——tree
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+10;//sum为原数组，add为懒标记ll n,m,x,y,k,opt,a[N],add[4*N],sum[4*N];//add[i]表示第i个区间内每个数要加的值，也就是懒标记(延迟标记)void build(ll i,ll l,ll r)//建树，i为线段树的下标，lr为原数组下标{ if(l==r)
2020-09-08 15:49:47
121
原创 codeforces训练（rating1400-1800）
Educational Codeforces Round 90 (Rated for Div. 2)D. Maximum Sum on Even Positions解题思路：首先将问题的多种不同情况列出来，发现有两种情况。这种数组的问题好像经常会有差分数组的构造。，下次解不出来构造一下差分数组。由于求的是连续的，所以构造差分数组，后求连续子段和，并且复杂度是O（n），满足。#include <bits/stdc++.h>using namespace std;const int N
2020-08-18 17:46:52
481
原创 Educational Codeforces Round 92 (Rated for Div. 2)题解(A-C)
1389A. LCM Problem害，水题a的太慢，一开始还想着暴力，时间复杂度都没看，还有没用longlong结果交了3次，后面的不会，水题a的慢，得改改。题意：给定两个整数定义的闭区间[l,r]，让你在区间内找出两个数x,y满足LCM(x,y)≤r；思路：容易验证LCM(x,y)至少是min(x,y)的二倍，所以直接构造一组最小的解(l,2l)(l,2l)#include <bits/stdc++.h>using namespace std;typedef long lo
2020-07-31 00:40:45
205
原创 Dijkstra算法和SPFA算法
P4779 【模板】单源最短路径（标准版）/*思路：用链式向前星存储顶点之间的关系与权值用优先队列存储边权小的先出首先将起点入队，向四周发散，再将起点与到达点的总权值入队，保证了是一步一步到达（如果不连通不可能遍历到），同时遍历的过程当中不断找更小的权值并更新优先队列的用处：若有两种不同的到达方式，优先队列会先遍历到短的那一条，然后将其入队，那远的一条就不会入队。*/#include <bits/stdc++.h>using namespace std;const in
2020-07-25 17:01:41
185
原创 树状数组
#include <bits/stdc++.h>//using namespace std;#define lowbit(x) ((x)&(-x))const int N=5e5+10;int tree[N],a[N],n,m;//构造一个树状数组,x为下标，k为数void update(int x,int k){ while(x<=n) { tree[x]+=k; x+=lowbit(x); }}
2020-07-23 01:30:45
75
原创 个人理解的kmp算法
kmp还是挺难上手的，看书加看博客，看了有五六篇才理解，看了大概四个小时。。#include <iostream>#include <string.h>#include <stdio.h>using namespace std;//next数组本质是模式串中的前缀和后缀的相等数int next[555];//得到next数组的过程也是模式串自身匹配的过程void GetNext(char *p){ int plen=strlen(p);
2020-07-21 01:23:21
90
原创 数据结构与算法-二叉树
----------------------------学习数据结构第三天-------------------------------前言：今天学习一下二叉树，以前没学的时候就感觉这个数据结构是个神奇的结构，一生二，二生四。。。对这个数据结构总是抱有莫大的好奇，今天终于学到了，感觉这个数据结构是非常奇妙的。今天学习的内容是：1.二叉树的定义与创建 2.前序遍历 3.中序遍历 4.后序遍历总结：1.二叉树的创建要用二级指针，我对这个为啥要用二级指针的原因也是一知半解，先暂时记住，以后用多了，就会慢
2020-07-19 15:52:10
136
原创 day2-栈
学习数据结构第二天，继续冲！栈的操作分为：栈的 创建，入栈，出栈，栈的输出。栈定义时，为一个结构体，定义一个栈顶，一个栈底，但是栈底基本不动，还要定义一个存储数据的线性表。#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct{ char data[100]; int top; int bottom;}stack;//栈的创建,就是分配空间加
2020-07-14 23:24:15
50
原创 day1-双向链表
前言-学习数据结构与算法第一天今天是2020年7月13日，今天开始学习数据结构与算法这门课程，之前好多立下的学习计划貌似都荒废了，这次可千万不能荒废啊，拜托了！今天先学习一个简单的，双向链表，有单链表的基础，这双向链表也是学的比较快，基本原理搞懂了，代码跟单链表一样一样的。#include <stdio.h>#include <stdlib.h>typedef struct node{ int data; struct node *next,*pre;
2020-07-13 23:29:42
109
原创 点餐系统（c语言）
#include<iostream>#include<cstring>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<cstring>#include<conio.h>using namespace std;typedef struct member{ char username[20];//用户名 char pa
2020-06-15 19:42:03
4938
2
原创 c语言期末复习（选择填空）
1.c语言程序从程序中的main函数开始运行。2.c语言程序的3种基本结构是顺序、选择、循环。3.c语言的工作过程是编辑、编译、连接、运行。4.标识符的命名规则1）只能由字母、数字、下划线构成2）数字不能作为标识符的开头3）关键字不能作为标识符5.c语言中简单数据类型包括整型、实型、字符型。6.二维数组的定义可以省略行数，不能省略列数。7.未指定存储类别的变量，其隐含的存储类别为auto。8.结构体类型名有typedef s才是结构体类型名typedef struct stu{
2020-06-13 22:43:22
482
2
原创 c语言文件
1.打开当前目录下名叫“data.in.txt”的文件FILE *fp=fopen("data.in.txt","r");//如果打开了的话，返回一个指针r为只读的打开方式，不存则返回NULLw为只写的打开方式，存则清，不存则建立a为追加的打开方式，存则加，不存则建立有“+”的都可读写r+，写时：存则覆盖原有内存，不存返回NULLw+，写时，同wa+，写时同a2.关闭文件 fclose(fp);3.读取文件中所有字符while(!feof(fp))//读取所有字符的方式，指针会自
2020-05-18 18:04:31
139
原创 链表基本操作
一、创建链表1.给出链表长度n需要创建三个节点（必须三个节点，两个不行），头尾新节点头节点用于返回，尾节点用于连接新节点Lnode *CreateList(int n){ Lnode *H,*p,*tail; int i; for(i=0;i<n;i++) { p=(Lnode*)malloc(sizeof(Lnode)); scanf("%d",&p->data); if(i==0)H=p;
2020-05-18 00:29:05
250
原创 碎碎念
今天考了一个c语言的小测试题目大概是：给n个字符串，给他们排序要求用指针数组，用函数要求动态分配内存#include <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>void process(char *a[50],int n){ int i,...
2020-04-30 18:11:57
118
原创 DFS（深搜/4/18）
P1605 迷宫一开始把newx和newy都设置成了全局变量，结果一直错，后来才发现不能这样，因为回溯的时候，回溯到前面的时候，newx newy还是后面的，没有回来，而局部变量的话就不用担心作用域内改变#include <bits/stdc++.h>using namespace std;int n,m,sum;//必须都要定义在前面，养成习惯int a[1005][100...
2020-04-18 18:42:48
260
原创 dp动态规划（持续连载）
今天开始学习动态规划了呢/2020/4/3动态规划真是简单呢（战术麻痹自己）一、数字三角形/2020/4/3P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles应该是最简单的dp题目了，从下往上滚dp[i][j]等于脚下两个dp的最大值加上a[i][j]#include <bits/stdc++.h>using namespac...
2020-04-03 23:43:02
172
原创 洛谷P1160（树）
P1160 队列安排我真的是个蒻蒟，不会做这道题，只能去看题解，看来看去，就这个代码既好看又好理解还感觉很牛X，就照着这个方法自己写了下（没办法我太菜了不会做啊）1-----用树建立各个节点的关系2-----用中序遍历输出#include <bits/stdc++.h>using namespace std;struct node{ int l,r,flag;//...
2020-04-01 12:16:24
124
原创 bfs（广度优先搜索）
P1032 字串变换这道题很多坑，坑了我一天1.设置一个map，防止重复搜索2.字符串的子串有多处相同，第五个点wa3.自己代码写的有点乱4.标志串不能简单直接替换，因为把y 换成yz就会死循环，要弄个别的字符来替换5.replace的两种写法，迭代器法和下标法总之：这题很烦#include <bits/stdc++.h>using namespace std;st...
2020-03-31 21:21:05
133
转载 int (*p)[N]与int *p[N]的区别
指针和数组的区别C++/C程序中，指针和数组在不少地方可以相互替换着用，让人产生一种错觉，以为两者是等价的。 数组要么在静态存储区被创建（如全局数组），要么在栈上被创建。数组名对应着（而不是指向）一块内存，其地址与容量在生命期内保持不变，只有数组的内容可以改变。 指针可以随时指向任意类型的内存块，它的特征是“可变”，所以我们常用指针来操作动态内存。指针远比数组灵活，但也更危险。数组指针...
2020-03-25 09:51:40
407
1
原创 挑战程序设计竞赛书的题解总结（连载中）
写在前面的话（前言）每天无所事事真是无趣啊，作为一个将来要征战acm的优秀青年，我感到有刷点什么的必要了！（鲁迅表示很淦）毕竟同级的acm大佬们真是太强了，跟着老师走肯定会一直被暴打下去。。去oj上刷题呢，又感觉效率 不高，太盲目，所以毅然决然买了这本优秀的书——挑战程序设计竞赛，每天刷几道，然后不太会的再在博客上总结，感觉锤爆同级大佬，夺取acm金，迎娶白富美，走向人生巅峰的日子就在眼前了，...
2020-03-21 14:14:44
217
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人