A 题目传送门
思路：在Y，M 处用 bfs 分别跑一边图，记录两个人到每个'@'的最小时间。最后再遍历一遍数组得到两个相加的结果的最小值，即答案。
//这道题跟蓝桥杯的一道题差不多 贴个链接
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int qs=1e6+7; 5 const int inf=0x3f3f3f3f; 6 char C[207][207]; 7 int vis[207][207]; // 判重 8 int A[207][207]; 9 int B[207][207]; 10 int n,m; 11 struct node 12 { 13 int x,y; 14 int num; 15 node(){} // 用于在队列中存结构体 16 node(int x,int y,int num):x(x),y(y),num(num){}; 17 }t,v; 18 queue<node> q; //队列 bfs 遍历 19 int l[4]={-1,1,0,0}; // 两个数组对应移动方向 20 int r[4]={0,0,-1,1}; 21 void bfs(int x,int y,int S[][207]) 22 { 23 int i,j; 24 for(i=0;i<=n;++i) // 重置数组 25 for(j=0;j<=m;++j) // ！！！这里，，，一开始写成 j<=n ，半天愣是没找出来，浪费了50分钟时间 26 vis[i][j]=0; // 之前一直用 memset 的，后来听说 memset 有问题就没用过 27 t.x=x; t.y=y; t.num=0; 28 vis[t.x][t.y]=1; //标记 29 q.push(t); 30 while(!q.empty()) 31 { 32 t=q.front(); q.pop(); 33 for(i=0;i<4;++i) //移动 34 { 35 v.x=t.x+l[i]; 36 v.y=t.y+r[i]; 37 v.num=t.num+11; 38 if(v.x<1||v.x>n||v.y<1||v.y>m||C[v.x][v.y]=='#'||vis[v.x][v.y]==1) continue; 39 S[v.x][v.y]=v.num; 40 vis[v.x][v.y]=1; 41 q.push(v); 42 } 43 } 44 return; 45 } 46 int main() 47 { 48 int i,j,k; 49 while(cin>>n>>m) 50 { 51 for(i=1;i<=n;++i) cin>>C[i]+1; 52 for(i=1;i<=n;++i) 53 for(j=1;j<=m;++j) 54 { 55 if(C[i][j]=='M') bfs(i,j,A); 56 if(C[i][j]=='Y') bfs(i,j,B); 57 } 58 int ans=inf; 59 for(i=1;i<=n;++i) 60 for(j=1;j<=m;++j) 61 { 62 if(C[i][j]=='@'&&A[i][j]&&B[i][j]) 63 ans=min(ans,A[i][j]+B[i][j]); 64 A[i][j]=0; 65 B[i][j]=0; 66 } 67 cout<<ans<<endl; 68 } 69 70 return 0; 71 }
View Code
B 题目传送门
思路：将图看成两部分，从（1，1）和（n,m）处分别dfs跑一遍，将贴近对角线的一条线上的点设为两部分的搜索结束点（使两边搜索复杂度尽可能平均） 因为ai,j<=1e18,可用STL库函数map记录,map[x][y][temp]记录在(x,y)处异或值为temp的路径个数。
//刚开始想dfs或bfs把整个图的每一条边都跑一边，后来被学长提醒后才明白。n,m<=20,直接从(1,1)遍历到(n,m)最大复杂度可达到 240.
附: a^b^a=b
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll A[23][23]; 5 map<ll,ll> mp[23][23]; 6 int n,m; 7 ll k; 8 bool check(int x,int y) //判断是否越界 9 { 10 if(x<1||y<1||x>n||y>m) return false; 11 return true; 12 } 13 ll ans=0; 14 void dfs(int x,int y,ll temp) //从（1，1）遍历 15 { 16 if(!check(x,y)) return; 17 if(x+y==n+1) //自己规定的结束点 18 { 19 mp[x][y][temp]++; //记录 20 return; 21 } 22 dfs(x+1,y,temp^A[x+1][y]); 23 dfs(x,y+1,temp^A[x][y+1]); 24 } 25 void dfs1(int x,int y,ll temp) 26 { 27 if(!check(x,y)) return; 28 if(x+y==n+1) 29 { 30 ans+=mp[x][y][temp^k^A[x][y]]; //因为终点多被异或一次，要异或回来。 31 return; 32 } 33 dfs1(x-1,y,temp^A[x-1][y]); 34 dfs1(x,y-1,temp^A[x][y-1]); 35 } 36 int main() 37 { 38 int i,j; 39 cin>>n>>m>>k; 40 for(i=1;i<=n;++i) 41 for(j=1;j<=m;++j) cin>>A[i][j]; 42 dfs(1,1,A[1][1]); 43 dfs1(n,m,A[n][m]); 44 cout<<ans<<endl; 45 return 0; 46 }
View Code
D 题目传送门
思路：设电梯在i楼,则对于在第j层的用户来说电梯耗费电力有 : (abs(i-j)+j+i)*2*A[j] ,剩下就嗯遍历，找出最优解即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int qs=1e6+7; 5 const int inf=0x3f3f3f3f; 6 int n,m; 7 int A[qs]; 8 int main() 9 { 10 int i,j; 11 cin>>n; 12 int x=0; 13 for(i=0;i<n;++i) cin>>A[i]; 14 int ans=inf; 15 for(i=0;i<n;++i) 16 { 17 int fx=0; 18 for(j=1;j<n;++j) 19 { 20 fx+=(abs(i-j)+j+i)*2*A[j]; 21 } 22 ans=min(ans,fx); 23 } 24 cout<<ans<<endl; 25 return 0; 26 }
View Code
E 题目传送门
思路：若啤酒总量小于杯子数，返回 -1。否则啤酒总量减去杯子数量再除以桶数得到平均值，平均值与桶中最小的啤酒量作比较，取小的即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll n,m; 5 int main() 6 { 7 ll i,j,k; 8 cin>>n>>m; 9 ll sum=0,x; 10 ll y=1e18; 11 for(i=1;i<=n;++i) 12 { 13 cin>>x; 14 y=min(x,y); 15 sum+=x; 16 } 17 ll ans=0; 18 if(sum<m) ans=-1; 19 else{ 20 ans=(sum-m)/n; 21 ans=min(ans,y); 22 } 23 cout<<ans<<endl; 24 return 0; 25 }
View Code
F 题目传送门
题目大意：求只有'a'组成的子序列个数，若子序列长度大于1，则子序列中任意 两两 'a' 在原字符串中的位置间都有至少一个 ‘b' .
思路：设 temp 为任意相离最近两个'b'之间的 'a' 的个数+1（此处+1是因为有可能不选这个区间的 'a'）。这个区间里面的 ’a' 不能相互组合。则用 temp 乘以这个区间之前已经形成的子序列个数，就是为到目前区间为止总子序列个数（包括空串），递推到字符串结束。最后再减去每个区间都不选的情况（即空串）。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod= 1e9+7; 5 int n,m; 6 int main() 7 { 8 string s; 9 cin>>s; 10 s+='b'; 11 ll temp=1; 12 ll ans=1; 13 for(int i=0;i<s.size();++i) 14 { 15 if(s[i]=='b') 16 { 17 ans=ans*temp%mod; 18 temp=1; 19 } 20 if(s[i]=='a') temp++; 21 } 22 23 cout<<ans-1<<endl; 24 return 0; 25 }
View Code
5.5 补 G: 题目传送门
树上dp,dfs一边即可。
1 #includ<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int inf=0x3f3f3f3f; 5 const int qs=3e5+7; 6 int n,m; 7 ll dp[qs]; 8 ll w[qs]; 9 ll ans=0; 10 struct node 11 { 12 ll x,y; 13 node(){} 14 node(ll x,ll y):x(x),y(y){}; 15 }t; 16 17 vector<node> v[qs]; 18 void dfs(ll temp,ll fa) 19 { 20 ans=max(ans,dp[temp]); 21 for(int i=0;i<v[temp].size();++i) 22 { 23 ll x=v[temp][i].x; 24 ll y=v[temp][i].y; 25 if(x==fa) continue; 26 dfs(x,temp); 27 ll dig=dp[x]-y; 28 ans=max(ans,dp[temp]+dig); 29 dp[temp]=max(dp[temp],w[temp]+dig); 30 } 31 } 32 int main() 33 { 34 ll u,vv,k,i,j; 35 cin>>n; 36 for(i=1;i<=n;++i) 37 { 38 cin>>w[i]; dp[i]=w[i]; 39 } 40 for(i=1;i<n;++i) 41 { 42 cin>>u>>vv>>k; 43 v[u].push_back(node(vv,k)); 44 v[vv].push_back(node(u,k)); 45 } 46 dfs(1,0); 47 cout<<ans<<endl; 48 return 0; 49 }
View Code
おもしろい
原文链接: https://www.cnblogs.com/Suki-Sugar/p/12824888.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/346319
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
