20250818总结

__LZH__ · 2025-08-18 18:23:04 · 个人记录

A - Beautiful Path

题意

有一个包含 N 个顶点和 M 条边的有向图。每条边都被赋予了两个正整数值，分别表示美丽值和花费。

对于 i = 1, 2, \ldots, M，第 i 条边是从顶点 u_i 指向顶点 v_i 的有向边，其美丽值为 b_i，花费为 c_i。这里保证 u_i < v_i。

请你选择一条从顶点 1 到顶点 N 的路径 P，使得 P 上所有边的美丽值之和除以 P 上所有边的花费之和为最大值

思路

看到除法我们可以考虑 01 分数规划，设二分值为 mid，最优路径为 path，边权，则有 \sum_{i \in path} b_i - mid \times c_i \ge 0，又可以发现输入保证 u_i < v_i，所以check时只要dp即可。

时空复杂度

时间：O(n \log V)

空间：O(n)

代码

#include<bits/stdc++.h>

#define int long long

#define double long double

using namespace std;

const int N = 2e5 + 10;

struct node{
  int x, w1, w2;
};

int n, m;
vector<node> v[N];
double dp[N];

bool check(double x){
  fill(dp + 2, dp + 1 + n, -1e10);
  for(int i = 1; i <= n; i++){
    for(auto [j, w1, w2] : v[i]){
      dp[j] = max(dp[j], dp[i] + w1 - x * w2);
    }
  }
  return dp[n] >= 0;
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1, x, y, w1, w2; i <= m; i++){
    cin >> x >> y >> w1 >> w2;
    v[x].push_back({y, w1, w2});
    }
    double l = 0, r = 1e10;
    for(int i = 1; i <= 100; i++){
    double mid = (l + r) / 2;
    if(check(mid)){
      l = mid;
    }else{
      r = mid;
    }
    }
    cout << fixed << setprecision(12) << l;
    return 0;
}

C - 循环位运算

题意

给定 n 个数 A_i，每个数我们都将其视为一个 32 位的二进制数。你可以进行 m 次操作，每次选择任意一个数将其循环左移一次，问做了不超过 m 次操作后，n 个数的和最大是多少。

思路

发现 n, m \leq 10^3， 我们可以设 dp_{i, j} 为前 i 个、左移过 j 次的最大和，我们可以暴力 O(nm^2) 转移，但数只有 32 位，所以只需要枚举转 32 次即可。

时空复杂度

时间：O(32nm)

空间：O(nm)

代码

#include<bits/stdc++.h>

#define int long long

#define double long double

using namespace std;

const int N = 1e3 + 10;

int n, m, a[N], dp[N][N];

int f(int x, int p){
  int op = 0;
  for(int i = 31 - p + 1, j = 0; i <= 31; i++, j++){
    op |= (x >> i & 1) * (1ll << j);
  }
  for(int i = 0; i <= 31 - p; i++){
    op |= (x >> i & 1) * (1ll << i + p);
  }
  return op;
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
    cin >> a[i];
    }
    for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      dp[i][j] = -1e18;
    }
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
    for(int j = m; j >= 0; j--){
      for(int k = 0; k <= min(j, 31ll); k++){
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + f(a[i], k));
      }
    }
    }
    cout << *max_element(dp[n], dp[n] + m + 1);
    return 0;
}

D - Transportation

题面

在 AtCoder 国有 N 个岛屿，最初每个岛屿上都没有机场和港口，岛屿之间也没有道路。作为国王的高桥君决定为这些岛屿之间提供交通方式。具体来说，高桥君可以无限次地选择并执行以下三种操作之一：

• 选择满足 1\leq i\leq N 的 i，支付费用 X_i，在岛屿 i 上建造机场。
• 选择满足 1\leq i\leq N 的 i，支付费用 Y_i，在岛屿 i 上建造港口。
• 选择满足 1\leq i\leq M 的 i，支付费用 Z_i，在岛屿 A_i 和岛屿 B_i 之间建造一条双向道路。

高桥君的目标是，使得对于任意两个不同的岛屿 U 和 V，都可以从岛屿 U 出发，通过无限次地选择并执行以下三种操作之一，到达岛屿 V：

• 如果岛屿 S 和 T 都有机场，可以从 S 移动到 T。
• 如果岛屿 S 和 T 都有港口，可以从 S 移动到 T。
• 如果存在连接岛屿 S 和 T 的道路，可以从 S 移动到 T。

请你求出高桥君达成目标所需的最小总费用。

思路

容易想到用最小生成树做，对于岛屿与机场的操作，我们可以分别开一个虚点来连边，但这时我们会发现只有 1 到 n 要连通，虚点随便连不连，所以还要分类讨论四种情况，还是有点恶心的。

时空复杂度

时间：O(n \log n)

空间：O(n)

代码

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 10;

struct node{
  int x, y, w;
}c[N], p[N * 3];

int n, m, t, f[N], a[N], b[N];

int find(int x){
  return f[x] == x ? x : f[x] = find(f[x]);
}

void init(){
  t = 0;
    for(int i = 1; i <= n + 2; i++){
    f[i] = i;
    }
}

void adda(){
  for(int i = 1; i <= n; i++){
    p[++t] = {i, n + 1, a[i]};
  }
}

void addb(){
  for(int i = 1; i <= n; i++){
    p[++t] = {i, n + 2, b[i]};
  }
}

void addc(){
  for(int i = 1; i <= m; i++){
    p[++t] = c[i];
  }
}

int getans(){
  int sum = 0;
  sort(p + 1, p + 1 + t, [](const node &a, const node &b){return a.w < b.w;});
  for(int i = 1; i <= t; i++){
    auto [x, y, w] = p[i];
    int fx = find(x), fy = find(y);
    if(fx != fy){
      sum += w, f[fy] = fx;
    }
  }
  for(int i = 1; i <= n; i++){
    if(find(i) != find(1)){
      return 1e18;
    }
  }
  return sum;
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
    cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
    cin >> b[i];
    }
    for(int i = 1, x, y, w; i <= m; i++){
    cin >> x >> y >> w;
    c[i] = {x, y, w};
    }
    int ans = 1e18;
    init(), addc();
    ans = min(ans, getans());
    init(), adda(), addc();
    ans = min(ans, getans());
    init(), addb(), addc();
    ans = min(ans, getans());
    init(), adda(), addb(), addc();
    cout << min(ans, getans());
    return 0;
}

E - 贸易

题面

这个世界上一共有 n 个国家，这些国家之间经常有贸易往来，于是为了方便，有 m 条道路连接这些国家，每条道路连接两个国家，使得这两个国家之间可以轻松进行往来。

有了这些道路之后，商人在国家之间会赚取到更多的利润，所以为了限制商人的财富，国家之间制定了一个规则。商人经过每条道路，需要上交这条路对应的过路费 w_i，商人从起点国家到达目的地国家时，会返还给他走的路径上的过路费最大的那条路的费用 \max w_i 减去过路费最小的那条路的费用 \min w_i。

现在，有 k 个商人要从一号国家出发，去各个国家进行贸易，你需要计算他们每个人如何走可以使得他自己的过路费最少，你只需要告诉他们每个人这个最小过路费即可。

思路

我们可以用 (i, 0/1, 0/1)，表示到第 i 个、减没减到最大或最小边权，然后去跑分层图即可。

为什么我们可以这么这么做呢？因为我们可以发现每次弹出队列的都是最小的，若这次减了最大边且下次弹出的就是从这个状态转移而来，那么之前这次减的一定比之前的都大，要不然弹出的就不是这个状态了，最小值同理，所以我们可以直接做分层图。

时空复杂度

时间：O(n \log n)

空间：O(n)

代码

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 10;

struct edge{
  int x, w;
};

struct node{
  int x, f1, f2, w;
};

bool operator < (const node &a, const node &b){
  return a.w > b.w;
}

int n, m, k, d[N][2][2], vis[N][2][2];
vector<edge> v[N];

void dijkstra(){
  for(int i = 1; i <= n; i++){
    d[i][0][0] = d[i][0][1] = d[i][1][0] = d[i][1][1] = 1e18;
  }
  priority_queue<node> q;
  q.push({1, 0, 0, 0}), d[1][0][0] = 0;
  while(!q.empty()){
    auto [x, f1, f2, w] = q.top(); q.pop();
    if(vis[x][f1][f2]){
      continue;
    }
    vis[x][f1][f2] = 1;
    for(auto [i, wi] : v[x]){
      if(d[i][f1][f2] > w + wi){
        d[i][f1][f2] = w + wi;
        q.push({i, f1, f2, w + wi});
      }
      if(!f1){
        if(d[i][1][f2] > w){
          d[i][1][f2] = w;
          q.push({i, 1, f2, w});
        }
      }
      if(!f2){
        if(d[i][f1][1] > w + wi * 2){
          d[i][f1][1] = w + wi * 2;
          q.push({i, f1, 1, w + wi * 2});
        }
      }
      if(!f1 && !f2){
        if(d[i][1][1] > w + wi){
          d[i][1][1] = w + wi;
          q.push({i, 1, 1, w + wi});
        }
      }
    }
  }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1, x, y, w; i <= m; i++){
    cin >> x >> y >> w;
    v[x].push_back({y, w});
    v[y].push_back({x, w});
    }
    dijkstra();
    for(int i = 1, x; i <= k; i++){
    cin >> x;
    cout << d[x][1][1] << '\n';
    }
    return 0;
}

H - Palindrome Query

题面

给定一个由小写英文字母组成、长度为 N 的字符串 S。
请按给定顺序处理 Q 个如下所述的查询。
查询有以下两种类型之一：

• 1 x c ：将 S 的第 x 个字符修改为小写英文字母 c。
• 2 L R ：如果 S 的第 L 个字符到第 R 个字符组成的子串是回文串，则输出 Yes，否则输出 No。

思路

看题面我们可以想到单点修改区间查询的线段树，而判断回文我们可以用哈希解决，所以我们用线段树去存哈希值，一颗存正序一颗存倒序，这样就可以实现本题操作了。

时空复杂度

时间：O(q \log n)

空间：O(8n)

代码

#include<bits/stdc++.h>

#define int unsigned long long

#define lp p<<1

#define rp p<<1|1

using namespace std;

const int base = 131;
const int MOD = 998244353;

const int N = 1e6 + 10;

struct node{
  int len, x;
}t[2][4 * N];

int n, m, h[N][2], b[N];
string s, tp;
char c;

node operator + (const node &a, const node &y){
  return {a.len + y.len, a.x * b[y.len] + y.x};
}

void build(int l, int r, int p){
  if(l == r){
    t[0][p] = {1, s[l - 1]};
    t[1][p] = {1, tp[l - 1]};
    return ;
  }
  int mid = (l + r) >> 1;
  build(l, mid, lp), build(mid + 1, r, rp);
  t[0][p] = t[0][lp] + t[0][rp];
  t[1][p] = t[1][lp] + t[1][rp];
}

void update(int l, int r, int p, int s, int ti, int id){
  if(l == r){
    t[id][p] = {1, ti};
    return ;
  }
  int mid = (l + r) >> 1;
  if(s <= mid){
    update(l, mid, lp, s, ti, id);
  }else{
    update(mid + 1, r, rp, s, ti, id);
  }
  t[id][p] = t[id][lp] + t[id][rp];
}

node query(int l, int r, int p, int s, int tt, int id){
  if(l > tt || r < s){
    return {0, 0};
  }
  if(s <= l && r <= tt){
    return t[id][p];
  }
  int mid = (l + r) >> 1;
  return (query(l, mid, lp, s, tt, id) + query(mid + 1, r, rp, s, tt, id));
}

bool check(int l, int r){
  return query(1, n, 1, l, r, 0).x == query(1, n, 1, n - r + 1, n - l + 1, 1).x;
}

signed main(){
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m >> s; tp = s, b[0] = 1;
  reverse(tp.begin(), tp.end());
  for(int i = 1; i <= n; i++){
    b[i] = b[i - 1] * base;
  }
  build(1, n, 1);
  for(int _ = 1, op, x, y; _ <= m; _++){
    cin >> op >> x;
    if(op == 1){
      cin >> c;
      update(1, n, 1, x, c, 0);
      update(1, n, 1, n - x + 1, c, 1);
    }else{
      cin >> y;
      cout << (check(x, y) ? "Yes\n" : "No\n");
    }
  }
  return 0;
}