牛客算法周周练3 ABCDE 分层图最短路
A:
思路：直接bfs就可以了。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
char a[105][105][105];
struct node{
int x, y, z, k;
};
queue<node> q;
int ans=-1;
void BFS(int n){
q.push(node{1, 1, 1, 1});
a[1][1][1]='*';
while(!q.empty()){
node t=q.front(); q.pop();
if(t.x==n&&t.y==n&&t.z==n){
ans=t.k;
return ;
}
for(int i=-1; i<2; i++){
for(int j=-1; j<2; j++){
for(int k=-1; k<2; k++){
int x=t.x+i, y=t.y+j, z=t.z+k;
if(((i==0&&j==0)||(i==0&&k==0)||(j==0&&k==0))&&x>=1&&x<=n&&y>=1&&y<=n&&z>=1&&z<=n&&a[x][y][z]!='*'){
q.push(node{x, y, z, t.k+1});
a[x][y][z]='*';
}
}
}
}
}
}
int main(){
int n; scanf("%d%*c", &n);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(int k=1; k<=n; k++){
scanf("%c", &a[i][j][k]);
}
getchar();
}
}
BFS(n);
printf("%d\n", ans);
return 0;
}
B:
思路：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=2333;
int a[3005][3005];
LL f[3005][3005];
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
scanf("%d", &a[i][j]);
}
}
for(int i=n; i>=1; i--){
for(int j=1; j<=m; j++){
if(a[i][j]==1) continue;
if(i==n&&j==1) f[i][j]=1;
else f[i][j]=(f[i+1][j]+f[i][j-1])%mod;
}
}
printf("%lld\n", f[1][m]);
return 0;
}
C:
建立m+1层图，前面m层是每条地铁线。因为每层之间可能公用了一些节点。我们之间让他们向虚拟节点连就可以了，i->(m * n+i)代价为0， (m * n+i)->i代价为a。
那么m * n+s->m * n+j就是题目的要求
#include <bits/stdc++.h>
using namespace std;
#define LL long long
vector<vector<pair<int, int> > > ve(600005);
int dis[600005]; //dis当前的最短路
int vis[600005]; //是否已经求出最短路
priority_queue<pair<int, int> > q;
int dijkstra(int s, int t){
while(!q.empty()) {
q.pop();
}
dis[s]=0;
q.push(make_pair(-dis[s], s));
while(!q.empty()){
int now=q.top().second;q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=0; i<ve[now].size();i++){
int v=ve[now][i].first;
if(!vis[v]&&dis[v]>dis[now]+ve[now][i].second){
dis[v]=dis[now]+ve[now][i].second;
q.push(make_pair(-dis[v], v));
}
}
}
if(dis[t]==dis[0]) return -1;
else return dis[t];
}
int main(){
int n, m, s, t; scanf("%d%d%d%d", &n, &m, &s, &t);
memset(dis, 7, sizeof(dis));
for(int i=0; i<m; i++){
int a, b, c; scanf("%d%d%d", &a, &b, &c);
int x=0, y=0;
for(int k=0; k<c; k++){
scanf("%d", &y);
if(k!=0){
ve[x+i*n].push_back({y+i*n, b});
ve[y+i*n].push_back({x+i*n, b});
}
ve[y+i*n].push_back({y+m*n, 0});
ve[y+m*n].push_back({y+i*n, a});
x=y;
}
}
cout<<dijkstra(n*m+s, n*m+t)<<endl;
return 0;
}D:
思路：用2个栈，一个放数字，一个放运算符。遇到就把数字栈里面的2个数放回栈。最后数字栈里面全部相加就可以了。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=10000;
char s[600005];
char op[600005];
LL x[600005], ts=0, tp=0;
int main(){
scanf("%s", s+1);
int n=strlen(s+1);
for(int i=1; i<=n; ){
if(s[i]=='+'||s[i]=='*'){
op[++tp]=s[i];
i++;
}
else{
LL ans=0;
while(i<=n&&s[i]>='0'&&s[i]<='9'){
ans=ans*10+s[i]-'0';
i++;
}
x[++ts]=ans%mod;
if(op[tp]=='*'){
tp--; x[ts-1]=x[ts]*x[ts-1]%mod;
ts--;
}
}
}
while(ts){
x[ts-1]=(x[ts]+x[ts-1])%mod;
ts--;
}
cout<<x[1]<<endl;
return 0;
}E：
思路：我们考虑从小到大枚举乳液的SPI，那么可能和他分配的牛[l, r]的l<=PSI<=r。但是我们贪心一定把它分配给是r最小的。因为r更大的可以和SPI更大的分配。如果SPI>r那么这头牛就不可能得到，因为后面的SPI更大，更不可能分配到。
用优先队列来维护牛的r就可以了。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct node{
int l, r;
}a[2505], b[2505];
priority_queue<int, vector<int>, greater<int> > q;
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%d%d", &a[i].l, &a[i].r);
}
for(int i=1; i<=m; i++){
scanf("%d%d", &b[i].l, &b[i].r);
}
sort(b+1, b+1+m, [](node &a, node &b){return a.l<b.l;});
sort(a+1, a+1+n, [](node &a, node &b){return a.l<b.l;});
int tot=1, ans=0;
for(int i=1; i<=m; i++){
int cut=b[i].r;
while(tot<=n&&a[tot].l<=b[i].l){
q.push(a[tot].r); tot++;
}
while(cut&&!q.empty()){
if(q.top()>=b[i].l){
ans++; cut--;
}
q.pop();
}
}
cout<<ans<<endl;
return 0;
}
投递荣耀等公司9个岗位