洛谷100题计划 (15/100)

P1094 [NOIP2007 普及组] 纪念品分组 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

要使得分组最少,其实就是要让一个大的和一个小的放一起,如果大的和小的一起放超过了\(w\),那大的就应该单独放,所以排完序之后,我们可以用双指针从两边寻找可以放一起的纪念品即可

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

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

    int w, n;
    cin >> w >> n;
    vector<int> a(n);
    int ans = 0;
    for (auto &i : a) cin >> i;

    sort(a.begin(), a.end());

    for (int i = 0, j = n - 1; i <= j;) {
        if (a[j] + a[i] > w) {
            ans ++;
            j--;
        } else {
            ans++;
            j --, i ++;
        }
    }

    cout << ans << '\n';

    return 0;
}

P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

考虑\(A- B=C\),如果直接暴力两重\(for\)循环\(\mathcal{O}(n^2)\)肯定是要超时的,我们稍微转换一下这个式子就可以得到\(A=B+C\),如果我们能知道\(B+C\)的个数(记为\(num_{B+C}\),\(A\)的个数(记为\(num_A\)),那么\(A=B+C\)的数对个数不就等于\(num_{B+C} \times num_A\)了吗,当然你也可以提前用一个数列把\(B+C\)算出来,不过我这里推荐用\(map\),\(map\)内置的\(find\)函数复杂度是\(\mathcal{O}(logn)\)的,且不用担心空间开太大的问题,这样总复杂度就是\(\mathcal{O}(nlogn)\)

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

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

    map<int, i64> mp;
    int c, m, n;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        cin >> m;
        mp[m]++;
    }
    i64 ans = 0;
    for (auto [i, j] : mp) {
        if (mp.find(i + c) != mp.end()) {
            ans += j * mp[i + c];
        }
    }
    cout << ans << endl;

    return 0;
}

P1105 平台 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

惹,实话实说,被这题ex到了感觉是这题的描述不太清楚,看了半天讨论区才改对

首先就是,我是先记录四个信息,该平台序号(\(id\)),高度(\(H\)),左边界(\(L\))和右边界(\(R\)),然后按高度排序,高度相同的情况下一定要把大的排前面,,这样后面第一次往前找到的平台才会是序号较小的平台,剩下就是去找到对应的平台,然后从这个平台往前面找,我们要找的这个平台高度相同的可以直接跳过,找到之后直接退出

代码可能有一点长,但主要是理解那个思维

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

struct Node {
    int id, H, L, R;
    Node(int i, int h, int l, int r): id(i), H(h), L(l), R(r) {};
};

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

    int n;
    cin >> n;
    vector<Node> a;
    for (int i = 1; i <= n; i ++) {
        int h, l, r;
        cin >> h >> l >> r;
        a.emplace_back(i, h, l, r);
    }

    sort(a.begin(), a.end(), [](Node x, Node y) {
        if (x.H == y.H) return x.id > y.id;
        return x.H < y.H;
    });

    for (int  i = 1; i <= n; i ++) {
        int pos = 0;
        for (int j = 0; j < n; j ++) {
            if (a[j].id == i) {
                pos = j;
                break;
            }
        }

        int ansL = 0, ansR = 0;
        for (int j = pos; j >= 0; j --) {
            if(a[j].H == a[pos].H) continue;
            if (a[pos].L > a[j].L && a[pos].L < a[j].R) {
                ansL = a[j].id;
                break;
            }
        }
        for (int j = pos; j >= 0; j --) {
            if(a[j].H == a[pos].H) continue;
            if (a[pos].R > a[j].L && a[pos].R < a[j].R) {
                ansR = a[j].id;
                break;
            }
        }
        cout << ansL << ' ' << ansR << '\n';
    }

    return 0;
}

P1111 修复公路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

以前写过的直接上代码了

采用并查集的思路,先把所有路按照时间的顺序排序,然后每建一条路就把两个村庄连起来,然后\(n-1\),当\(n=1\)时,说明所有的村庄都被一个村庄连起来,此时任意两个村庄都能通车,输出此时的时间即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int id[N];
int n, m, p;
struct Edge {
    int x, y, t;
} edge[N];
int find(int k) {
    if (id[k] == k) return k;
    return id[k] = find(id[k]);
}
bool cmp(struct Edge a, struct Edge b) {
    return a.t < b.t ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m ;
    for (int i = 1; i <= n; i++)
        id[i] = i;
    int z, x, y;
    for (int i = 0; i < m; i++)
        cin >> edge[i].x >> edge[i].y >> edge[i].t ;

    sort(edge, edge + m, cmp);

    for (int i = 0; i < m; i++) {
        if (find(edge[i].x ) != find(edge[i].y )) {
            id[find(edge[i].x)] = find(edge[i].y);
            n--;
        }
        if (n == 1) {
            cout << edge[i].t << endl;
            break;
        }
    }
    if (n != 1) cout << "-1\n" ;
    return 0;
}

P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

考虑\(dp[i]\)表示为过去一个子段当前点的最大值,所以得出转移方程\(dp[i] = max(dp[i -1]+a[i],a[i])\),如果过去的加上现在的还更小了,那我们直接就断掉前面的,又从当前点新开一个段

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

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

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

    a[0] = INT_MIN;
    vector<i64> dp(n + 1,INT_MIN);
    for(int i = 1;i <= n;i ++){
        dp[i] = max(dp[i - 1] + a[i], a[i]);
    }

    i64 ans = *max_element(dp.begin() + 1, dp.end());
    cout << ans << '\n';

    return 0;
}