牛客算法周周练3 题解

A. Jelly

Solution

之前的牛客小白赛做过, 然后一点开代码就在上面了(于是8秒ac了
就是个三维bfs的裸题而已

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ll;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
const int N = 2e5 + 5;
const int mod = 20010905;
struct node{
    int x, y, z;
    int step;
    node(int _x = 0, int _y = 0, int _z = 0, int _step = 0):x(_x), y(_y), z(_z), step(_step){}
};
int dist[6][3] = {1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1};
char maze[105][105][105];
bool vis[105][105][105];
int n;
int bfs(int x, int y, int z){
    queue<node>q;
    q.push(node(x, y, z, 1));
    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(now.x == n && now.y == n && now.z == n){
            return now.step;
        }
        for(int i = 0; i < 6; i++){
            int xx = now.x + dist[i][0];
            int yy = now.y + dist[i][1];
            int zz = now.z + dist[i][2];
            if(!vis[xx][yy][zz] && maze[xx][yy][zz] == '.'){
                vis[xx][yy][zz] = 1;
                q.push(node(xx, yy, zz, now.step + 1));
            }
        }
    }
    return -1;
}
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++){
                cin >> maze[i][j][k];
            }
        }
    }
    vis[1][1][1] = 1;
    cout << bfs(1, 1, 1) << endl;
}

B. 「木」迷雾森林

Solution

我的做法是记忆化搜索, 用dp[x][y] 表示 x行 y列到达右上角的方案数，直接搜索即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e6 + 5;
const ll mod = 2333;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
template<class T>inline void redi(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;
}
int dist[2][2] = {-1, 0, 0, 1};
int n, m;
int dp[3005][3005];
int maze[3005][3005];
int dfs(int x, int y){
  //cout << x << ' ' << y << "\n";
  if(x <= 0 || x > n || y <= 0 || y > m || maze[x][y] == 1) return 0;
  if(dp[x][y] != -1) return dp[x][y];
  if(x == 1 && y == m) return 1;
  ll ans = 0;
  for(int i = 0; i < 2; i++){
    ans += dfs(x + dist[i][0], y + dist[i][1]);
    ans %= mod;
  }
  return dp[x][y] = ans % mod;
}
int main(){
  redi(n), redi(m);
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      redi(maze[i][j]);
    }
  }
  memset(dp, -1, sizeof(dp));
  dfs(n, 1);
  // for(int i = 1; i <= n; i++) {
  //   for(int j = 1; j <= m; j++){
  //     cout << dp[i][j] << " \n"[j == m];
  //   }
  // }
  printf("%d\n", dp[n][1]);
  return 0;
}

C. 小雨坐地铁

Solution

分层图最短路, 也是某个小白月赛的题, 做了一个多小时orz
每条地铁线看做是一层图
我的做法是把对每个车站建立一个超级源点, 车站到超级源点的花费是0, 源点往车站的花费是上/转地铁的花费
最后跑一遍Dijkstra 找超级源点s到超级源点t的最短路
样例图是这样的(红色的是超级源点):
图片说明
从超级源点1 -> 1 -> 3 -> 超级源点3 -> 另一层线路的3 -> 4
总花费为 2 + 2 + 2 + 1 = 7

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 2e6 + 5;
const ll mod = 2333;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int a[N], b[N];
struct Edge {
  int v, nextz;
  ll w;
}edge[N << 1];
int tot, head[N];
struct qnode {
  int v;
  ll cost;
  qnode(int _v = 0, ll _cost = 0): v(_v), cost(_cost) {}
  bool operator < (const qnode &s)const {
    return cost > s.cost;
  }
};
void addedge(int u, int v, ll w) {
  edge[tot].v = v;
  edge[tot].w = w;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
ll dist[N];
bool vis[N];
void Dijkstra(int start) {
  for(int i = 1; i <= 1e6; i++) dist[i] = inf;
  priority_queue<qnode> q;
  q.push(qnode(start, 0));
  dist[start] = 0;
  while(!q.empty()) {
    qnode tmp = q.top();
    q.pop();
    int u = tmp.v;
    if(vis[u]) continue;
    vis[u] = 1;
    for(int i = head[u]; ~i; i = edge[i].nextz) {
      ll cost = edge[i].w;
      int v = edge[i].v;
      if(!vis[v] && dist[v] > dist[u] + cost) {
        dist[v] = dist[u] + cost;
        q.push(qnode(v, dist[v]));
      }
    }
  }
}
int main() {
  memset(head, -1, sizeof(head));
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  for(int i = 1; i <= m; i++) {
    int num;
    cin >> a[i] >> b[i] >> num;
    int x = 0, last = 0;
    for(int j = 1; j <= num; j++) {
      cin >> x;
      if(j != 1) {
        addedge((i - 1) * n + x, (i - 1) * n + last, b[i]);
        addedge((i - 1) * n + last, (i - 1) * n + x, b[i]);
      }
      addedge((i - 1) * n + x, (m + 1) * n + x, 0);
      addedge((m + 1) * n + x, (i - 1) * n + x, a[i]);
      last = x;
    }
  }
  Dijkstra((m + 1) * n + s);
  cout << (dist[(m + 1) * n + t] >= inf ? -1 : dist[(m + 1) * n + t]) << "\n";
  return 0;
}

D. 表达式求值

Solution

因为只有乘和加, 我们考虑先做乘法, 剩下的数字存到一个栈里, 最后栈里肯定都是做加法运算的
直接加完即可
因为只保留后面四位, 要模个1e4

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e6 + 5;
const ll mod = 2333;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int main(){
  string s;
  cin >> s;
  stack<int> st;
  for(int i = 0; i < s.size(); ) {
    if(isdigit(s[i])) {
      ll res = 0;
      while(isdigit(s[i])) {
        res = res * 10 + s[i] - '0';
        res %= 10000;
        i++;
      }
      st.push(res);
    }
    else if(s[i] == '*') {
      ll p = 0;
      i++;
      while(isdigit(s[i])) {
        p = p * 10 + s[i] - '0';
        p %= 10000;
        i++;
      }
      int last = st.top();
      st.pop();
      st.push(last * p % 10000);
    }
    else if(s[i] == '+') {
      i++;
    }
  }
  while(st.size() >= 2) {
    int p1 = st.top();
    st.pop();
    int p2 = st.top();
    st.pop();
    st.push((p1 + p2) % 10000);
  }
  cout << st.top() % 10000 << "\n";
  return 0;
}

E Sunscreen

Solution

一道贪心题
题意 c只牛, l种防晒, 每种牛有一个舒适范围, 防晒能够让牛位于某个值SPF, 但有数量限制
做法是贪心
把牛按区间右端点排序, 把防晒按SPF值排序, 因为数据范围很小
找到剩余防晒中第一个能让牛位于舒适区的防晒即可
看了眼数据范围, 直接 $O(cl)$ 解决即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
const ll mod = 2333;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
struct cow {
  int l, r;
}C[N];
struct lu {
  int p, num;
}L[N];
int main() {
  int c, l;
  cin >> c >> l;
  for(int i = 1; i <= c; i++) {
    cin >> C[i].l >> C[i].r;
  }
  for(int i = 1; i <= l; i++) {
    cin >> L[i].p >> L[i].num;
  }
  sort(L + 1, L + 1 + l, [](const lu &x, const lu &y){return x.p < y.p;});
  sort(C + 1, C + 1 + c, [](const cow &x, const cow &y){return x.r < y.r;});
  int ans = 0;
  for(int i = 1; i <= c; i++) {
    for(int j = 1; j <= l; j++) {
      if(L[j].p >= C[i].l && L[j].p <= C[i].r && L[j].num) {
        L[j].num--;
        ans++;
        break;
      }
    }
  }
  cout << ans << "\n";
  return 0;
}