L3-1 森森旅游

Solution

对1到 的所有点建图正向跑关于 的最短路
反向建图，对 到 1的所有点跑关于 的最短路
令正向最短路为 , 反向最短路为
在过程中最短路大小是不会变的，不难推出每个点的贡献是 (向上取整)
用一个 维护最小值即可，每次进行查找和删除操作
注意并不是所有点都能在此将现金转换并到达终点，所有还需要特判一下，否则只有29分

Code

#include <bits/stdc++.h>
typedef unsigned long long ll;

using namespace std;

const int N = 1e5 + 5;
const double pi = acos(-1.0);
vector<pair<int, int> > G[N], R[N];
ll dist[N], Re[N];
void Dijkstra1(int n, int start) {
    for (int i = 1; i <= n; i++) {
        dist[i] = 5e18;
    }
    dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int>> > q;
    q.push({0, start});
    while (!q.empty()) {
        auto tmp = q.top(); q.pop();
        int u = tmp.second;
        for (auto &it : G[u]) {
            int v = it.first, w = it.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}
ll a[100005];
void Dijkstra2(int n, int start) {
    for (int i = 1; i <= n; i++) {
        Re[i] = 5e18;
    }
    Re[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int>> > q;
    q.push({0, start});
    while (!q.empty()) {
        auto tmp = q.top(); q.pop();
        int u = tmp.second;
        for (auto &it : R[u]) {
            int v = it.first, w = it.second;
            if (Re[v] > Re[u] + w) {
                Re[v] = Re[u] + w;
                q.push({Re[v], v});
            }
        }
    }
}
void solve() {
    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        G[u].emplace_back(v, c);
        R[v].emplace_back(u, d);
    }    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    Dijkstra1(n, 1);
    Dijkstra2(n, n);
    // for (int i = 1; i <= n; i++) {
    //     cout << dist[i] << " \n"[i == n];
    // }
    // for (int i = 1; i <= n; i++) {
    //     cout << Re[i] << " \n"[i == n];
    // }
    multiset<ll> st;
    ll ans = 5e18;
    for (int i = 1; i <= n; i++) {
        if (Re[i] != 5e18)
            st.insert(dist[i] + (Re[i] + a[i] - 1) / a[i]);
        //cout << i << ' ' << dist[i] + (Re[i] + a[i] - 1) / a[i] << '\n';
    }
    while (q--) {
        int l, r; cin >> l >> r;
        if (Re[l] != 5e18) {
            auto pos = st.find(dist[l] + (Re[l] + a[l] - 1) / a[l]); 
            st.erase(pos);
            a[l] = r;
            st.insert(dist[l] + (Re[l] + a[l] - 1) / a[l]);
        }
        cout << *st.begin() << '\n';
    }    
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

L3-2 还原文件

Solution

对序列进行 , 由于存在解唯一，用一个 存所有哈希值，扫一遍能匹配就匹配上去，并在 里删除这个哈希值即可。

Code

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

const int N = 1e7 + 5;
const int mod = 1e9 + 7;
vector<int> v[100005];
bool vis[100005];
void solve() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }  
  int q; cin >> q;
  multiset<unsigned long long> st;
  map<unsigned long long, int> mp;
  int tot = 0;
  for (int id = 1; id <= q; id++) {
    int num; cin >> num;
    unsigned long long res = 0;
    for (int i = 1; i <= num; i++) {
      int x; cin >> x;
      res = res * mod + x;
    }  
    st.insert(res);
    if (!mp.count(res)) {
      mp[res] = ++tot;
    }
    v[mp[res]].emplace_back(id);
  }
  int cur = 0;
  vector<int> ans;
  while (cur < n) {
    unsigned long long res = 0;
    int pos = cur, ok = 0;
    while (pos < n && !ok) {
      res = res * mod + a[pos];
      ++pos;
      auto pos = st.find(res);
      if (pos != st.end()) {
        ok = 1;
        st.erase(pos);
        ans.emplace_back(v[mp[res]].back());
        v[mp[res]].pop_back();
        break;
      }
    }
    cur = pos - 1;
    if (int(ans.size()) == q) break;
    //cout << cur << ' ' << ans.size() << '\n';
  }
  for (int i = 0; i < int(ans.size()); i++) {
    cout << ans[i] << " \n"[i == int(ans.size()) - 1];
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int T = 1; //cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}