6、岛屿个数
#include <bits/stdc++.h>using namespace std;const int M=51;int T,m,n;int vis[M][M],used[M][M];int dx[]={1,-1,0,0,1,1,-1,-1};int dy[]={0,0,1,-1,1,-1,1,-1};string mp[M];struct node{//记录一点坐标 int x,y;};void bfs_col(int x,int y){ queue<node>q; q.push({x,y});vis[x][y]=1; while(q.size()){ auto u=q.front(); q.pop(); for(int i=0;i<4;i++){//搜索岛屿只有四个方向 int a=u.x+dx[i]; int b=u.y+dy[i]; if(a<0||b<0||a>m-1||b>n-1||vis[a][b]==1||mp[u.x][u.y]=='0')continue; q.push({a,b});vis[a][b]=1;//打上标记判重 } }}bool bfs_edge(int x,int y){ for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ used[i][j]=0;//初始化 } } queue<node>q; q.push({x,y});used[x][y]=1; while(q.size()){ auto t=q.front(); q.pop(); //能走到边界了说明不是子岛屿 if(t.x==0||t.x==m-1||t.y==0||t.y==n-1)return true; for(int i=0;i<8;i++){//判断是否到边界有八方向 int a=t.x+dx[i]; int b=t.y+dy[i]; if(a<0||b<0||a>m-1||b>n-1||used[a][b]==1||mp[a][b]=='1') continue; q.push({a,b});used[a][b]=1; } } return false;}void solve(){ int ans=0; cin>>m>>n; for(int i=0;i<m;i++){ cin>>mp[i]; for(int j=0;j<n;j++){ vis[i][j]=0;//初始化为0 } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(!vis[i][j]&&mp[i][j]=='1'){ bfs_col(i,j);//搜索每"一块"岛屿 if(bfs_edge(i,j))ans++; } } } cout<<ans<<'\n';}int main(){ios::sync_with_stdio(0);cin.tie(0); int T; cin>>T; while(T--)solve(); return 0;}7、字串简写
#include <bits/stdc++.h>using namespace std;int k;string s;char c1,c2;long long ans,sum_c1;int main(){cin>>k;cin>>s>>c1>>c2;//以c2为窗口的尾巴,找到所有距离大于等于k的c1,把所有满足条件的c1数加起来 for(int i=k-1,j=0;i<s.length();i++,j++){//i,j同时移动,形成滑动窗口 if(s[j]==c1)sum_c1++;//找到头,c1数加一 if(s[i]==c2)ans+=sum_c1;//找到尾巴了,累加答案数 }cout<<ans;return 0;}8、整数删除
#include <bits/stdc++.h>using namespace std;#define int long long const int N = 5e5 + 10;int n, k;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;//优先队列维护最小值int pre[N], ne[N];//维护左边元素和右边元素的下标的下标int cnt[N], a[N], tmp;//cnt代表下标为i的元素需要修改的值signed main(){ cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> tmp; q.push(make_pair(tmp, i)); pre[i] = i - 1;//下标为i的元素的左边元素的下标为i-1 ne[i] = i + 1;//下标为i的元素的右边的元素的下标为i+1 } while (q.size() > n - k) {//查找k次 int num = q.top().first;//获取最小值 int id = q.top().second;//获取最小值的下标 q.pop(); /*这里cnt非0，说明在前面的操作过程中，该元素已经进行修改了，但是队列中还没有更新 现在对队列的这个值进行修正，修正后重新查找最小值*/ if (cnt[id]) { q.push({ num + cnt[id],id }); cnt[id] = 0; } else { int left = pre[id]; int right = ne[id]; cnt[left] += num;//对左边的值进行修改 cnt[right] += num;//对右边的值进行修改 //将该元素在双向链表中删除 ne[left] = right; pre[right] = left; } } while (!q.empty()) { int num = q.top().first; int id = q.top().second; q.pop(); a[id] = num + cnt[id]; } for (int i = 1; i <= n; i++) { if (a[i]) { cout << a[i] << " "; } } return 0;}
