首页 > 其他分享 >JOI 2020 Final

JOI 2020 Final

时间：2024-10-04 20:49:30浏览次数：1  
标签：ui le min int 2020 JOI Inf Final dis

A - 長いだけのネクタイ (Just Long Neckties)

JOI 公司开了一个派对。有 \(n + 1\) 条领带，第 \(i\) 条领带的长度是 \(a_i\)。有 \(n\) 名员工，第 \(i\) 名员工适合长度不超过 \(b_i\) 的领带。
对于一种将 \(n\) 条领带配对给 \(n\) 的人的方案，设第 \(i\) 条领带匹配了第 \(j\) 个人，则我们称派对的奇怪值为 \(\max(a_i - b_j, 0)\) 的最大值。
现在 \(\forall i \in [1, n + 1]\)，你需要求出，若移除第 \(i\) 条领带，将剩下的领带和员工配对，最小的奇怪值是多少。
\(n \le 2 \times 10^5\)。

首先如果人和领带的集合确定，那么将 \(a\) 和 \(b\) 分别排序后顺次配对一定最优。

那么我们将 \(a\) 和 \(b\) 排序，每次相当于一段前缀正常匹配，然后去掉一个位置，然后后缀继续匹配。那么我们做一个前缀 \(\max\) 和一个后缀 \(\max\)，然后拼一下即可。

时间复杂度 \(O(n \log n)\)。

Code 
#include <iostream>
#include <algorithm>

using namespace std;
using Pii = pair<int, int>;

const int N = 2e5 + 5; 

int n, ans[N];
Pii a[N];
int b[N], pre[N], suf[N];

int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n + 1; ++i) {
    cin >> a[i].first, a[i].second = i; 
  }
  sort(a + 1, a + n + 2);
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
  }
  sort(b + 1, b + n + 1);
  for (int i = 1; i <= n; ++i) {
    pre[i] = max(pre[i - 1], a[i].first - b[i]);
  }
  for (int i = n + 1; i >= 2; --i) {
    suf[i] = max(suf[i + 1], a[i].first - b[i - 1]); 
  } 
  for (int i = 1; i <= n + 1; ++i) {
    ans[a[i].second] = max(pre[i - 1], suf[i + 1]);
  }
  for (int i = 1; i <= n + 1; ++i) {
    cout << ans[i] << ' '; 
  }
  cout << '\n';
  return 0; 
}

B - JJOOII 2 (JJOOII 2)

我们称由 \(k\) 个 \(\texttt{J}\)，\(k\) 个 \(\texttt{O}\)，\(k\) 个 \(\texttt{I}\) 顺次拼接得到的字符串称为 \(k\) 阶 \(\texttt{JOI}\) 串。
给定一个长度为 \(n\) 的字符串 \(s\) 和整数 \(k\)，你可以进行以下三种操作：

  • 删除 \(s\) 中开头的字符，代价为 \(0\)。
  • 删除 \(s\) 中结尾的字符，代价为 \(0\)。
  • 删除 \(s\) 中任意位置的字符，代价为 \(1\)。

求将 \(s\) 变成 \(k\) 阶 \(\texttt{JOI}\) 串的最小代价。
\(1 \le n \le 2 \times 10^5\)。

我们钦定 \(s\) 的一个子序列为答案，假设子序列的第一个元素为 \(s_l\)，最后一个元素为 \(s_r\)，显然不在 \([l, r]\) 中的可以以 \(0\) 的代价删除。于是题意可转化为求一个子串 \(s[l, r]\)，使得其包含一 \(k\) 阶 \(\texttt{JOI}\) 串作为子序列，最小化 \((r -l + 1) - 3k\)。

枚举该子串的开头位置 \(l\)，现在从左往右直接匹配 \(k\) 阶 \(\texttt{JOI}\) 串最优。双指针预处理 \(nx_{i, 0/1/2}\) 表示从 \(i\) 开始的第 \(k\) 个 \(\texttt{J/O/I}\) 出现在什么位置，即可加速子序列匹配。

时间复杂度 \(O(n)\)。

Code 
#include <iostream>

using namespace std;

const int N = 2e5 + 5; 

int n, k, a[N], nx[3][N];

int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    char s;
    cin >> s;
    a[i] = (s == 'J' ? 0 : (s == 'O' ? 1 : 2));
  }
  for (int o = 0; o < 3; ++o) {
    for (int i = 1, j = 0, cnt = 0; i <= n + 1; ++i) {
      while (j < n && cnt < k) {
        ++j;
        cnt += a[j] == o;
      }
      nx[o][i] = (cnt == k ? j : n + 1);
      cnt -= a[i] == o;
    }
  }
  int ans = N;
  for (int i = 1; i <= n; ++i) {
    int j = i - 1; 
    for (int o = 0; o < 3 && j != n + 1; ++o) {
      j = nx[o][j + 1];
    }
    if (j != n + 1) 
      ans = min(ans, j - i + 1);
  }
  cout << (ans == N ? -1 : ans - k * 3) << '\n';
  return 0; 
}

C - スタンプラリー 3 (Collecting Stamps 3)

有 \(n\) 个雕像坐落在一个长度为 \(l\) 的环上，第 \(i\) 个雕像的位置为 \(a_i\)，出现时间为 \([0, b_i]\)。
你现在从位置 \(0\) 开始以 \(1\) 的速度行走，求最多能收集到多少雕像。
\(n \le 200\)，\(1 \le a_i \le l \le 10^9\)。

显然可以区间 \(\text{dp}\)，由于时间（距离）维度很大，我们将其设为最优化属性。

设 \(f_{i, j, k, 0/1}\) 表示当前尝试收集过 \(i\) 以前和 \(j\) 以后的蜡像，收集成功了 \(k\) 个，位于第 \(i/j\) 个蜡像处的最小时间。转移只有两种选择，代价是 \(O(1)\) 的。

时间复杂度 \(O(n^3)\)。

Code 
#include <iostream>

using namespace std;
using LL = long long;
using Pii = pair<int, int>;

const int N = 205;
const LL Inf = 1e12;

int n, l, a[N], b[N];
LL f[N][N][N][2];

int Dis (int x, int y) {
  int d = abs(x - y);
  return min(d, l - d);
}

int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> l; 
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  } 
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
  }
  fill(f[0][0][0], f[n + 1][n + 1][n] + 2, Inf);
  f[0][n + 1][0][0] = 0; 
  for (int l = n + 1; l >= 2; --l) {
    for (int i = 0, j = i + l; j <= n + 1; ++i, ++j) {
      for (int k = 0; k < n; ++k) {
        for (int l = 0; l < 2; ++l) {
          int cur = (!l ? a[i] : a[j]);
          for (int l0 = 0; l0 < 2; ++l0) {
            int p = (!l0 ? i + 1 : j - 1);
            LL d = f[i][j][k][l] + Dis(cur, a[p]);
            int k0 = k + (d <= b[p]);
            auto f0 = (!l0 ? f[i + 1][j] : f[i][j - 1]);
            f0[k0][l0] = min(f0[k0][l0], d);
          }
        }
      }   
    }
  }
  int ans = 0;
  for (int i = 0; i <= n; ++i) {
    for (int k = 0; k <= n; ++k) {
      for (int l = 0; l < 2; ++l) {
        if (f[i][i + 1][k][l] < Inf) {
          ans = max(ans, k);
        }
      }
    }
  }
  cout << ans << '\n';
  return 0; 
}

D - オリンピックバス (Olympic Bus)

给定一张 \(n\) 个结点 \(m\) 条边的图，你可以进行如下操作至多一次：

  • 选择第 \(i\) 条边将其翻转 （\(u \rightarrow v\) 变成 \(v \rightarrow u\)），代价为 \(d_i\)。

然后你在图上从结点 \(1\) 开始行走，走第 \(i\) 条边的代价为 \(w_i\)，求走出一条路径 \(1 \rightarrow n \rightarrow 1\) 的最小代价。
\(1 \le n \le 200, 1 \le m \le 5 \times 10^4\)。

首先对原图求一遍最短路（可使用 \(\text{Floyd}\)），若不进行翻转边的操作，则总代价为 \(dis(1, n) + dis(n, 1)\)。

接下来考虑可以翻转边的情况，容易想到枚举一条边，然后重跑 \(O(n^2)\) 的 \(\text{Dijkstra}\)，但这样时间复杂度是 \(O(mn^2)\)，无法接受。

但是显然并不是所有边都需要重跑最短路。我们拉出以 \(1/n\) 为根，正图/反图的最短路树，则至少在一棵最短路树上的边只有 \(O(n)\) 条。

具体而言，我们对所有边分情况讨论：

  • 若它在某一棵最短路树上，则这样的边只有 \(O(n)\) 条，我们沿用前面的算法，重跑 \(\text{Dijkstra}\) 即可。
  • 若它不在任意一棵最短路树上，则关于 \(1/n\) 的所有最短路不会改变，此时大力分类讨论即可求出 \(dis(1, n)\) 和 \(dis(n, 1)\)。

时间复杂度 \(O(n^3)\)。

Code 
#include <iostream>
#include <vector>
#include <set>
#include <numeric>
#include <algorithm>

using namespace std;
using ui = unsigned int; 
using Pii = pair<int, int>; 

const int N = 205;
const ui Inf = 1.3e9;

int n, m, p[N];
ui e[N][N], e1[N][N], e2[N][N], e3[N][N], g[N][N];
ui dis[N][N];
set<Pii> s;

namespace Dijkstra {
  ui Solve (ui e[N][N]) {
    vector<ui> dis(n + 1, Inf);
    vector<bool> vis(n + 1);
    dis[1] = 0; 
    for (int t = 1; t <= n; ++t) {
      int u = 0; 
      for (int i = 1; i <= n; ++i) {
        if (!vis[i] && (!u || dis[i] < dis[u])) {
          u = i; 
        }
      }
      vis[u] = 1; 
      for (int v = 1; v <= n; ++v) {
        dis[v] = min(dis[v], dis[u] + e[u][v]);
      }
    }
    ui ans = dis[n];
    fill(dis.begin(), dis.end(), Inf);
    fill(vis.begin(), vis.end(), 0);
    dis[n] = 0; 
    for (int t = 1; t <= n; ++t) {
      int u = 0; 
      for (int i = 1; i <= n; ++i) {
        if (!vis[i] && (!u || dis[i] < dis[u])) {
          u = i; 
        }
      }
      vis[u] = 1; 
      for (int v = 1; v <= n; ++v) {
        dis[v] = min(dis[v], dis[u] + e[u][v]);
      }
    }
    ans += dis[1];
    return min(ans, Inf);
  }
}

void Build (int o) {
  auto add = [&](int x, int y) -> void {
    if (o & 1) swap(x, y);
    s.insert({x, y});
  };
  auto ev = [&](int x, int y) -> ui {
    if (o & 1) swap(x, y);
    return e[x][y]; 
  };
  int s = (o <= 1 ? 1 : n);
  vector<bool> vis(n + 1);
  vector<int> pre(n + 1);
  vector<ui> dis(n + 1, Inf);
  dis[s] = 0;
  for (int t = 1; t <= n; ++t) {
    int u = 0; 
    for (int i = 1; i <= n; ++i) {
      if (!vis[i] && (!u || dis[i] < dis[u])) {
        u = i; 
      }
    }
    vis[u] = 1; 
    if (pre[u]) {
      add(pre[u], u);
    }
    for (int v = 1; v <= n; ++v) {
      ui d = dis[u] + ev(u, v);
      if (d < dis[v]) {
        dis[v] = d, pre[v] = u; 
      }
    } 
  }
}

int main () {
  // freopen("01-13.in", "r", stdin);
  // freopen("01-13.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  fill(e[0], e[n] + n + 1, Inf);
  fill(e1[0], e1[n] + n + 1, Inf);
  fill(e2[0], e2[n] + n + 1, Inf);
  fill(e3[0], e3[n] + n + 1, Inf);
  for (int i = 1, u, v, w, d; i <= m; ++i) {
    cin >> u >> v >> w >> d;
    e2[u][v] = min(e2[u][v], ui(w) + e1[u][v]);
    e2[u][v] = min(e2[u][v], ui(w) + d + e[u][v]);
    e[u][v] = min(e[u][v], ui(w));
    e1[u][v] = min(e1[u][v], ui(w) + d);
    e3[u][v] = min(e3[u][v], ui(w) * 2 + d);
  }
  fill(dis[0], dis[n] + n + 1, Inf);
  for (int i = 1; i <= n; ++i) {
    dis[i][i] = 0; 
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      dis[i][j] = min(dis[i][j], e[i][j]);
      g[i][j] = e[i][j];
    }
  }
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) { 
      for (int j = 1; j <= n; ++j) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    } 
  }
  for (int o = 0; o < 4; ++o) {
    Build(o);
  }
  ui ans = min(Inf, dis[1][n] + dis[n][1]);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (i == j) continue;
      if (s.count({i, j})) {
        g[i][j] = Inf, g[j][i] = 0; 
        ans = min(ans, Dijkstra::Solve(g) + e1[i][j]);
        g[i][j] = 0;
        ans = min(ans, Dijkstra::Solve(g) + e2[i][j]);
        g[i][j] = e[i][j], g[j][i] = e[j][i];
      }
      else {
        auto s = [&](ui a, ui b, ui c) -> ui {
          return min(Inf, a + b + c);
        }; 
        ans = min(ans, min(s(dis[1][j], dis[i][n], dis[n][1]), s(dis[1][n], dis[n][j], dis[i][1])) + e1[i][j]);
        for (int o = 0; o < 2; ++o) {
          int u = 1, v = n;
          if (o) swap(u, v);
          ui l0 = min(dis[u][i] + dis[i][u], Inf), l1 = min(dis[v][j] + dis[j][v], Inf);
          ans = min(ans, l0 + l1 + e2[i][j]);
        }
        ans = min(ans, min(Inf, dis[1][j] + dis[i][n]) + min(Inf, dis[n][j] + dis[i][1]) + e3[i][j]);
      }
    }
  }
  cout << int(ans == Inf ? -1 : ans) << '\n';
  return 0; 
}

E - 火事 (Fire)

有一个序列，给定它在 \(0\) 时刻的形态 \(a_1, a_2, \ldots, a_n\)，之后每过一单位时间，这个序列会同时发生 \(\forall i \in [1, n], a_i \gets \max(a_{i - 1}, a_i)\) 的变化。
有 \(q\) 次询问，每次询问给定 \(t, l, r\)，求在 \(t\) 时刻末的 \(\sum\limits_{i = l}^{r} a_i\)。

显然由于是类似 \(\text{checkmax}\) 的操作，所以序列中的所有值只会不断变大，所以我们考虑维护元素相对与初始值的增量。而原序列的贡献可以前缀和简单维护。

考虑如何刻画增量形式。一个位置 \(i\) 在 \(t\) 时刻相当于给 \([i, i + t]\) 施加了一个 \(\text{checkmax}\)。那么在这个区间中的数就可能会变大。

那么对于一个位置 \(i\)，它第一次会被 \(L_i\) 覆盖。其中 \(L_i\) 表示 \(i\) 左边第一个比 \(i\) 大的数，可以单调栈线性求出。被覆盖后可以认为 \(i\) 所在连续段合并到了 \(L_i\) 所在的连续段。

于是考虑 \(i\) 和 \(L_i\) 合并的过程。开始时间显然是 \(L_i - i\)，此时对位置 \(i\) 的值有 \(a_{L_i} - a_i\) 的增量，然后第 \(L_i - i + 1\) 秒会对 \(i + 1\) 的值也有 \(a_{L_i} - a_{i}\) 的增量（此处钦定了 \(a_{i + 1} < a_i\)，那么 \(i + 1\) 已经被 \(i\) 合并），一直重复这个过程，直到 \(R_i\) 为止，其中 \(R_i\) 表示 \(i\) 右边第一个比 \(i\) 大的数。

我们将上面过程写成形式化的语言：\((l, r, t_0, v) = (i, R_i - 1, i - L_i, a_{L_i} - a_i)\)，在 \(t_0\) 时刻将 \(a_l \gets a_l + v\)，在 \(t_0 + 1\) 时刻将 \(a_{l + 1} \gets a_{l + 1} + v\)，以此类推。

然后询问的形式可以描述为三元组 \((l, r, t)\) 的形式，表示查询 \(t\) 时刻 \(\sum\limits_{i = l}^{r} a_i\) 的值。那么我们就将原问题抽象成了一个较为形式化的数据结构问题。

再做一些转化，容斥一下，将前面修改的四元组 \((l, r, t_0, v)\) 改为 \((l, t_0, v)\) 的形式，即没有 \(r\) 的限制，这样会好看一点。具体的，\((l, r, t_0, v)\) 可以拆成 \((l, t_0, v)\) 和 \((r + 1, t_0 + r - l, -v)\)。

对询问也拆一下，变成 \((p, t)\) 的形式，表示查询 \(t\) 时刻 \(\sum\limits_{i = 1}^{n} a_p\) 的值。

在对序列做个前缀和，修改可重写为在 \(t_0\) 时刻 \([l, n]\) 一段后缀 \(+v\)，\(t_0 + 1\) 时刻 \([l + 1, n]\) 一段后缀 \(+v\)，以此类推。查询重写为 \(t\) 时刻 \(a_p\) 的值。

直接模拟这个操作相当于二维平面上的三角形 \(+v\)，也不好做。你那你考虑算一次修改 \((l, t_0, v)\) 对一次询问 \((p, t)\) 给贡献，我们发现这个贡献是 \(\max(0, \min(p - l + 1, t - t_0 + 1)) v\)。

这个看起来清新很多，我们令 \(p \gets p + 1, t \gets t + 1\)，然后把 \((l, t_0)\) 和 \((p, t)\) 分别看成平面直角坐标系上的点。对于一个修改点 \((x_u, y_u, v)\) 和一个查询点 \((x_q, y_q)\)，贡献为 \(\max(0, \min(x_q - x_u, y_q - y_u))v\)。

这个很想三维偏序，但稍微想想就知道其实是二维偏序，因为只有以下两种情况有贡献：

  • \(0 \le x_q - x_u \le y_q - y_u\)，贡献为 \((x_q - x_u)v\)。
  • \(0 \le y_q - y_u < x_q - x_u\)，贡献为 \((y_q - y_u)v\)。

这个扫描线 + 树状数组或者 \(\text{CDQ}\) 即可。我懒得讨论负数下标和值域范围，所以选了 \(\text{CDQ}\)。

时间复杂度 \(O(n \log n)\)。

Code 
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
using LL = long long;

const int N = 2e5 + 5; 

int n, q, m; 
int a[N], L[N], R[N];
LL ans[N], pre[N];

struct Node {
  int x, y, val, id;
} v[N * 4], tmp[N * 4];

void Solve1 (int l, int r) {
  if (l == r) return; 
  int mid = (l + r) >> 1;
  Solve1(l, mid);
  Solve1(mid + 1, r);
  LL cnt = 0, sum = 0; 
  for (int i = l, j = l, k = mid + 1; i <= r; ++i) {
    if (j != mid + 1 && (k == r + 1 || v[j].x - v[j].y >= v[k].x - v[k].y)) {
      tmp[i] = v[j++];
      if (!tmp[i].id) {
        cnt += tmp[i].val, sum += 1ll * tmp[i].x * tmp[i].val;
      }
    }
    else {
      tmp[i] = v[k++];
      if (tmp[i].id) {
        ans[tmp[i].id] += tmp[i].val * (tmp[i].x * cnt - sum);
      }
    }
  }
  copy(tmp + l, tmp + r + 1, v + l);
}

void Solve2 (int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  Solve2(l, mid);
  Solve2(mid + 1, r);
  LL cnt = 0, sum = 0; 
  for (int i = l, j = l, k = mid + 1; i <= r; ++i) {
    if (j != mid + 1 && (k == r + 1 || v[j].x - v[j].y < v[k].x - v[k].y)) {
      tmp[i] = v[j++];
      if (!tmp[i].id) {
        cnt += tmp[i].val, sum += 1ll * tmp[i].y * tmp[i].val;
      }
    }
    else {
      tmp[i] = v[k++];
      if (tmp[i].id) {
        ans[tmp[i].id] += tmp[i].val * (tmp[i].y * cnt - sum);
      }
    }
  } 
  copy(tmp + l, tmp + r + 1, v + l);
} 

int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q; 
  for (int i = 1; i <= n; ++i) {
    cin >> a[i], pre[i] = pre[i - 1] + a[i];
  }
  stack<int> s;
  for (int i = 1; i <= n; ++i) {
    while (!s.empty() && a[i] > a[s.top()]) {
      R[s.top()] = i;
      s.pop();
    }
    if (!s.empty()) L[i] = s.top();
    s.push(i);
  }
  while (!s.empty()) {
    R[s.top()] = n + 1;
    s.pop();
  }
  for (int i = 1; i <= n; ++i) {
    if (L[i]) {
      v[++m] = Node({i, i - L[i], a[L[i]] - a[i], 0});
      v[++m] = Node({R[i], R[i] - L[i], a[i] - a[L[i]], 0});
    }
  }
  for (int i = 1, t, l, r; i <= q; ++i) {
    cin >> t >> l >> r;
    ans[i] = pre[r] - pre[l - 1];
    v[++m] = Node({r + 1, t + 1, 1, i});
    v[++m] = Node({l, t + 1, -1, i});
  } 
  sort(v + 1, v + m + 1, [&](Node a, Node b) -> bool {
    return a.x < b.x;
  });
  Solve1(1, m);
  sort(v + 1, v + m + 1, [&](Node a, Node b) -> bool {
    return a.y < b.y;
  }); 
  Solve2(1, m);
  for (int i = 1; i <= q; ++i) {
    cout << ans[i] << '\n';
  }
  return 0; 
}

标签：ui,le,min,int,2020,JOI,Inf,Final,dis
From： https://www.cnblogs.com/hztmax0/p/18444443

相关文章

  • 信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重
    PDF文档公众号回复关键字:202410041P7074[CSP-J2020]方格取数[题目描述]设有n×m的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中......
  • [题解]P7077 [CSP-S2020] 函数调用
    P7077[CSP-S2020]函数调用题意简述给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\)，给定\(m\)个函数，每个函数可能是下面\(3\)种类型，用\(T_x\)表示函数\(x\)的类型：\(T_x=1\)，对下标\(p\)增加\(v\)。\(T_x=2\)，对所有元素乘\(v\)。\(T_x=3\)，由若干类型\(1\)和类型\(2\)组成......
  • Codeforces2020D Connect the Dots(观察 + 并查集 + 差分)
    题意多组数据。数轴上有\(n\)个点，编号为\(1\simn\)，对这些点做$m$次操作。每次操作给出三个整数\(a_i(1\lea_i\len)\\\d_i(1\led_i\le10)\\\k_i(0\lek_i\len)\)。将点\(a_i,a_i+d_i,a_i+2\timesd_i,a_i+3\timesd_i,\cdot\cdot\cdo......
  • 信息学奥赛复赛复习10-CSP-J2020-03表达式求值-栈、后缀表达式、isdigit函数、c_str函
    PDF文档公众号回复关键字:202410031P7073[CSP-J2020]表达式[题目描述]小C热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为0或1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的......
  • 题解：P9788 [ROIR 2020 Day2] 区域规划
    法1枚举\(a,b,c\)，考虑到\(c\)的最小值为\(\max(1,\frac{(a\cdotb−n)}{b})\)，所以直接剪枝即可通过。代码：#include<bits/stdc++.h>usingnamespacestd;intans,n,m;intmain(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(i......
  • 信息学奥赛复赛复习09-CSP-J2020-03表达式求值前置知识点-中缀表达式求值、摸运算、模
    PDF文档公众号回复关键字:20241002**1P1981[NOIP2013普及组]表达式求值**[题目描述]给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值[输入格式]一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“×”，且没有括号，所有参与运......
  • CF2020(Codeforces Round 976 (Div. 2))
    CF2020A.FindMinimumOperations难度：红转换进制，每一位上数字相加。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llt,n,k,ans;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){cin&......
  • JOI 2018 Final
    A-ストーブ(Stove)有\(n\)个客人将要来访，第\(i\)个客人的来访时间为\([a_i,a_i+1]\)，保证\(\foralli\in[1,n),a_i<a_{i+1}\)。在每个客人来访时，你都需要保证暖炉是亮着的（初始时暖炉为熄灭状态）。你可以在任意时刻熄灭暖炉，但每次点亮都需要消耗一根火柴，且你......
  • Mockito 是借助什么技术来 mock final 类和 final 方法的
    Mockito借助JavaAgent和字节码操作技术来实现对final类和final方法的mock。具体来说，它主要依赖于以下两个关键技术：1.JavaAgent(InstrumentationAPI)Mockito通过使用JavaAgent来实现运行时的字节码操作，这允许在程序加载类时修改类的字节码行为，从而突破final......
  • 信息学奥赛复赛复习08-CSP-J2020-03表达式前置知识点-后缀表达式、栈、字符读取
    PDF文档公众号回复关键字:202410011P1449后缀表达式[题目描述]所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）本题中运算符仅包含+-*/。保证对于/运算......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99