知乎评价：如何评价第七届广西大学生程序设计大赛?

榜单：CCPC榜单

补题链接：codeforces 、 PTA（签到获得金币，补题时不选择时光机，就不用付费）

难度	签到题	普通题	中等题	难题
题号	B E L	F J	A D H K M	C G I
情况	✔	✔	〇	-

---

题目/官方题解PDF：一至八届 GXCPC广西大学生程序设计竞赛 题目与题解

---

签到题

B. Black Friday

黑色星期五

题目大意：

n 件物品，每件物品有一个原价和促销价。求折扣符合给定要求的物品的促销价之和。
1 ≤ n ≤ 10 ^ 4
给定的折扣计算方法：
$$\frac{pi-qi}{pi}$$

官方解题思路：

个人解题思路：

和官方一致。
满足折扣的条件如下：
$$\frac{a}{b}\le \frac{p_i-q_i}{p_i}$$
两侧同乘分母，或者说，十字交叉相乘（不涉及负数，不用考虑变号的）就是：
$$a\cdot p_i\le (p_i-q_i)\cdot b$$

给定的int数据范围不大，相乘不会超int范围

参考代码c++（官方思路）

#include<iostream>
using namespace std;
int main()
{
    int n, a, b, p, q, sum = 0;
    cin >> n >> a >> b;
    while (n--) {
        cin >> p >> q;
        if (a * p <= (p - q) * b) {
            sum += q;
        }
    }
    cout << sum;
    return 0;
}

---

E. Epsilon Estuary

ε河口

题目大意：

有 n 只史莱姆，第 i 只血量是 xi 。
每次史莱姆受到攻击会裂成两个，受到攻击后的血量是 x 的话，会裂成 ⌊x/2⌋ 和 ⌈x/2⌉。
现在你可以使用法术，每次对全场所有史莱姆造成 y 点攻击。
问清场最少需要使用多少次法术。
1 ≤ n ≤ 10 ^ 5, 1 ≤ xi, y ≤ 10 ^ 18

官方解题思路：

个人解题思路：

官方题解说得对！找出最大值，再进行处理。
数据规模大，注意读写速度。

参考代码c++（官方思路）

#include<iostream>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, y, maxn = 0, cnt = 0;
        scanf("%lld %lld", &n, &y);
        while (n--) {
            long long x;
            scanf("%lld", &x);
            maxn = max(maxn, x);
        }
        while (maxn > 0) {
            maxn = (maxn - y + 1) / 2;
            cnt++;
        }
        printf("%lld\n", cnt);
    }
    return 0;
}

---

L. Loong

龙年

题目大意：

输出第 x 年之后的下一个龙年是哪年。

1 ≤ x ≤ 9999

官方解题思路：

个人解题思路：

众所周知，2024 年是龙年，则 2024 ± 12 * n 年都是龙年。

x 的范围不大（1 ≤ x ≤ 9999），可以这么解：换言之， 8 + 12 * n 年都是龙年。

• x < 8：直接输出 8
• x ≥ 8：输出的数 ≤ x + 12，且满足 8 + 12 * n
  假设 结果为 res ，可设 res = x + i，可知 i ≤ 12
  那么 res = 8 + 12 * n
  也就 x + i = 8 + 12 * n
  移项 i = 8 + 12 * n - x
  等同 i = 12 - (x - 8) % 12
  结果 res = x + 12 - (x - 8) % 12

$$res=\{\begin{array}{ll}8,& 1\le x\le 8\\ x+12-(x-8)\%12,& 8\le x\le 9999\end{array}$$

---

当然也可以不分开讨论，那样就是：
i = 12 + (x + 12 - 8) % 12 ⇨ i = 12 + (x + 4) % 12
res = x + 12 + (x + 4) % 12

$$res=x+12-(x+4)\%12,1\le x\le 9999$$

那自然有很多种写法。

参考代码c++（官方思路）

#include<iostream>
using namespace std;
int main()
{
    int x;
    cin >> x;
    cout << ((x + 4) / 12) * 12 + 8;
    return 0;
}

参考代码c++（个人思路 - 分开讨论）

#include <iostream>
using namespace std;
int main()
{
    int x, res;
    cin >> x;
    
    // if-else 写法
    if (x < 8) {
        res = 8;
    } else {
		res = x + 12 - (x - 8) % 12;
    }
    
    // 三元表达式 写法
    // res = x < 8 ? 8 : x + 12 - (x - 8) % 12;
    
    cout << res;
    return 0;
}

参考代码c++（个人思路 - 不分开讨论）

#include<iostream>
using namespace std;
int main()
{
    int x;
    cin >> x;
    cout << x + 12 - (x + 4) % 12;
    return 0;
}

---

普通题

F. Farewell GXCPC!

再见，GXCPC！

题目大意：

有n 个题，每个题有一个难度di 和一个有趣程度fi 。
Colin 要从中选一些组成一场比赛，满足：

1. 所有选中题目难度之和∈ [L, R]
2. 所有选中题目有趣程度最大。
   现在Colin 会进行q 组询问，每次给出一对L, R ，求此时可能的选中题目有趣程度
   之和的最大值。
   1 ≤ n, di, Li, Ri ≤ 5000, 1 ≤ fi, q ≤ 105

官方解题思路：

GPT-4o解题思路：

官方题解说得对。

以下内容由 GPT-4o 生成，仅供参考

1. 动态规划解决背包问题：

• 我们使用一个动态规划（DP）数组 dp，其中 dp[j] 表示难度和恰好为 j 的最大有趣程度。
• 初始化 dp[0] = 0（因为难度为0时有趣程度为0），其他 dp[j] 初始化为 -1（表示无法达到的状态）。

2. 填充DP表：

• 遍历每个题目，并更新DP表。为了防止覆盖当前迭代的结果，我们从后向前更新DP表。
• 对于每个题目的难度 d 和有趣程度 f，更新 dp[j] 为 max(dp[j], dp[j - d] + f)，其中 j 从 5000 到 d。

3. 区间最大值查询（RMQ）：

• 填充完DP表后，我们需要对其进行预处理，以便能够高效地回答区间最大值查询。我们可以使用稀疏表（Sparse Table）或者线段树。为了简便，我们使用稀疏表。

4. 回答查询：

• 对于每个查询给定的区间 [Li, Ri]，使用预处理好的RMQ结构获取该区间内的最大 dp[j] 值。

参考代码c++（GPT-4o生成）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 5000;
const int INF = 1e9;

int dp[MAXN + 1];
int sparse[MAXN + 1][13];

void preprocessSparseTable(int n) {
    for (int i = 0; i <= n; ++i) {
        sparse[i][0] = dp[i];
    }
    for (int j = 1; (1 << j) <= n + 1; ++j) {
        for (int i = 0; (i + (1 << j) - 1) <= n; ++i) {
            sparse[i][j] = max(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int querySparseTable(int L, int R) {
    int j = 31 - __builtin_clz(R - L + 1);
    return max(sparse[L][j], sparse[R - (1 << j) + 1][j]);
}

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

    int n, q;
    cin >> n >> q;
    
    vector<pair<int, int>> problems(n);
    for (int i = 0; i < n; ++i) {
        cin >> problems[i].first >> problems[i].second;
    }
    
    fill(dp, dp + MAXN + 1, -INF);
    dp[0] = 0;
    
    for (auto [d, f] : problems) {
        for (int j = MAXN; j >= d; --j) {
            if (dp[j - d] != -INF) {
                dp[j] = max(dp[j], dp[j - d] + f);
            }
        }
    }
    
    preprocessSparseTable(MAXN);

    while (q--) {
        int L, R;
        cin >> L >> R;
        int result = querySparseTable(L, R);
        if (result == -INF) {
            cout << -1 << '\n';
        } else {
            cout << result << '\n';
        }
    }

    return 0;
}

---

J. Judge System with Random

系统随机判题

题目大意：

某场比赛一个题，评测系统会随机返回正确/错误。

一个人如果至少有一个提交的返回结果是正确的，罚时计算方式是，第一次正确的提交时间+ （此前提交次数）× 20 。

一个人如果至少有一个提交的返回结果是正确的，并且罚时是所有的这些人里最小的，那么他就是冠军。如果有多个最小的这些人会共享冠军。

Colin 和Eva 分别进行了n 次提交和m 次提交，并给出相应的提交时间。

问所有的2n+m 种可能性中，有多少种Colin 会成为冠军。
1 ≤ n, m ≤ 105

官方解题思路：

群友解题思路：

下面的代码思路源自群友的代码，和官方思路一致。

• 定义了一个用于快速计算大数幂模的函数，采用了二分法（递归乘法）来实现。
• 使用双指针方法遍历 Colin 的提交时间，并计算相应的惩罚时间。
• 对于每一个 Colin 的提交，检查有多少 Eva 的惩罚时间小于当前 Colin 的惩罚时间。
• 累积计算所有可能的组合数，最终计算出符合条件的组合数。

参考代码c++（群友思路）

感谢 南宁训练联盟学生群 的 群友提供的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
int p[N];
int q[N];

// 快速幂函数，用于计算 (a^b) % p
long long kuai(long long a,long long b,long long p){
	long long sum=1;
	while(b){
		if(b&1)sum=sum*a%p;
		b=b>>1;
		a=a*a%p;
	}
	return sum;
}

int main(){
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){
		cin>>p[i];	
	}

	for(int i=1;i<=m;i++){
		cin>>q[i];
	}

	ll sum=0;
	ll en=0;

	q[m+1]=1e17; // 设置一个极大值，作为哨兵
	ll cnt=0;
	ll cnt2=0;

	for(int i=1;i<=n;i++){
		sum=p[i]+20*(i-1); // 计算 Colin 的惩罚时间
		
		// 统计 Eva 的所有惩罚时间小于当前 Colin 惩罚时间的情况数
		while(q[cnt2+1]+20*(cnt2)<sum){
			cnt2++;
            cnt+=kuai(2,(m-cnt2),mod);
            cnt%=mod;
		}
	
		en+=(kuai(2,n-i,mod)*cnt)%mod;
		en%=mod;
	}

	en+=kuai(2,m,mod);
	en%=mod;
    en=((kuai(2,n+m,mod))-en+mod)%mod;
	en%=mod;
	cout<<en;
}

---

中等题

D. Dune

C.Dune

沙丘

题目大意：

解题思路：

参考代码c++：

使用deepseek辅助生成

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

#define ll long long 
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define endl '\n'
#define pb(a) push_back(a)

struct node{
    ll a,b,op,len;
    bool operator < (const node&t)const
    {
        if(a*t.b != t.a*b) return a*t.b < t.a*b; 
        else return op < t.op;
    }
};

void solve() {
    int n, x;
    cin >> n >> x;
    vector<node> e;

    for (int i = 1; i <= n; i++) {
        ll l, r, v;
        cin >> l >> r >> v;
        if (r < x) {
            e.push_back({x - r, v, 0, r - l});
            e.push_back({x - l, v, 1, r - l});
        } else if (l <= x) {
            e.push_back({0, 1, 0, r - l});
            e.push_back({x - l, v, 1, r - l});
        }
    }

    sort(all0(e));
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    unordered_map<ll, int> del_cnt;
    ll ans = 0;

    for (int i = 0; i < (int)e.size(); ++i) {
        auto [a, b, op, len] = e[i];
        if (op == 0) {
            pq.push(len);
        } else {
            del_cnt[len]++;
        }

        if (i < (int)e.size() - 1) {
            auto [a1, b1, op1, len1] = e[i + 1];
            if (a * b1 != a1 * b || op != op1) {
                // Clean up invalid elements
                while (!pq.empty()) {
                    ll t = pq.top();
                    auto it = del_cnt.find(t);
                    if (it != del_cnt.end() && it->second > 0) {
                        if (--it->second == 0) {
                            del_cnt.erase(it);
                        }
                        pq.pop();
                    } else {
                        break;
                    }
                }
                if (!pq.empty()) {
                    ans = max(ans, pq.top());
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

---

H. Hashing Collision

D.Hashing Collision

哈希冲突

题目大意：

解题思路：

参考代码c++：

使用deepseek辅助生成

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

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

    ll n, p, m;
    cin >> n >> p >> m;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<ll> b;
    b.reserve(n * (n + 1) / 2);
    for (int i = 0; i < n; i++) {
        ll h = 0;
        for (int j = i; j >= 0; j--) {
            h = (h * p + a[j]) % m;
            b.push_back(h);
        }
    }
    sort(b.begin(), b.end());
    ll ans = 0;
    ll cnt = 1;
    for (size_t i = 1; i < b.size(); ++i) {
        if (b[i] == b[i-1]) {
            ++cnt;
        } else {
            ans += cnt * (cnt - 1);
            cnt = 1;
        }
    }
    ans += cnt * (cnt - 1);

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

    ll same_pairs = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            same_pairs += lcp[i][j];
        }
    }

    ans -= same_pairs * 2;
    cout << ans << '\n';
    return 0;
}

其他题还没写到，先鸽着🧐

---

难题

超出我所能想象的程度了hhhh，可以参考网上别人的解法😊

ADHJKM题 题解（来自网友）

---

难度	题号	备注
签到题	B E L	✔
普通题	F J	✔
中等题	A D H K M	〇
难题	C G I	-