复杂问题的小整理

复杂问题的小整理

P2670 扫雷游戏
1.设立两个数组，遇到*，就把他八方的+1
2.然后输出，不是*的就输出数字好了

#include<bits/stdc++.h>
using namespace std;
int main()
{   int b[105][105]={0};
char a[105][105];int m,n;cin>>m>>n;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];if(a[i][j]=='*'){b[i][j+1]++;b[i][j-1]++;b[i+1][j]++;b[i+1][j-1]++;b[i+1][j+1]++;b[i-1][j]++;b[i-1][j+1]++;b[i-1][j-1]++;}}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(a[i][j]=='*')cout<<'*';elsecout<<b[i][j];}cout<<endl;}} 

dsp想法
1.dx，dy对应八个方向
2.dsp 其实就是把周围的数在没有越界条件下都加上1
3.是地雷就调用它

#include<bits/stdc++.h>
using namespace std;
char a[101][101];//地图
int b[101][101]={0};//答案
int n,m,i,j;
int dx[8]={1,0,-1,0,-1,1,1,-1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
void dsp(int x,int y)
{
int nx,ny,k;
for(k=0;k<8;k++)
{
nx=x+dx[k];
ny=y+dy[k];
if(nx>1&&nx<=n&&ny>=1&&ny<=m)
b[nx][ny]++;
}
}
int main()
{cin>>n>>m;//输入for (i=1;i<=n;i++)for (j=1;j<=m;j++){cin>>a[i][j];if (a[i][j]=='*')dfs(i,j);//如果是地雷就调用函数}for (i=1;i<=n;i++){for (j=1;j<=m;j++)if (a[i][j]=='*')//判断是地雷就直接输出cout<<a[i][j];elsecout<<b[i][j];//不是地雷输出答案cout<<endl;}return 0;
}

P1601 高精度A+B
孩子永远讨厌高精度
1.输入两个字符串型的数字
2.算出长度
3.摆放到另外一个int型数组中，数组里每个数就是一位，倒序
4.找到和的位数，然后加一加各位
5.前导0记得，倒序输出

#include<bits/stdc++.h>
using namespace std;
int main()
{char a[505]={0},b[505]={0};int la,lb,x[550]={0},y[505]={0},lh,ans[550]={0};cin>>a>>b;la=strlen(a);lb=strlen(b);for(int i=0;i<la;i++){x[la-i]=a[i]-'0';}for(int i=0;i<lb;i++){y[lb-i]=b[i]-'0'; }lh=max(la,lb)+1;for(int i=1;i<=lh;i++){ans[i]+=x[i]+y[i];ans[i+1]=ans[i]/10;ans[i]=ans[i]%10;}if(ans[lh]==0&&lh>0)lh--;for(int i=lh;i>0;i--){cout<<ans[i];}  return 0;} 

P1177 快速排序
我以为我会了
1.最左端，最右端进入
2.记录下这两个，变成两个指针
3.不断比较
4.交换，继续推进
5.继续排左边右边

#include<bits/stdc++.h>using namespace std;int n,a[1000002];void qsort(int left,int right){int i=left,j=right;int mid=a[(left+right)/2];while(i<=j){if(a[i]<mid){i++;continue;}if(a[j]>mid){j--; continue;}if(i<=j){swap(a[i],a[j]);i++;j--;}}if(left<j) qsort(left,j);if(i<right) qsort(i,right);}int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];qsort(1,n);for(int i=1;i<=n;i++)cout<<a[i]<<" ";} 

P1923 求第k小的数
1.stl
nth_element(a+x,a+x+y,a+x+len);
执行之后数组 a下标 x 到 x+y-1 的元素都小于 a[x+y]，下标 x+y+1 到 x+len-1的元素 都大于 a[x+y]，但不保证数组有序。此时 a[x+y] 就是数组区间 x 到 x+len-1 中第 y 小的数，当然也可以自己定义 cmp函数。

#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&x[i]);nth_element(x,x+k,x+n);printf("%d",x[k]);
}

2.二分的思想（quicksort）

#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
void qsort(int l,int r)
{int i=l,j=r,mid=x[(l+r)/2];do{while(x[j]>mid)j--;while(x[i]<mid)i++;if(i<=j){swap(x[i],x[j]);i++;j--;}}while(i<=j);//快排后数组被划分为三块： l<=j<=i<=rif(k<=j) qsort(l,j);//在左区间只需要搜左区间else if(i<=k) qsort(i,r);//在右区间只需要搜右区间else //如果在中间区间直接输出{printf("%d",x[j+1]);exit(0);}
}
int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&x[i]);qsort(0,n-1);
}

P1036选数
主要是想怎么做到全排序：这里是利用循环+不断递归（递归里面再次循环）

#include<bits/stdc++.h> 
using namespace std;
long long int ans=0,a[299]={0},z,g;
bool sushu(int a)
{ if((a==1)||(a==0) )return 0;//1不是质数 for(int i=2;i<=sqrt(a);i++){if(a%i==0)return 0;else continue;}return 1;}void paixu(int st,int ge,int sum)
{if(ge==g){ if(susuh(sum)）ans++;return ;}for(int i=st;i<z;i++){paixu(i+1;ge+1;sum+a[i];}return ;}int main()
{cin>>z>>g;for(int i=0;i<z;i++){cin>>a[i];}paixu(0,0,0);cout<<ans<<endl;return 0;
}

P1706 全排序
1.深搜的边界条件：k==n;
2.1-n循环搜数
3.当前数字没有被使用过，标记他使用过了，然后填入数组(这个很秒，为了让下面的好递归）
4.继续深搜
5.记得要把标记取消掉，方便下一次循环搜数

void dfs(int k)
{int i;if(k==n){print();return;}for(int i=1;i<=n;i++){if(!pd[i]){pd[i]=1;used[k+1]=i;dst(k+1);pd[i]=0;}}}

全排列函数 next_permutation
函数每运行一次就可以把数组排成下一个字典排数

#include<iostream>//P1706
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include <algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
int a[10];
int main()
{int n,i,j=1,k;cin>>n;for(i=1;i<=n;i++){a[i]=n-i+1;j*=i;}//题目好像没说要从小到大输出//但保险起见还是初始赋值为最大序列//即a[1~n]=n~1;顺便计算n!for(i=1;i<=j;i++){next_permutation(a+1,a+n+1);for(k=1;k<=n;k++)cout<<"    "<<a[k];//排一次输出一次//空格建议复制cout<<endl;}return 0;
}

P1255数楼梯
1.递归人开心得太早，他还有高精度
2.f[k][i] 用来存储走k个阶梯所用的步数走法
f[k][i]=f[k-1]f[i]+f[k-2]f[i];对于每一位
再次循环，该进位的进位
if(f[k][len+1])len++;就是说个位大于10了才有下一位

void jia(int k)
{
for(int i=1;i<=len;i++)
f[k][i]=f[k-1][i]+f[k-2][i];
for(int i=1;i<=len;i++)
if(f[k][i]>10)
{
f[k][i+1]+=f[k][i]/10;
f[k][i]=f[k][i]%10;
if(f[k][len+1])len++;
}int main()
{
int n;
cin>>n;
f[1][1]=1;
f[2][1]=2;
for(int i=3;i<=n;i++)
jia(i);
for(int i=len,i>=1;i--)
cout<<f[n][i];}

P1449后缀表达式
1.遇到数字就入栈，遇到符号调用前面两个
2.他是有.来表示一个数字结束，所以还要有字符串转换为数字的意识 遇到.的时候将它入栈；
3.遇到符号的时候，栈得倒数第二想重新赋值，然后把站的数量减去一个（数组实现）

#include<bits/stdc++.h>
using namespace std;
int main()
{   long long int zhan[100000]; int num=0,i=0;char str;while((str=getchar())!='@'){if(str>='0'&&str<='9'){num*=10;num+=str-'0';}if(str=='.'){	zhan[++i]=num;num=0;}if(str=='+'){zhan[i-1]=zhan[i-1]+zhan[i];zhan[i]=0;i--;}if(str=='-'){zhan[i-1]=zhan[i-1]-zhan[i];zhan[i]=0;i--;}if(str=='*'){zhan[i-1]=zhan[i-1]*zhan[i];zhan[i]=0;i--;}if(str=='/'){zhan[i-1]=zhan[i-1]/zhan[i];zhan[i]=0;i--;}}cout<<zhan[1];return 0; 
}

直接利用stl的栈
1.出栈两个，两个相加在入栈
2.入栈，到.入栈s

#include <bits/stdc++.h>
using namespace std;
stack<int> n;
char ch;
int s,x,y;
int main()
{while(ch!='@'){ch=getchar();switch(ch){case '+':x=n.top();n.pop();y=n.top();n.pop();n.push(x+y);break;case '-':x=n.top();n.pop();y=n.top();n.pop();n.push(y-x);break;case '*':x=n.top();n.pop();y=n.top();n.pop();n.push(x*y);break;case '/':x=n.top();n.pop();y=n.top();n.pop();n.push(y/x);break;case '.':n.push(s);s=0;break;default :s=s*10+ch-'0';break;}}printf("%d\n",n.top());return 0;
}

P1996约瑟夫问题
1.用队列去写，每次都加1，到那个数的人出队列，其他的人拍到队伍后面

{
queue<int> q;
int n,m,e=1;
for(int i=1;i<=n;i++)
{
q.push(i);
}
while(!q.empty())
{
if(e==m)
{
cout<<q.front()<<" " :
q.pop();
e=1;
}
else
{
e++;
q.push(q.front())
q.pop();
}

数组模拟链表

#include<iostream>
using namespace std;
int next[1000005];
int main(){int n,m;cin>>n>>m;//输入n、mfor(int i=0;i<n;i++)//初始化next[i]=i+1;next[n]=1;int p=0;for(int i=1;i<=n;i++){//开始模拟出圈过程for(int j=1;j<m;j++)p=next[p];//p位置右移cout<<p[next]<<" ";//输出出圈人的位置next[p]=next[next[p]];//删掉出圈人}return 0;//功德圆满
}

n次出圈，所以有个n循环
m此为一个小循环，删掉一个，输出一个
数组代替了链表

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int m,n;
struct Node{int data;Node*next;
}*head,*p,*tail,*temp; 
int main()
{cin>>m>>n;head=new Node;head->next=NULL;tail=head;for(int i=1;i<=m;i++){p=new Node;p->data=i;p->next=NULL;tail->next=p;tail=p;} p=head->next;tail->next=head->next;for(int i=1;i<=m;i++){for(int j=1;j<n-1;j++){p=p->next;}printf("%d",p->next->data);temp=p->next;p->next=temp->next;p=p->next;//更新p free(temp);}return 0;} 

标准的链表：头结点，尾节点，要删除的，临时
建立链表，不断增加节点 new，data和next要写出来
最后做到头尾相连（有点迷惑，要复习循环链表了
最后两次循环
删除出去的，保存，指针的转移，更新p本身，free

P1241括号序列

 #include<stdio.h>
#include<string.h>
struct node
{char a;int m;
}kuo[110];
bool b[110];
int main()
{char str1[110];scanf("%s",str1);memset(b,0,sizeof(b));int top=0;int len=strlen(str1);for(int i=0;i<len;i++){if((str1[i]=='(')||(str1[i]=='[')){kuo[top].a=str1[i];kuo[top].m=i;top++;}if((str1[i]==')')&&(kuo[top-1].a=='(')) {b[i]=1;b[kuo[top-1].m]=1;top--;}if((str1[i]==']')&&(kuo[top-1].a=='[')) {b[i]=1;b[kuo[top-1].m]=1;top--;}}for(int i=0;i<len;i++){if(b[i]==1) printf("%s",str1[i]);else{if ((str1[i]=='(')||(str1[i]==')')) printf("()");if ((str1[i]=='[')||(str1[i]==']')) printf("[]");}}return 0;} 

P1030 求先序排列
1.先序排列，后续排列，中序排列是有一定规律顺序的
2.根据后续排列确定节点，然后到中序排列里面划分左右子树，写出find
3，每次输出被找到的那个根节点，递归左右子树，（l1，l2，r1，r2)，这些的个数是改变的

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s1[10];
char s2[10];
int len;
inline int find(char ch)
{for(int i=0;i<len;i++){if(s1[i]==ch) return i;}
}
void dfs(int l1,int r1,int l2,int r2)
{int m=find(s2[r2]);cout<<s2[r2];if(m>l1) dfs(l1,m-1,l2,r2-r1+m-1);//第二个是节点个数 具有左子树，遍历左子树if(m<r1) dfs(m+1,r1,l2+m-l1,r2-1);
}
int main()
{cin>>s1;cin>>s2;len=strlen(s1);dfs(0,len-1,0,len-1);
}

自己构造出一棵树，然后中序遍历它

#include<iostream>
#include<cstring>using namespace std;char pre[10];//后序遍历
char mid[10];//前序遍历
int num[300];//字母对应的数字
char let[10];//数字对应的字母struct node//结点
{int key;node * p=NULL;//父节点node * left=NULL;//左子node * right=NULL;//右子
};
typedef struct node * bNode;//结点指针bNode tree_insert(bNode tree_root,int nkey)//二叉搜索树插入函数
{bNode z=new node,y=NULL,x=tree_root;z->key=nkey;while(x!=NULL){y=x;if(nkey<x->key)x=x->left;else x=x->right;}z->p=y;if(y==NULL)tree_root=z;else if(nkey<y->key)y->left=z;else y->right=z;return tree_root;
}void tree_preorder(bNode k)//前序遍历输出
{if(k==NULL)return;cout<<let[k->key];//key对应的字母tree_preorder(k->left);tree_preorder(k->right);
}int main()
{bNode t1=NULL;cin>>mid>>pre;for(int i=0;mid[i]!='\0';i++)//建立字母与标号的双向联系{num[mid[i]]=i;let[i]=mid[i];}for(int i=strlen(pre)-1;i>=0;i--)//按颠倒顺序插入{t1=tree_insert(t1,num[pre[i]]);}tree_preorder(t1);return 0;
}

看不懂