牛客算法周周练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;
}