算法基础-线性规划(二)-各种DP
各种DP区间DP
123456789101112131415161718192021222324252627282930#include <iostream>#include <cstring>using namespace std;const int N=310;const int INF=0x3f3f3f3f;int s[N];int f[N][N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; for(int i=1;i<=n;i++) s[i]=s[i]+s[i-1]; //区间DP的遍历方式！ for(int len=2;len<=n;len++)//遍历长度！ { for(int i=1;i+len-1<=n;i++)//遍历起点! { int l=i,r=i+len-1; f[ ...
算法基础-线性规划(二)-线性DP
线性DP数字三角形
12345678910111213141516171819202122232425262728293031#include <iostream>#include <cstring>using namespace std;const int N=510;const int INF=1e9;int a[N][N],f[N][N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; for(int i=0;i<=n;i++)//初始化 for(int j=0;j<=i+1;j++)//注意初始化到i+1！！！ f[i][j]=-INF; f[1][1]=a[1][1]; for(int i=2;i<=n;i++) fo ...
算法基础-动态规划（一）-背包问题
动态规划
01背包
朴素123456789101112131415161718192021222324#include <iostream>#include <algorithm>using namespace std;const int N=1010;int v[N],w[N];int f[N][N];int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { f[i][j]=f[i-1][j];// 当前背包容量装不进第i个物品，则价值等于前i-1个物品 if(j-v[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-v[i ...
算法基础-数论
数论质数判断质数–试除法1234567891011121314151617181920212223#include <iostream>using namespace std;bool is_prime(int x){ if(x<2) return false; for(int i=2;i<=x/i;i++)//不建议i*i<=n||i<=sqrt(n) if(x%i==0) return false; return true;}int main(){ int n; cin>>n; for(int i=0;i<n;i++) { int a; cin>>a; if(is_prime(a)) puts("Yes"); else puts("No"); }}
分解质因数–试除法性质：n中最多 ...
linux-1
linux-1ls语法：ls [-a -l -h] [路径]-a 显示隐藏内容-l 以列表形式展示-h 与-l搭配，以更人性化的方式显示可组合使用
cd 切换目录 Change Directory语法：cd [路径]
pwd 查看工作目录 Print Work Directory语法：pwd
相对路径cd ~cd ..cd ../..
mkdir Make Directory语法：mkdir [-p] 路径-p 一次性创建多个层级的目录
touch/cat/moretouch可以创建文件语法：touch 路径cat：查看文件内容（全部）语法：cat 路径more：查看文件内容（可翻页）语法：more 路径
cp/mv/rmcp：复制文件或文件夹语法：cp [-r] 参数1 参数2复制文件夹要 -r参数一：被复制的文件位置 参数二：要复制去的位置
mv：移动文件语法：mv 参数1 参数2
rm：删除文件、文件夹语法：rm [-r -f] 参数一 参数二 参数三…文件夹要 -r
rm支持通配符*rm testrm testrm test
...
算法基础--数据结构
trie12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>#include <cstring>using namespace std;const int N=1e5+10;int son[N][26],cnt[N],idx;char str[N];void insert(char str[]){ int p=0;//父节点，从根开始遍历 for(int i=0;str[i];i++) { int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++;}int query(char str[]){ int p=0; for(int i=0;str[i];i++) { ...
算法基础-哈希
哈希哈希表的插入与查找123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>#include <cstring>using namespace std;const int N=2e5+3;const int INF=0x3f3f3f3f;int h[N];int find(int x){ int k=(x%N+N)%N; while(h[k]!=INF && h[k]!=x) { k++; if(k==N) k=0; } return k;}int main(){ memset(h,0x3f,sizeof h); int n; cin>>n; for(int i=0;i<n;i++) { char op; int x; ...
数据结构上机复习五
1.顺序创建图，删除
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <iostream>#include <cstring>using namespace std;const int N = 20010;int n, m;int h[N], e[N], ne[N], w[N], idx=0;void add(int a, int b, int c){ e[idx] = b, w[idx] = c; if (h[a] == -1 || b < e[h[a]]) ne[idx] = h[a], h[a] = idx++; else { int t = h[a], pre = h[a]; while (b > e[t] && t != -1) pre = t, t = ne[t]; ne[idx ...
算法基础课-图论
图论顺序add123456789101112void add(int a, int b, int c){ e[idx] = b, w[idx] = c; if(h[a]==-1||b<e[h[a]]) ne[idx]=h[a],h[a]=idx++; else { int t=h[a],pre=h[a]; while(b>e[t]&&t!=-1) pre=t,t=ne[t]; ne[idx]=t,ne[pre]=idx++; }}
1.dfs1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <iostream>#include <cstring>using namespace std;const int N=1e5+10;int h[N],e[N],ne[N],idx;int n;bool st[N];void add(int a,int b) ...