比赛详情 - 育华学校

已结束乐多开始于: 2025-3-28 18:00 54 小时主持人:

yhxx 20

本期简单

[20250329- 8:20] 更新数据 T4 T6 原来数据有误

T1

#include <bits/stdc++.h>
using namespace std;

int main() 
{
	int x, y;
	cin >> x >> y;
	int ans = (y + x - 1) / x;
	cout << ans;
	return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
int n;
int ans = -1; 
int a[100005];
int main()
{
	cin >> n;

	for(int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	for(int i = 2; i <= n - 1; ++i)
	{
		if(a[i - 1] < a[i] && a[i] > a[i + 1])
		{
			ans = max(ans, a[i] - (a[i - 1] + a[i + 1]) / 2);

		}
	}
	cout << ans;
	return 0;
}

T3

#include <bits/stdc++.h>
using namespace std;
int a[205][205];
int dp[205][205];
int main() {
    int n, m;
    cin >> n >> m;
    if (n < 1 || m < 1 || m % 2 == 0) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    int mid = m / 2 + 1;
    for (int j = 1; j <= m; ++j) {
        if (abs(j - mid) <= 2) {
            dp[n][j] = a[n][j];
        } else {
            dp[n][j] = -1e9;
        }
    }
    for (int i = n - 1; i >= 1; --i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = -1e9;
            for (int d = -2; d <= 2; ++d) {
                int k = j + d;
                if (k >= 1 && k <= m) {
                    dp[i][j] = max(dp[i][j], dp[i + 1][k] + a[i][j]);
                }
            }
        }
    }
    int ans = -10000005;
    for (int j = 1; j <= m; ++j) {
        ans = max(ans, dp[1][j]);
    }
    cout << ans << endl;

    return 0;
}

T4

方法一二分答案+bfs 利用连通性逼近答案

#include<bits/stdc++.h>
using namespace std;
const int N = 2e9;
int n, m;
int a[1010][1010];
bool vis[1010][1010];
int ans = 2e9;

struct Point {
    int x, y;
};

int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

int bfs(int mid) {
    memset(vis, 0, sizeof(vis));
    queue<Point> q;
    q.push({1, 1});
    vis[1][1] = 1;
    while (q.size()) {
        Point b = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = b.x + dir[i][0];
            int y = b.y + dir[i][1];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (vis[x][y]) continue;
            if (abs(a[x][y] - a[b.x][b.y]) <= mid) {
                if (x == n && y == m) return 1;
                vis[x][y] = 1;
                q.push({x, y});
            }
        }
    }
    return vis[n][m];
}

int rf(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (bfs(mid)) {
            r = mid;
            ans = min(ans, mid);
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cout << rf(0, 1e6 + 10);
    return 0;
}

方法二利用贪心每次将连通点的边放入优先队列,每次取最小边值进行遍历,直到目的地,可以证明此为最小值

  #include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int ans[N][N];
bool vis[N][N];
int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct Node {
    int x, y;
    int dis;

    bool operator<(const Node& b) const {
        return dis > b.dis;
    }
};

void bfs() {
    priority_queue<Node> q;
    q.push({1, 1, 0});
    memset(vis, false, sizeof(vis));
    while (!q.empty()) {
        Node qq = q.top();
        q.pop();
        if (vis[qq.x][qq.y])continue;
        vis[qq.x][qq.y] = true;
        if (qq.x == n && qq.y == m) {
            cout << qq.dis;
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = qq.x + dx[i];
            int ny = qq.y + dy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > m)continue;
            int eq = max(qq.dis, abs(ans[nx][ny] - ans[qq.x][qq.y]));
            q.push({nx, ny, eq});
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> ans[i][j];
        }
    }
    bfs();
    return 0;
}

T5

首先，分析问题：每种糖果的发放是独立的，总方法数是每种糖果发放方法数的乘积。对于一种糖果有 $a_i$ 颗，分给 $m$ 个学生。每个学生得到的数量可以是 $0$ 到 $a_i$ ，且总和不超过 $a_i$ 。这相当于求 $x_1 + x_2 + ... + x_m ≤ a_i$ 的非负整数解的个数。转换一下，令 $x_{m+1} = a_i - x_1 - x_2 - ... - x_m$ ，则 $x_1 + x_2 + ... + x_m +x_{m+1}= a_i$ ,于是非负整数解的个数是组合数 C (a_i + m, m)。接下来，预处理阶乘和逆元，因为 n 和 m 到 1e5，需要快速计算组合数。用模 1e9+7。步骤：预处理阶乘和逆元数组。对每个 $a_i$ ，计算 $C (a_i + m, m)$ ，累乘结果。

#include <iostream>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 10;
long long fact[MAXN], inv_fact[MAXN];

// 快速幂计算a^b mod MOD
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和阶乘逆元
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[n] = qpow(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

// 计算组合数C(n, k)
long long C(long long n, long long k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    int n, m;
    cin >> n >> m;
    init(2e5);
    long long ans = 1;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        ans = ans * C(a + m, m) % MOD;
    }
    cout << ans << endl;
    return 0;
}

T6

简单的线段树应用

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree {
	vector<int> mtree;
	int n;
	void init(int size) {
		n = size;
		mtree.resize(4 * n + 1);
	}
	void build(int node, int l, int r, vector<int>& a) {
		if (l == r) {
			mtree[node] = a[l];
			return;
		}
		int mid = (l + r) / 2;
		build(2 * node, l, mid, a);
		build(2 * node + 1, mid + 1, r, a);
		mtree[node] = max(mtree[2 * node], mtree[2 * node + 1]);
	}
	void update(int node, int l, int r, int idx, int val) {
		if (l == r) {
			mtree[node] = val;
			return;
		}
		int mid = (l + r) / 2;
		if (idx <= mid) update(2 * node, l, mid, idx, val);
		else update(2 * node + 1, mid + 1, r, idx, val);
		mtree[node] = max(mtree[2 * node], mtree[2 * node + 1]);
	}
	int query(int node, int l, int r, int p) {
		if (l > r) return -1;
		if (mtree[node] < p) return -1;
		if (l == r) {
			return (mtree[node] >= p) ? l : -1;
		}
		int mid = (l + r) / 2;
		int lres = query(2 * node, l, mid, p);
		if (lres != -1) {
			return lres;
		}
		return query(2 * node + 1, mid + 1, r, p);
	}
};
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	SegmentTree st;
	st.init(n);
	st.build(1, 1, n, a);
	int q;
	cin >> q;
	while (q--) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, y;
			cin >> x >> y;
			st.update(1, 1, n, x, y);
		} else {
			int p;
			cin >> p;
			cout << st.query(1, 1, n, p) << '\n';
		}
	}
	return 0;
}

状态: 已结束
规则: 乐多
题目: 6
开始于: 2025-3-28 18:00
结束于: 2025-3-31 0:00
持续时间: 54 小时
主持人: yhxx
参赛人数: 20

育华周赛第十二期

T1

T2

T3

T4

T5

T6

状态

开发

支持

育华周赛 第十二期

T1

T2

T3

T4

T5

T6

状态

开发

支持

还没有账户？

登录

育华周赛第十二期