S+测试
A. 沙漠化
其实不需要BFS,只需要 $O(n^2)$ 枚举每个目前为 D 的格子，向四个方向扩展。
这里有一个点，就是扩展时最好扩展成 d ,这样就可以在当前时间点不去扩展这个点，在所有点都遍历过后再将 d 转换为D。所以在扩展时要记得判断，如果这个点本来就是 D 就不去扩展。
然后因为 $T\le 10^9$ 所以有一个优化，每次遍历时记录遍历到的 D 点，如果总数 $=0$ 或者等于整个地图大小，就直接退出。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
char mp[15][15];
int n,t;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>mp[i];
int nl=(int)strlen(mp[1]);
cin>>t;
while (t--) {
int dnum=0;
for (int i=1;i<=n;i++) {
for (int j=0;j<nl;j++) {
if (mp[i][j]=='D') {
dnum++;
if (mp[i-1][j]!='D') mp[i-1][j]='d';
if (mp[i+1][j]!='D') mp[i+1][j]='d';
if (mp[i][j-1]!='D') mp[i][j-1]='d';
if (mp[i][j+1]!='D') mp[i][j+1]='d';
}
}
}
for (int i=1;i<=n;i++) {
for (int j=0;j<nl;j++) {
if (mp[i][j]=='d') mp[i][j]='D';
}
}
if (dnum==0||dnum==n*nl) break;
}
int ans=0;
for(int i=1;i<=n;i++) {
for (int j=0;j<nl;j++) {
if (mp[i][j]=='D'||mp[i][j]=='d') ans++;
}
}
cout<<ans<<endl;
return 0;
}B. 筒装球
还是挺简单的~
用一个栈维护序列，元素是连续的值和这个值的个数。
每次输入一个新值，取出栈顶，如果相同且数量 $+1$ 后不超过值，就让数量 $+1$ 后回栈，否则直接清空；如果不同，新开一个元素存储。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+10;
int ans=0,n,a[N];
struct ball {
int vl,num;
};
stack<ball> st;
signed main(){
Cios;
cin>>n;
st.push({0,0});
for(int i=1;i<=n;i++) {
cin>>a[i];
ball b=st.top();
if (b.vl==a[i]) {
st.pop();
ans-=b.num;
if (b.num+1!=b.vl) {
ans+=b.num+1;
st.push({b.vl,b.num+1});
}
}
else {
ans++;
st.push({a[i],1});
}
cout<<ans<<endl;
}
return 0;
}
评论（0）
暂无评论