首页 > 其他分享 >2024百度之星决赛部分题解(难度排序前六题)

2024百度之星决赛部分题解(难度排序前六题)

时间:2024-08-18 23:18:12浏览次数:10  
标签:const int 题解 long 2024 ++ maxn 六题 define

前言

手速6题,可惜第四题磨了几个小时没磨出来,多做一题就金了,还是实力差了点,最后银牌前列。下面的题解是根据代码回忆大概的题意,主要是给出来赛时的参考代码

A.状压

题意:

学校集训队总的有 \(n\) 个人,保证 \(n\) 是3的倍数,每个人有个人实力 \(a_i\), 每两个人之间有配合程度 \(b_{ij}\),每个人可以选择挂机或者不挂机,队伍有不同的总权值(题目中把所有可能的搭配都给出来了), 问合理安排下,最多使得所有队伍的权值和最大是多少。

分析

看到数据范围很显然是考虑状压DP,二进制状态1表示已经安排好队伍,0表示还没,从小到大枚举状态时候,一次性枚举三个是0的位置,考虑这三个人的最大权值,然后更新dp值。
然后可以稍微预处理一下,有效的状态一定是1的数量是3的倍数的,可以把这些数提前存vector里面,可以少枚举一些状态,而且 \(C(n, 3)\)枚举时候可以先把状态里为0的位置存起来,再3个for循环枚举,也能优化一点点。

代码

点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = (1 << 22) + 100;
int a[maxn], b[30][30];
int dp[maxn];
int co[30][30][30];
vector<int> vec;
int cal(int x, int y, int z) {
    int res = max({a[x], a[y], a[z], b[x][y], b[y][z], b[x][z],
                   b[x][y] * b[y][z] * b[x][z]});
    return res;
}
signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < (1 << n); i++)
        if (__builtin_popcount(i) % 3 == 0)
            vec.push_back(i);
    for (int i = 0; i < (1 << n); i++)
        dp[i] = -1e18;
    dp[0] = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> b[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                co[i][j][k] = cal(i, j, k);
    for (auto u : vec) {
        vector<int> tem;
        for (int i = 0; i < n; i++)
            if (!(u >> i & 1))
                tem.push_back(i);
        int sz = tem.size();
        for (int i = 0; i < sz; i++)
            for (int j = i + 1; j < sz; j++)
                for (int k = j + 1; k < sz; k++) {
                    int nxt = u | (1 << tem[i]) | (1 << tem[j]) | (1 << tem[k]);
                    dp[nxt] = max(dp[nxt], dp[u] + co[tem[i]][tem[j]][tem[k]]);
                }
    }
    cout << dp[(1 << n) - 1] << "\n";
    return 0;
}

B.模拟、高精

题意

给定一个n \((n \leq 21)\) 位的二进制数,输出它和十进制数21相乘后的结果的二进制表示

分析

由于乘法不用管进制,所以直接类似高精度乘法一样,对这两个二进制数乘法,并且21比较小已经给定,甚至可以直接取21的二进制为1的那些位,相当于把原来二进制串右移对应位后相加,数据范围比较小,所以随便怎么暴力都可以。

代码

点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn], c[maxn];
signed main() {
    string str;
    cin >> str;
    reverse(all(str));
    for (int i = 0; i < str.length(); i++)
        a[i] = str[i] - '0';
    int tem = 21, cnt = 0;
    while (tem) {
        b[cnt++] = tem % 2;
        tem /= 2;
    }
    for (int i = 0; i < 5; i++) {
        if (b[i]) {
            for (int j = 0; j < str.length(); j++) {
                c[j + i] += a[j];
            }
        }
    }
    int mx = str.length() + 30;
    for (int i = 0; i <= mx; i++) {
        c[i + 1] += c[i] / 2;
        c[i] %= 2;
    }
    string ans;
    for (int i = 0; i <= mx + 31; i++)
        ans.push_back(c[i] + '0');
    while (!ans.empty() && ans.back() == '0')
        ans.pop_back();
    reverse(all(ans));
    cout << ans << "\n";
    return 0;
}

C. 01BFS

题意

有一个二维无限平面,给定起始点 \((x1, y1)\) 和终点 \((x2, y2)\), 平面上有 \(n\) 个障碍物,它们的坐标都是 \(0 \leq x \leq 10^3\), \(0 \leq y \leq 10^3\),问从起点到终点,最少要穿过几个障碍物

分析

这题应该有更简单的方法,但是赛时比较紧张,第一反应是建一个最短路,相邻格点建边,目标有冰块就权值1,否则权值0,然后跑迪杰斯特拉。不过发现评测机跑样例都内存超限了,就被迫考虑优化,发现刚好权值都是0和1,想到01bfs,就不用建边,直接跑最短路,在队列取出来的时候再判断相邻节点有哪些,然后权值是1的放队尾,权值0的放队首。赛后想想,可能普通的最短路也行,只要不显式的建边,可能也不会爆内存。
这题有个坑点,就是建边时候判断边界要是1001,不能只判断到1000,因为虽然那些坐标都在1000以内,但是实际人是可以绕到1000外面再走回去,所以得多往外面判断几格。

点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 1e3 + 10;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int tag[maxn][maxn], dis[maxn * maxn], vis[maxn * maxn];
int trans(int i, int j) {
    return (i - 1) * 1005+ j;
}
signed main() {
    memset(dis, 0x3f, sizeof dis);
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    int m = 1e3 + 5;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        tag[x][y] = 1;
    }
    deque<int> dq;
    dis[trans(x1, y1)] = 0;
    dq.push_back(trans(x1, y1));
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        if (vis[u]) continue;
        vis[u] = 1;
        int x = (u - 1) / m + 1, y = u % m;
        if (x == x2 && y == y2) {
            cout << dis[u] << "\n";
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx < 1 || xx > m || yy < 1 || yy > m) continue;
            int v = trans(xx, yy);
            dis[v] = min(dis[v], dis[u] + tag[xx][yy]);
            if (tag[xx][yy]) dq.push_back(v);
            else dq.push_front(v);
        }
    }
    return 0;
}

5.二分、倍增

这题我感觉是前六题里面最难的,一开始还读错题了

题意

原题意有点绕,我直接给出形式化题意吧。给定一个数组, 将其分成不超过 \(k\) 个连续子数组, 每一段内的极差 (最大值减最小值)不超过 \(d\)。然后问三个问题:
假如只给定 \(k\) 求最小的 \(d\), 假如只给定 \(d\) 求最小的 \(k\), 假如给定了 \(d\) 和 \(k\) ,问最长能从原数组里取多长的子数组。

分析

  • 第一个问题,给定分段数,求最小极差,显然可以二分答案,检验方式也很明显,假设当前二分的答案是mid,从头到尾遍历数组,维护当前分段的最大最小值,如果超了就另起一段。看最后分段的数量有没有超过 \(k\)。
  • 第二个问题,给定极差,求最小分段数。发现这不就是第一个问题里的check函数,所以从头扫一遍数组,维护极差,超了另起一段,最后总的段数就是答案。
  • 第三个问题比较难一点,给定 \(d\) 和 \(k\) ,求最长的连续子数组满足这两个条件的长度。会发现,假如选定了这个子数组的起始位置,然后就是之前的check函数那样的暴力判断,看什么时候不满足这两个条件,复杂度 \(O(n^2)\)。然后想到,每个位置,往后一直到不合法为止,这个长度是固定的,相当于是一段一段的跳。所以可以预处理,从每个位置开始,往后第一个不合法的地方,枚举起点后就可以连着跳 \(k\) 次,看最后到了哪里。然后发现这个过程可以用倍增维护,直接预处理每个位置往后跳 \(2^i\) 个段的位置,就可以枚举起点后 \(logk\)的判断终点。然后怎么判断第一次跳到哪里会超,可以用st表加二分,看第一次最大值和最小值差超过 \(d\) 的位置就是所求的,然后倍增处理查询即可。

代码

点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define ll long long
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 5e5 + 10;
int arr[maxn], lg[maxn];
int mx[maxn][22], mn[maxn][22];
int st[maxn][22];
int n, k, d;
int qmn(int l, int r) {
    int k = lg[r - l + 1];
    return min(mn[l][k], mn[r - (1 << k) + 1][k]);
}
int qmx(int l, int r) {
    int k = lg[r - l + 1];
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
bool ck1(int mid) {
    // 分成 k 段, 求最小 段内极差
    int cnt = 1;
    int mxx = arr[1], mnn = arr[1];
    for (int i = 1; i <= n; i++) {
        mxx = max(mxx, arr[i]);
        mnn = min(mnn, arr[i]);
        if (mxx - mnn > mid) {
            cnt++;
            mxx = arr[i];
            mnn = arr[i];
        }
        if (cnt > k) return 0;
    }
    return cnt <= k;
}
signed main() {
    for (int i = 2; i < maxn; i++)
        lg[i] = lg[i >> 1] + 1;
    cin >> n >> k >> d;
    for (int i = 1; i <= n; i++)
        cin >> arr[i], mn[i][0] = mx[i][0] = arr[i];
    for (int j = 1; j < 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        }
    {
        int l = 0, r = 1e9, ans = 0;
        while (l <= r) {
            int mid = ((ll)l + r) >> 1;
            if (ck1(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans << "\n";
    }
    {
        //给定极差 d 求最小段数
        int mxx = arr[1], mnn = arr[1], ans = 1;
        for (int i = 1; i <= n; i++) {
            mxx = max(mxx, arr[i]);
            mnn = min(mnn, arr[i]);
            if (mxx - mnn > d) {
                mxx = arr[i], mnn = arr[i];
                ans++;
            }
        }
        cout << ans << "\n";
    }
    {
        // 预处理每个位置开始往后跳第一次越界的地方
        for (int i = 1; i <= n; i++) {
            int l = i + 1, r = n, ans = n + 1;
            while (l <= r) {
                int mid = ((ll)l + r) >> 1;
                int mxx = qmx(i, mid), mnn = qmn(i, mid);
                if (mxx - mnn > d) ans = mid, r = mid - 1;
                else l = mid + 1; 
            }
            st[i][0] = ans;
        }
        st[n + 1][0] = n + 1;
        for (int j = 1; j < 21; j++)
            for (int i = 1; i <= n + 1; i++)
                st[i][j] = st[st[i][j - 1]][j - 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) { //枚举起点
            int s = i;
            for (int j = 0; j < 21; j++)
                if (k >> j & 1)
                    s = st[s][j];
            ans = max(ans, s - i);
            if (n - i + 1 <= ans)
                break;
        }
        cout << ans << "\n";
    }
    return 0;
}

6. DP,LIS

题意

给定长度为 \(n\) (\(n\)) 的数组,问有多少个子序列是严格山峰的(有且仅有一个最大值,左边严格递增,右边是严格递减)

分析

考虑去枚举山峰的最大值,以它为最大值的贡献,是左侧的严格上升子序列,并且结尾小于当前最大值。右侧的严格下降子序列,并且开头小于中间这个最大值的总和,二者乘积即为当前的贡献。所以就去处理左右两侧,然后就转化为,对每个 \(i\) 求以它结尾的最长上升子序列个数,用树状数组即可处理,是经典dp。再倒着做一遍,然后前后缀两个树状数组,不断维护一下前后缀的那些子数组数量就好。

代码

点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 3e5 + 10;
struct BIT {
    vector<int> v;
    int len;
    int lowbit(int x) { return x & -x; }
    BIT(int n) {
        len = n + 3;
        v.resize(len);
    }
    void update(int i, int x) {
        i++;
        for (int pos = i; pos <= len; pos += lowbit(pos))
            v[pos] = ((v[pos] + x) % mod + mod) % mod;
    }
    int ask(int i) {
        int res = 0;
        i++;
        for (int pos = i; pos; pos -= lowbit(pos))
            res = ((res + v[pos]) % mod + mod) % mod;
        return res;
    }
    void clear() {
        for (int i = 0; i < len; i++)
            v[i] = 0;
    }
};
int arr[maxn], b[maxn];
int predp[maxn], sufdp[maxn];
signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        b[i] = arr[i];
    }
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++) {
        arr[i] = lower_bound(b + 1, b + 1 + len, arr[i]) - b;
    }
    BIT pre(len), suf(len);
    pre.update(0, 1);
    for (int i = 1; i <= n; i++) {
        predp[i] = pre.ask(arr[i] - 1);
        pre.update(arr[i], predp[i]);
    }
    suf.update(0, 1);
    for (int i = n; i >= 1; i--) {
        sufdp[i] = suf.ask(arr[i] - 1);
        suf.update(arr[i], sufdp[i]);
    }
    pre.clear();
    pre.update(0, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        suf.update(arr[i], -sufdp[i]);
        ans = ((ans + pre.ask(arr[i] - 1) * suf.ask(arr[i] - 1) % mod) % mod + mod) % mod;
        pre.update(arr[i], predp[i]);
    }
    cout << ans << "\n";
    return 0;
}
## 7.LCA、边差分、堆 ### 题意 给一棵树,每条边有边权,然后给一个序列,从1号节点出发按顺序经过这些节点。总权值定义为经过的所有的边权的和。然后至多有 $k$ $(k \leq 10^9)$次操作,每次可以选择一条边权 $w$ 使其变为 $\lfloor \frac{w}{2} \rfloor$, 问最少的总权值和是多少。 ### 分析 首先,很容易想到使用边差分(先把路径的权值跟节点绑定,然后一条路径u->v 对应u的次数++, v的次数++, lca的次数-=2,最后一次dfs累加差分数组还原)来统计出,最终按照这个序列走完后,树上的每条边被经过的次数。然后题意转化为有若干条边,每条边有选择次数 $cnt$ 和权值 $w$, 最多进行 $k$ 次操作,每次让一个边的 $cnt$ 除以2,求 $min (\sum cnt \times w)$ 这个地方,很容易考虑去贪心的用一个堆,每次找 $cnt \times w$ 最大的边,然后除以2,放回去。不过看到数据范围 $k \leq 10^9$ 会以为超时。不过仔细分析一下就发现,由于对于 $cnt$ 最多除以log次就变成0了,而变成0后这条边就肯定不会再用到,直接pop。所以有效的除以2次数也就 $nlogn$ 次,所以直接暴力的这样贪心删就可以 $nlog(n^2)$ 的得到答案。 实现上,由于有除以二向下取整这个操作,所以保险起见可以直接新建一个结构体存 $cnt$ 和 $w$,然后重载运算符,把小于的规则定义为 $w$ 除以二向下取整后,总权值的变化量小于。 ### 代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 6e5 + 10;
vector<pii> G[maxn];
int lg[maxn], fa[maxn][23], dep[maxn];
int xu[maxn], val[maxn], sub[maxn];
struct Node {
    int a, b;
    Node(int a1, int b1) {a = a1, b = b1;}
};
void dfs(int u, int f, int deep) {
    fa[u][0] = f, dep[u] = deep;
    for (int i = 1; i <= lg[dep[u]]; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto [v, w] : G[u]) {
        if (v == f) continue;
        val[v] = w;
        dfs(v, u, deep + 1);
    }
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] > dep[v])
        u = fa[u][lg[dep[u] - dep[v]]];
    if (u == v) return u;
    for (int i = lg[dep[u]]; ~i; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
void dfs1(int u, int f) {
    for (auto[v, w] : G[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sub[u] += sub[v];
    }
}
bool operator < (Node a, Node b) {
    auto [x, y] = a;
    int res1 = x * y - (x / 2) * y;
    auto [c, d] = b;
    int res2 = c * d - (c / 2) * d;
    return res1 < res2;
}
signed main() {
    for (int i = 2; i < maxn; i++)
        lg[i] = lg[i >> 1] + 1;
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    for (int i = 1; i <= m; i++)
        cin >> xu[i];
    xu[0] = 1;
    dfs(1, 0, 0);
    for (int i = 1; i <= m; i++) {
        int u = xu[i - 1], v = xu[i];
        sub[u]++, sub[v]++;
        sub[lca(u, v)] -= 2;
    }
    dfs1(1, 0);
    priority_queue<Node> q;
    for (int i = 2; i <= n; i++) {
        q.push(Node(val[i], sub[i]));
    }
    while (k-- && !q.empty()) {
        auto [w, cnt] = q.top();
        q.pop();
        w /= 2;
        if (cnt)
            q.push(Node(w, cnt));
    }
    int ans = 0;
    while (!q.empty()) {
        auto [w, cnt] = q.top();
        q.pop();
        ans += cnt * w;
    }
    cout << ans << "\n";
    return 0;
}

后记

第四题不会做可惜了,这里放个题意,感兴趣的可以想想。给一个长度为 \(n\) 的环形字符串,每个位置有一个权值。然后多次操作,第一种操作是修改单点权值。第二种操作是选择一个区间,然后从左到右开始,每有两个同样的字符,就删去这两个字符以及中间的字符。求最后剩下的字符的位置上的权值和。
再练一年希望明年拿个金,加训!

标签:const,int,题解,long,2024,++,maxn,六题,define
From: https://www.cnblogs.com/TJUHuangTao/p/18366319

相关文章

  • NOI2024 游记
    Day0报到。这是第一次参加NOI,有点紧张。CQ真的好热啊qaq教练飞机晚点,但是我的学籍证明在教练那。由于害怕教练来得太迟错过报名时间,就先去报到了,但是被告知没有学籍证明不能拿胸牌,没有胸牌不能进宿舍,于是坐在宿舍楼下等了\(\infty\)分钟。期间在宿舍到大门的坡道上来回......
  • 百度之星 2024 打铁记
    前言听说百度之星有铁牌发,我就来了。Day0坐了四小时高铁,又在北京市内坐了两小时地铁加公交车,终于到达九华宾馆。报道领了胸牌,还发了一副牌和一件衣服,还可以领取贴纸,比如“铁牌预定”“群/我=佬”“N^2过百万”。晚上练习赛,找了半天才知道网线怎么接,然后试了半天准考证号才......
  • 2024.8.18
    DATE#:20240818ITEM#:DOCWEEK#:SUNDAYDAIL#:捌月拾伍TAGS <BGM="pureimagination--Rook1e"><theme=oi-contest><[NULL]><[空]><[空]>```前天是小兔子,昨天是小鹿,今天是你。--Clannad```T1玩具时间限制:1s 内存限制:5......
  • 2024年Java面试题最新整理
    一、Java基础部分面试题1.Java面向对象的三个特征封装:对象只需要选择性的对外公开一些属性和行为。继承:子对象可以继承父对象的属性和行为,并且可以在其之上进行修改以适合更特殊的场景需求。多态:允许不同类的对象对同一消息做出响应。篇幅限制下面就只能给大家展示小册部分内容......
  • 第四届能源、动力与电气工程国际学术会议(EPEE 2024) 2024 4th International Conferenc
    文章目录一、会议详情二、重要信息三、大会简介四、嘉宾五、征稿主题六、咨询一、会议详情二、重要信息议官网:https://ais.cn/u/vEbMBz接受/拒稿通知:投稿后5天内会议收录检索:IEEEXplore,EI,Scopus三、大会简介随着前3届的成功举办(EPEE2021由东北电力大学主......
  • ANSYS2024.R2安装教程
    软件介绍ANSYS是一款融结构、流体、电场、磁场、声场分析于一体的大型通用有限元分析(FEA)软件,能与多数计算机辅助设计软件接口,实现数据的共享和交换,如Creo,NASTRAN、Algor、I-DEAS、AutoCAD等。软件下载https://pan.quark.cn/s/7527c0d7199d软件安装1、右键解压文件后进......
  • 洛谷P1983 [NOIP2013 普及组] 车站分级 题解
    思路由题可知,在一趟车次的区间内,停靠的站点的等级恒大于不停靠的站点。因此,对于每一趟车次的区间,给所有停靠的站点向所有不停靠的站点两两连有向边,然后求图中最长的路径长度,就能得到答案。实现因为可能出现重边,而且\(n\le1000\),所以在处理车次连边的时候使用邻接矩阵,再改成邻......
  • 2024.8.18 鲜花
    鱼,好大的鱼,虎纹鲨鱼回リ続ける歯车には成リ下がらない平均演じる诞生から始まった地狱游び半分で神が导いた盤上の世界NONONOGAMENOLIFEぬるい平穏をばっさリ切リ舍てて栄光への阶段に存在刻むんだ目に映るのは完全胜利の运命何もかも计算どおり変えて......
  • 2024.8.18 周总结(上周天到这周六集训,这周天放假)
    感觉这一周上难度了,尤其没听懂的是二分图和博弈论那天上午休息完之后的部分。有复习,有新知识,收获还是比较大的。晚上打游戏打多了。文化课没学多少。中午看番、玩寝室楼下桌上的游戏去了,因为寝室要关灯拉窗帘睡得也更早,一周就只写了一点点字帖,看了一点点《乡土中国》。综......
  • 学习笔记 韩顺平 零基础30天学会Java(2024.8.14)
    P500集合体系图     单列集合是指自己只有一个值,双列集合是像键值对这样的P501Collection方法     对于第三点,像Set这样的,存放进去的和取出来的顺序可能不是一样的,所以就叫无序的P502迭代器遍历在调用iterator.next()方法之前必须要调用iterator.ha......