Solution * 2025 - 暑期集训 DAY3

平均难度：7/10

平均AC率：28%

水题×3\times3

数据截止至2025/7/18 11:00

A. 最小贪吃量 24/100 24% 2/10

枚举+模拟。分别用3种方式——按甜度降序、按咸度降序、按甜度咸度之和降序来排序，求解出三个“最”小贪吃量，再在这3个数里选一个最小值即得最小贪吃量。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
#include <initializer_list>      // 用于第68行的{...}
using namespace std;

using ll = long long;

const int N = 2e5 + 10;
struct Dish {
    int a;
    int b;
};

bool compare1(const Dish x, const Dish y) { return x.a > y.a; }
bool compare2(const Dish x, const Dish y) { return x.b > y.b; }
bool compare3(const Dish x, const Dish y) { return (x.a + x.b) > (y.a + y.b); }

int main() {
    freopen("eat.in", "r", stdin);
    freopen("eat.out", "w", stdout);
    int n;
    ll x, y;
    scanf("%d %lld %lld", &n, &x, &y);
    vector<Dish> dishes(n);
    for (int i = 0; i < n; i++) scanf("%d", &dishes[i].a);
    for (int i = 0; i < n; i++) scanf("%d", &dishes[i].b);

    vector<Dish> sorted1 = dishes;
    sort(sorted1.begin(), sorted1.end(), compare1);
    ll SumA1 = 0, SumB1 = 0;
    int total1 = 0;
    for (int i = 0; i < n; i++) {
        SumA1 += sorted1[i].a;
        SumB1 += sorted1[i].b;
        total1++;
        if (SumA1 > x or SumB1 > y) break;
    }

    vector<Dish> sorted2 = dishes;
    sort(sorted2.begin(), sorted2.end(), compare2);
    ll SumA2 = 0, SumB2 = 0;
    int total2 = 0;
    for (int i = 0; i < n; i++) {
        SumA2 += sorted2[i].a;
        SumB2 += sorted2[i].b;
        total2++;
        if (SumA2 > x or SumB2 > y) break;
    }

    vector<Dish> sorted3 = dishes;
    sort(sorted3.begin(), sorted3.end(), compare3);
    ll SumA3 = 0, SumB3 = 0;
    int total3 = 0;
    for (int i = 0; i < n; i++) {
        SumA3 += sorted3[i].a;
        SumB3 += sorted3[i].b;
        total3++;
        if (SumA3 > x or SumB3 > y) break;
    }

    printf("%d", min({total1, total2, total3}));
    return 0;
}

水题+1

B. 三连纯一数 24/70 34% 2/10

三重循环枚举三个纯一数，相加后取出对应的数即可。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

using ll = long long;
ll ones[] = {1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111};
set<ll> nums;

int main() {
    freopen("three.in", "r", stdin);
    freopen("three.out", "w", stdout);
    int n;
    scanf("%d", &n);

    for (int i = 0; i < 13; i++)
        for (int j = 0; j < 13; j++)
            for (int k = 0; k < 13; k++) nums.insert(ones[i] + ones[j] + ones[k]);
    
    vector<ll> _nums(nums.begin(), nums.end());      // 方便取数
    printf("%lld", _nums[n-1]);
    return 0;
}

水题+1

C. 倒立数对 24/83 28% 5/10

我们需要找出所有满足条件的数对 (a,b)(a,b)，其中 aa 和 bb 都在 1∼n1\sim n 的范围内。条件要求 aa 的最后一位等于 bb 的第一位，且 aa 的第一位等于 bb 的最后一位。直接枚举所有可能的 aa 和 bb 会因时间复杂度 O(n2)O(n^2) 而不可行，因此需要优化。

注意到条件只涉及数字的首位和末位数字，因此可以将数字按照其首位和末位数字进行分类。对于每个数字，我们忽略末位为 0 的情况（因为首位不能为 0，无法满足条件）。

  • 使用一个二维数组 count 来记录满足首位为 d 且末位为 e 的数字的数量（d 和 e 均从 1 到 9）。
  • 遍历从 1 到 N 的所有数字，对于每个数字，如果其末位不为 0，则计算其首位和末位，并更新 count 数组。
  • 最后，遍历所有可能的首位和末位组合 (x, y)，将 count[x][y] * count[y][x] 累加到结果中。这是因为对于每个首位为 xx、末位为 yy 的数字 aa，需要匹配首位为 yy、末位为 xx 的数字 bb。

遍历所有数字需要 O(n)O(n) 时间，每个数字的首位计算最多需要 O(1)O(1) 时间（因为数字最大为 2×1052\times10^5，最多 6 位）。总时间复杂度为 O(n)O(n)，空间复杂度为 O(100)O(100)（10×1010\times10 的二维数组）。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

using ll = long long;

const int N = 2e5 + 10;
ll total[20][20];

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    ll n;
    scanf("%lld", &n);
    
    for (int i = 1; i <= n; i++) {
        if (i % 10 == 0) continue;
        int first = i, last = i%10;
        while (first >= 10) first /= 10;
        total[first][last]++;
    }

    ll result = 0;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++) result += total[i][j] * total[j][i];
    printf("%lld", result);
    return 0;
}

D. 池塘 8/24 33% 7/10

要解决这个问题，我们需要在给定的 n×nn\times n 网格中找到所有可能的 k×kk\times k子区域，并确定每个子区域中元素的中位数，最终输出这些中位数中的最小值。由于直接计算每个子区域的中位数会导致较高的时间复杂度，我们需要采用更高效的算法，如二分查找结合二维前缀和来优化。

  1. 二分查找：我们可以在可能的数值范围内进行二分查找，确定是否存在至少一个 k×kk\times k 的子区域，其中至少一半（即中位数位置）的元素不超过某个中间值 mid。

  2. 二维前缀和：对于每个中间值 mid，将原矩阵转换为一个二进制矩阵，其中元素1表示原矩阵中的值 ≤\lemid。然后计算这个二进制矩阵的二维前缀和，这样可以快速查询任意 k×kk\times k 子区域中 1 的个数。如果某个子区域的 1 的个数超过或等于中位数所需的数量（即 k22+1\cfrac{k^2}{2}+1），则说明该子区域的中位数可能 ≤\lemid。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

int n, k;
int a[810][810];
int pf[810][810];

bool check(int mid) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int ignore = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1];
            if (a[i-1][j-1] <= mid) pf[i][j] = ignore + 1;
            else pf[i][j] = ignore;
        }
    int req = (k*k + 1) / 2;
    for (int i = k; i <= n; i++)
        for (int j = k; j <= n; j++) {
            int SumofPf = pf[i][j] - pf[i-k][j] - pf[i][j-k] + pf[i-k][j-k];
            if (SumofPf >= req) return true;
        }
    return false;
}

int binary_search() {
    int l = 0, r = INT_MAX;
    int result = r;

    while (l <= r) {
        int mid = l + (r-l >> 1);
        if (check(mid)) {
            result = mid;
            r = mid-1;
        } else l = mid+1;
    }
    return result;
}

int main() {
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);
    printf("%d", binary_search());
    return 0;
}

E. 区间合并

模板题。区间合并讲义

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

vector<pair<int, int> > segs;

void merge(vector<pair<int, int> > &segs) {
    vector<pair<int, int>> res;
    sort(segs.begin(), segs.end()); 
    int st = -2e9, ed = -2e9;
    for (auto item : segs)
        if (ed < item.first) {
            if (st != -2e9) res.push_back(make_pair(st, ed));
            st = item.first, ed =  item.second;
        }
        else ed = max(ed, item.second);
    if (st != -2e9) res.push_back(make_pair(st, ed));
    segs = res;
}

int main() {
    freopen("merge.in", "r", stdin);
    freopen("merge.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back(make_pair(l, r));
    }
    merge(segs);
    for (auto p : segs) printf("%d %d\n", p.first, p.second);
    return 0;
}

水题+1

F. 恰好一个 8/34 23% 9/10

为了更简单地解决这个问题，我们可以利用每个顶点必须恰好有一条出边的条件。这意味着我们需要为图中的每个顶点选择一条出边，并且这些选择必须满足整个图的约束条件。

每个顶点必须恰好有一条出边。因此，整个图的边数必须至少等于顶点数（m≥nm\ge n），否则无法满足每个顶点都有一条出边。此外，每个连通分量的顶点数必须等于边数（v=ev=e），否则无法满足每个顶点恰好一条出边的条件。

使用并查集（DSU）来统计每个连通分量的顶点数和边数。如果存在任何连通分量的顶点数不等于边数，则整个图的方案数为 0。

对于每个满足 v=ev = e 的连通分量，其定向方案数为 2。因为基环树的环部分有两种定向方向（顺时针或逆时针），而树部分的方向由环的方向唯一确定。因此，整个图的方案数是所有连通分量方案数的乘积。例如，有 kk 个这样的连通分量，总方案数为 2k2^k。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
using namespace std;

const int Mod = 998244353;

struct DSU {
    vector<int> parent;
    vector<int> size_vertex;
    vector<int> size_edge;

    DSU(int n): parent(n), size_vertex(n, 1), size_edge(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) { 
        if (parent[u] != u) parent[u] = find(parent[u]);
        return parent[u];
    }

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            size_edge[u]++;
            return ;
        }
        if (size_vertex[u] < size_vertex[v]) swap(u, v);
        parent[v] = u;
        size_vertex[u] += size_vertex[v];
        size_edge[u] += size_edge[v] + 1;
    }
};

int main() {
    freopen("one.in", "r", stdin);
    freopen("one.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        dsu.unite(u, v);
    }

    vector<bool> proce(n, false);
    long long result = 1;
    for (int i = 0; i < n; i++) {
        int root = dsu.find(i);
        if (proce[root]) continue;
        proce[root] = true;
        if (dsu.size_vertex[root] != dsu.size_edge[root]) {
            result = 0;
            break;
        }
        result = result * 2 % Mod;
    }

    printf("%lld", result);
    return 0;
}

©LY 2025/7/18 *

Edit by Typora(Markdown)

Partial by Deepseek

Thanks xqwl.netlify.app (Authors @gdy @root)

0 条评论

目前还没有评论...
117
已通过
0
题解被赞
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 27ms
  4. Powered by Hydro v5.0.0-beta.13 Community