首页 > 其他分享 >8.1 个人赛

8.1 个人赛

时间：2023-08-03 13:00:19浏览次数：30  
标签：8.1 PII idx int sum long st 个人赛

比赛链接: 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;
}

标签：8.1,PII,idx,int,sum,long,st,个人赛
From： https://www.cnblogs.com/mostimali/p/17599294.html

相关文章

  • 8.1总结
    现在已经23：30了，想起来今天博客还没发，今天真的好忙啊，上午起来做推文，作海报等等就过了一上午，打包了一会pta的报告，后来就做暑期算法协会留的作业，时间复杂度，做了一两个就吃饭了，留着以后做吧，下午接着写文案做推文，找素材，真的很难办。哎，家里地还被冲开一个口子，下午去地里填土了，真的很累，今......
  • 2023.8.1
    8月第一天，约好球友一起玩，早上去广场的一号球场玩了一小会儿，好久没有这么爽过了，运动完出一身汗去吃自助餐，中午十二点吃到下午2点，告别彼此坐车回家，路上买了一批冰激凌，老冰棍啥的，晚上学习了一小时半吧，有些累了，看了个电影就休息了。......
  • 2023.8.1
    今天看SROP的时候，突然想到，既然ctfwiki上讲的不是很详细，搜其他SROP的博客，里面讲的例题又和ctfwiki上的不是很一样，仅有一点参考价值。那我为什么不能直接去搜ctfwiki加上SROP这两个关键词呢？这么一搜，果然找到了符合ctfwiki上内容，又有详细解读的博客，找到的第一篇里还是有点不够详细，找......
  • 8.1打卡
    L1-087机工士姆斯塔迪奥#include<bits/stdc++.h>usingnamespacestd;intmain(){intN,M,Q;cin>>N>>M>>Q;intsum=0;inta[N][M];memset(a,0,sizeof(a));for(intk=1;k<=Q;k++){intT,C;cin>>T>>C......
  • 2023.8.1 英雄的力量
    题目要求返回所有的非空英雄组的力量之和，换言之，只要枚举到的所有组即可，不用管顺序如何。因此我们可以先对序列进行排序，一旦排序完成，那么max和min计算会变得非常简单。前i个数最大的一定是末端那个，最小的一定是起始那个。现在假设a,b,c,d,e五个数（已经排序）。如果现在令d为最大值......
  • 8.1 周二总结
    跟着课程做了一些练习，买飞机票和找质数，开发验证码和数组元素的复制，还有评分。通过今天的学习，更加熟练了eclipse这一软件和Java代码编程的使用。明天准备做一些pta试题，并根据课程继续学习接下来的内容。......
  • 暑假集训D8 2023.8.1 补题
    C.P3029[USACO11NOV]CowLineupS有\(n\)只牛,他们各自有自己的编号(不同牛的编号可能是相同的).这些牛站在不同的位置.现在需要给这些牛拍一张照.有如下要求选定一个范围内的牛拍照,这些牛需要包含所有出现过的编号照片的成本是这个范围,因此范围越小越好已经给定所有......
  • 8.1
    #include<math.h>#include<stdio.h>#include<stdlib.h>#include<string.h>intmain(){inti;//用于循环intk;//表示平局的间隔次数intindex;//标记平局次数charname[20];//输入出招名字scanf("%d&q......
  • 2023.8.1 周二：自定义异常
    1//MyException2//继承Exception的类，即为自定义的异常类3publicclassMyExceptionextendsException{4//传递数字>10，则报异常5privateintdetail;6//Alt+Insert自动添加构造方法7publicMyException(inta){8this.detail=......
  • 8.1日
    一、队友拉了一场数论赛，打了三个小时，组合数，快速幂。二、自己又刷了一道cf1300分的较难的题目。#include<bits/stdc++.h>#defineintlonglong#definexfirst#defineysecond#defineendl'\n'#definepqpriority_queueusingnamespacestd;typedefpair<int,int>pi......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99