1代表空地 0代表阻挡物 3代表出口 4代表补给站 问最短路径 因为可以重复走 为了防止超时 要用一个use数组 要是当前的时间比use数组的大 更新use数组的值 相当于剪枝 AC代码： #include<stdio.h> #include<queue> #include<string.h> using namespace std; struct node{  int x; int y; int time; int step; }; int flag; int use[10][10]; int way[4][2]={ 0,1,0,-1,1,0,-1,0};...

题目来源：点这里 题目大致意思就是切木头要付出代价，求最小代价。（贪心） 这里考到了二叉数的知识，要领：最小的数和次小的数是兄弟节点。 AC代码： #include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; ll l[200005]; int main() {  int n; ll ans=0; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&l[i]); w...

背包问题： 每个物品w千克 v个价值 要想在输入的we限定重量内 价值最高。 AC代码： #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[1000][1000]; int we; int v[1000]; int wm[1000]; int n; int res; int rec(int i,int w) {  if(dp[i][w]>=0)//剪枝 把走过的记录下来 return dp[i][w]; if(i==n) { res=...

例如串1ABCE 串2为BCDE 那么他们公共子串就是BCE 这里要用到动态规划dp 思路：dp[i][j]指的是字符串s1和s2的最长公共子序列 要求它的下一个i+1 j+1时候的状态要分情况讨论： 情况1：如果他们末尾的字母相等，那么该字母肯定是子序列中的一个dp[i][j]+1就行。 情况2：如果不相等，就要取串1i+1和串2j的最大公共子序列和串i和串2j+1的公共子序列 这两个的最优解，这里的最优解指的是最长子序列。 AC代码： #include<stdio.h> #include<algorithm> #include<string.h> usi...

高精度加法 // C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &A, vector<int> &B) {  if (A.size() < B.size()) return add(B, A); vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ) {  t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10...

快排模板`` #include<iostream> using namespace std; void quick_sort(int l,int r,int q[]) {  if(l>=r) return ; int x=q[l+r>>1],i=l-1,j=r+1; while(i<j) {  do i++; while(x>q[i]); //不用do while 语句会死循环。 do j--; while(x<q[j]); if(i<j) swap(q[i],q[j]); } quick_sort(l,j,q); quick_sort(j...

纯暴力写for(i=0;i<n;i++) for(j=0;j<n;j++) 暴力搜 优化代码如下： #include<iostream> #include<algorithm> using namespace std; int a[1000005]; int s[1000005]; int main() {  int i,j; int n; int res=0; scanf("%d",&n); for(i=0;i<n;i++) {  scanf("%d",&a[i]); } for(i=0,j=0...

题目 给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。 输入格式 第一行包含整数N，表示数列长度。 第二行包含N个整数，表示整数数列。 输出格式 共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。 数据范围 1≤N≤1051≤N≤105 1≤数列中元素≤1091≤数列中元素≤109 输入样例： 5 3 4 2 7 5 输出样例： -1 3 -1 2 2 如果当前输入的x小于等于栈顶，那么x是更优解，退栈顶，直到比x小的数，那么输出栈顶就行了，最后把x加进去。 #include<iostream> using...

原题点这里 代码如下 #include<iostream> using namespace std; const int N=100010; int ne[N],e[N],head,idx; void init() {  idx=0; head=-1; } void dele(int k) {  ne[k]=ne[ne[k]]; } void add_to_head(int x) {  e[idx]=x; ne[idx]=head; head=idx; idx++; } void add(int k,int x) {  e[idx]=x; ne[idx]=ne[k]; ne[k]=...

题目在这里 ’代码如下： #include<iostream> using namespace std; const int N=100010; int l[N],r[N],idx,e[N]; void init () {  idx=2; r[0]=1; l[1]=0; } void dele(int k) {  l[r[k]]=l[k]; r[l[k]]=r[k]; } void add(int k,int x) {  e[idx]=x; l[r[k]]=idx; r[idx]=r[k]; l[idx]=k; r[k]=idx; idx++; } int main() {  in...

题目 代码如下： #include<iostream> using namespace std; const int N=1000010; int a[N],q[N]; int main() {  int hh=0,tt=-1; int n,k; cin>>n>>k; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) {  if(hh<=tt&&i-k+1>q[hh]) hh++;//判断队首是否已退队 while(hh<=tt&&amp...

题目在这~ 思路就是求出最小模板链的移动，求出模板链最大的相等前后缀字符串。 #include<iostream> using namespace std; const int N=1000010; char p[N],s[N]; int ne[N]; int main() {  int n; int m; scanf("%d",&n); cin>>p+1;//注意下标从1开始 cin>>m; cin>>s+1; for(int i=2,j=0;i<=n;i++)//i不用从1开始因为ne[1]=0 {  whi...

题目点这里 要注意，输出的是最大的能通过的货物重量，只需要在原来最短路代码上修改一下就可。 #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int N=2010; int d[N],g[N][N]; bool vis[N]; int n,m; int h; int v; void djs() {  for(int i=1;i<=n;i++) { d[i]=g[1][i]; } for(int i=1;i<=n;i++) {  ...

题目大致意思就是1想见2，它可以通过石头来中转，让路径中每次跳的最大距离最小。输出极限距离。 AC代码： #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; const int N=1010; double d[N],w[N][N]; bool vis[N]; int n; struct node{  double x; double y; }now[N];...