ABC351

C 栈的应用

#include<bits/stdc++.h>using namespace std;stack<int>stk;int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int a;cin>>a;while(!stk.empty()&&a==stk.top()){stk.pop();a++;}stk.push(a);}cout<<stk.size()<<endl;return 0;
}
//每次操作序列最右边的两个球，不难想到可以使用栈来进行维护。为了便于处理，
//每次操作不将数字放入栈后再进行判断，直接拿该球与栈顶元素比较，如果相同就删除栈顶元素，并增加小球大小，
//直到栈空或栈顶元素与当前小球大小不同，然后将小球放入栈中。结束操作后，栈中元素数量即为最后的答案。

D BFS加set

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include<queue>
#define x first
#define y secondusing namespace std;const int N = 1e3+10;
typedef pair<int, int> PII;char c[N][N];
int n,m,ans=0;
int dp[N][N],vis[N][N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};queue<PII>Q;
set<PII>V;
set<PII>S;bool check(int x,int y)
{for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(c[a][b]=='#')return 0;}return 1;
}void bfs(int x,int y)
{V.clear();S.clear();Q.push({x,y});vis[x][y]=1;while(!Q.empty()){auto t=Q.front();Q.pop();V.insert(t);for(int i=0;i<4;i++){int a=t.x+dx[i],b=t.y+dy[i];if(a>=1&&b>=1&&a<=n&&b<=m&&check(a,b)&&vis[a][b]==0){vis[a][b]=1;Q.push({a,b});}}}for(auto man:V){for(int i=0;i<4;i++){int a=man.x+dx[i],b=man.y+dy[i];if(c[a][b]=='.'&&vis[a][b]==0){S.insert({a,b});}}}int size=V.size()+S.size();ans=max(ans,size);
}void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>c[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(vis[i][j]==0&&c[i][j]=='.'){ans=max(ans,1);if(check(i,j))bfs(i,j);}}cout<<ans<<endl;
}int main()
{solve();return 0;
}