牛客算法周周练3(ABCD题解)

A Jelly


思路：非常裸的一个三维bfs，Dungeon Master poj2251和这题差不多。就是在二维的基础上多加两个方向，其他的就是常规操作。
代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

char str[300][300][300];
int vis[300][300][300];
int step[300][300][300];
int dir[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,1},{0,0,-1}};
struct node{
    int x,y,z;
    node(int a,int b,int c):x(a),y(b),z(c){}
    node(){}
};
int n;
void bfs(int x1,int y1,int z1,int x2,int y2,int z2){
    queue<node>st;
    st.push(node(x1,y1,z1));
    vis[x1][y1][z1]=1;
    step[x1][y1][z1]=0;
    bool flag=true;
    while(!st.empty()){
        int fxx=st.front().x;
        int fyy=st.front().y;
        int fzz=st.front().z;
        st.pop();
        if(fxx == n && fyy == n && fzz == n){
            flag = false;
            cout<<step[fxx][fyy][fzz] + 1<<endl;break;
        }
        for(int i=0;i<6;i++){
            int fx=fxx+dir[i][0];
            int fy=fyy+dir[i][1];
            int fz=fzz+dir[i][2];
            if(fx < 1||fy < 1||fz < 1||fx > n||fy > n||fz > n)continue;
            if(str[fz][fx][fy]=='.'&&!vis[fx][fy][fz]){
                vis[fx][fy][fz]=1;
                st.push(node(fx,fy,fz));
                step[fx][fy][fz]=step[fxx][fyy][fzz]+1;
                //cout<<fx<<" "<<fy<<" "<<fz<<" "<<step[fx][fy][fz]<<endl;
            }
        }
    }
    if(flag){
        cout<<"-1"<<endl;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    scanf(" %c",&str[i][j][k]);
    bfs(1,1,1,n,n,n);
}

思路：也是非常裸的一个经典dp了。
dp[i][j]：表示从(m,1)到(i,j)的路径条数。
转移方程
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] (a[i][j] == 0)
dp[i][j] = 0 (a[i][j] != 0)
代码

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e4 + 10;
int a[3100][3100];
int mod = 2333;
ll dp[3100][3100];
//dp[i][j]:从(1,1)到(i,j)的方案数
//dp[i][j] = dp[i + 1][j] + dp[i][j - 1] 
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
void solved(){
    int m,n;read(m);read(n);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            read(a[i][j]);
    dp[m][1] = 1;
    for(int i = 2; i <= n; i++){
        if(a[m][i] == 0)dp[m][i] = dp[m][i - 1];
        else dp[m][i] = 0;
    }

    for(int i = m - 1; i >= 1; i--){
        if(a[i][1] == 0)dp[i][1] = dp[i + 1][1];
        else dp[i][1] = 0;
    }

    for(int i = m - 1; i >= 1; i--){
        for(int j = 2; j <= n; j++){
            if(a[i][j] == 0)
            dp[i][j] = ((dp[i + 1][j] % mod) + (dp[i][j - 1] % mod)) % mod;
            else dp[i][j] = 0;
        }
    }    
    //for(int i = 1; i <= m; i++){
    //    for(int j = 1; j <= n; j++){
    //        cout<<dp[i][j]<<" ";
    //    }
    //    cout<<endl;
    //}
    printf("%lld",dp[1][n] % mod);
}
int main(){
    solved();
    return 0;
}

思路：
一个码量不是很大的模拟题，因为它要的是最后四位数，所以我们可以不断的取模，并且只有 + 和 * ，所以我们考虑用栈来维护一下运算符的优先级，如果是 + 我们就把它丢进栈里面去，如果是 * 我们就，不断的 * 直到遇到 + 才停下来这样就可以把 * 全部消掉，这个时候 * 的值全部计算完毕，把它丢到栈里面去，到时候只需要做加法就行了。记住要不断的取模，防止爆ll。
代码

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e5 + 10;
void solved(){
    string s;cin>>s;
    ll num = 0;
    stack<ll>st;
    for(int i = 0; i < s.size(); i++){
        if(isdigit(s[i])){
            num = num * 10 + (s[i] - '0');
        }else{
            if(s[i] == '+'){
                st.push(num % 10000);num = 0;
            }else{
                ll ans = 0;
                for(++i;i < s.size() && s[i] !='+' ;i++){
                    if(isdigit(s[i])){
                        ans = ans * 10 + (s[i] - '0'); 
                    }else{
                        num *= ans;num%=10000;
                        ans = 0;
                    }
                }
                num *= ans;num%=10000;
                st.push(num % 10000);num = 0;
            }
        }
    }
    st.push(num % 10000);
    ll res = 0;
    while(!st.empty()){
        //cout<<st.top()<<endl;
        res += st.top();st.pop();res %= 10000;
    }
    cout<<res%10000<<endl;
}
int main(){
    solved();
    return 0;
}

思路：
为了让防晒霜的价值最大化，我们需要先对防晒霜的第一关键字排序，因为把最小的处理掉才能留出更多的空间。
同理对牛的第一关键字排序，然后把第一关键字小于等于防晒霜的第一关键字的牛保存起来(说明改防晒霜可以适合它)，然后判断牛的第二关键字是否大于等于防晒霜的第一关键字，只有这样才满足题目要求，为了使得防晒霜的使用最大化，我们希望牛的第二关键字升序，所以这里可以考虑用优先队列的维护，在满足条件的情况下输出数量就是最优解了。
代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 10;
struct node{
    int x,y;
    node(){}
    node(int a,int b):x(a),y(b){}
}a[maxn],b[maxn];
bool cmp(node a,node b){
    return a.x < b.x;
}
void solved(){
    int c,l;cin>>c>>l;
    for(int i = 1; i <= c; i++){
        cin>>a[i].x>>a[i].y;
    }
    for(int i = 1; i <= l; i++){
        cin>>b[i].x>>b[i].y;
    }
    sort(a + 1,a + 1 + c,cmp);
    sort(b + 1,b + 1 + l,cmp);
    int ans = 0;
    int j  = 1;
    priority_queue<int, vector<int>, greater<int> >st;
    for(int i = 1; i <= l; i++){
        for(;j <= c && a[j].x <= b[i].x;j ++){
            st.push(a[j].y);
            //cout<<a[j].y<<endl;
        }
        while(!st.empty()&& b[i].y > 0){
            int v = st.top();st.pop();
            if(v < b[i].x)continue;
            ans++;b[i].y--;
        }
    }
    cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
}