首页 > 其他分享 >河南萌新联赛2024第（三）场：河南大学

河南萌新联赛2024第（三）场：河南大学

时间：2024-08-01 22:30:37浏览次数：12  
标签：i64 河南大学 int cin long 2024 萌新 using dp

河南萌新联赛2024第（三）场：河南大学

前言

这场应该算是比较简单的了，隔壁都有佬 ak 了，咱只有 8t，还是得加训。

A-圆周率日挑战_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

Python 最有用的一集。

抄了个 500 行的浮点高精度代码爆内存了，改了两个小时也没过，崩溃。

代码

n = int(input())
pi = 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
arr = []
for i in range(n):
    p, a4 = map(int, input().split())
    arr.append((abs(p * (10**100) // a4 - pi), p, a4))
arr.sort()
print(arr[0][1], arr[0][2])

B-正则表达式_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

按题意模拟。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n;
   cin >> n;

   int ans = 0;
   for(int i = 0;i < n;i ++){
      int x[4]{};
      char c;
      cin >> x[0] >> c >> x[1] >> c >> x[2] >> c >> x[3];

      bool f = 1;
      for(int j = 0;j < 4;j ++) {
         if(x[j] > 255)
            f = 0;
      }

      ans += f;
   }

   cout << ans << '\n';

   return 0;
}

C-Circle_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

是个找规律题啊，刚开始被样例迷惑了还以为 \(2^{n-1}\) 呢，但是一看数据范围不对啊，结果还是交了一发 wa 了，50 min 后才发现规律 \(\dots\)

官方题解有证明，这里就说下我的结论好了。

\[n=\begin{cases} (n-1)^2+n+1 &\text{if $n$ $\ge$ 0}\\ 1 &\text{if $n$ $=$ 0}\\ \end{cases} \]

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i ++) {
        i64 n;
        cin >> n;

        if (n)
            cout << (n - 1)*(n - 1) + n + 1 << ' ';
        else
            cout << 1 << ' ';
    }

    return 0;
}

D-开心消消乐（Right Version）_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

打表找规律吧，题解好像也给了较严格的证明，不过这种题的话一般来说打表找规律就是了。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        if (a[i] != a[i - 1] && a[i])
            ans ++;
    }

    cout << ans << '\n';

    return 0;
}

E-区间_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

线段树维护最大字段和/ 01 串最大连续 1 的个数模板题。

把白色和黑色看成 1/0 两个数就行了。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

#define lc u << 1
#define rc u << 1 | 1
const int N = 1e5 + 5;
i64 w[N], n, m, p;
struct Tree { //线段树
    int l, r;
    int sum1, lmax1, rmax1, max1;
    int sum0, lmax0, rmax0, max0;
    int tag, rev;
} tr[N << 2];

void cal_lazy(int fa, int ch) {
    int len = tr[ch].r - tr[ch].l + 1;
    if (tr[fa].tag == 0) {
        tr[ch].tag = 0, tr[ch].rev = 0;
        tr[ch].sum0 = tr[ch].lmax0 = tr[ch].rmax0 = tr[ch].max0 = len;
        tr[ch].sum1 = tr[ch].lmax1 = tr[ch].rmax1 = tr[ch].max1 = 0;
    }
    if (tr[fa].tag == 1) {
        tr[ch].tag = 1, tr[ch].rev = 0;
        tr[ch].sum0 = tr[ch].lmax0 = tr[ch].rmax0 = tr[ch].max0 = 0;
        tr[ch].sum1 = tr[ch].lmax1 = tr[ch].rmax1 = tr[ch].max1 = len;
    }
    if (tr[fa].rev) {
        tr[ch].rev ^= 1;
        swap(tr[ch].sum1, tr[ch].sum0);
        swap(tr[ch].lmax1, tr[ch].lmax0);
        swap(tr[ch].rmax1, tr[ch].rmax0);
        swap(tr[ch].max1, tr[ch].max0);
    }
}

void tag_union(int fa, int ch) {
    tr[ch].tag = tr[fa].tag;
    tr[ch].rev ^= tr[fa].rev;
}

void init_lazy(int u) {
    tr[u].tag = -1;
    tr[u].rev = 0;
}

void pushdown(int u) {
    if (tr[u].tag != -1 || tr[u].rev != 0) {
        cal_lazy(u, lc);
        cal_lazy(u, rc);
        // tag_union(u, lc);
        // tag_union(u, rc);
        init_lazy(u);
    }
}

void pushup(int u) { //上传
    tr[u].sum1 = tr[lc].sum1 + tr[rc].sum1;
    tr[u].sum0 = tr[lc].sum0 + tr[rc].sum0;
    tr[u].lmax1 = tr[lc].lmax1 + (tr[lc].sum0 ? 0 : tr[rc].lmax1);
    tr[u].rmax1 = tr[rc].rmax1 + (tr[rc].sum0 ? 0 : tr[lc].rmax1);
    tr[u].lmax0 = tr[lc].lmax0 + (tr[lc].sum1 ? 0 : tr[rc].lmax0);
    tr[u].rmax0 = tr[rc].rmax0 + (tr[rc].sum1 ? 0 : tr[lc].rmax0);
    tr[u].max1 = max({tr[lc].max1, tr[rc].max1, tr[lc].rmax1 + tr[rc].lmax1});
    tr[u].max0 = max({tr[lc].max0, tr[rc].max0, tr[lc].rmax0 + tr[rc].lmax0});
}

void build(int u, int l, int r) { //建树
    tr[u].l = l, tr[u].r = r;
    init_lazy(u);
    if (l == r) {
        int t = 1;
        tr[u] = {l, r, t, t, t, t, t ^ 1, t ^ 1, t ^ 1, t ^ 1, -1, 0};
        return ;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(u);

}

void modify(int u, int l, int r, int op) {
    if (tr[u].l >= l && tr[u].r <= r) {
        int len = tr[u].r - tr[u].l + 1;
        if (op == 0) {
            tr[u].rev = 0, tr[u].tag = 0;
            tr[u].sum0 = tr[u].lmax0 = tr[u].rmax0 = tr[u].max0 = len;
            tr[u].sum1 = tr[u].lmax1 = tr[u].rmax1 = tr[u].max1 = 0;
        } else if (op == 1) {
            tr[u].rev = 0, tr[u].tag = 1;
            tr[u].sum0 = tr[u].lmax0 = tr[u].rmax0 = tr[u].max0 = 0;
            tr[u].sum1 = tr[u].lmax1 = tr[u].rmax1 = tr[u].max1 = len;
        } else {
            tr[u].rev ^= 1;
            swap(tr[u].sum1, tr[u].sum0);
            swap(tr[u].lmax1, tr[u].lmax0);
            swap(tr[u].rmax1, tr[u].rmax0);
            swap(tr[u].max1, tr[u].max0);
        }
        return ;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        modify(lc, l, r, op);
    if (r > mid)
        modify(rc, l, r, op);
    pushup(u);
}

Tree query(int u, int l, int r) { //区查
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (r <= mid) return query(lc, l, r);
    else if (l > mid) return query(rc, l, r);
    else {
        Tree res, L = query(lc, l, mid), R = query(rc, mid + 1, r);
        res.sum1 = L.sum1 + R.sum1;
        res.sum0 = L.sum0 + R.sum0;
        res.lmax1 = L.lmax1 + (L.sum0 ? 0 : R.lmax1);
        res.rmax1 = R.rmax1 + (R.sum0 ? 0 : L.rmax1);
        res.lmax0 = L.lmax0 + (L.sum1 ? 0 : R.lmax0);
        res.rmax0 = R.rmax0 + (R.sum1 ? 0 : L.rmax0);
        res.max1 = max({L.max1, R.max1, L.rmax1 + R.lmax1});
        res.max0 = max({L.max0, R.max0, L.rmax0 + R.lmax0});
        return res;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q;
    cin >> n >> q;

    build(1,1,n);

    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int x;
            cin >> x;
            modify(1,x,x,2);
        }else{
            int l,r;
            cin >> l >> r;

            auto ans = query(1,l,r);
            cout << ans.max1 << '\n';
        }
    }
    
    return 0;
}

F-累加器_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

考虑当 \(x=1,y=1e6\) 时最多只会加 \(1e6\) 次，那么先预处理所有发生改变的次数用下前缀和即可，然后用 \(1\sim x+y\) 变化次数减去 \(1\sim x\) 变化的就是 \(x\sim x+y\) 变化的次数了。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const int N = 2e6;
i64 pre[N + 10];

void solve() {

   int x, y;
   cin >> x >> y;

   cout << pre[x + y] - pre[x] << '\n';

}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int x = 0;
   for (int i = 1; i <= N; i ++, x++) {
      pre[i] += pre[i - 1];
      pre[i] += __builtin_popcount((x + 1)^x);
   }

   int t;
   cin >> t;
   while (t--) {
      solve();
   }

   return 0;
}

G-求值_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

变量有 3 个，不过有限制条件 \(x+y+z=n,0\le x,y,z\) 在，那么就可以用 \(n-x-y\) 代替 \(z\) 了。

即 \(|x\times A+y\times B+(n-x-y)\times C-W|\)，这是个两元一次的方程，因为绝对值的存在，所以其图像是一个V 的单峰函数，想到单峰函数，那么自然是我们的三分出场啦。

枚举 \(x\)，三分 \(y\) ，每次更新最小值即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void solve() {

    i64 a, b, c, n, w;
    cin >> a >> b >> c >> n >> w;

    auto check = [&](i64 mid, i64 x) {
        return abs(x * a + mid * b + (n - mid - x) * c - w);
    };

    i64 ans = LLONG_MAX >> 1;
    for (int i = 0; i <= n; i ++) {

        int l = 0, r = n - i;
        while (l <= r) {
            i64 midl = l + (r - l) / 3;
            i64 midr = r - (r - l) / 3;
            ans = min({ans, check(midl, i), check(midr, i)});
            if (check(midl, i) > check(midr, i))
                l = midl + 1;
            else
                r = midr - 1;
        }
    }

    cout << ans << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

H-魔法_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

赛时想复杂了，其实应该还是蛮简单的，肯定是我太菜了，还得加练。

考虑 dp。

设 \(dp_{i,jk}\) 表示为在 \((i,j)\) 这个位置花费了 \(k\) 次魔法所剩的最大体力值。

转移方程为：

\[dp_{i,j,k}=\max(dp_{i,j,k},dp_{i-1,j,k}-a_{i,j},dp_{i,j-1,k}-a_{i,j}) \]

表示为消耗同次数下从两个方向转移过来，当次数大于 0 的时候还需要考虑直接从两个方向直接用魔法不消耗体力转移过来：

\[dp_{i,j,k}=\max(dp_{i,j,k},dp_{i-1,j,k-1},dp_{i,j-1,k-1})[k>0] \]

\(k\) 最大为 \(n+m\) ，即从一直使用魔法达到 \((n,m)\)。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n, m, h;
   cin >> n >> m >> h;

   vector a(n + 1, vector<int>(m + 1));
   for (int i = 1; i <= n; i ++)
      for (int j = 1; j <= m; j ++)
         cin >> a[i][j];

   vector dp(n + 1, vector<vector<i64>>(m + 1, vector<i64>(n + m + 1)));

   dp[1][1][0] = h;

   for (int i = 1; i <= n; i ++) {
      for (int j = 1; j <= m; j ++) {
         for (int k = 0; k <= n + m; k ++) {
            dp[i][j][k] = max({dp[i][j][k], dp[i - 1][j][k] - a[i][j], dp[i][j - 1][k] - a[i][j]});
            if (k > 0) {
               dp[i][j][k] = max({dp[i][j][k], dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]});
            }
         }
      }
   }

   i64 ans = 0;
   for (int i = 0; i < n + m; i ++)
      if (dp[n][m][i] > 0) {
         ans = i;
         break;
      }

   cout << ans << '\n';

   return 0;
}

I-游戏_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

从 \(1\) 到 n ，无非两种情况：1、从 \(1\) 走可以通过的边到达 \(n\) 。2、从 \(1\) 走到 \(k\) 拿到钥匙后走到 \(n\)。

所以使用两次 dijkstra ，对全 1 的边使用一次，然后从 1 走到 k 后再使用一次，两者取最小值即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct DIJ {
    using i64 = long long;
    using PII = pair<i64, i64>;
    vector<i64> dis;
    vector<vector<PII>> G;

    DIJ() {}
    DIJ(int n) {
        dis.assign(n + 1, 1e18);
        G.resize(n + 1);
    }

    void add(int u, int v, int w) {
        G[u].emplace_back(v, w);
    }

    void dijkstra(int s) {
        priority_queue<PII> que;
        dis[s] = 0;
        que.push({0, s});
        while (!que.empty()) {
            auto p = que.top();
            que.pop();
            int u = p.second;
            if (dis[u] < p.first) continue;
            for (auto [v, w] : G[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    que.push({-dis[v], v});
                }
            }
        }
    }
};

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n,m,k;
   cin >> n >> m >> k;

   DIJ dij(n),dij2(n);

   for(int i = 0;i < m;i ++){
      int u,v,w,st;
      cin >> u >> v >> w >> st;
      if(st){
         dij2.add(u,v,w);
         dij2.add(v,u,w);
      }
      dij.add(u,v,w);
      dij.add(v,u,w);
   }

   dij2.dijkstra(1);
   i64 ans = dij2.dis[n];

   dij.dijkstra(k);

   ans = min(ans,dij2.dis[k]+dij.dis[n]);

   cout << (ans == 1e18 ? -1 : ans) << '\n';

   return 0;
}

J-keillempkill学姐の卷积_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

按题意模拟。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector a(n + 1, vector<i64>(n + 1));
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            cin >> a[i][j];

    vector b(m + 1, vector<int>(m + 1));
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> b[i][j];


    for (int i = 1; i <= m - n + 1; i ++) {
        for (int j = 1; j <= m - n + 1; j ++) {
            int ans = 0;
            for (int l = 1; l + i - 1 <= m && l <= n; l ++) {
                for (int r = 1; r + j - 1 <= m && r <= n; r++)
                    ans += a[l][r] * b[l + i - 1][r + j - 1];
            }

            cout << ans << " \n"[j == m - n + 1];
        }
    }

    return 0;
}

K-暴食之史莱姆_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

考虑一个史莱姆能吃掉的最大应该为两侧小于它体积的第一个的史莱姆能吃掉的个数 + 1，因为吃掉这个更小的史莱姆后其体积就会变成这个小史莱姆的体积，所以小史莱姆能吃多少，那么它就能吃多少，在此基础上还能吃掉小史莱姆。

固定一边，用单调栈维护一下该边比当前史莱姆更小的第一个位置即可。

另一边同理。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n;
   cin >> n;

   vector<int> a(n + 1);
   for (int i = 1; i <= n; i ++)
      cin >> a[i];

   stack<int> st;

   vector<int> dp1(n + 1), dp2(n + 1);

   for (int i = 1; i <= n; i ++) {
      while (st.size() && a[st.top()] > a[i]) {
         st.pop();
      }

      if (st.size()) {
         dp1[i] = max(dp1[i], dp1[st.top()] + 1);
      }

      st.push(i);
   }

   while (st.size())st.pop();
   for (int i = n; i >= 1; i --) {
      while (st.size() && a[st.top()] > a[i]) {
         st.pop();
      }

      if (st.size()) {
         dp2[i] = max(dp2[i], dp2[st.top()] + 1);
      }

      st.push(i);
   }

   for (int i = 1; i <= n; i ++)
      cout << dp1[i] + dp2[i] << " \n"[i == n];

   return 0;
}

L-SSH_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

字符串模拟，稍有点 ex，有点天梯赛那味。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n, q;
    cin >> m >> n >> q;

    map<string, string> p;
    for (int i = 0; i < m; i ++) {
        string a, b;
        cin >> a >> b;
        p[b] = a;
    }

    map<string, set<string>> ipuser;
    map<string, set<string>> has;

    for (int i = 0; i < n; i ++) {
        string ip;
        int k;
        cin >> ip >> k;
        for (int j = 0; j < k; j ++) {
            string loser, pub;
            int t;
            cin >> loser >> t;
            ipuser[ip].insert(loser);
            while (t--) {
                cin >> pub;
                has[ip + loser].insert(pub);
            }
        }
    }

    while (q--) {
        string u, ip, pri;
        cin >> u >> ip >> pri;
        if (ipuser[ip].count(u) && has[ip + u].count(p[pri]))
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}

M-推箱子_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

赛时应该不想那个 dp的，状态设计错了不说，感觉另外两道还稍简单点（？

直接暴力 bfs。

同时搜索箱子和人的位置，当人走到箱子的位置时就和箱子同步移动。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   vector<array<int, 2>> loc(3);
   for (auto &[x, y] : loc)
      cin >> x >> y;

   vector mp(35, vector<int>(35));
   int m;
   cin >> m;
   while (m --) {
      int x, y;
      cin >> x >> y;
      mp[x][y] = 1;
   }

   const int u[] = {1, -1, 0, 0}, v[] = {0, 0, 1, -1};

   queue<array<int, 5>> Q;
   const int N = 35;
   int vis[N][N][N][N] {};

   Q.push({loc[0][0], loc[0][1], loc[2][0], loc[2][1], 0});
   vis[loc[0][0]][loc[0][1]][loc[2][0]][loc[2][1]] = 1;

   while (Q.size()) {
      auto [x1, y1, x3, y3, t] = Q.front();
      Q.pop();

      if (x3 == loc[1][0] && y3 == loc[1][1]) {
         cout << t << '\n';
         return 0;
      }

      for (int i = 0; i < 4; i ++) {
         int dx = x1 + u[i], dy = y1 + v[i];
         int boxx = x3, boxy = y3;
         if (dx > 0 && dx <= 30 && dy > 0 && dy <= 30 && !mp[dx][dy]) {
            if (dx == boxx && dy == boxy) {
               boxx += u[i], boxy += v[i];
            }
            if (boxx > 0 && boxx <= 30 && boxy > 0 && boxy <= 30 && !mp[boxx][boxy] && !vis[dx][dy][boxx][boxy]) {
               Q.push({dx, dy, boxx, boxy, t + 1});
               vis[dx][dy][boxx][boxy] = 1;
            }
         }
      }
   }

   cout << "-1\n";

   return 0;
}

标签：i64,河南大学,int,cin,long,2024,萌新,using,dp
From： https://www.cnblogs.com/Kescholar/p/18337708

相关文章

  • 2024牛客暑期多校训练营6
    Abstract好难qwqA-CakeIdea全是博弈！首先来解释题目意思。phase1：给出一颗树，根节点为1，树上每一条边的权值为0或者1。初始时刻，根节点处有一只小马，小G和小O依次控制小马移动，每次只能向子节点移动，若当前节点是叶节点，phase1结束。在移动的过程中，需要记录经过的边的......
  • 2024牛客暑期多校训练营6 A Cake
    题目大意详细题目传送门\(A\)和\(B\)要从轮流走，从根到一个叶子节点位置，\(A\)先。树有边权\(0,1\)，按照顺序经过的边权按字符串拼接得到一个串\(S\)。现在\(B\)可以把\(1\)拆分成任意个分数（但不能超过\(S\)的长度，且分数可以为空,）两人按照\(S\)串的顺序选取，如果\(S_......
  • 喜报 | 极限科技入选北京市 2024 年第一批科技中小企业名单
    2024年7月24日，北京市科学技术委员会、中关村科技园区管理委员会发布《关于北京市2024年第一批拟入库科技型中小企业名单的公示》。根据《科技型中小企业评价办法》(国科发政〔2017〕115号)和《科技型中小企业评价服务工作指引》(国科火字〔2022〕67号)有关规定，极限数据（北......
  • 2024.8 - 做题记录与方法总结
    2024.8-RecordofQuestionsandSummaryofMethodology先分享一个歌单：永无止境的八月！2024/08/01先来点重量级的P4768[NOI2018]归程题面：[NOI2018]归程题目描述本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个\(n\)个节......
  • 2024暑假集训测试17
    前言比赛链接。T1没加记忆化莫名原因T飞了，T2没做过IO交互不知道咋测样例干脆没交，T3到现在还不知道为啥爆零了，赛时不知道咋合并背包根本不敢打，离线下来寻思快点结果全死了，T4不可做题。还是老毛病，遇到之前见的不多题型（尤其是T1、T2放）就寄，这次T1倒是没卡住（但是挂分......
  • 2024.8.1 test
    A\(n\)个点的完全图，\(i\toj(i<j)\)的边权是\(u_j-u_i\)，问最小生成树。\(n\le3e5\)。考虑boruvka算法。boruvka算法是重复以下过程，直到只有一个连通块。找到所有连通块的连向外面的最小边，并把这些边加入最小生成树。不难发现这是最多做\(\logn\)次的。我们现在考虑......
  • 2024年1月刷题记录
    2024年1月1日【leetcode】1599.经营摩天轮的最大利润题意：你正在经营一座摩天轮，该摩天轮共有4个座舱，每个座舱最多可以容纳4位游客。你可以逆时针轮转座舱，但每次轮转都需要支付一定的运行成本runningCost。摩天轮每次轮转都恰好转动1/4周。给你一个长度为n的......
  • 2024年4月刷题记录
    2024年4月1日【leetcode】2810.故障键盘题意：你的笔记本键盘存在故障，每当你在上面输入字符'i'时，它会反转你所写的字符串。而输入其他字符则可以正常工作。给你一个下标从0开始的字符串s，请你用故障键盘依次输入每个字符。返回最终笔记本屏幕上输出的字符串。2024......
  • 2024年3月刷题记录
    2024年3月1日【leetcode】2369.检查数组是否存在有效划分题意：给你一个下标从0开始的整数数组nums，你必须将数组划分为一个或多个连续子数组。如果获得的这些子数组中每个都能满足下述条件之一，则可以称其为数组的一种有效划分：子数组恰由2个相等元素组成，例如，子......
  • 2024年2月刷题记录
    2024年2月2日【leetcode】1686.石子游戏VI题意：Alice和Bob轮流玩一个游戏，Alice先手。一堆石子里总共有n个石子，轮到某个玩家时，他可以移出一个石子并得到这个石子的价值。Alice和Bob对石子价值有不一样的的评判标准。双方都知道对方的评判标准。给你两个长度为......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99