暑假刷题第20天--8/3

B-序列的与和_2023河南萌新联赛第（四）场：河南大学 (nowcoder.com)（dfs）

#include<iostream>
#include<string>
using namespace std;
#define ull unsigned long long
int n,k;
ull a[21];
ull ans=0;
int check(ull sum){int q=0;while(sum){q++;sum&=(sum-1);}return q;
}
void dfs(int x,ull sum){if(check(sum)==k)ans++;for(int i=x+1;i<=n;i++){dfs(i,sum&a[i]);}
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){dfs(i,a[i]);}cout<<ans<<endl;
}

D-幂运算_2023河南萌新联赛第（四）场：河南大学 (nowcoder.com)(快速幂类似)

#include<iostream>
#include<string>
using namespace std;
long long qowe(long long a,long long n,long long p){//指数幂long long ans=2;while(n){ans=(long long)ans*ans%p;a=(long long)a*a%p;n=n-1;}return ans;
}
int main(){int n,k;cin>>n>>k;cout<<qowe(2,n,k);
}

P4554 小明的游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)(双端队列bfs--模板)

#include<iostream>
#include<string>
#include<vector>
#include<deque>
#include<cstring>
using namespace std;
int n,m;
struct node{int xx,yy,step;
};
string s[505];
int x1,y1,a,b;
bool vis[505][505];
int cnt[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int in(int x,int y){if(x<0||y<0||x>=n||y>=m)return 0;return 1;
}
int bfs(int x,int y){node c;c.xx=x,c.yy=y,c.step=0;deque<node>q;q.push_front(c);while(!q.empty()){node temp=q.front();q.pop_front();node now;vis[temp.xx][temp.yy]=true;if(temp.xx==a&&temp.yy==b)return temp.step;for(int i=0;i<4;i++){now.xx=temp.xx+cnt[i][0];now.yy=temp.yy+cnt[i][1];if(!vis[now.xx][now.yy]&&in(now.xx,now.yy)&&s[temp.xx][temp.yy]==s[now.xx][now.yy]){now.step=temp.step;q.push_front(now);}else if(!vis[now.xx][now.yy]&&in(now.xx,now.yy)&&s[temp.xx][temp.yy]!=s[now.xx][now.yy]){now.step=temp.step+1;q.push_back(now);}}}return 0;
}
int main(){while(cin>>n>>m&&(n||m)){for(int i=0;i<n;i++){cin>>s[i];}cin>>x1>>y1>>a>>b;memset(vis,0,sizeof(vis));cout<<bfs(x1,y1)<<"\n";}
}

Labyrinth - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)(双端队列bfs)

#include<iostream>
#include<string>
#include<vector>
#include<deque>
#include<cstring>
#include<queue>
using namespace std;
const int N=2005;
int n,m;
struct node{int xx,yy,step1,step2;
};
string s[N];
int x1,y1,a,b;
bool vis[N][N];
int cnt[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
int ans=1;
int in(int x,int y){if(x<0||y<0||x>=n||y>=m)return 0;return 1;
}
int bfs(int x,int y){node c;c.xx=x,c.yy=y,c.step1=0,c.step2=0;deque<node>q;q.push_front(c);vis[x][y]=true;while(!q.empty()){node temp=q.front();q.pop_front();node now;for(int i=0;i<4;i++){now.xx=temp.xx+cnt[i][0];now.yy=temp.yy+cnt[i][1];if(!in(now.xx,now.yy)||vis[now.xx][now.yy]||s[now.xx][now.yy]=='*')continue;if(i==0||i==1){now.step1=temp.step1;now.step2=temp.step2;q.push_front(now);vis[now.xx][now.yy]=true;ans++;}else if(i==2){if(temp.step1>=a)continue;now.step1=temp.step1+1;now.step2=temp.step2;q.push_back(now);vis[now.xx][now.yy]=true;ans++;}else if(i==3){if(temp.step2>=b)continue;now.step1=temp.step1;now.step2=temp.step2+1;q.push_back(now);vis[now.xx][now.yy]=true;ans++;}}}return 0;
}
int main(){cin>>n>>m;cin>>x1>>y1>>a>>b;for(int i=0;i<n;i++){cin>>s[i];}bfs(x1-1,y1-1);cout<<ans<<"\n";
}

175. 电路维修 - AcWing题库(双端队列bfs)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <deque>
using namespace std;
typedef pair<int, int > PII;
int n, m;
const int N = 510;
char g[N][N];
int d[N][N];
inline bool check(int x, int y)
{if(x >= 0 && x <= n && y >= 0 && y <= m) return true;return false;
}
inline int bfs()
{memset(d, 0x3f, sizeof d);deque<PII> dq;dq.push_front({0, 0});d[0][0] = 0;int moved[4][2] = {{-1, -1},{-1, 1},{1, 1},{1, -1}};int movei[4][2] = {{-1, -1},{-1, 0},{0, 0},{0, -1},};char cp[] = "\\/\\/";while(dq.size()){auto t = dq.front();dq.pop_front();int x = t.first, y = t.second;for(int i = 0; i < 4; i ++){int a = x + moved[i][0], b = y + moved[i][1];if(check(a, b)){int j = x + movei[i][0], k = y + movei[i][1];int w;if(g[j][k] != cp[i]) w = 1;else w = 0;if(d[a][b] > d[x][y] + w){d[a][b] = d[x][y] + w;if(w) dq.push_back({a, b});else dq.push_front({a, b});}}}}if(d[n][m] == 0x3f3f3f3f) return -1;else return d[n][m];
}inline void solve()
{cin >> n >> m;for(int i = 0; i < n; i ++) cin >> g[i];int res = bfs();if(res == -1) puts("NO SOLUTION");else cout << res << endl;
}
int main()
{int t;cin >> t;while( t -- ) solve();return 0;
}