8.1 个人赛

比赛链接: https://www.luogu.com.cn/contest/122137#description

A - Barn Echoes G

解题思路

一道字符串匹配的题, 两个字符串中较小的长度就是匹配字符串最大的长度; 然后讲长度从大到小遍历分别找以第一个和第二个为前缀的情况即可找出最大值;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
signed main() {
    string s1, s2;
    cin >> s1 >> s2;
    int maxn = 0;
    int len = min(s1.size(), s2.size());
    for (int i = len; i >= 1; i--) {
        string s3 = s1.substr(0, i);
        string s4 = s2.substr(s2.size() - i, i);
        if (s3 == s4) {
            maxn = max(maxn, i);
            break;
        }
    }
    for (int i = len; i >= 1; i--) {
        string s3 = s2.substr(0, i);
        string s4 = s1.substr(s1.size() - i, i);
        if (s3 == s4) {
            maxn = max(maxn, i);
            break;
        }
    }
    cout << maxn;
    return 0;
}

B - 天际线

解题思路

作为一道普及-的题, 如果想不出来怎么做就直接暴力就好了...不过本题的边界问题需要仔细考虑;
不过正常做法据说是个提高+, 我这就先不做了...理解万岁

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m, idx;
int h[N];
signed main() {
    int a, b, c;
    int l = 1e9, r = 0;
    while (cin >> a >> b >> c) {
        l = min(l, a);
        r = max(r, c);
        for (int i = a; i < c; i++) {
            h[i] = max(h[i], b);
        }
    }
    int d = -1;
    for (int i = l; i <= r; i++) {
        if (h[i]!=d) {
            d = h[i];
            cout << i << ' ' << h[i] << ' ';
        }
    }
    return 0;
}

C - Cow Lineup S

解题思路

一道比较简单的双指针题目; i为区间的右端点, j为左端点; 如果j所指的奶牛品种在区间中的个数大于1, 那么j就可以往右移来缩小区间;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m, idx;
PII f[N];
map<int, int> mp;
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        mp[b]++;
        f[i] = { a,b };
    }
    int num = mp.size();
    mp.clear();
    sort(f + 1, f + 1 + n);
    int res = 1e9, idx = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        int id = f[i].second;
        if (!mp[id])  idx++;
        mp[id]++;
        while (mp[f[j].second] > 1) {
            mp[f[j].second]--;
            j++;
        }
        if (idx == num) {
            res = min(res, f[i].first - f[j].first);
        }
    }
    cout << res;
    return 0;
}

D - 贴海报

解题思路

本题设计线段树的区间修改和标记, 照旧又去恶补了一下, 因为内容有点多所以本篇博客也晚发了一天; 因为n的数据范围高达1e7, 所以用结构体存回爆内存, 因为我们只需要维护左右区间和是否被染色, 所以我们可以把左右区间在函数中用变量表示 ,这样我们只需要开一个数组表示是否被染色即可, 这样也省去了建树的过程; 具体代码如下;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e7+10;
int n, m, f, res;
int A[1010], B[1010];
bool color[4 * N];
void pushup(int u) {
    color[u] = color[u << 1] && color[u << 1 | 1];
}
void modify(int u, int lu, int ru, int l, int r) {
    if (color[u]) return;
    if (lu >= l && ru <= r) {
        color[u] = true;
        f = 1;
        return;
    }
    else {
        int mid = lu + ru >> 1;
        if (l <= mid) modify(u << 1, lu, mid, l, r);
        if (r > mid) modify(u << 1 | 1, mid + 1, ru, l, r);
        pushup(u);
    }
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> A[i] >> B[i];
    for (int i = m; i >= 1; i--) {
        f = 0;
        modify(1, 1, n, A[i], B[i]);
        if (f) res++;
    }
    cout << res;
    return 0;
}

E - Fountain

解题思路

本题需要用到倍增的思想, 说到倍增我们就会想到最近公共祖先的算法, 不过lca是基于树这种数据结构, 于是我们发现本题也可以建树, (后面还会讲不建树的倍增); 根据圆盘的直径我们可以判断水的流向, 而根据流向我们可以建一棵树; 先用单调栈找出当前圆盘a后面第一个大于的它的圆盘b, 对此我们可以把水池设为第n+1个圆盘, 并把直径和容量设为无限大; 然后根据单调栈的关系建树, b就是a的父节点; 然后用bfs处理倍增, 核心思路为: f[j][k] = f[f[j][k - 1]][k - 1] 和 sum[j][k] = sum[j][k - 1] + sum[f[j][k - 1]][k - 1]; 处理完倍增后, 对于每一组询问我们从大到小遍历倍增数组, 如果最后水流还有剩余说明下一个圆盘就可以将其全部装下; 如果最后的圆盘是n+1就输出0即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m, idx;
int d[N], c[N], nx[N];
int h[N], e[N], ne[N], dep[N];
int f[N][21], sum[N][21];
stack<int> st;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void find() {
    for (int i = 1; i <= n+1; i++) {
        while (st.size() && d[i] > d[st.top()]) {
            nx[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
}
void bfs(int u) {
    memset(dep, 0x3f, sizeof dep);
    dep[u] = 1, dep[0] = 0;
    queue<int> q;
    q.push(u);
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dep[j] > dep[t] + 1) {
                dep[j] = dep[t] + 1;
                q.push(j);
                f[j][0] = t;
                sum[j][0] = c[t];
                for (int k = 1; k <= 20; k++) {
                    f[j][k] = f[f[j][k - 1]][k - 1];
                    sum[j][k] = sum[j][k - 1] + sum[f[j][k - 1]][k - 1];
                }
            }
        }
    }
}
signed main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> c[i];
    }
    d[n + 1] = 1e16, c[n + 1] = 1e16;
    find();//单调栈
    for (int i = 1; i <= n; i++)  add(nx[i], i);//建树
    bfs(n + 1);//倍增
    for (int i = 1; i <= m; i++) {
        int r, v;
        cin >> r >> v;
        if (c[r] >= v) {
            cout << r << endl;
            continue;
        }
        v -= c[r];
        for (int j = 20; j >= 0; j--) {
            if (sum[r][j] <= v) {
                v -= sum[r][j];
                r = f[r][j];
            }
        }
        if (v) r = f[r][0];
        if (r == n + 1) r = 0;
        cout << r << endl;
    }
    return 0;
}

如果不建树也是可以做的, 思路大致相同, 但是单调栈的处理方式和倍增数组的处理方式不同, 代码如下;

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m, idx;
int d[N], c[N];
int f[N][21], sum[N][21];
stack<int> st;
void find() {
    for (int i = 1; i <= n; i++) {
        while (st.size() && d[i] > d[st.top()]) {
            f[st.top()][0] = i;
            sum[st.top()][0] = c[i];
            st.pop();
        }
        st.push(i);
    }
}
void check() {
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            sum[i][j] = sum[i][j - 1] + sum[f[i][j - 1]][j - 1];
        }
    }
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> c[i];
    }
    memset(sum, 0x3f, sizeof sum);
    find();//单调栈
    check();//倍增
    for (int i = 1; i <= m; i++) {
        int r, v;
        cin >> r >> v;
        if (c[r] >= v) {
            cout << r << endl;
            continue;
        }
        v -= c[r];
         for (int j = 20; j >= 0; j--) {
            if (f[r][j] != 0&&sum[r][j] <= v) {
                v -= sum[r][j];
                r = f[r][j];
            }
        }
        if (v) r = f[r][0];
        cout << r << endl;
    }
    return 0;
}

F - Music Notes S

解题思路

签到题, 用前缀和找到所有标记点后用二分查找即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
int f[N], s[N];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
        s[i] = s[i - 1] + f[i];
    }
    for (int i = 1; i <= m; i++) {
        int a;
        cin >> a;
        int id = upper_bound(s + 1, s + 1 + n, a) - s;
        cout << id << endl;
    }
    return 0;
}

G - 巧克力

解题思路

一道算是比较明显的贪心, 因为后期块数变多, 切块的成本也会增大, 所以我们必须让成本大的尽早切; 根据这个思路模拟一下就可以了;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
int n, m, idx;
vector<int> v1, v2;
signed main() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int a;
        cin >> a;
        v1.push_back(a);
    }
    for (int i = 1; i < m; i++) {
        int a;
        cin >> a;
        v2.push_back(a);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    int r = 1, c = 1;
    int res = 0;
    while (v1.size() && v2.size()) {
        int a = v1.back(), b = v2.back();
        if (a >= b) {
            res += a * r;
            c++;
            v1.pop_back();
        }
        else{
            res += b * c;
            r++;
            v2.pop_back();
        }
    }
    while (v1.size()) {
        res += v1.back() * r;
        v1.pop_back();
    }
    while (v2.size()) {
        res += v2.back() * c;
        v2.pop_back();
    }
    cout << res;
    return 0;
}

H - 封印

解题思路

一道比较明显的线性dp, 状态表示d[i]表示从开始到破解第i层所需要的最少元气; 状态计算有两种方式, 可以由d[i-1]通过第一种方式得来, 也可以从0~i-1种满足第二种方式要求的用第二种方式得来;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
int n, m, idx;
int f[N], s[N], d[N];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        d[i] = 1e13;
        cin >> f[i];
        s[i] = s[i - 1] + f[i];
    }
    d[0] = 0;
    int k = n * n;
    for (int i = 1; i <= n; i++) {
        d[i] = min(d[i], d[i - 1]+ f[i] * k);
        for (int j = 1; j < i; j++) {
            if (f[i] + f[j] <= m) {
                int a = (f[i] + f[j]) * (s[i] - s[j - 1]);
                d[i] = min(d[i], d[j - 1] + a);
            }
        }
    }
    cout << d[n];
    return 0;
}

本栏目推荐文章
• 个人职业生涯规划
• [Python学习记]个人感受(持续更新）
• 个人博客详细设计说明书
• 个人的vscode配置调优
• PowerDotNet平台化软件架构设计与实现系列（17）：PCRM个人用户管理平台
• 个人是否可以建立自己的网站？
• ubuntu frame 个人开发心得
• 【转】chrome-调试技巧个人总结
• 教育，是点亮一个人，点亮每一个人
• 第一次个人编程作业

个人赛 个人 8.1个人赛 个人8.1 个人 个人赛 typora个人 python个人 flink个人 crypto个人 个人赛 个人 个人主页 faceswap个人