暑假刷题第19天--8/1

170. 加成序列 - AcWing题库（dfs+迭代加深--重点理解）

#include<iostream>
using namespace std;
int n;
int a[11];
int dfs(int x,int h){if(x>h+1)return 0;if(a[x-1]==n)return 1;bool st[130]={};for(int i=1;i<=x-1;i++){for(int j=1;j<=i;j++){int sum=a[i]+a[j];if(sum>n||sum<=a[x-1]||st[sum])continue;st[sum]=true;a[x]=sum;if(dfs(x+1,h))return 1;}}return 0;
}
int main(){a[1]=1;while(cin>>n&&n){vis[1]=true;a[1]=1;int p=1;while(!dfs(2,p)){p++;}for(int i=1;i<=p;i++){cout<<a[i]<<' ';}cout<<endl;}
} 

171. 送礼物 - AcWing题库（双向搜索--重点理解）

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define int long long
int n,w;
int q[1<<24];
int a[50];
int ans=0,cnt,t=0;
void dfs(int x,int sum){if(x>n/2-1){q[t++]=sum;return;}dfs(x+1,sum);if(sum+a[x]<=w)dfs(x+1,sum+a[x]);
}
void dfs1(int x,int sum){if(x>=n){int l=0,r=cnt-1;while(l<r){int mid=(l+r+1)/2;if(q[mid]+sum<=w)l=mid;else {r=mid-1;}}ans=max(q[l]+sum,ans);return;}dfs1(x+1,sum);if(sum+a[x]<=w)dfs1(x+1,sum+a[x]);
}
signed main(){cin>>w>>n;for(int i=0;i<n;i++){cin>>a[i];} sort(a,a+n,greater<int>());dfs(0,0);sort(q,q+t);cnt=unique(q,q+t)-q;dfs1(n/2,0);cout<<ans<<endl;
} 

173. 矩阵距离 - AcWing题库(模板稍微变形)

#include<iostream>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
string s[1005];
int a[1005][1005];
bool vis[1005][1005];
struct node{int xx,yy;int step;
};
int cnt[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
queue<node>q;
int in(int x,int y){if(x>=n||y>=m||x<0||y<0)return 0;return 1;
}
void bfs(){while(!q.empty()){node temp=q.front();q.pop();node t;t.step=temp.step+1;for(int i=0;i<4;i++){t.xx=temp.xx+cnt[i][1];t.yy=temp.yy+cnt[i][0];if(!in(t.xx,t.yy))continue;if(s[t.xx][t.yy]=='0'&&a[t.xx][t.yy]==0)a[t.xx][t.yy]=t.step;if(!vis[t.xx][t.yy])q.push(t);vis[t.xx][t.yy]=true;}}
}
int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>s[i];}for(int i=0;i<n;i++){for(int j=0;j<m;j++){node t;t.step=0;t.xx=i;t.yy=j;if(s[i][j]=='1')q.push(t),a[i][j]=0,vis[i][j]=true;}}bfs();for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<' ';}cout<<endl;}
}

B-游游的排列构造_牛客周赛 Round 5 (nowcoder.com)(签到)

#include<iostream>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
int main(){int m,k;cin>>m>>k;int a=m-k+1;int b=1;while(b<m-k+1||a<=m){if(a<=m){cout<<a<<' ';a++;}if(b<m-k+1){cout<<b<<' ';b++;}}
}

C-游游的二进制树_牛客周赛 Round 5 (nowcoder.com)(dfs)

#include<iostream>
#include<string>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
#define ll long long
int n;
ll l,r;
string s;
int ans=0;
map<pair<int,int>,int>ma;
const int N=1005;
const int M=2005;
int h[N],e[M],ne[M],idx;
bool vis[N];
void add(int x,int y){e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}
void dfs(int x,ll sum,int p){vis[x]=true;if(sum>r)return ;else if(sum<=r&&sum>=l&&p==2)ans++;for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!vis[j]){dfs(j,sum*2+s[j-1]-'0',2);}}
}
int main(){cin>>n>>l>>r;cin>>s;memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int x,y;cin>>x>>y;if(x==y||ma[{x,y}]==1||ma[{y,x}]==1)continue;add(x,y);add(y,x);ma[{x,y}]=1;ma[{y,x}]=1;}for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));dfs(i,s[i-1]-'0',1);}cout<<ans<<endl;
}

4122. 字符串转换 - AcWing题库

#include<iostream>
#include<string>
#include<queue>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
using namespace std;
#define ll long long
int main(){int t;cin>>t;for(int q=1;q<=t;q++){string s,f;cin>>s>>f;int ans=0;for(int i=0;i<s.size();i++){int cnt=26;for(int j=0;j<f.size();j++){cnt=min(cnt,abs(s[i]-f[j]));cnt=min(cnt,abs(s[i]+26-f[j]));cnt=min(cnt,abs(s[i]-26-f[j]));}ans+=cnt;}printf("Case #%d: %d\n",q,ans);}
}