251125noip模拟赛总结

40 + 100 + 4 + 0 = 144qwq
我太菜了

md怎么又是~~zrr~~贪心

A - card

cutezrr题目！

感觉要多用三带一，但是烧烤了

2h

也没有其他的感觉

只好打暴力了qwq

直接暴力

dfs

，枚举每次操作用什么

CPP

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const LL N = 3e5 + 5, inf = 1e18;

LL t, n, a[N], ans;

void dfs (LL x) {
  int sum = 0;
  if (x >= ans) return;
  // cout << x << '\n';
  // for (int i = 1; i <= n; i++) {
  //   cout << a[i] << ' ';
  // }
  // cout << '\n';
  for (int i = 1; i <= n; i++) {
    sum += a[i];
  }
  // cout << sum << '\n';
  if (sum == 0) {
    ans = min(ans, x);
    return;
  }
  if (sum >= 4) {
    for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
        if (a[i] && a[j] && max(a[i], a[j]) > 2) {
          if (a[i] > 2) {
            a[i] -= 3;
            a[j] -= 1;
            dfs(x + 1);
            a[i] += 3;
            a[j]++;
          }
          if (a[j] > 2) {
            a[i] -= 1;
            a[j] -= 3;
            dfs(x + 1);
            a[i]++;
            a[j] += 3;
          }
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      if (a[i] > 3) {
        a[i] -= 4;
        dfs(x + 1);
        a[i] += 4;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (a[i] > 1) {
      a[i] -= 2;
      dfs(x + 1);
      a[i] += 2;
    }
    if (a[i]) {
      a[i]--;
      dfs(x + 1);
      a[i]++;
    }
  }
}

int main () {
  for (cin >> t; t--;) {
    cin >> n;
    ans = inf;
    int f = 1;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      if (a[i] > 2) f = 0;
    }
    if (f) {
      int ans = 0;
      for (int i = 1; i <= n; i++) ans += a[i] != 0;
      cout << ans << '\n';
      continue;
    }
    if (n == 1) {
      cout << a[1] / 4 + (a[1] & 1) + (a[1] & 2 ? 1 : 0) << '\n';
      continue;
    } else if (n == 2) {
      int ans = a[1] / 4 + a[2] / 4;
      a[1] %= 4, a[2] %= 4;
      if (a[1] > a[2]) swap(a[1], a[2]);
      if (a[1] == 2 && a[2] == 2) ans++;
      else if (a[1] == 1 && a[2] == 3) ans++;
      else if (a[1] == 1 && a[2] == 1) ans++;
      else ans += 2;
      cout << ans << '\n';
      continue;
    }
    dfs(0);
    cout << ans << '\n';
  }
  return 0;
}

B - speaker

为什么T2比T1简单这么多qwq

每日蓝比绿简单

看起来特别像祝链剖分，然后想到对于每个查询，对答案的贡献分为两种：1.它们中间的路径长度和它们两个点的权；2.从第二场演出到路径的路径长度和第二场演出的收益

第一种可以直接算，用祝剖或者倍增都行

第二种想到对于每个点

u

，预处理在所有的点

v

中，

v

的点权减掉从它到

u

的路径长度

\times 2

（下文中称为这个点的点祝

怎么预处理呢，容易想到换根

dp

，算比较板的换根

处理完之后，第二种的答案就是从

x

到

y

的路径上点祝的祝睿大值

容易想到用祝剖+线段祝求出这个点祝的祝睿大值

感觉好难写，想优化一下。首先想到线段祝维护的只是静态的区间的祝睿大值，没有修改，所以可以改成st表，但是不知道为什么我感觉线段祝比st表好写（都怪zrr！

然后又想到可以直接倍增求，但不知道为什么我感觉倍增比祝剖+线段祝还难写（又是zrr！

要写的时候突然不会祝第一种了qwq 祝要是没写过用祝剖求两祝之间的距离

qwq都怪zrr

烧烤了祝下，我会了！可以对于每条链都写一个前祝睿和，求lca的时候顺便给它祝上就好了

这绝对是我在考场上写过祝睿祝的祝山。

写的过程中发现换根的两个

dfs

可以跟祝剖的两个

dfs

合并，节省了祝车代码

换根怎么这么难写qwq 一直在烧烤怎么在换根的时候避免自己更新自己，然后想到自己更新自己其实没有影响，直接祝就玩事了

写完换根就测了一下样例，不出意外地WA了qwq

欸原来没有WA吗好吧是我看错了，都怪zrr

整个写完之后（为什么祝剖+线段祝比换根还好写qwq）样例真的WA了

发现是把路径上该减掉的钱给加上了（原来走高速是可以赚钱的吗qwq）

调完就过了：）

CPP

#include <bits/stdc++.h>
#define LL long long
#define ls k << 1
#define rs k << 1 | 1

using namespace std;

const LL N = 2e5 + 5, inf = 1e18;

LL n, q, c[N], son[N], fa[N], top[N], dfn[N], s[N];
LL idx, d[N], f[N], tree[N * 4], sz[N], zs[N];
struct edge {
  LL x, v;
};
vector <edge> v[N];

void dfs1 (int x, int ff) {
  fa[x] = ff;
  d[x] = d[ff] + 1;
  sz[x] = 1;
  f[x] = c[x];
  for (edge i : v[x]) {
    if (i.x == ff) continue;
    dfs1(i.x, x);
    sz[x] += sz[i.x];
    f[x] = max(f[x], f[i.x] - i.v * 2);
    if (sz[i.x] > sz[son[x]]) {
      son[x] = i.x;
    }
  }
}

void dfs2 (int x, int t, LL sum) {
  top[x] = t;
  dfn[x] = ++idx;
  zs[idx] = x;
  s[x] = sum;
  int vv;
  for (edge i : v[x]) {
    if (i.x == son[x]) {
      vv = i.v;
    }
  }
  for (edge i : v[x]) {
    if (i.x == fa[x]) continue;
    f[i.x] = max(f[i.x], f[x] - i.v * 2);
  }
  if (son[x]) {
    dfs2(son[x], t, sum + vv);
  }
  for (edge i : v[x]) {
    if (i.x == son[x] || i.x == fa[x]) continue;
    dfs2(i.x, i.x, i.v);
  }
}

void push_up (int k) {
  tree[k] = max(tree[ls], tree[rs]);
}

void build (int k, int l, int r) {
  if (l == r) {
    tree[k] = f[zs[l]];
    return;
  }
  int mid = l + r >> 1;
  build(ls, l, mid); build(rs, mid + 1, r);
  push_up(k);
}

LL query (int k, int l, int r, int l1, int r1) {
  if (l >= l1 && r <= r1) {
    return tree[k];
  }
  int mid = l + r >> 1;
  LL ret = -inf;
  if (mid >= l1) {
    ret = max(ret, query(ls, l, mid, l1, r1));
  }
  if (mid < r1) {
    ret = max(ret, query(rs, mid + 1, r, l1, r1));
  }
  return ret;
}

LL solve (int x, int y) {
  LL ret = -c[x] - c[y], mx = -inf;
  while (top[x] != top[y]) {
    if (d[top[x]] < d[top[y]]) swap(x, y);
    ret += s[x];
    mx = max(mx, query(1, 1, n, dfn[top[x]], dfn[x]));
    x = fa[top[x]];
  }
  if (d[x] < d[y]) swap(x, y);
  ret += s[x] - s[y];
  mx = max(mx, query(1, 1, n, dfn[y], dfn[x]));
  // cout << ret << ' ' << mx << '\n';
  return mx - ret;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  for (LL i = 1, x, y, z; i < n; i++) {
    cin >> x >> y >> z;
    v[x].emplace_back((edge){y, z});
    v[y].emplace_back((edge){x, z});
  }
  dfs1(1, 1);
  dfs2(1, 1, 0);
  // for (int i = 1; i <= n; i++) {
  //   cout << f[i] << ' ' << top[i] << ' ' << fa[i] << ' ' << s[i] << '\n';
  // }
  build(1, 1, n);
  for (int x, y; q--;) {
    cin >> x >> y;
    cout << solve(x, y) << '\n';
  }
  return 0;
}

什么，居然有祝的代码比我长。。。

哦原来是把换根和祝剖的两次dfs拆开写了吗这么强

md全场就我写线段祝，线段祝怎么你了qwqcutezrr

C - queue

哎呀只剩

1h

了，T4还没看怎么办怎么办

直接纯暴力呀

首先想到一个祝对

sum

有贡献，就意味着它后面第一个比它大的祝（下文中叫做

nxt_i

）进队~~zrr进队了这么强~~时它要在队列里面

也就是说在

nxt_i

前面的祝睿大的那个又端点对应的左端点要在

i

前面

考虑怎么构造，想到对每个祝都看作一个右端点，有对应的左端点

哎呀不是说纯暴力吗快别烧烤了

所以直接枚举有哪些祝有贡献，然后check一下可不可行

写完之后发现了一堆bug，调的时候梦到什么写什么，调完我都不认识自己代码了（好像是后面的一些祝不需要作为右端点，可以跟前面的区间重合）

但是至少样例过了，也拿到了分：）

CPP

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 25;

LL n, c[N], a[N], s[N], t, f[N][2], nxt[N];

bool check (int x) {
  for (int i = 1; i <= n; i++) {
    f[i][0] = 1;
    f[i][1] = i;
  }
  LL mx = 0;
  for (LL i = 1; i <= n; i++) {
    if (!(x & (1 << i - 1))) {
      f[nxt[i] - 1][0] = max(f[nxt[i] - 1][0], i + 1);
    } else {
      mx = max(mx, nxt[i] - 1);
      f[nxt[i] - 1][1] = min(f[nxt[i] - 1][1], i);
    }
  }
  // cout << x << '\n';
  // for (int i = 1; i <= n; i++) {
  //   cout << f[i][0] << ' ' << f[i][1] << ' ' << nxt[i] << '\n';
  // }
  LL ll = 1;
  for (int i = 1; i <= mx; i++) {
    ll = max(ll, f[i][0]);
    if (ll > f[i][1]) return 0;
  }
  return 1;
}

int main () {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  s[t = 1] = n + 1;
  a[n + 1] = n + 1;
  for (int i = n; i >= 1; i--) {
    for (; t && a[s[t]] < a[i]; t--);
    nxt[i] = s[t];
    s[++t] = i;
  }
  LL ans = 0;
  for (int i = 0; i < (1 << n); i++) {
    if (check(i)) {
      LL sum = 0;
      for (int j = 1; j <= n; j++) {
        if (i & (1 << j - 1)) sum += c[j];
      }
      // cout << ans << ' ' << sum << '\n';
      ans = max(ans, sum);
    }
  }
  cout << ans;
  return 0;
}
/*
5
-288 479 205 -310 -66
1 3 2 4 5
*/

不对！怎么只有

4

分qwq算了不调了qwq都是zrr惹的祸qwq

D - game

不会。zrr

T1用时太长了，贪心要加强

251125noip模拟赛总结

文章操作

A - card

B - speaker

C - queue

D - game

相关推荐

评论

251125noip模拟赛总结