1.栈
- 栈是一种基本数据结构。
- 栈是一种操作受到限制的线性表：只能在一端进行读写操作，这一端称为栈顶
-栈的基本操作：
1.定义：stack 栈名(q)
2.压栈（入栈） q.push(x);
3.z出栈：q.pop();
4.读取栈顶： q.top();
5.判断栈是否为空： q.empty() - 栈与队列的区别：栈是先进后出，队列是先进先出
如下图：
例题1：程序员的输入问题(t1.*)
#include
using namespace std;
string a;
char ai[1100];
int main()
{
freopen("t1.in","r",stdin);
freopen("t1.out","w",stdout);
while(getline(cin,a))
{
stack s;
int len=a.size();
for(int i=0;i=1;i--) cout<<ai[i];
cout<<endl;
}
return 0;
}
例题2：括号的匹配(t2.*)
#include
using namespace std;
string a;
stack s;
int main()
{
freopen("t2.in","r",stdin);
freopen("t2.out","w",stdout);
getline(cin,a);
int len=a.size();
for(int i=0;i<len;i++)
{
if(a[i]=='(') s.push(a[i]);
else if(a[i]==')')
{
if(!s.empty()) s.pop();
else
{
cout<<"NO"<<endl;
return 0;
}
}
}
if(!s.empty()) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
return 0;
}
至于为什么没有例三，是因为例三我用栈打炸了…………
例4、表达式求值(noip2013，expr)
#include
using namespace std;
int m=10000;
char a;
int b,c;
stack s;
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>c;
c%=m;
s.push(c);
while(cin>>a>>b)//a-符号,b-字母
{
if(a=='*')
{
c=s.top();
s.pop();
s.push(c*b%m);
}
else s.push(b);
}
int sum=0;
while(s.size())
{
sum+=s.top();
sum%=m;
s.pop();
}
cout<<sum<<endl;
return 0;
}
2.深度优先搜索（DFS）
- 深度优先搜索（Depth First Search，简写DFS），简
称深搜，其状态“退回一步”的顺序符合“后进先
出”的特点，所以采用“栈”存储状态。深搜的空
间复杂度较小，因为它只存储了从初始状态到当前
状态的一条搜索路径。但是，深搜找到的第一个解
不一定是最优解，要找最优解必须搜索整棵“搜索
树”。所以，深搜适用于要求所有解方案的题目。
因为很早以前就学过了，所以就不在此解释
例题1：体积
#include
using namespace std;
int n,v[30],hash[1001];
//v表示目前方案的体积和 ,hash表示体积I是否出现过
void dfs(int cs,int sum)//cs表示层数，sum为体积和
{
if(cs>n)
{
hash[sum]=1;
return;
}
dfs(cs+1,sum+v[cs]);
dfs(cs+1,sum);
}
int main()
{
freopen("volume.in","r",stdin);
freopen("volume.out","w",stdout);
cin>>n;
for(int i=1;i>v[i];
dfs(1,0);
int ans=0;
for(int i=1;i<=1000;i++)
{
if(hash[i]==1) ans++;
}
cout<<ans;
return 0;
}
2.瓷砖
#include
using namespace std;
int n,m,x,y,sum;
char a[55][55];
int xi[5]={0,1,-1,0,0};
int yi[5]={0,0,0,1,-1};
void dfs(int x,int y)
{
a[x][y]='#';
sum++;
for(int i=1;i=1 && new_x=1 && new_y>n>>m;
if(n==0 && m==0) break;
for(int i=1;i<=m;i++)
{
for(int j=1;j>a[i][j];
if(a[i][j]=='@') x=i,y=j;
}
}
dfs(x,y);
cout<<sum<<endl;
}
return 0;
}
3.最大黑区域
#include
using namespace std;
int n,m,a[110][110],ans,maxn;
int xi[5]={0,0,0,1,-1};
int yi[5]={0,1,-1,0,0};
void dfs(int x,int y)
{
ans++;
a[x][y]=0;
for(int i=1;i>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j>a[i][j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==1)
{
ans=0;
dfs(i,j);
maxn=max(maxn,ans);
}
}
}
cout<<maxn;
return 0;
}
4.数的划分
#include
using namespace std;
int n,rest,s[25],sum;
void dfs(int dep,int rest)
{
if(rest==0 && dep>1)
{
sum++;
for(int i=1;i<dep-1;i++) cout<<s[i]<<"+";
cout<<s[dep-1]<<endl;
}
else
{
for(int i=s[dep-1];i>n;
s[0]=1;
dfs(1,n);
cout<<"total="<<sum;
return 0;
}
5.01背包（dfs做法
#include
using namespace std;
int k,s,w[110],b[110],f;
void dfs(int cs,int x,int sum)
{
if(sum==s)
{
for(int i=1;i<=x;i++) cout<<b[i]<<" ";
cout<s) return;
else if(cs>k) return;
else
{
b[x+1]=w[cs];
dfs(cs+1,x+1,sum+w[cs]);
dfs(cs+1,x,sum);
}
}
int main()
{
freopen("pack.in","r",stdin);
freopen("pack.out","w",stdout);
cin>>k>>s;
for(int i=1;i>w[i];
dfs(1,0,0);
if(f==0) cout<<"No Answer！";
return 0;
}
今天就这么愉快的结束了
then就没有then了
I had hotpot today and was late
(真服了)
S组昨天的第一题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 998244353;
int T,n;
char s[N];
ll b2[N],b3[N];
void prepare(){
b2[0]=b3[0]=1;
for(int i=1;i<N;++i){
b2[i]=b2[i-1]*2%mod;
b3[i]=b3[i-1]*3%mod;
}
}
int main(){
freopen("binary.in","r",stdin);
freopen("binary.out","w",stdout);
prepare();
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
n=strlen(s+1);
ll ans=0;
for(int i=1;i<=n;++i)
if(s[i]=='1')
{
(ans+=b2[i-1]*b3[n-i]%mod)%=mod;
}
printf("%lld\n",ans);
}
}